LSM-Trees & Compaction

0. The 5-Minute Version

0.1 The promise

A log-structured merge-tree (LSM tree) stores sorted key-value data so that writes are cheap and reads stay fast. It does it with three moves:

1. Keep the newest data sorted in memory, in a table called the MemTable.
2. Write it out as immutable sorted files. When the MemTable is full, we write it to disk in one sequential pass as a sorted file called an SSTable (sorted string table). A file is never changed after it is written.
3. Merge the files in the background. A job called compaction merges SSTables, throws away overwritten and deleted data, and keeps the number of files a read must check small.

Nothing is updated in place. An overwrite is a new version and a delete is a new "deleted" marker; the newest version always wins.

Synthesizing vector architecture diagram...

What to notice: data only moves right. Files are created by flush and compaction and deleted after compaction replaces them; they are never edited.

0.2 What we assume from the log

This page pairs with the Write-Ahead Log loop primitive (Write-Ahead Log, fsync & Group Commit), which is not written yet. Here is the contract this page relies on, so it stands on its own:

• A write-ahead log (WAL) is an append-only file. append(record) writes a record and makes it durable (with fsync, a call that forces the bytes onto the disk itself) before the write is acknowledged. Many writers can share one fsync; that is group commit.
• Each record gets a sequence number (seq) that goes up by one per write. The same number is the version of the entry in the LSM tree. One number, two jobs.
• replay(from_seq) returns the records in order after a crash and stops at the first damaged one.
• The LSM tree tells the log one thing: "everything up to sequence N is safely in a flushed file." Log segments holding only records up to N may then be deleted. Section 1.6 gives the order that makes this safe.

0.3 The numbers to remember

0.4 When to choose what

0.5 Reading paths

0.6 The tiny store

One small running example goes all the way through. Every trace on this page was produced by running a private reference implementation of this store, not written by hand.

The writes we follow. Snapshot S5 is a reader that asked to see the data "as of sequence 5"; it is taken after seq 5 and released after seq 16.

0.7 Where this shows up

---

Part 1. The Write Side

1.1 Why not update in place?

The classic alternative is a B-tree: a balanced tree of fixed-size pages (16 KB in InnoDB, 8 KB in PostgreSQL), where each key lives in one leaf page. To change a row, the engine changes its page in memory and later writes the whole page back to the same place on disk.

That is less costly than it is often made to look, for two reasons. The B-tree engine also logs every change first, so a write is acknowledged after a small sequential log append, not a page write. And the buffer pool (its page cache) coalesces: if 8 rows on one page change before the page is written back, one page write covers all 8.

So a B-tree's write cost depends on how many changes $u$ land on a page of size $P$ before it is written back, with records of size $r$. Pages also need protection against torn writes (a crash in the middle of a page write): InnoDB writes each page twice (the doublewrite buffer), and PostgreSQL logs a full copy of a page the first time it changes after a checkpoint. Call that extra factor $d \approx 1$. Per byte of user data:

$$\text{WA}_{\text{B-tree}} \approx \frac{P}{u \cdot r}\,(1 + d) + 1\ \text{(the log)}$$

Assumptions: $d = 1$, no compression, inner-node pages ignored (they are few and cached).

An LSM tree never writes a page in place: all its writes are sequential, and it pays later, in compaction, about 12 to 15 times in our simulation (section 3.3). So it writes fewer bytes when keys are random and the table is much larger than memory, and it can write more bytes than a B-tree when writes have strong locality. Reads are simpler in a B-tree. The full, equal-terms comparison is section 5.1.

1.2 The core idea and three invariants

The diagram in 0.1 is the whole structure. Three invariants (rules that are always true) hold it together:

I3 is why reads search in a fixed order (2.3) and why compaction must be careful about what it drops (3.1).

1.3 Internal keys, sequence numbers and tombstones

An LSM tree never stores a bare key → value. Each entry is an internal key plus a value:

Entries sort by user key ascending, then sequence number descending, so all versions of a key sit together, newest first. We write an entry as key@seq, for example user:2@6 DEL.

• An overwrite is a new version. PUT user:1 alicia at seq 5 does not touch user:1@1 alice; it adds user:1@5, which sorts in front of it.
• A delete is a new version, called a tombstone. DELETE user:2 at seq 6 writes user:2@6 DEL. The old value may sit in an immutable file we cannot change, so the tombstone hides it until compaction removes both.
• A read at sequence S sees, for each key, the newest entry with a sequence number at most S. A snapshot is exactly that: a sequence number a reader holds on to for a consistent view.

Smallest example. PUT a=1 at seq 1, PUT a=2 at seq 5, DELETE a at seq 8:

The tiny store's first eight writes, as internal keys:

The cost: old versions and tombstones take space until compaction removes them.

1.4 The MemTable

The MemTable must stay sorted (so flush writes a sorted file in one pass, and scans work), accept many concurrent writers, and let readers search while writes go on. A hash table is not sorted. A balanced tree is sorted but rebalances near the root, which needs wide locks. The usual answer, in LevelDB and RocksDB, is a skip list: a sorted linked list with extra "express lanes". Every node is on lane 0; each node also joins the next lane up with probability $p$ (LevelDB and RocksDB use $p = 1/4$). A search runs along the top lane and drops a lane whenever the next node would overshoot, so search and insert take expected $O(\log n)$ steps, and an insert only changes a few pointers.

The first MemTable of the tiny store after four inserts, with lane heights fixed so the example repeats (user:1@1 = 1, user:2@2 = 2, order:9@3 = 1, user:3@4 = 3). The search for user:3 follows the thick arrows:

Synthesizing vector architecture diagram...

What to notice: lane 2 would overshoot straight away, so the search drops to lane 1, takes one step to user:2@2, and drops to lane 0, where the next node is the answer. That is 1 step right instead of 3 on lane 0 alone.

Memory and the flush trigger. The engine counts the MemTable's bytes. Past the limit (write_buffer_size, 64 MB), the MemTable becomes immutable, a new one takes writes, and a flush is scheduled. RocksDB keeps at most max_write_buffer_number MemTables (default 2) per column family, so MemTable memory defaults to up to 128 MB.

Go deeper: the skip list algorithm.

textCopy
SEARCH(list, target)                  -- target is an internal key (user key, seq)
  x = list.head
  for lane from top down to 0:
      while x.next[lane] != END and x.next[lane].key < target:
          x = x.next[lane]            -- move right
  return x.next[0]                    -- first entry >= target

INSERT(list, entry)
  h = 1; while random() < p: h = h + 1
  walk as in SEARCH, remembering the last node before entry on each lane
  for lane from 0 to h - 1:           -- bottom lane first, so readers never see a gap
      entry.next[lane] = remembered[lane].next[lane]
      remembered[lane].next[lane] = entry

RocksDB also offers a vector MemTable (fast bulk loads, sorted only at flush) and hash-indexed MemTables that speed up lookups within a key prefix at the cost of full-order scans.

1.5 The write path end to end

Synthesizing vector architecture diagram...

textCopy
WRITE(op, key, value)                         -- op is PUT or DEL
  1. seq = next sequence number               -- shared with the log
  2. append (seq, op, key, value) to the current WAL segment and make it durable
     per the sync policy (group commit)
  3. insert (key, seq, op) -> value into the active MemTable
  4. make seq visible to new readers
  5. acknowledge the client
  6. if the MemTable is over its size limit:
         check the stall conditions (3.5): maybe delay or wait
         freeze it as immutable; start a new MemTable and a new WAL segment
         schedule a flush (1.6)

Step 2 comes before step 5, so a crash can only lose writes nobody was told succeeded. Step 4 comes before step 5, so a client that reads its own key right after the acknowledgment sees it. A new WAL segment per MemTable lets the engine delete a whole segment once its MemTable is on disk.

Trace: the first nine writes (4-entry MemTable):

In that first compaction user:1@1 alice was dropped (snapshot S5 reads the newer user:1@5, so no reader can see @1), while user:2@2 bob was kept because S5 still reads it.

How it breaks: if flushes cannot keep up, immutable MemTables pile up, and when all max_write_buffer_number of them are full, writes stop (3.5).

1.6 Flush

A flush turns an immutable MemTable into a Level 0 SSTable. The naive way (write the file, then delete the WAL) has a gap: a crash between the two, in the wrong order, loses data.

textCopy
FLUSH(imm)
  1. write imm's entries in sorted order into a new file f: data blocks,
     then the filter, index and footer (2.1)          -- one sequential pass
  2. fsync f, then fsync its directory               -- the bytes and the name are durable
  3. append to the manifest: { add f at Level 0, "logs before wal-(n+1) not needed" }
     and fsync the manifest
  4. readers start using f instead of imm
  5. only now delete the released WAL segment

The manifest is a small log that lists which files make up the tree (4.1). A file on disk that the manifest does not list does not exist for the engine.

Synthesizing vector architecture diagram...

Synthesizing vector architecture diagram...

A note on duplicates: our tiny store's flush writes every entry of the MemTable, as LevelDB does. RocksDB's flush also drops versions no snapshot can see, using the same rules as compaction (3.1).

---

Part 2. Files and the Read Side

2.1 The SSTable

An SSTable is sorted entries split into blocks, so a read fetches only the small block it needs. Scanning a whole file for one key would read megabytes; the layout below reads one block.

Synthesizing vector architecture diagram...

What to notice: a lookup touches the filter, the index and one data block. Keep the first two in memory and a lookup costs at most one disk read.

textCopy
FILE_GET(file, key, read_seq)
  1. if key is outside the file's [smallest, largest]:    not here
  2. if the filter says "certainly absent":               not here, no disk read
  3. binary search the index for the first block whose separator >= (key, read_seq)
  4. read that block (block cache or disk) and search inside it
  5. return the first entry for key with seq <= read_seq, if any
     (it may continue into the next block)

Worked size for a 64 MB file (24-byte key, 200-byte value, about 11 bytes of overhead, so 235 bytes per entry, before compression):

About 1 MB of index and filter per 64 MB file: about 16 GB for 1 TB of data. If that does not fit in memory, lookups pay extra disk reads just to consult them, which is why it is a sizing question (6.1).

Trace: one lookup. GET order:7 in F3 ([order:7@7 pen, order:9@3 book], [user:1@5 alicia]): the key is in range, the filter says maybe, the index points to block 0, and block 0 holds order:7@7 pen.

Go deeper: inside a block. Sorted keys share prefixes, so each key stores only how many bytes it shares with the previous key plus the new suffix (prefix compression). To keep binary search possible, every 16th key (block_restart_interval = 16) is stored in full as a restart point, and the block ends with an array of restart offsets. A search binary-searches the restart points, then scans forward at most 16 keys.

2.2 Bloom filters in an LSM tree

A Bloom filter is a bit array and $k$ hash functions. Adding a key sets its $k$ bits; testing a key checks them. Any zero bit means "certainly absent"; all ones means "probably present". It never says absent for a key that is there. The structure itself is covered in Primitive #03: Bloom filters.

With $b$ bits per key and $k$ hashes:

$$p \approx \left(1 - e^{-k/b}\right)^{k}, \qquad \text{best } k = b \ln 2, \qquad p_{\min} \approx 0.6185^{\,b}$$

Our reference filter measured 0.83% at 10 bits per key. RocksDB's filter is documented at 0.95%: it keeps a key's bits in one cache line to save CPU, at a small cost in accuracy. That is the source of the rule of thumb "10 bits per key, about 1%". RocksDB does not build a filter unless one is configured.

Wasted reads. A lookup for an absent key checks up to one filter per candidate file. With 4 Level 0 files and 6 deeper levels, that is 10 files: $10 \times 0.0095 \approx 0.1$ wasted block reads, against up to 10 disk reads with no filter.

Range scans get no help. A scan of [user:1, user:4] is not a membership test for one key; it must visit every file whose range overlaps. Filters make point reads cheap, not scans (2.4).

2.3 The point-read algorithm

Checking every file for every read would make reads slower as the tree grows. Invariant I3 lets a read stop early.

textCopy
GET(key, read_seq = latest)
  1. search the active MemTable, then immutable MemTables, newest first
  2. search every Level 0 file whose range covers key, newest first  -- they overlap
  3. for each deeper level: the one file whose range covers key       -- no overlap
  4. inside each file: skip it if the filter says no (FILE_GET, 2.1)
  5. the FIRST entry with seq <= read_seq wins:
        PUT -> its value      DEL -> not found
     nothing anywhere -> not found

Synthesizing vector architecture diagram...

Trace. State after seq 14, with snapshot S5 alive:

After the later compactions (section 3.2's tiny-store run), the filters do the skipping: GET user:2 finds Level 1's F13 covers the key but its filter says no, and goes on to Level 2.

How it breaks: read cost grows with the number of Level 0 files and levels (2.5).

2.4 Range scans

A range scan returns every live key in [lo, hi] in order. The data is spread across the MemTables, every Level 0 file and each deeper level, all sorted. The engine merges them with a merge iterator: one child iterator per source, and a min-heap (a priority queue that always yields the smallest entry) holding each child's current entry.

Synthesizing vector architecture diagram...

textCopy
SCAN(lo, hi, read_seq)
  seek one iterator per source to lo; put each current entry on a min-heap
  last_key = none
  while the heap is not empty:
      e = pop the smallest; advance that iterator and push its next entry
      if e.key > hi: stop
      if e.seq > read_seq: continue          -- too new for this reader
      if e.key == last_key: continue         -- older version, shadowed
      last_key = e.key
      if e is a tombstone: continue          -- deleted
      emit (e.key, e.value)

Trace, SCAN [user:1, user:4] on the state in 2.3:

1. user:1@10 DEL (F5): tombstone, hide user:1. Then user:1@5 alicia (Level 1): shadowed.
2. user:2@12 bea (F5): emit. Then user:2@6 DEL and user:2@2 bob: shadowed.
3. user:3@14 cara (MemTable): emit. Then user:3@4 carol: shadowed.
4. user:4@8 dave (Level 1): emit.

The same scan at snapshot S5 skips everything newer than 5 and returns user:1 alicia, user:2 bob, user:3 carol.

Why scans cost more: every source must be positioned and filters cannot rule any out, and every old version and tombstone in the range passes through the heap before being thrown away. A queue-like table that deletes from the front and scans from the start can step over thousands of tombstones before its first live row (3.7, 6.2).

2.5 Read amplification

Read amplification is the work a read does beyond the one block holding its answer. With $n_0$ Level 0 files, $L$ deeper levels, false-positive rate $p$ and index and filter blocks cached:

$$\text{files consulted} \le n_0 + L, \qquad \text{wasted block reads} \approx (n_0 + L)\,p$$

Synthesizing vector architecture diagram...

Upper line: no filters, one block read per file checked. Lower line: 10-bit filters (0.95% false positives), about 0.1 block reads at most.

A range scan costs at least one seek per source, however short the range. Where the block cache helps: keep index and filter blocks cached first (every read touches them), then hot data blocks.

---

Part 3. Compaction: the Algorithm and the Policies

3.1 The merge algorithm

Without compaction, files pile up: reads check more and more of them, and overwritten and deleted data never leaves the disk. Simply deleting old files would lose keys that were never overwritten. Compaction instead merges sorted files into new sorted files that keep only what someone can still read.

textCopy
COMPACT(inputs, output_level, live_snapshots)
  1. merge all inputs in internal-key order (key ascending, seq descending)
  2. for each key, walk its versions newest first:
       stripe(v) = the oldest live snapshot >= v.seq, or LATEST if there is none
       -- all versions in one stripe look the same to every reader
       if a newer version of this key is in the same stripe:  drop v   (shadowed)
       else if v is a tombstone
            and no live snapshot is older than v.seq
            and no file below output_level may hold this key:  drop v   (delete finished)
       else: keep v
  3. cut the output into files of about the target size,
     never splitting one key's versions across files
  4. write the outputs sequentially; fsync them and their directory
  5. one manifest edit: { delete all inputs, add all outputs }   -- atomic switch
  6. delete the inputs once no reader still holds them (4.1)

The two drop rules are the hard part:

• Shadowed versions go once no snapshot sits between them and a newer version. With no live snapshot, only the newest version of each key survives.
• A tombstone goes only when both conditions hold. If an older version might sit in a deeper level this compaction does not read, dropping the tombstone would bring that value back. If a live snapshot is older than the tombstone, the snapshot may still need the older value, and the tombstone must stay to hide that value from everyone else.

3.2 A worked compaction

A Level 1 file A is picked and merged with the two Level 2 files that overlap its range [k:b, k:e]. One live snapshot is at sequence 30. Level 3 holds an old version of k:e.

Synthesizing vector architecture diagram...

With the snapshot at 30 there are two stripes: seq up to 30, and seq above 30.

8 entries in, 6 out. Reads afterwards: k:b latest gives b3, at snapshot 30 gives b1; k:c and k:e give not found either way. k:e@29 DEL can go only when a compaction merges it with C at Level 3.

The same rules in the tiny store. After seq 16 the two Level 0 files F5 and F6 merge with Level 1 files F3 and F4 while S5 is alive. The tombstones user:1@10 and order:7@15 stay (S5 is older than them), alicia, bob, carol and book stay for S5, and the shadowed order:7@7 pen and user:2@6 DEL go: 15 entries in, 13 out, in files F7 to F10. Level 1 then has 4 files, over its limit of 2, so F7 and F8 move to Level 2. Nothing overlaps them there, so the engine does a trivial move: a manifest edit that relabels the file, without rewriting it.

S5 is released after seq 16. After seq 24, the next Level 0 merge meets user:5@20 DEL and user:5@9 erin with no snapshot alive and no deeper file covering user:5: both are dropped, and that delete is finished. Meanwhile F7 and F8 in Level 2 still carry book, alicia and bob, which nobody can read any more. They stay until a compaction touches those files again; RocksDB's periodic_compaction_seconds exists to force that eventually.

3.3 Leveled compaction

Leveled compaction (the default in LevelDB and RocksDB) keeps every level below Level 0 as one sorted run: its files never overlap, and each level's target size is $T$ times the one above.

Synthesizing vector architecture diagram...

What to notice: one file from above meets only its overlapping neighbours below; the rest of the level is not touched.

textCopy
PICK_COMPACTION()
  1. score Level 0 as (file count / trigger); score each deeper level as (size / target)
  2. take the level with the highest score above 1
  3. Level 0: take all its files and the overlapping files of the base level
     deeper level: pick one file (RocksDB default: the smallest overlap with the
     next level relative to its size) and the overlapping files of the next level
  4. if nothing overlaps below, just move the file (a manifest edit)

Level 0 is special: its files are flushed MemTables whose ranges overlap, so they are merged together into the base level.

Level targets at real scale. RocksDB 11.11 defaults: base size 256 MB (max_bytes_for_level_base), ratio 10, and since version 8.4 level_compaction_dynamic_level_bytes = true, which sizes the levels from the bottom so the last level holds about $T/(T+1) \approx 91\%$ of the data. For 1 TB: about 1 TB, 102 GB, 10 GB and 1 GB. The next level up would be about 102 MB, below 256 MB, so the 1 GB level is the base level that Level 0 compacts into: 4 levels below Level 0.

Deriving write amplification for 1 TB, $T = 10$, 64 MB MemTables. Count how many times one byte is written:

1. WAL: 1.
2. Flush to Level 0: 1.
3. Level 0 to the base level: 4 files × 64 MB = 256 MB merge with the overlapping base level, which is all of its 1 GB when keys are random. Writing 256 MB down costs $256 + 1024$ MB: a factor of $1 + 1024/256 = 5$.
4. Each deeper move: a file of size $s$ from level $i$ covers the fraction $s / \text{size}(L_i)$ of the keys, so it overlaps about $T s$ bytes of level $i+1$. The merge writes $s + T s$: at most $T + 1 = 11$ per level. It is lower in practice because the next level is not always full and the picker prefers files with little overlap.

$$\text{WA} \approx 1 + 1 + 5 + 3 \times (5\ \text{to}\ 11) \approx 22\ \text{typical},\ 40\ \text{at the bound}$$

Assumptions: uniform random keys, levels at their targets, no compression, the WAL counted. Keys written in order overlap less and do better.

Checked against the reference implementation (1 million writes, $T = 10$, Level 0 trigger 4, base level the size of one Level 0 batch, so step 3 costs about 2):

A full level cost about 5 per byte, about $T/2$, well under the bound of 11. In the tiny store the same effect is visible at a smaller scale: 24 writes were flushed once, and the three compactions then wrote 7 + 13 + 9 = 29 more entries.

Read amplification: at most the Level 0 files plus one file per level (2.5). Space amplification: stale copies in the upper levels add at most about $1/T + 1/T^2 + \dots \approx 0.11$ of the data, so about $1.11\times$ plus one compaction's temporary files. Our update-heavy run measured 1.18 because its last level was not full.

Go deeper: stacked write amplification. An SSD has its own write amplification: to reuse space, it must erase whole flash blocks and copy live pages elsewhere first. The bytes that reach the flash are the product of both: $\text{WA}_{\text{total}} = \text{WA}_{\text{LSM}} \times \text{WA}_{\text{SSD}}$. Large sequential writes and free space on the drive keep $\text{WA}_{\text{SSD}}$ close to 1; a nearly full drive with small random writes can raise it several times. If we assume $\text{WA}_{\text{SSD}} = 1.5$, an LSM at 22 writes about 33 bytes of flash per user byte, which is what drive endurance ratings must cover (6.4).

3.4 Other policies

Different workloads want different trade-offs, and the loops mention all of these.

• Size-tiered (Cassandra's default, STCS; RocksDB's universal compaction is the same family): wait for several files of similar size (Cassandra: at least min_threshold = 4, within about 50% of each other) and merge them into one bigger file. Each byte is rewritten about once per tier: with tiers growing 4 times, 1 TB built from 64 MB flushes has about $\log_4(16{,}384) = 7$ tiers.
• FIFO: never merge; delete the oldest files once the total passes a size limit or they pass a time to live (TTL).
• Time-window (Cassandra's TWCS): group files by the time window of their data, run size-tiered compaction only inside the current window, and drop a whole window's file once all of its data has expired.

The RUM conjecture (Athanassoulis et al., 2016) names the pattern: a storage method cannot make Read, Update and Memory (space) overheads all minimal at once. Leveled buys cheap reads and space with writes; size-tiered buys cheap writes with reads and space; FIFO gives up old data.

How they break: size-tiered needs free disk for its big merges (3.6); FIFO loses data by design; time-window handles late updates and deletes badly, because they land in new windows and cannot be merged away.

3.5 Scheduling, stalls and the feedback loop

Compaction runs in background threads. If it falls behind, Level 0 fills (reads slow down, 2.5) and disk fills (3.6). So the engine slows writers on purpose, then stops them, to keep the tree bounded.

Synthesizing vector architecture diagram...

The math. Each client byte costs WA bytes of flush and compaction writes. With $B$ bytes per second of disk write bandwidth for that work:

$$\text{ingest} \times \text{WA} \le B \quad\Longrightarrow\quad \text{sustainable ingest} \approx \frac{B}{\text{WA}}$$

Synthesizing vector architecture diagram...

Worked timeline. At 120 MB/s with 64 MB MemTables, a flush lands about every $64 / 120 \approx 0.53$ s. If compaction cannot drain Level 0, it grows from 4 files to the slowdown point of 20 in about $16 \times 0.53 \approx 8.5$ s, and would reach the stop point of 36 about 8.5 s after that without the slowdown. Then writers wait until compaction brings Level 0 back under 36. This is the pattern in the drill The Time-Series Database That Froze on Flush: excellent latency most of the time, then a freeze of several seconds. Its first question, why writes stall completely, is answered here: flushes add Level 0 files faster than compaction can merge them, and the engine stops writers on purpose so reads and disk use stay bounded. Its second question is answered in 5.1.

3.6 Space, tombstones and disk-full

Temporary space. A compaction writes its outputs before deleting its inputs, so both exist at once.

• Leveled: a compaction is a few files; RocksDB tries to keep one under max_compaction_bytes (default 25 × target_file_size_base = 1.6 GB). A few GB per concurrent compaction is enough.
• Size-tiered: merging the largest tier writes a file as large as its inputs minus what it drops. In the worst case (all the data in one merge, nothing dropped) that is free space equal to the data being merged, so the disk must stay at most about half full. Our simulation peaked at 2.97 times the live data during a merge. ScyllaDB's incremental compaction (ICS) splits big files into runs of about 1 GB fragments to remove this peak.

When deleted data really disappears: only when compaction brings the tombstone together with the old value and the tombstone reaches a point where nothing older can exist below it (3.1). Until then it costs space and scan time.

Zombies in replicated stores. In Cassandra, a replica that was down during a delete never got the tombstone. If the other replicas purge their tombstones and the lagging replica later shares its old value through repair, the deleted row comes back: a zombie. Cassandra keeps tombstones for gc_grace_seconds (default 864,000 s, 10 days) before they can be purged, and every node must be repaired within that window so every replica learns about each delete.

Disk-full. A compaction that runs out of space cannot finish, so it cannot delete its inputs, so no space is freed, while writes keep coming. Recover by adding space (or removing backups and snapshots), not by starting another compaction. Prevent it with headroom sized to the policy (6.1).

3.7 Deletes at scale

Deleting a billion keys one by one writes a billion tombstones. Each must be written to the WAL, flushed, scanned past by readers, and carried down the levels until compaction can drop it, so a big cleanup can slow reads for days.

The key deleted near the top of the tree takes longest to go: in 3.2, k:e@29 DEL sits in Level 2 because an older k:e is in Level 3, and it stays until a compaction merges it with Level 3.

The ways out:

Designing the keys so data that expires together sits together is usually the cheapest delete of all.

---

Part 4. Keeping the Tree Consistent: Manifest, Versions and Recovery

4.1 Immutable files and version sets

A flush adds one file; a compaction deletes several and adds several. A reader must never see half of it: both the inputs and the outputs (duplicate data) or neither (lost data).

The manifest is an append-only log of version edits. Each edit lists files to add (with level and key range) and files to delete, plus bookkeeping: the last sequence number used and the oldest WAL segment still needed. The current version of the tree is what you get by replaying all edits. One edit is one record, so a flush or a compaction switches in one step. A small file named CURRENT points to the active manifest.

Synthesizing vector architecture diagram...

The tiny store's manifest, as the reference implementation recorded it:

Reference counting. A reader holds on to the version that was current when it started. Files deleted by a later edit stay on disk while any reader still holds a version that lists them, and are deleted when the last one lets go.

Go deeper: forgotten iterators and snapshots. An iterator (an open scan) pins the files of its version, so a scan left open for hours keeps every file that compactions have replaced since then: disk use grows while the data does not. A snapshot pins no files, but it makes compaction keep the versions it can see (3.2), which also holds space. Both show up as "disk use grows, live data does not"; the fix is closing long-lived iterators and releasing snapshots.

4.2 Full crash recovery

textCopy
RECOVER()
  1. read CURRENT, then replay the manifest's edits in order
       -> live files per level, last sequence number, oldest WAL segment still needed
  2. delete data files the manifest does not list         -- orphans of unfinished work
  3. replay the WAL from the oldest segment still needed, in order,
     stopping at the first damaged record (the log's rule)
       -> rebuild a MemTable with each record's original seq
  4. next seq = max(manifest's last seq, last replayed seq) + 1
  5. flush the rebuilt MemTable (usually), record it, delete the old segments
  6. open for traffic

Synthesizing vector architecture diagram...

Crash during a flush: the table in 1.6. Crash during a compaction (F3 to F6 merged into F7 to F10):

One rule covers every change: new files durable, then one manifest edit, then delete what it replaced.

4.3 Why immutability pays off

• Cheap consistent backups. A backup is the manifest plus the files it lists, and a file already copied never needs copying again, so incremental backups upload only new files. RocksDB's checkpoint makes a consistent copy by hard-linking the live files.
• Free snapshots. A snapshot is just a sequence number (1.3).
• Moving data by file. A new replica can be seeded by copying files rather than replaying every write.
• Simple caching. A cached block can never be stale.

The distributed key-value store loop and the S3-like object storage loop both lean on these properties.

---

Part 5. Choosing: LSM vs B-tree, Variants and Engines

5.1 LSM vs B-tree, honestly compared

Both log every write first. They differ in where the rest of the write cost goes. A B-tree pays in page writes: dirty pages written back in place at checkpoints or when the buffer pool needs room, plus torn-page protection (the Write-Ahead Log page will cover checkpoints and full-page writes in depth). An LSM tree pays in compaction.

Decision guide:

Applied to two workloads. (1) The drill's telemetry store: 250,000 random-key points per second, far more data than memory, written in time order and expiring. LSM with time-window compaction. (2) An inventory service: 90% point and short range reads, updates with strong key locality, steady p99 required. B-tree: its write amplification is about 3 to 5 here, so the LSM's main advantage is gone while its scan cost and compaction interference would remain.

5.2 Large values and time series

Key-value separation. With large values, compaction mostly moves value bytes that never change. The WiscKey design (Lu et al., FAST 2016) keeps only keys and small pointers in the LSM tree and appends values to a separate value log.

textCopy
PUT(key, value)                     -- with key-value separation
  1. append value to the value log; get its position
  2. write (key -> position) through the normal LSM write path
GET(key)
  1. read the position from the LSM tree (2.3)
  2. read the value from the value log         -- one extra read
GARBAGE_COLLECT(value log file)
  3. for each value: keep it only if the tree still points to it; rewrite the live ones

Worked amplification (24-byte key, 16-byte pointer, LSM write amplification 22 as in 3.3; assumed value-log garbage collection rewriting each value about once):

The costs: an extra read per lookup, scans that read values from scattered places, and value-log garbage collection that must check each value against the tree. RocksDB implements this as BlobDB (enable_blob_files, with min_blob_size below which values stay inline); TiKV offers Titan. Worth it when values are large and point reads dominate.

Time series fit time-window compaction (whole windows expire at once) and caches fit FIFO (3.4).

5.3 The engines table (corrected)

5.4 On AWS

• Self-run RocksDB, Cassandra or ScyllaDB on EC2. Instance-store NVMe is fastest but is lost when the instance stops, so replication is required. EBS survives instance stops; size gp3 or io2 throughput for the flush and compaction budget of 3.5, not just for client writes. Leave free space for the policy: a little for leveled, up to half the disk for size-tiered.
• Flink state on Amazon Managed Service for Apache Flink uses the RocksDB state backend, with checkpoints handled by the service.
• Amazon Keyspaces (for Apache Cassandra) is serverless and speaks the Cassandra protocol. AWS does not publish its storage internals, so the compaction tuning on this page does not apply to it, and we make no claim about what runs underneath.
• Amazon DynamoDB is the contrast case: a managed WAL plus B-tree design, nothing here to tune.

---

Part 6. Operating It

6.1 Knobs mapped to the algorithm

Sizing formulas:

• MemTable memory $= \texttt{write\_buffer\_size} \times \texttt{max\_write\_buffer\_number}$: $64 \times 2 = 128$ MB per column family by default.
• Filter memory $= \text{keys} \times \text{bits per key} / 8$: one billion keys at 10 bits is 1.25 GB.
• Disk write bandwidth for flush and compaction $= \text{ingest} \times \text{WA}$: 20 MB/s at WA 22 needs 440 MB/s (and about as much reading).
• Free space: leveled, a few GB per concurrent compaction plus about 10% for upper levels; size-tiered, up to the largest tier (plan for 50% free).

Tuning by ingest rate (per node; NVMe, leveled, WA about 22):

6.2 Diagnostics

Synthesizing vector architecture diagram...

6.3 Incident stories

The compaction storm (the drill):

Lesson: a stall is a budget problem (3.5), not a bug.

The tombstone meltdown. A job queue in Cassandra deletes each job after it runs, and the poller scans from the start of the partition. After a busy day each poll steps over hundreds of thousands of tombstones, and queries fail at the tombstone limit. Lesson: deletes stay until compaction removes them; don't scan over them (3.7).

The zombie delete. A Cassandra node came back after two weeks without a repair. The other replicas had purged tombstones older than 10 days, so its old rows spread back through repair. Lesson: repair within gc_grace_seconds (3.6).

Disk full during compaction. A size-tiered table at 70% disk use began its first merge of the largest tier and ran out of space halfway. Lesson: size-tiered needs up to half the disk free (3.6).

6.4 The Well-Architected lens

---

Part 7. Practice

7.1 Think-first drills

7.2 Hand simulations

Simulation A. Fresh tiny store (MemTable 4 entries, blocks of 2). Apply: 1 PUT cart:1 pen, 2 PUT cart:2 ink, 3 DELETE cart:1, 4 PUT cart:3 pad, 5 PUT cart:2 nib, 6 PUT cart:4 cap. Give the Level 0 file, the MemTable, GET cart:1, GET cart:2, GET cart:3, GET cart:5, and SCAN [cart:1, cart:4].

Simulation B. Level 1 file: k:b@35 b3, k:c@38 DEL, k:d@33 d2. Level 2 file: k:a@10 a1, k:b@31 b2, k:b@20 b1, k:c@12 c1, k:d@25 d1. Level 3 is empty. Output files hold up to 4 entries. Give the output (1) with a live snapshot at 30 and (2) with none.

7.3 Interview questions with model answers

7.4 The cheat card

Failure checklist: ingest × WA within the disk budget? Level 0 count and backlog alarmed? Filters configured and cached? Free space for the policy? Scans over tombstones? Repairs inside gc_grace_seconds? Long-lived iterators or snapshots holding space?

7.5 Where to go next

• The Write-Ahead Log loop primitive (Write-Ahead Log, fsync & Group Commit), coming next: the log this page builds on.
• Primitive #03: Bloom filters: the filter structure in depth.
• Primitive #04: caching: the block cache is a cache with the same trade-offs.
• Drill: The Time-Series Database That Froze on Flush, answered in 3.5 and 5.1.
• Loops: the distributed key-value store (step 1.2 and compaction) and S3-like object storage (metadata compaction).