The LSM write and read path

The problem: 40,000 click writes a second

Snip's click history store takes about 40,000 writes a second per region at peak, each a small row: code, time, country, referrer. A B-tree would rewrite a page for most of them. The LSM-tree turns them into large sequential writes instead. Here's exactly how, and what it costs.

The write path

1. Append to the write-ahead log, so the write survives a crash (04.06 Write-ahead logs and crash recovery).
2. Insert into the memtable, a sorted structure in memory (a skip list or balanced tree). The write is now done; the client gets its acknowledgement.
3. Flush. When the memtable reaches its size limit, it's frozen, a new empty one takes its place, and the frozen one is written to disk in one sequential pass as an immutable sorted file, usually called an SSTable (sorted string table). Its log can then be deleted.

Each SSTable has a small index of where keys are in the file (one entry per block, not per key) and a Bloom filter saying which keys it might contain.

The read path

1. Check the memtable (and any frozen one still being flushed).
2. Check SSTables from newest to oldest. For each, ask its Bloom filter first: "definitely not here" skips the file without reading it. Otherwise look up the block in the file's index and read that block.
3. The first version found is the answer, because it's the newest. If it's a tombstone, the key was deleted.

Try it

Tombstones

A delete can't remove anything from immutable files, so it writes a tombstone: "this key is gone as of now". The tombstone hides older values during reads, and both are dropped only when compaction merges the tombstone with every older file that might hold the key.

In a replicated store, tombstones must also outlive the time a replica might be offline: if a tombstone were dropped before a lagging replica heard about the delete, that replica could later bring the old value back. Cassandra keeps tombstones for gc_grace_seconds, by default 864,000 seconds (ten days), and removes them only at a compaction after that.

Compaction strategies

Without compaction, files multiply, reads check more of them, and dead data piles up. How compaction chooses what to merge is the main tuning knob:

Leveled (RocksDB's default style, Cassandra's LCS). Freshly flushed files land in level 0, where key ranges overlap. Every level below is one sorted run, split into files by key range, with size targets that grow exponentially, typically about ten times per level. A read checks at most one file per level below L0. The cost is write amplification: data is rewritten as it moves down each level, and RocksDB's documentation describes leveled compaction's write amplification as often larger than 10.

Tiered (RocksDB's universal compaction, Cassandra's size-tiered STCS). Instead of merging small runs into big ones straight away, it waits for several runs of similar size and merges them together. Far lower write amplification, at the cost of more runs to check on reads, and temporary double disk usage during a full compaction. RocksDB suggests trying it when leveled compaction can't keep up with the write rate.

Time-window (Cassandra's TWCS). For data written in time order and expired by TTL, like Snip's clicks: files are grouped by time window and whole old windows are dropped when they expire, with almost no merging.

Snip uses time-window compaction for click history: the data arrives in time order, is never updated, and expires after 13 months.

A tiny LSM-tree

type Value = string | null; // null is a tombstone

export class TinyLsm {
  memtable = new Map<string, Value>();
  runs: Map<string, Value>[] = []; // sorted runs on "disk", newest first
  written = 0; // entries written to disk, for write amplification

  constructor(private readonly memtableLimit = 4) {}

  put(key: string, value: Value) {
    this.memtable.set(key, value);
    if (this.memtable.size >= this.memtableLimit) this.flush();
  }

  flush() {
    if (this.memtable.size === 0) return;
    const sorted = new Map([...this.memtable].sort(([a], [b]) => (a < b ? -1 : 1)));
    this.runs.unshift(sorted);
    this.written += sorted.size;
    this.memtable = new Map();
  }

  /** Newest first: memtable, then each run. The first hit wins, and a tombstone means "deleted". */
  get(key: string): { value: Value; runsSearched: number } {
    if (this.memtable.has(key)) return { value: this.memtable.get(key)!, runsSearched: 0 };
    let searched = 0;
    for (const run of this.runs) {
      searched++;
      if (run.has(key)) return { value: run.get(key)!, runsSearched: searched };
    }
    return { value: null, runsSearched: searched };
  }

  /** Merge every run into one, keeping only the newest value per key and dropping tombstones. */
  compact() {
    const merged = new Map<string, Value>();
    for (const run of [...this.runs].reverse()) for (const [k, v] of run) merged.set(k, v); // newer overwrite older
    for (const [k, v] of merged) if (v === null) merged.delete(k);
    this.runs = [new Map([...merged].sort(([a], [b]) => (a < b ? -1 : 1)))];
    this.written += merged.size;
  }
}

Tested with the lab's 24 writes (six keys, every seventh write a delete): six runs on disk, every read returned the same value as a plain map would, deleted keys read as tombstones, and after compaction one run remained, still matching. This sketch has no write-ahead log, Bloom filters or levels; it shows the shape.

Recap

Interview questions