Add an LMDB backend

[simonmar]

As an experiment I spent some time yesterday replacing RocksDB with LMDB (https://www.symas.com/mdb) in Glean's backend. The thinking is that LMDB is vastly simpler than RocksDB - just one .c file that we could bundle with Glean. And since it works by mmapping the DB into memory it might be possible to hack the storage scheme to avoid duplicating keys.

Anyway, I got it working as far as passing a bunch of tests and was able to test a large indexing run. The experiment is on my branch here: simonmar@a392ce3

I'm creating this issue to record the findings in case we want to pick it up later.

Findings so far:

• I tried indexing Stackage with the Haskell indexer, and writing seems to be about 3x slower than RocksDB going by the throughput metrics produced by the server during indexing. That's worse than I hoped. I didn't try any tuning but 3x will be hard to overcome, so for now I'll leave the experiment here. (EDIT: disregard this, I was compiling without optimisation)

• Key sizes are limited. Default is 511 bytes, but I managed to bump the max key size to 32KB by forcing a couple of settings in LMDB (which possibly had an effect on performance), but even 32KB wasn't enough to finish the indexing run of Stackage without a key size error. To make this viable we would have to add support for larger keys, probably by using LMDB's duplicate key support: basically move the overflow part of the key into the value, and linear-search entries with identical keys during key lookup. It probably wouldn't be too bad - I bet we almost never have multiple keys where the first 32KB are identical. Even using the LMDB default of 2KB might be enough.

• There's no way to control memory usage, all the DBs are mmaped into the address space and you have to rely on the OS's paging algorithms to do a good job. Not clear at all whether this would work well at scale.

[josefs]

I'd be interested to see how the read performance is affected. B-trees seems to have an edge there, compared to lsm trees. Though in the context of running a whole query, any win might be negligible.

[simonmar]

Aha, it turns out I hadn't compiled with optimisation, now the numbers look more respectable. Experiment continuing, I'll post some numbers when I've done some proper benchmarking.

[simonmar]

Status update:

• It mostly works and performs better than RocksDB on the benchmarks I've tried, up to 2x faster on some things.
• Long keys are a problem. I've hacked it for now but we have to change some assumptions in glean/rts to really fix it, in particular I think we have to drop the assumption that iterators return keys in lexicographic order. One nice consequence of this should be that we can change the RocksDB backend to truncate large keys in the key->Id table, which would save some space at the expense of performance.
• Storage size: LMDB doesn't do compression. My stackage DB was ~3x larger (3GB vs. 1GB with RocksDB). This could perhaps be recovered by using filesystem-level compression (btrfs supports per-file compression) or something like squashfs, or perhaps we just don't care?