Redis RAX radix tree

기본 데이터 구조

rax struct : 24 bytes

raxNode struct : 4+? bytes

API

• raxInsert(): 저장
  int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old)
  • Stream: rax -> key, s -> id, data -> listpack(field,value) pointer
  • ACL: rax -> Users, s -> username, data -> user pointer
    ACL에서 username으로 사용자 정보를 저장/조회할 때 사용한다. 예) acl setuser username
  • Cluster: rax -> slots_to_keys, s -> key, data -> NULL
    클러스터에서 슬롯별로 키를 관리하는데 사용한다. 예) cluster getkeysinslot <slotnum>
  • Client: rax -> clients_index, s -> client id, data -> client pointer
    Client id를 rax에 저장해 놓고 id로 client를 찾을 때 사용한다. 예) client unblock <id>
• raxRemove(): 삭제
  int raxRemove(rax *rax, unsigned char *s, size_t len, void **old)
• raxFind(): 같은 키 찾기
  void *raxFind(rax *rax, unsigned char *s, size_t len)
• raxFree(): Rax 구조체 메모리 해제
  void raxFree(rax *rax): 내부에서 raxRecursiveFree()를 호출해서 모든 node 메모리를 해제한다.
• raxStart(): 찾기 초기 설정
  void raxStart(raxIterator *it, rax *rt)
• raxSeek(): 위치 찾기
  int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len)
  op는 ele를 기준으로 ^(처음 데이터), $(마지막 데이터), >=, <= 등이 사용한다.
• raxNext(): 다음
  int raxNext(raxIterator *it)
• raxPrev(): 이전
  int raxPrev(raxIterator *it)
• raxStop(): 찾기 종료
  void raxStop(raxIterator *it)

Internal API

• raxSetData(): 데이터(value) 저장
  void raxSetData(raxNode *n, void *data)
• raxGetData(): 데이터(value) 조회
  void *raxGetData(raxNode *n)
• raxLowWalk(): 위치(insert, split) 찾기
  static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts)
• raxAddChild()
  raxNode *raxAddChild(raxNode *n, unsigned char c, raxNode **childptr, raxNode ***parentlink)
• raxRemoveChild()
  raxNode *raxRemoveChild(raxNode *parent, raxNode *child)

RAX Data Structure

Insert A, B, C

Insert ABC, A

Insert key1, key2, key3

Insert test, toaster, toasting, slow, slowly

Insert romane ... rubicundus

1. romane
2. romanus
3. romulus
4. rubens
5. ruber
6. rubicon
7. rubicundus

• Memory conscious:
  • Packed nodes representation.
  • Able to avoid storing a NULL pointer inside the node if the key is set to NULL (there is an isnull bit in the node header).
    키가 NULL로 설정된 경우 노드 내에 NULL 포인터를 저장하지 않아도 됩니다 (노드 헤더에 isnull 비트가 있음).
  • Lack of parent node reference. A stack is used instead when needed.
    부모 노드 참조 부족. 필요한 경우 스택이 대신 사용됩니다.
• Fast lookups: 빠른 조회
  • Edges are stored as arrays of bytes directly in the parent node, no need to access non useful children while trying to find a match. This translates into less cache misses compared to other implementations.
    가장자리는 부모 노드에 직접 바이트 배열로 저장되므로 일치하지 않는 하위 항목에 액세스 할 필요가 없습니다. 이것은 다른 구현에 비해 캐시 누락이 적습니다.
  • Cache line friendly scanning of the correct child by storing edges as two separated arrays: an array of edge chars and one of edge pointers.
    가장자리를 두 개의 분리된 배열 (가장자리 문자 배열과 가장자리 포인터 중 하나)로 저장하여 올바른 하위 항목을 캐시에 친숙하게 스캔합니다. ???
• Complete implementation: 완전한 구현
  • Deletion with nodes re-compression as needed.
    필요에 따라 노드를 다시 압축하여 삭제하십시오.
  • Iterators (including a way to use iterators while the tree is modified).
    반복자(트리가 수정되는 동안 반복자를 사용하는 방법 포함).
  • Random walk iteration. 랜덤 워크 반복.
  • Ability to report and resist out of memory: if malloc() returns NULL the API can report an out of memory error and always leave the tree in a consistent state.
    메모리 부족 저항과 보고 기능 : malloc()이 NULL을 반환하면 API는 메모리 부족 오류를 보고 하고 항상 트리를 일관된 상태로 유지할 수 있습니다.
• Readable and fixable implementation: 가독성있고 유연한 구현
  • All complex parts are commented with algorithms details.
    모든 복잡한 부분은 소스 코드에 자세한 알고리즘을 설명(주석)합니다.
  • Debugging messages can be enabled to understand what the implementation is doing when calling a given function.
    지정된 함수를 호출할 때 구현이 수행하는 작업을 이해하기 위해 디버깅 메시지를 사용할 수 있습니다.
  • Ability to print the radix tree nodes representation as ASCII art.
    기수 트리 노드 표현을 ASCII 아트로 인쇄하는 기능.
• Portable implementation: 이식성있는 구현
  • Never does unaligned accesses to memory.
    메모리에 조정되지 않은 액세스를하지 않습니다.
  • Written in ANSI C99, no extensions used.
    ANSI C99로 작성되었으며 실행파일은 확장자을 사용하지 않았습니다.
• Extensive code and possible states test coverage using fuzz testing.
  광범위한 코드 및 가능한 상태는 퍼지 테스트를 사용하여 적용 범위를 테스트합니다.
  • Testing relies a lot on fuzzing in order to explore non trivial states.
    테스트는 사소하지 않은 상태를 탐색하기 위해 퍼지에 많이 의존합니다.
  • Implementation of the dictionary and iterator compared with behavior-equivalent implementations of simple hash tables and sorted arrays, generating random data and checking if the two implementations results match.
    사전 및 반복자의 구현은 간단한 해시 테이블 및 정렬된 배열의 동작과 동등한 구현과 비교하여 임의의 데이터를 생성하고 두 구현 결과가 일치하는지 확인합니다.
  • Out of memory condition tests. The implementation is fuzzed with a special allocator returning NULL at random. The resulting radix tree is tested for consistency. Redis, the primary target of this implementation, does not use this feature, but the ability to handle OOM may make this implementation useful where the ability to survive OOMs is needed.
    메모리 부족 상태 테스트 구현은 NULL 무작위로 돌아오는 특별한 할당자로 퍼지됩니다. 결과 기수 트리의 일관성을 테스트합니다. 이 구현의 주요 대상인 Redis는 이 기능을 사용하지 않지만 OOM을 처리하는 기능은 OOM을 생존할 수 있는 기능이 필요한 경우 이 구현을 유용하게 만들 수 있습니다.
  • Part of Redis: the implementation is stressed significantly in the real world.
    Redis의 일부: 구현은 실제 세계에서 크게 강조됩니다.

+----+---+--------+--------+--------+--------+
|HDR |xyz| x-ptr  | y-ptr  | z-ptr  |dataptr |
+----+---+--------+--------+--------+--------+

+----+---+--------+
|HDR |ABC|chld-ptr|
+----+---+--------+

Creating a radix tree and adding a key

Key lookup

Deleting keys

Basic iterator usage

while(raxNext(&iter)) {
    printf("Key: %.*s\n", (int)iter.key_len, (char*)iter.key);
}

Seek operators

•   ==     seek the element exactly equal to the given one.
•   >     seek the element immediately greater than the given one.
•   >=     seek the element equal, or immediately greater than the given one.
•   <     seek the element immediately smaller than the given one.
•   <=     seek the element equal, or immediately smaller than the given one.
•   ^     seek the smallest element of the radix tree.
•   $     seek the greatest element of the radix tree.

Iterator stop condition

raxIterator iter;
raxStart(&iter);
raxSeek(&iter,">=",(unsigned char*)"AAA",3); // Seek the first element
while(raxNext(&iter)) {
    if (raxCompare(&iter,">",(unsigned char*)"BBB",3)) break;
    printf("Current key: %.*s\n", (int)iter.key_len,(char*)iter.key);
}
raxStop(&iter);

Checking for iterator EOF condition

Modifying the radix tree while iterating

while(raxNext(&iter,...)) {
    if (raxRemove(rax,...)) {
        raxSeek(&iter,">",iter.key,iter.key_size);
    }
}

• Iterators need to be sought again with raxSeek every time keys are added or removed while iterating.
• The current iterator key is always valid to access via iter.key_size and iter.key, even after it was deleted from the radix tree.

Re-seeking iterators after EOF

raxSeek(&iter,"^",NULL,0);
while(raxNext(&iter,NULL,0,NULL))
    printf("%.*s\n", (int)iter.key_len, (char*)iter.key);

raxSeek(&iter,"==",iter.key,iter.key_len);
while(raxPrev(&iter,NULL,0,NULL))
    printf("%.*s\n", (int)iter.key_len, (char*)iter.key);

Random element selection

Printing trees

• alligator = (nil)
• alien = 0x1
• baloon = 0x2
• chromodynamic = 0x3
• romane = 0x4
• romanus = 0x5
• romulus = 0x6
• rubens = 0x7
• ruber = 0x8
• rubicon = 0x9
• rubicundus = 0xa
• all = 0xb
• rub = 0xc
• ba = 0xd

[abcr]
 `-(a) [l] -> [il]
               `-(i) "en" -> []=0x1
               `-(l) "igator"=0xb -> []=(nil)
 `-(b) [a] -> "loon"=0xd -> []=0x2
 `-(c) "hromodynamic" -> []=0x3
 `-(r) [ou]
        `-(o) [m] -> [au]
                      `-(a) [n] -> [eu]
                                    `-(e) []=0x4
                                    `-(u) [s] -> []=0x5
                      `-(u) "lus" -> []=0x6
        `-(u) [b] -> [ei]=0xc
                      `-(e) [nr]
                             `-(n) [s] -> []=0x7
                             `-(r) []=0x8
                      `-(i) [c] -> [ou]
                                    `-(o) [n] -> []=0x9
                                    `-(u) "ndus" -> []=0xa

do_units: --units

• randomWalkTest:
• iteratorUnitTests: raxSeek() 테스트
• tryInsertUnitTests: raxInsert(), raxTryInsert() 테스트

do_regression: --regression

• regtest1:
• regtest2:
• regtest3:
• regtest4:
• regtest5:
• regtest6:

do_hugekey: --hugekey

• testHugeKey:

do_fuzz_cluster: --fuzz-cluster

• fuzzTestCluster:

do_fuzz: --fuzz

• uzzTest(KEY_INT):
• uzzTest(KEY_UNIQUE_ALPHA):
• uzzTest(KEY_RANDOM):
• uzzTest(KEY_RANDOM_ALPHA):
• uzzTest(KEY_RANDOM_SMALL_CSET):
• uzzTest(KEY_CHAIN):
• iteratorFuzzTest(KEY_CHAIN):
• iteratorFuzzTest(KEY_UNIQUE_ALPHA):
• iteratorFuzzTest(KEY_RANDOM_ALPHA):
• iteratorFuzzTest(KEY_RANDOM):

do_benchmark: --bench

• benchmark():

1. The rax-test is executed using Valgrind, adding a printf() so that for the fuzz tester we see what iteration in the loop we are in.
2. After every modification of the radix tree made by the fuzz tester in rax-test.c, we add a call to raxTouch().
3. Now as soon as an operation will corrupt the tree, raxTouch() will detect it (via Valgrind) immediately. We can add more calls to narrow the state.
4. At this point a good idea is to enable Rax debugging messages immediately before the moment the tree is corrupted, to see what happens. This can be achieved by adding a few "if" statements inside the code, since we know the iteration that causes the corruption (because of step 1).