How LSM-trees power modern databases

RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, the storage layers of CockroachDB and TiDB, most time-series databases: underneath, they all use the same data structure, the log-structured merge-tree. Its central idea is a refusal: never update data in place. Buffer writes in memory, write them out as sorted, immutable files, and merge those files in the background.

That one choice turns random writes into sequential ones and makes writes very cheap, at the cost of more work on reads and a constant background tax of merging. This article walks through the write and read paths, the two compaction strategies and the three-way trade-off between them, the maths of Bloom filters, and why deletes are the hardest operation in the system. The main figure simulates a small LSM-tree and counts its write amplification as it runs.

Why not a B-tree?

A B-tree keeps data sorted in fixed-size pages and updates them in place. Changing one 100-byte row means reading a 4–16 KB page, modifying it and writing the whole page back, at a random location on disk. On spinning disks random I/O was slow. On SSDs it is fast but wears the flash and is still much slower than sequential writing. For write-heavy workloads such as logging, metrics, messaging and ingestion, a B-tree spends most of its I/O rewriting pages. (How B-tree indexes are laid out and searched is covered in the article on database indexes.)

O’Neil et al.’s 1996 LSM-tree paper proposed batching instead: accumulate changes in memory and merge them into disk-resident sorted structures in large sequential passes. Google’s Bigtable (2006) brought the design to industry, LevelDB (2011) made it a library, and Facebook’s RocksDB (2012) made it the default embedded storage engine for a generation of databases.

The write path

1. Write-ahead log. Append the operation to a log file, sequentially, and optionally fsync. This is the only thing that makes the write durable before it reaches a sorted file.
2. Memtable. Insert into an in-memory sorted structure. RocksDB uses a skiplist by default, which supports concurrent inserts and in-order iteration.
3. Flush. When the memtable reaches its size limit (64 MB by default in RocksDB) it becomes immutable, a new one takes its place, and a background thread writes it out in key order as an SSTable in level 0. The corresponding WAL segment can then be deleted.

The foreground cost of a write is one sequential log append and one in-memory insert. Everything else happens later, in the background, in bulk.

SSTables

A Sorted String Table is an immutable file of key–value pairs in key order. Inside, it is split into data blocks (4 KB by default in RocksDB, often compressed), followed by an index block mapping the last key of each data block to its offset, a filter block holding a Bloom filter over the file’s keys, and a footer that points to them. To find a key in one SSTable: check the filter, binary-search the index, read one data block. Immutability makes everything simpler. Files can be cached, replicated, snapshotted and compressed freely, because nothing will ever change them.

Compaction

Flushes alone would pile up files forever, and every read would have to check them all. Compaction merges sorted files into larger sorted files, like the merge step of merge sort. It keeps only the newest version of each key and discards overwritten values. Levels grow geometrically: each is T times larger than the one above (T = 10 by default in RocksDB), so a few levels hold a very large dataset. Level 0 is special: its files come straight from memtable flushes and may overlap. Below L0, how levels are organised depends on the strategy.

• Leveled (RocksDB’s default, Cassandra’s LCS). Each level below L0 is one sorted run, split into files with non-overlapping key ranges. Compaction picks a file from level i and merges it into the overlapping files of level i+1. Because level i+1 is T times larger, one file overlaps roughly T files there, so each entry is rewritten about T times per level.
• Tiered (Cassandra’s size-tiered STCS, RocksDB’s universal compaction). A level collects up to T runs, and when it is full they are merged together into one run in the next level. Each entry is rewritten about once per level, but a key may exist in up to T runs per level.

Hybrids exist. Dostoevsky’s “lazy leveling” tiers the upper levels and levels only the last. Cassandra 5’s unified compaction strategy can be tuned anywhere between the two.

Three amplifications

Every storage engine trades three costs against each other:

• Write amplification: bytes written to disk per byte the user writes. In a leveled LSM with L levels it is roughly T · L, often 10–30× in practice. It costs disk bandwidth and SSD lifetime.
• Read amplification: disk reads per lookup. Up to one per run that might hold the key, cut down dramatically by Bloom filters and caches.
• Space amplification: bytes on disk per byte of live data. Overwritten values and deleted keys take up space until compaction reaches them.

The RUM conjecture (Athanassoulis et al., 2016) states that no access method can be optimal in all three, Read, Update and Memory, at once. You can only choose where on the triangle to sit. Leveling and tiering are two corners of it, and the size ratio T slides along the edge between them.

The read path

A point lookup checks, in order, until it finds the key:

1. the active memtable, then any immutable memtables waiting to flush;
2. every L0 file whose range covers the key, newest first. L0 files overlap, which is why RocksDB triggers L0 compaction at just four files and stalls writes if L0 grows too large;
3. one file per level below that, found by binary search over the level’s file ranges.

The first version found is the newest, and if it is a tombstone the key is absent. Range scans are harder: they must merge iterators over the memtable, every L0 file and every level, and skip shadowed versions as they go. This is a k-way merge, and the main reason scans are slower on LSMs than on B-trees.

Bloom filters

Most lookups for a key in a given file find nothing. A Bloom filter answers “definitely not here” without reading the file. It is a bit array of m bits, and each key sets k bits chosen by hashing. A lookup checks those k bits: if any is 0, the key was never added. If all are 1, the key is probably there, though those bits may have been set by other keys. False positives are possible, false negatives never. With n keys:

At 10 bits per key, a filter rejects over 99% of unnecessary file reads for about 1.25 bytes per key of memory. Monkey (Dayan et al., 2017) noticed that giving every level the same bits per key is wasteful: the deepest level holds most keys but costs at most one read, so shifting bits toward the smaller upper levels lowers the total false-positive cost for the same memory. RocksDB also offers Ribbon filters, which reach the same accuracy in about 30% less space.

Deletes and tombstones

Since files are immutable, a delete can’t remove anything. It writes a tombstone, a marker that says “this key is deleted as of sequence number s”. Reads that find the tombstone first treat the key as absent. The tombstone itself can only be discarded when compaction carries it to the bottom level: before that, an older value of the key may still sit in a lower level, and dropping the tombstone would bring it back to life.

Range deletes (“delete every key with prefix user:42:”) are stored as a single range tombstone rather than one per key, but they complicate every read, which must check whether a key falls inside a deleted range.

In practice

• Write stalls. If compaction can’t keep up with ingestion, L0 grows, reads slow down, and RocksDB deliberately throttles and then stops writes. Compaction throughput, not memtable speed, is the real ceiling on sustained write rate.
• Large values. Compaction rewrites values along with keys. WiscKey (Lu et al., 2016) stores values in a separate log and keeps only keys and pointers in the LSM, cutting write amplification for large values. RocksDB’s BlobDB does the same.
• Tuning knobs. Memtable size (fewer, larger flushes), the level size ratio (write versus read amplification), bits per key in filters (memory versus reads), block cache size, and compression per level (cheap compression at the top, strong at the bottom where most data lives).

A tiny LSM in code

A memtable, immutable sorted runs with Bloom filters, a newest-first read path, tombstones, and a compaction that keeps the newest version and drops tombstones when it produces the bottom run.

// A toy LSM-tree: memtable -> immutable sorted runs, newest first, each with a Bloom filter.
type Entry = { key: string; value: string | null; seq: number }; // null value = tombstone

class Bloom {
  private bits: Uint8Array;
  constructor(private m: number, private k: number) { this.bits = new Uint8Array(m); }
  // Double hashing: k positions from two base hashes (Kirsch & Mitzenmacher).
  private positions(key: string) {
    let h1 = 2166136261, h2 = 5381;
    for (let i = 0; i < key.length; i++) {
      h1 = Math.imul(h1 ^ key.charCodeAt(i), 16777619) >>> 0;
      h2 = (Math.imul(h2, 33) + key.charCodeAt(i)) >>> 0;
    }
    return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);
  }
  add(key: string) { for (const p of this.positions(key)) this.bits[p] = 1; }
  mayContain(key: string) { return this.positions(key).every((p) => this.bits[p] === 1); }
}

class SSTable {
  readonly bloom: Bloom;
  constructor(readonly entries: Entry[]) { // sorted by key, one entry per key
    this.bloom = new Bloom(Math.max(64, entries.length * 10), 7); // ~10 bits per key
    for (const e of entries) this.bloom.add(e.key);
  }
  get(key: string): Entry | undefined {
    if (!this.bloom.mayContain(key)) return undefined; // skip the disk read entirely
    let lo = 0, hi = this.entries.length - 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1, k = this.entries[mid].key;
      if (k === key) return this.entries[mid];
      if (k < key) lo = mid + 1; else hi = mid - 1;
    }
    return undefined;
  }
}

export class LSM {
  private mem = new Map<string, Entry>();
  private runs: SSTable[] = []; // newest first
  private seq = 0;
  constructor(private memLimit = 1024, private maxRuns = 4) {}

  put(key: string, value: string | null) {
    // A real store appends to the write-ahead log here, before touching the memtable.
    this.mem.set(key, { key, value, seq: ++this.seq });
    if (this.mem.size >= this.memLimit) this.flush();
  }
  delete(key: string) { this.put(key, null); } // a delete is a write

  get(key: string): string | null {
    const hit = this.mem.get(key) ?? this.runs.map((r) => r.get(key)).find((e) => e !== undefined);
    return hit?.value ?? null; // a tombstone and a miss both read as "absent"
  }

  private flush() {
    const sorted = [...this.mem.values()].sort((a, b) => (a.key < b.key ? -1 : 1));
    this.runs.unshift(new SSTable(sorted));
    this.mem.clear();
    if (this.runs.length > this.maxRuns) this.compact();
  }

  // Merge every run into one, keeping only the newest version of each key.
  // This run is now the bottom of the tree, so tombstones can finally be dropped.
  private compact() {
    const newest = new Map<string, Entry>();
    for (const run of this.runs)
      for (const e of run.entries) if (!newest.has(e.key) || newest.get(e.key)!.seq < e.seq) newest.set(e.key, e);
    const merged = [...newest.values()].filter((e) => e.value !== null).sort((a, b) => (a.key < b.key ? -1 : 1));
    this.runs = [new SSTable(merged)];
  }
}

References

1. O’Neil, P., Cheng, E., Gawlick, D. & O’Neil, E. (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica. doi:10.1007/s002360050048
2. Chang, F. et al. (2006). Bigtable: A Distributed Storage System for Structured Data. OSDI. usenix.org
3. Dong, S. et al. (2021). RocksDB: Evolution of Development Priorities in a Key-value Store Serving Large-scale Applications. ACM Transactions on Storage. doi:10.1145/3483840
4. Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. CACM. doi:10.1145/362686.362692
5. Dayan, N., Athanassoulis, M. & Idreos, S. (2017). Monkey: Optimal Navigable Key-Value Store. SIGMOD. doi:10.1145/3035918.3064054
6. Dayan, N. & Idreos, S. (2018). Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. SIGMOD. doi:10.1145/3183713.3196927
7. Athanassoulis, M. et al. (2016). Designing Access Methods: The RUM Conjecture. EDBT. openproceedings.org
8. Lu, L. et al. (2016). WiscKey: Separating Keys from Values in SSD-conscious Storage. FAST. usenix.org
9. Lakshman, A. & Malik, P. (2010). Cassandra: A Decentralized Structured Storage System. ACM SIGOPS. doi:10.1145/1773912.1773922