I was working peacefully through some stuff with Voron, when I ran into some really bad performance in a pretty important scenario. I decided that this is probably something that I was doing wrong, and set out to reproduce the same scenario in LMDB, to figure out what I was doing wrong.

Here is the code:

int main(int argc,char * argv[])
{
    int i = 0, j = 0, rc;
    UUID id;
    MDB_env *env;

    MDB_val key, data;

    MDB_stat mst;
    MDB_cursor *cursor;
    char sval[32];
    clock_t start = clock(), end;

    srandom(time(NULL));

    rc = mdb_env_create(&env);
    rc = mdb_env_set_mapsize(env, 1024*1024*768);
    rc = mdb_env_set_flags(env, MDB_WRITEMAP, 1); 
    rc = mdb_env_open(env, "E:\\data\\lmdb2", 0, 0664);

    key.mv_size = sizeof(UUID);
    data.mv_size = sizeof(sval);
    data.mv_data = sval;
    
    for (i=0;i<100;i++) {    
        MDB_txn *txn;
        MDB_dbi dbi;

        rc = mdb_txn_begin(env, NULL, 0, &txn);
        rc = mdb_open(txn, NULL, 0, &dbi);

        for (j= 0; j < 100; j++)
        {
            UuidCreate(&id);
            
            key.mv_data = &id;
            rc = mdb_put(txn, dbi, &key, &data, 0);
        }

        rc = mdb_txn_commit(txn);
        mdb_close(env, dbi);
    }

    end = clock();

    printf("%i", (end - start));
    fgetc(stdin);
    mdb_env_close(env);

    return 0;
}

As you can see, we are inserting 10,000 items (100 transactions of 100 items each). Each item has key of 16 bytes and a value of 100 bytes. Now, you might note that this is probably the worst case scenario for a B+Tree, UUIDs are unordered, and this generates a lot of fragmentation in the tree. Bad scenario, yes, but also a relatively common one, and one that needs to be handled properly for our needs. It took me a long time to narrow down what is actually going on. At first I was convinced that the problem was with Windows’ implementation of memory mapped files, but eventually I realized that select ain’t broken.

Here is the Process Monitor’s trace of the first few transactions. The highlighted calls are to FlushBuffersFile, which is how FlushFileBuffers look, which indicates a commit.

As I said, those are the first few transactions. You can see that the OS is doing a pretty good job in merging writes and avoiding seeks. However, as times goes by …

And as more times goes by, we get to (there are more rows at the top that I had to remove so I could take the snapshot) …

In fact, I put the data in Excel and got:

And those are some really bad numbers, I think you’ll agree. After the very short period of time, the cost of committing a transaction goes to over 50 seeks and writing of 350 KB.

Let us compare that to what happens when we are actually writing sequential data (using UuidCreateSequential instead of UuidCreate). The test complete in half the time, and the actual statistics are also very interesting.

We are writing a lot less, but much more importantly, we are doing a lot less seeks. For reference, here is the final transaction that we have with the sequential write scenario:

I ran those tests on a HDD drive, so seek times matter a lot, but I have gotten similar results when running on an SSD.

Now, the interesting question here is what exactly is going on? And I think that a large part of this is the way LMDB allocates pages. It uses a copy-on-write method, which means that after the transaction is done, the previously used pages are free. That means that they can be reclaimed, and the next transaction will do just that. The problem with this approach is that it tends to spread writes all over the file. This saves disk space, but requires a lot more seeks when you need to commit a transaction.

That means that, in order to optimize this particular scenario, I probably need to do some thinking about the free page allocation behavior. We want to be a lot more conservative about when and how we give out those pages, to make sure that we aren’t generating a really bad situation for the database when commit time comes.