LSM tree simulator

The tree starts with 200 writes of random keys between 0 and 999. Each write goes into the memtable, shown as a row of keys; when it holds 16 keys it is flushed to a new file in level 0 (L0). The diagram draws every SSTable as a bar covering the range of keys it holds, so you can see which files overlap. The table under it shows how full each level is.

Use Put, Delete and Get on a single key, or the batch buttons to write or read 100 random keys. The panel on the right explains what the last action did: flushes, compactions with the number of entries read and written, and for a get, which files were read and which were skipped. Things to try:

• Write 100 random keys a few times and watch the write amplification climb as data is compacted down the levels.
• Switch to Size-tiered. The same operations are replayed: write amplification drops, while the number of files and the space used go up.
• Turn the Bloom filter off and read 100 random keys. Then turn it back on and compare the file reads per get.
• Delete a key, get it, and find the tombstone that answers.

The model is small but faithful: in levelled mode it follows LevelDB’s documented rules (L0 compacts when it has 4 files; deeper levels compact one file at a time into the overlapping files below), with a size ratio of 4 between levels instead of LevelDB’s 10 so that the levels fill up quickly. Every get is checked against a plain map in tests, and the Bloom filters are real, so their false positives are too.

A log-structured merge tree (LSM tree) is a way of storing sorted key-value data on disk that never updates anything in place. New writes are collected in memory and written out in large sorted batches; old data is merged and rewritten in the background. Every disk write is therefore sequential, which disks and SSDs handle far better than scattered small writes.

The price is paid elsewhere. A key may exist in several files at once, in different versions, so a read has to know which files to check and in what order. And the background merging, called compaction, rewrites the same data several times. Designing an LSM tree is a matter of trading these costs against each other: write amplification (how many times each byte is written), read amplification (how many files a lookup reads) and space amplification (how much disk the data takes compared with its live size). The three numbers at the top of the page are those, measured on the tree you are building.

A write does two things. It appends the change to a write-ahead log on disk, so it survives a crash, and it inserts the key into the memtable, a sorted structure in memory. LevelDB and RocksDB use a skip list for the memtable because it keeps keys in order and allows fast concurrent inserts. The write is now complete: there was one sequential append to disk and no disk read.

When the memtable reaches its size limit, it is frozen and written to disk in key order as a new SSTable file. This is a flush. Engines start a new memtable straight away and flush the old one in the background; once the file is safely on disk, the matching part of the log can be deleted. A crash before the flush only loses the memtable, which is rebuilt by replaying the log. The write-ahead log guide covers that side in detail.

Updates and deletes follow the same path. Writing a key that already exists does not touch the old version; the new one simply shadows it, and compaction removes the old one later.

An SSTable (sorted string table, a name from Google’s Bigtable) is an immutable file of key-value pairs sorted by key. Real SSTables are split into blocks of a few kilobytes, usually compressed, followed by an index of the first key in each block and a Bloom filter of all the keys in the file. A lookup reads the index (often already cached), then at most one block.

Because SSTables never change after they are written, they need no locks, can be read by many threads at once, copied for backups and shared between snapshots. A file is only ever replaced as a whole, by compaction.

Files in L0 are flushed memtables, so their key ranges overlap: each covers whatever keys happened to be written in that period. In the diagram, L0 bars usually stretch across most of the key range. Compaction turns them into files with tidy, non-overlapping ranges in the levels below.

Compaction reads several sorted files, merges them like the merge step of merge sort, keeps only the newest version of each key, and writes new files. It is what keeps reads fast and space bounded, and it is where most of an LSM tree’s writing happens. The two main strategies differ in when they merge.

Levelled compaction (LevelDB, and RocksDB by default) keeps every level below L0 as a single sorted run: its files have non-overlapping key ranges, so at most one file per level can contain a given key. Each level may hold a fixed multiple more data than the one above, here 4 times. When a level grows past its limit, one of its files is merged with the files it overlaps in the next level down. Data is rewritten every time it moves down a level, and often again while it waits there, so write amplification is high; in exchange, reads are cheap and few old versions survive.

Size-tiered compaction (Cassandra’s long-standing default, SizeTieredCompactionStrategy) lets a level collect several sorted runs of similar size, here 4, and only then merges them into one bigger run in the next level. Each entry is rewritten fewer times, but a level can hold several overlapping runs, so a read may have to check several files per level, and older versions of a key stay on disk until their runs are merged.

Running the same 6,000 random operations (55% puts, 10% deletes, 35% gets over 1000 keys) through the simulator’s model with each strategy:

A get must return the newest version of a key, so it searches from newest to oldest and stops at the first match: the memtable, then each L0 file from newest to oldest (they overlap, so any of them could hold it), then one file per deeper level in levelled mode, or one file per run in size-tiered mode. A key that does not exist is the worst case, because every candidate file must be checked.

Most of those checks are avoided with a Bloom filter per SSTable, kept in memory. A Bloom filter answers “definitely not here” or “possibly here”: it can give false positives but never false negatives, so a file it rules out can be skipped safely. The false positive rate depends on the number of bits per key. With m bits, n keys and k hash functions it is about (1 − e^−kn/m)^k, lowest when k = (m/n) ln 2. The simulator’s filters, tested with 100,000 keys that were never added:

Since files are never modified, a delete is written like any other change: a tombstone, a record for the key that says it has been deleted. A read that reaches the tombstone first returns “not found”, even though older versions of the key still sit in deeper levels. Try it in the simulator: delete a key that is on disk, then get it.

Compaction can drop older versions as soon as a newer one, including a tombstone, is merged with them. The tombstone itself can only be dropped when the compaction writes to the bottom of the tree, where nothing older can be hiding below. Until then, deleted data still takes space, and a range scan over many tombstones has to read and skip each of them. In a replicated database like Cassandra there is an extra rule: tombstones are kept for a grace period (gc_grace_seconds, ten days by default) so that a replica that missed the delete cannot bring the data back during repair. Workloads that delete heavily, such as queues stored in a table, are a known trap for LSM databases.

The B-tree is the other common way to store sorted data on disk, used by PostgreSQL, MySQL’s InnoDB and SQLite. It keeps one copy of each key in a page and updates the page in place. A point read follows one path from the root to a leaf. A write must find and rewrite the leaf page, even to change a few bytes, and pages fill up unevenly.

Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil described the LSM tree in 1996 (Acta Informatica), for indexes on tables with very high insert rates, such as history tables, where a B-tree would need a random disk access for every insert. Their design had a small tree in memory and larger ones on disk, merged continuously by a “rolling merge”.

Google’s Bigtable paper (OSDI 2006) brought the idea into wide use and gave us the terms memtable and SSTable, along with minor compactions (flushes) and major compactions. Jeff Dean and Sanjay Ghemawat released LevelDB in 2011 as an open-source single-machine engine on the same design, with levelled compaction. Facebook forked it in 2012 to create RocksDB, adding multithreaded compaction and many options for SSDs. Apache Cassandra and HBase, both open-sourced around 2008, built distributed databases on LSM storage.

• LevelDB compacts L0 when it has 4 files, and lets level L hold 10^L MB before compacting a file from it into level L + 1, according to its implementation notes.
• RocksDB uses levelled compaction by default, with the same L0 trigger of 4 files (level0_file_num_compaction_trigger) and a size ratio of 10 between levels (max_bytes_for_level_multiplier). It also offers universal (tiered) and FIFO compaction, and runs under many other databases, among them MyRocks (MySQL), TiKV and, until it moved to its own Go reimplementation Pebble, CockroachDB.
• Apache Cassandra lets each table choose its compaction strategy: size-tiered, levelled, time-window, or from version 5.0 the unified strategy.
• HBase and ScyllaDB are distributed databases on LSM storage; ScyllaDB reimplements Cassandra’s design in C++.

Operators of these systems watch the same three numbers as the simulator: compaction falling behind shows up as growing L0 file counts and slower reads; heavy deletes show up as tombstone warnings; disk filling faster than the data grows shows up as space amplification.

LSM trees come up in system design interviews whenever a design needs to absorb many writes: time series, logs, metrics, messaging, or a key-value store. Be ready to walk through the write path (log, memtable, flush), the read path (memtable, newest to oldest files, Bloom filters), why deletes are tombstones, and how compaction works. The most common follow-up is “LSM tree or B-tree?”, and the answer is the amplification trade-off: LSM trees for write-heavy workloads where reads are mostly by key, B-trees where reads and range scans dominate.

A common deeper question is designing a key-value store from scratch, as in “design a key-value store like Bigtable or Cassandra”; the LSM tree is the usual answer for the storage engine on each node.