MemTable with array based Threaded Red-Black Tree

[rockeet]

This memory pool is aimed to showing advantages of our MemTable refactory:

1. Memory dumpable
2. Without RocksDB key value prefix len encoding
3. Dynamic Plugable MemTable(MemTable Abstract Factory: #18)

Using array based Threaded Red-Black Tree:

struct Node {
    uint32_t  left;
    uint32_t  right;
    uint64_t  offset : 39; // offset to key value data in mempool
    uint64_t  color  :  1; // red or black
    uint64_t  keylen : 24; // valuelen = offset[idx+1] - offset.nodes[idx] - keylen;
};

1. node and KeyValue data share single mempool
2. nodes start at begin of mempool, growing upward
3. offsets start at end of mempool, growing downward (KeyValue data)
4. max node num is 232 - 2
5. max KeyValue mempool capacity is 512G
6. max KeyLen is 224-1

[rockeet]

Value in RocksDB MemTable must be prefix len encoded, so keylen field is not needed! Tree Node should be:

#pragma pack(push,1)
struct Node {
    uint32_t  left   : 31;
    uint32_t  color  :  1; // red or black
    uint64_t  right  : 31;
    uint64_t  offset : 33; // offset to KeyValue data in mempool
};
#pragma pack(pop)

1. node and KeyValue data use two different mem blocks, both growing upward, reasons:
   • RocksDB does not allow insert to MemTable fail
   • using multiple trees requires a heap for iterator
   • Threaded Red-Black Tree does not support concurrent, so mem blocks can be realloc'ed
2. In a KeyValue pair, Value is stored before Key, keylen = offset[i+1] - offset[i] - valuelen
3. max node num is 231 - 2
4. max KeyValue mempool capacity is 8G

[rockeet]

done