Reviewing Lightning Memory-Mapped Database Library: On Page Splits and Other Painful Things

i don’t know if you noticed,  but the lmdb codebase is giving me serious headache issues. the bloody thing is a very dense piece of code, but at the same time, it is also quite interesting. in particular, b-trees are pretty much the answer for a lot of on disk data structures, but they tend to be quite hard to handle properly. so i am looking forward to this piece of code, in which i am going to figure out if i can figure out this code. just to note mdb_page_split is also another 400 lines method with goto sprinkled all over.

in order to do that, i wrote the following code (in a single transaction):

and then i spent another few minutes trying to get it to compile. mostly because i started out with “for (int i=0; …” and c doesn’t allow that (blah!).

anyway, i got the page to split, and now i want to see how it actually behaves. i am currently at the first part where we take the root (currently leaf) page and turn it into a branch. this is an interesting case of a root split.

we start with:

and the first thing we do is to go to this mode:

we add an empty implicit pointer to the previous root. but this is really just the beginning, now we need to divide the entries that used to be in the root between the left & right sides. this is made complex by the fact that you might have it setup so it has a few large & small values, so just cutting them in the middle would produce a result that would be too big. at least, that is what a comment says. i am not sure how that can be. we are going from one page to two pages, so i don’t see how you can get into a situation where that would happen. i guess it is time to slot into more code.

okay, i got it, the issue is that we do a page split because we need to add a new item. so that is the reason we have to jump through those hops. because we add a new item (that is already too big for the original page, since that is why we are actually splitting that).

another complex issue with page splits is that they might be recursive. if we need to split a page, we need to add an entry to the parent page, which might cause that page to split, etc…

an interesting observation on the sizes involved, a lmdb page has 4084 bytes available for storage. the data for the page number is 8 bytes long (it uses pointer size page number) and assuming keys that are 16 bytes keys in size (and including about 8 bytes for node header), we get about 128 keys per branch page. even considering that b-tree are specifically designed to make themselves efficient in the presence of memory hierarchies, it is  quite impressive.

consider, assuming a full tree, if we hold just the root and the first level in memory, we would consume about 512kb. and that would give us just one seek to get any of ~2 million items. as an aside, one reason that i like reading this code is that for once, this is a b-tree implementation that isn’t covered in locking code, which is how this is usually works in rdbms.

another aspect that is quite interesting is that this code really shows important aspects for working with relational databases. it is all about keeping things inside the same page, with spill over to overflow pages slowing things down because you need to do another seek. or a really obvious explanation why page splits are such a bad thing, and a lot of other details that you learn when you go a bit deep into relational databases but (at least for me) have never been real before i started dealing with building databases myself.