rmind/masstree

Masstree -- lockless cache-aware trie of B+ trees [experimental]

Masstree: lockless cache-aware tree [experimental]

Masstree is a lockless cache-aware trie of B+ trees. This project provides an implementation written in C11, distributed under the 2-clause BSD license. Based on the design by Y. Mao, E. Kohler and R. Morris. Reference:

    http://pdos.csail.mit.edu/papers/masstree:eurosys12.pdf

WARNING:

• This code is experimental and is known to be unstable. Use it at your own risk. Support is not provided at this stage.
• The concurrent delete operation is known to have bugs.
• Certain optimisations and features from the original paper are not implemented.

NOTE: For a stable alternative, please see the concurrent trie-hash map project.

masstree's Issues

A question about unstable state?

I see in your implementation, that unstable state is not a problem, because you put each key as deeper as possible, so each time there is key conflict you can inserting a new layer instead of replacing one.(Am i right?)
This is really clever! In this case key suffix is not needed and we don't have to retry when masstree_get, but at the cost of a bit more memory.

How do you come up with that?

I implement this algorithm lately, and I also did some modification, that new layer is created lazily, eg. a key with length 100 is store in layer 0 if there is no prefix conflict.

A question about keysuffixes

Hi:
Thanks for your masstree, it's cool.
I have a question about keysuffixes, my code is as follows:

tree = masstree_create(NULL);
char* key = "01234567AB";
char* key2 = "01234567XY";
masstree_put(tree, key, sizeof(key), (void *)1);
masstree_put(tree, key2, sizeof(key2), (void *)2);

I debug this and find key suffixes stored in layer 1, just like :

Layer 0              keyslice[0]: 01234567
                                 |
                               /  
Layer 1             keyslice[0]:AB         
                    keyslice[1]:XY

Layer 1 is leaf nodes in B+ tree, so, I think keyslice should store a complete key for range, and in paper, it has keysuffix_t keysuffixes, but I did not find in your code.

So, why store keysuffixes in keys-lice?