LSM tree

This site has 1184 commits. In them the contents of some file changed 11,762 times: routes/web.php was rewritten 101 times, the interface dictionaries 82 times each, and 131 times a file was deleted. Imagine that the site keeps its files not on disk but in a key-value database: the path is the key, the contents the value. Then the history is a stream of writes, half a billion bytes. A B-tree would fix a page on disk in place for each write. An LSM tree acts differently: it never fixes what has been written. Press “Play”, and the whole history goes through the tree in half a minute.

The blue bar is memory: writes gather in it until it holds 4 MB. Then the memory goes onto disk whole as one sorted run in L0. When L0 has four runs, they are merged with the next level, and an overflowing level is merged with a deeper one still. By the end of the history the program has written 477 MB, and the tree 1697 MB, 3.56 times as much: each byte was rewritten another two and a half times during merges. But not one write needed a read from disk or touched old data.

The idea

New writes go into a sorted structure in memory. When it fills up, it is written to disk whole in one sequential piece, an immutable sorted run. A read looks into memory, then into the runs from newest to oldest, and takes the first version it finds. To keep the runs from multiplying, a background process merges them, as in merge sort, leaving each key only its newest version. A deletion is a write too: a “tombstone” that covers the key’s older versions.

The names come from the 2006 paper on Bigtable: the structure in memory is the memtable, a run on disk is an SSTable, a sorted string table. The memory is usually a skip list or a balanced tree: the keys in it must be in order so that a flush is a simple write-out. So that writes are not lost if the process crashes before the flush, each is first appended to a log on disk, sequentially, at the end of the file. Inside an SSTable the keys are split into blocks of a few kilobytes, and at the end of the file lies an index: the first key of each block. Finding a key in a run is a binary search over the index and one read of a block.

Why not a B-tree

A B-tree keeps each key in its place. To write a new version of routes/web.php, you have to find its leaf, read the page, change it and write the page back: a read and a write at a random place on disk for every update. An LSM tree first gathers writes in memory and writes them in a batch. Sequential writing on any medium is tens of times faster than random writing, and on an SSD it also wears the cells less: the difference between “in a row” and “scattered” is one of the largest in computing. That is why databases that are written to in a continuous stream, events, metrics, messages, almost always stand on an LSM tree.

This is paid for three times over. Rewriting: the same byte is rewritten in every merge it goes through. Space: until a merge gets there, the disk holds both old versions of a key and tombstones. Reading: a key may be in any of the runs, and you have to look until you find it. The whole design of an LSM tree is a choice of how much to pay in each of these three coins.

Versions and tombstones

Every write has a sequence number. When runs are merged, a key keeps the version with the largest number, and the others disappear. In the site’s history this works at full strength: of the 477 MB written, 231 MB are live data at the end of the history. The rest is old versions of rewritten files, and only merges clean them out.

Deletion cannot work like that: if the key is simply not written, a read will find its old version in a deep run. So a deletion writes a tombstone, a record saying “the key is gone”. A tombstone covers all older versions, and during a merge it cannot be thrown out while an old version may lie somewhere below: otherwise the deleted file would “come back to life”. A tombstone can be thrown out when the merge has reached the very bottom level, or when no older run has this key. Look up planetshader.js in the scene: it was deleted at the end of the history, and its tombstone still lies in the top run. And GameController.php was deleted long ago: the tombstone reached the bottom and vanished along with all the versions, and a read honestly goes through all the runs and finds nothing. The first problem is about this.

Levels and tiers

When to merge is the main question. There are two main answers.

Levels (leveled). Each level holds one sorted run, and each level is T times larger than the previous one. New data is merged with the level’s run at once, and an overflowing level goes down. There are few runs, one per level, and reads are fast. But a level’s data is rewritten every time a new portion arrives from above, on average about T/2 times until the level fills up, and so on every level. This is how RocksDB and LevelDB work by default.

Tiers (tiered). Runs on a level accumulate without merging until there are T of them; then all T merge into one and go down. Each byte is rewritten about once per level, but a level holds up to T runs, and a read that does not find the key has to check them all. This is how Cassandra works by default.

Below is the same history of the site through both kinds of tree, with levels growing by factors from 2 to 10.

The tiered scheme with a growth of 10 rewrites each byte only 1.64 times, but keeps 6.2 runs on disk on average, 11 by the end of the history, and takes 25% extra space. The leveled one rewrites 3.6–3.9 times at any growth, but has three runs on average and 4–6% extra space. In such a short history there are only three or four levels, and the bottom one has no time to fill, so the difference is not as great as in large databases. But the direction is the same: you cannot write little, store little and read little at the same time. Manos Athanassoulis and co-authors in 2016 called this the RUM conjecture, read, update, memory: any two costs can be improved, but the third will grow.

Reads: Bloom filters

The most expensive read is of a key that does not exist. It goes through all the runs: in the scene a request for a non-existent file reads them all. A Bloom filter on each run helps: a small bit array in memory that answers the question “is the key in the run” with “definitely not” or “possibly”. With 10 bits per key it is wrong in about 1% of cases, and almost all the extra reads vanish: a run is opened only when the filter said “possibly”. For 5790 keys that is 7 KB of memory for the filters.

But the bits need not be shared equally. A false positive of the filter of a small top run costs one extra read, exactly as much as that of a huge bottom one, while the small one needs hundreds of times fewer bits. In 2017 Niv Dayan, Manos Athanassoulis and Stratos Idreos showed that it pays to give the top runs more bits per key and the bottom ones fewer: with the same memory the expected number of extra reads falls, and the more so the more levels there are. Computing this allocation is the second problem.

Filters do not help with ranges: a query for “all files in the directory resources/js/” has to open every run, find the start of the range in it by binary search and merge all the runs on the fly, with a heap by key, skipping stale versions and tombstones. So long scans in an LSM tree cost more than in a B-tree, where a range lies in a row in the leaves.

Code

The listing runs the site’s history through both kinds of tree with the same parameters as the scene: 4 MB of memory, four runs in L0, a first level of 16 MB, growth by a factor of 4. At the end come five reads: a hot file, a fresh one, one just deleted, one deleted long ago and one that does not exist.

The fresh solver.js is still in memory, and the disk is not needed at all. routes/web.php was rewritten until the last commits, and it is in the top run. The recently deleted planetshader.js is found at once, as a tombstone. And the long-deleted file and the non-existent one go through all the runs: four in the leveled tree and five in the tiered one. The model is simplified: an overflowing level here merges down whole, while RocksDB cuts a level into files of tens of megabytes and merges them down one file at a time; the amount of rewriting is the same, but more even, without bursts.

What it costs

A write is an insertion into the structure in memory, O(log m) for m records in it, plus a share in future merges. If there are L levels and each is T times larger than the previous one, in the leveled scheme a byte is rewritten about T·L/2 times, in the tiered one about L times, where L ≈ log_T(N/M) for N bytes of data and M bytes of memory. A read takes one run per level in the leveled scheme and up to T per level in the tiered one; with Bloom filters, almost always one run per key found. The space is the data plus stale versions: in the leveled scheme the excess is of order 1/T, in the tiered one it can be twice what is needed until a big merge finishes.

Merges are sequential reading and sequential writing, as in external sorting. While they run in the background, writes do not wait. But if the stream of writes is stronger than the merges can keep up with, runs pile up in L0, and databases start slowing down writes; otherwise reads would drown in runs.

Where it works

Embedded stores. LevelDB was written by Jeff Dean and Sanjay Ghemawat; RocksDB grew out of it and became the storage under many databases and queues. Both merge by levels by default.

Distributed databases. Bigtable, HBase, Cassandra, ScyllaDB: writes go to memory and a log, flushes to immutable files, merges run in the background. Immutability is especially convenient here: a finished file can be copied to other machines and compared without fear that it will change.

Search. Lucene writes an inverted index in small immutable segments and merges them in the background: the same scheme, only the runs are pieces of the index.

History

Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil described the LSM tree in 1996 in the journal Acta Informatica. The task was a bank’s transaction log: a huge stream of records that are rarely read, where a B-tree would spend a random disk read on each insertion. In 2006 the Bigtable paper gave the structure its present names, memtable and SSTable, and showed how to build a distributed store on it. LevelDB was opened in 2011, RocksDB in 2013.

Problems

In the first problem you have to merge runs so that deleted files do not come back to life while unneeded tombstones do not pile up. In the second, divide the memory of Bloom filters among runs of different sizes so that a search for a missing key reads as little as possible.