LSM tree vs B-tree: amplification simulator

Set the number of writes and how many different keys they may hit; fewer keys means more updates of the same keys. Both engines receive exactly the same writes. The LSM tree flushes its memtable to sorted files and compacts them, leveled or size-tiered; the B+ tree inserts into fixed-size leaf pages, splitting full ones, and writes a dirty page to disk only when the buffer pool evicts it. Sizes are counted in entries, so an amplification of 10× means ten entries written to disk for every entry written by the application.

A B-tree keeps every key in one place, a page of a balanced tree, and changes that page when the key changes. Reads follow one path from the root. A log-structured merge tree never updates in place: writes collect in an in-memory table, which is written out as a sorted, immutable file when it fills, and a background process merges files into larger ones, discarding overwritten versions. The LSM design was published by Patrick O’Neil and colleagues in 1996 and underlies RocksDB, LevelDB, Cassandra and many other stores; B-trees remain the default in most relational databases.

An LSM tree writes each entry to the log, once when its memtable is flushed, and again every time compaction merges it into a lower level. With leveled compaction each level is about T times bigger than the one above, and pushing a file down rewrites the overlapping part of the next level, so each level costs several rewrites; the RocksDB documentation notes leveled write amplification is often larger than 10. Size-tiered compaction merges runs of similar size together, so an entry is rewritten about once per tier. On 200,000 random writes over a million possible keys, with a 1,000-entry memtable:

A point lookup in a B-tree reads one page per level, and the upper levels are almost always cached, so in practice one or two disk reads. An LSM tree has to check the memtable, every level-0 file and then one file per level, newest first, and a key that doesn’t exist has to be looked for everywhere. LSM engines keep a Bloom filter for each file, which rules out most files without reading them, and cache the index blocks; range scans still have to merge every level. Size-tiered compaction leaves more runs to search than leveled.

B-tree pages are rarely full: after random inserts, leaves split in half and average about 69% full (the simulation measured 69%), so the tree uses about 1.45 times the space of its data. An LSM tree keeps dead versions of updated keys until compaction removes them. With mostly new keys that costs little, but when the same 20,000 keys are updated over and over, leveled compaction held 1.61 times the live data and size-tiered 4.85 times, since tiers hold several copies of the same keys until they merge.

Athanassoulis and colleagues’ RUM conjecture (EDBT 2016) states that an access method can bound at most two of its read overhead, update overhead and memory or space overhead. The table above shows it: leveled compaction spends writes to keep reads and space low, tiered compaction saves writes at the cost of reads and space, and a B-tree reads cheaply but pays for random updates unless it has memory to spare. Choosing a storage engine, or tuning one, is choosing where on that triangle to sit.