Optimizing Voron and the Cost of Multi Trees

One of the nice features that Voron got from LMDB is the notion of multi trees. If I recall correctly, LMDB calls them duplicate items, or something like that. Basically, it is the ability to store multiple values for a single key.

Update: The behavior described in this post has been in LMDB for the over 3 years. It is just something that Voron didn't have. Please note that this post discuss the Voron's limitation and its solution, not LMDB, which has had the solution for a long time.

Those items are actually stored as a nested tree, which effectively gives us a great way to handle duplicates. From an API standpoint, this looks like this:

    // store
    tree.MultiAdd(tx, "Eini", "users/1");
    tree.MultiAdd(tx, "Eini", "users/3");
    tree.MultiAdd(tx, "Eini", "users/5");


    //read 
    using(var it = tree.MultiRead(tx, "Eini"))
    {
        if(it.Seek(Slice.BeforeAllKeys) == false)
            yield break;
        do
        {
            yield return it.CurrentKey; // "users/1", "users/3", "users/5"
        }while(it.MoveNext());
    }

Internally, we handle this in the following fashion:

• If a multi add operation is the very first such operation, we’ll add it as a simple key/value pair in the tree.
• If a multi add operation is the 2nd such operation, we’ll create a new tree, and add both operations to the new tree. The original tree will have the key/nested tree reference stored.

That lead to a very easy to use API, which is quite useful in many cases. However, it also have space usage implication. In particular, a tree means that we have to allocate at least one page to it. And that means that we have to allocate 4KB to hold any multi tree with more than a single value. Since there are actually a lot of scenarios where we would want to store a small number of small values, that can often lead to a lot of waste on our part. We use 4KB to store data that we could have stored in just 64 bytes, for example. That means that when we want to actually store things that might be duplicated, we actually need to consider the taken space consideration as well.

I think that this is a pretty bad idea, because it leads us to do things with composite keys under some scenarios. That is something that Voron should be able to just handle for me.  So we changed that, in fact, what we did was changed the way we approach multi trees in general. Now, for every multi value, we can store up to 1KB of items in the same page as the key, before we devolve into a full blown multi tree.

The idea is that we can use the same Page mechanism we use elsewhere, and just have a nested page inside the parent page. As long as the nested page is small enough, we can just store it embedded. That result in some nice space saving. Since usually we have items in the following counts: zero, one, few, lots.

We need this to help with Corax, and in general, that would reduce the amount of space we need to use in many cases.