LSM-Trees & Compaction

Part 0. Start here

The problem: 100,000 writes a second on one cloud disk

A storage node in a key-value store has to take 100,000 small writes a second. Each write is about 100 bytes, so that is about 10 MB/s of new data. The keys are random (user IDs, device IDs), and the data is far larger than the node's memory.

The node's disk is an AWS EBS gp3 volume (a general-purpose SSD block volume, attached to the instance over the network) at its baseline, which every gp3 volume includes: 3,000 IOPS (small reads or writes a second) and 125 MiB/s of throughput (about 131 MB/s). So the disk is good at one thing and bad at another:

The big picture

A log-structured merge-tree (LSM tree) is the design from the answer above. Here is the whole of it on one screen; the rest of the page opens each box.

Synthesizing vector architecture diagram...

What you'll be able to do after this page

1. Name the three pieces of an LSM tree and the job of each (Part 1).
2. Walk through a write, including overwrites and deletes (Part 2).
3. Explain how the MemTable becomes a file without losing data in a crash (Part 3).
4. Walk through a read, and say why Bloom filters make it cheap (Part 4).
5. Run a compaction by hand, and explain why writes stall when compaction falls behind (Part 5).
6. Explain how the engine knows which files exist and which level each is in (Part 6).
7. Argue LSM tree vs B-tree for a given workload (Part 7).
8. Trace a write and a read from your code through the operating system to the disk (Part 8).
9. Describe what the engine does when it restarts after a crash (Part 9).
10. Explain how corruption is detected and repaired (Part 10).
11. Say where an LSM tree runs on AWS, size its disk and instance, and name the services that only look like one (Part 11).

You may have arrived from step 1.2 of the distributed key-value store loop or from the metadata store of the S3-like object storage loop: both run on the engine this page takes apart.

Part 1. The core mental model

Before any algorithm, we need the pieces and the rules they keep. Everything later on the page is one of these pieces doing its job.

The three pieces

We start with a log because it is the only way to make a write durable with one small sequential append. Then two more pieces turn that log into sorted, searchable data.

Synthesizing vector architecture diagram...

Three rules the engine never breaks

The tiny store we follow

Real engines hold billions of keys, which is too many to watch. So one small example runs through the whole page: a store with a 4-entry MemTable that takes 24 writes. We call it "watching the tree grow". Every trace on this page was produced by running a private reference implementation of this store, not worked out by hand.

For now you only need the settings:

The 24 writes, for reference (the traces refer back to them). Each write gets a sequence number, seq, that goes up by one per write. A reader called snapshot S5 asks to see the data "as of seq 5": it is taken after write 5 and released after the compaction that follows write 16.

Part 2. Writes, step by step

A write must be durable before we say "OK", and visible to reads right after. And since files never change, an overwrite or a delete cannot touch the old value. This Part shows how one ordered list of steps gives all three.

What we need from the log

This page pairs with the Write-Ahead Log loop primitive, Write-Ahead Log, fsync & Group Commit, which covers durability in depth. All we assume from it:

• Append a record and make it durable before acknowledging. Making it durable means forcing it onto the disk itself with fsync (Part 8); many writers can share one fsync, which is called group commit.
• The append returns the record's sequence number. The same number becomes the version of the entry in the LSM tree. One number, two jobs.
• After a crash, replay the log in order from a given sequence number, stopping at the first damaged record (Part 10).
• The LSM tree tells the log one thing: "everything up to sequence N is now safely in a file." Log segments that hold only records up to N may then be deleted (Part 3).

Versions and tombstones

Every write adds a new version; nothing is overwritten. Each entry is stored as (key, sequence number, type) plus a value, where the type is PUT or DEL. Entries sort by 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 adds user:1@5, which sorts in front of user:1@1 alice.
• A delete is a new version called a tombstone. DELETE user:2 at seq 6 writes user:2@6 DEL. It hides the older value until compaction removes both (Part 5).
• A read at sequence S sees, for each key, the newest entry with a sequence number at most S. A snapshot is just 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 cost: old versions and tombstones take space until compaction removes them.

The MemTable is a skip list

The MemTable must stay sorted (so a flush can write a sorted file in one pass), take many writers at once, and let readers search while writes go on. A hash table is not sorted. The usual answer, in LevelDB and RocksDB, is a skip list: a sorted linked list with extra levels of pointers on top, called lanes, and each higher lane skips over some of the nodes below it. A search runs along the top lane and drops down a lane whenever the next node on this lane is not smaller than the key it wants, so a search or an insert takes about log n steps, and an insert only changes a few pointers.

The tiny store's MemTable after writes 1 to 4. Real skip lists pick each node's height at random; we fixed the heights to keep the picture small. The search for user:3 follows the thick arrows:

Synthesizing vector architecture diagram...

The write path

pseudocodeCopy
WRITE(op, key, value)                               -- op is PUT or DEL
    1. seq = next sequence number
    2. append (seq, op, key, value) to the WAL and make it durable
    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 full:
           freeze it
           start a new MemTable and a new WAL segment
           schedule a flush (Part 3)

WRITE is the path of every client write, and its purpose is to make the write durable and visible before the client hears "OK". Its inputs come from the client: op is PUT or DEL, key is the key (for example user:1), and value is the new value (for example alicia), with no value for a delete. seq is the next sequence number: it goes up by one per write and becomes the version of this entry, so write 5 creates user:1@5. The function appends the tuple (seq, op, key, value) to the write-ahead log (WAL) and waits until it is durable, then inserts the entry into the active MemTable, makes seq visible to new readers, and acknowledges the client. When the MemTable is full (4 entries in the tiny store, about 64 MB at real scale), it also freezes that MemTable, starts a new MemTable and a new WAL segment, and schedules a flush. The result the client receives is the acknowledgement; the changes are one new log record and one new MemTable entry.

Synthesizing vector architecture diagram...

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 "OK" sees it. The order is always WAL first, then MemTable, then acknowledge.

Trace: writes 1 to 4 fill the first MemTable

Write 4 fills the MemTable, so it is frozen, a new MemTable and wal-2 take write 5, and a flush is scheduled.

How it breaks: if flushes cannot keep up, the number of frozen MemTables grows. Engines allow only a few MemTables at once (RocksDB's default is two), so when all are full, writes wait (Part 5).

Part 3. Flushing the MemTable to disk

Memory is limited and the WAL grows without end, so the frozen MemTable must become a file on disk, and the log segment that holds those writes must then be deleted. Done in the wrong order, a crash loses data.

What a flush writes: the SSTable

The frozen MemTable is already sorted, so the flush writes it out in one sequential pass. Scanning a whole file for one key would read megabytes, so an SSTable splits its sorted entries into small blocks and adds a small index and filter, so a read fetches only the one block it needs.

Synthesizing vector architecture diagram...

The safe order

pseudocodeCopy
FLUSH(frozen MemTable m, covered by WAL segment n)
    1. write m's entries in sorted order into a new file f   -- one sequential pass
    2. fsync f
       fsync f's directory                    -- the bytes and the file's name are durable
    3. append one edit to the manifest:
           "add f at Level 0"
           "WAL segment n not needed"
       fsync the manifest
    4. readers start using f instead of m
    5. only now delete WAL segment n

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

FLUSH turns a frozen MemTable into a file on disk and only then lets the engine delete the log segment that holds those writes. Its input m is the frozen MemTable, already sorted, and n is the WAL segment that holds the same writes (in the trace, wal-2 for F2). f is the new SSTable file it creates at Level 0. The order of the steps is the point: first the file's bytes and its name in the directory are made durable with fsync, then one manifest edit that both adds f and marks segment n as not needed is appended and synced, then readers switch from m to f, and only after all of that is segment n deleted. A crash at any step therefore leaves either the log or a listed file holding every write. FLUSH returns nothing; it changes the tree by adding f to Level 0, and it frees the memory of m and the disk space of segment n.

Synthesizing vector architecture diagram...

Trace: F1 and F2 land in Level 0

Write 4 filled the first MemTable. The flush writes F1, two blocks of two entries each:

Synthesizing vector architecture diagram...

After write 4: F1 is recorded in the manifest and wal-1 is deleted. The panel "Level 0" now holds F1, whose key range runs from order:9 to user:3. Its four entries are stored in sorted order in two blocks of two entries each: block 0 holds order:9@3 book and user:1@1 alice, and block 1 holds user:2@2 bob and user:3@4 carol. The panel "MemTable" is empty and ready for write 5, and "Level 1" and "Level 2" are still empty.

Writes 5 to 8 (alicia, the user:2 tombstone, pen, dave) fill the second MemTable, and its flush writes F2. Level 0 now has two files whose key ranges overlap: both cover user:1 to user:3. That is normal for Level 0, because each file is simply one MemTable's worth of writes.

Synthesizing vector architecture diagram...

After write 8: two Level 0 files is the tiny store's compaction trigger, so a compaction is scheduled to run in the background (Part 5). Until it runs, reads must search both files. The panel "Level 0, newest first" lists F2 above F1 because F2 holds the newer writes, 5 to 8. The two key ranges, order:7 to user:4 for F2 and order:9 to user:3 for F1, overlap, so a read for a key such as user:1 must look in F2 first and then, if F2 does not hold it, in F1. The MemTable is empty and ready for write 9.

Part 4. Reads, step by step

Writes are now cheap, but the data is spread over a MemTable and several files. Checking every file for every read would make reads slower as the tree grows. The "newest version wins" rule lets a read search in a fixed order and stop at the first match.

The search path

pseudocodeCopy
GET(key, read_seq = latest)
    1. search the active MemTable, then the frozen MemTables, newest first
    2. search every Level 0 file whose range covers key, newest first   -- they overlap
    3. for each deeper level:
           search only the one file whose range covers key   -- no overlap
    4. inside each file (FILE_GET below): the Bloom filter skips most files
    5. the FIRST entry with seq <= read_seq wins:
           PUT -> its value
           DEL -> not found
       nothing anywhere -> not found

GET answers a point read for one key. Its inputs are key, the key the reader asks for, and read_seq, the sequence number the reader reads at: the latest one by default, or a snapshot's number, such as 5 for snapshot S5. It searches the sources from newest to oldest: the active MemTable, the frozen MemTables, every Level 0 file whose key range covers key (several can, because Level 0 files overlap), and then only one file per deeper level. Inside each file it uses FILE_GET below, whose Bloom filter lets it skip most files without a disk read. The first entry found with a sequence number at most read_seq decides the answer, because every source searched later holds only older data. GET returns that entry's value for a PUT, and "not found" for a DEL (a tombstone) or when no source holds the key; it changes nothing.

pseudocodeCopy
FILE_GET(file, key, read_seq)
    1. if key is outside the file's [smallest, largest]:
           not here
    2. if the Bloom filter says "certainly absent":
           not here                                  -- no disk read
    3. binary search the index for the block that may hold key
    4. read that block (from the block cache or the disk)
       search inside it
    5. return the newest entry for key with seq <= read_seq, if any

FILE_GET searches one SSTable for one key and avoids disk reads wherever it can. Its inputs are file, the SSTable being searched; key; and read_seq, the same read sequence number GET was called with. The file's smallest and largest keys, [smallest, largest], rule it out at once when key falls outside them. The Bloom filter rules it out without any disk read when it says the key is certainly absent; about 1% of absent keys still pass at 10 bits per key. Otherwise a binary search of the index finds the one data block, about 4 KB, that may hold key, and that block is read from the block cache (the engine's own in-memory cache of recently read blocks, Part 8) or from the disk and searched. FILE_GET returns the newest entry for key whose sequence number is at most read_seq, or nothing when the file has no such entry; it changes nothing except possibly filling the block cache.

Synthesizing vector architecture diagram...

Bloom filters skip files that lack the key

Most files a read could check do not hold the key. A Bloom filter lets us skip them without a disk read. It is a bit array plus a few hash functions: adding a key sets a few bits, and 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 Bloom Filters & Counting Filters. The one approximate rule to remember:

(An ideal filter at 10 bits per key gives about 0.8%; real engines use slightly less accurate but faster designs, so people say "about 1%".) So a lookup for an absent key that has 10 candidate files wastes about 10 × 1% = 0.1 block reads, instead of 10 disk reads with no filter. The memory cost: 1 billion keys × 10 bits ÷ 8 = 1.25 GB.

Trace: four kinds of read

Write 9 (PUT user:5 erin) has gone into the new MemTable, and the compaction scheduled in Part 3 has not run yet. Snapshot S5 is alive.

Synthesizing vector architecture diagram...

After write 9, before the first compaction. This is the state the read trace below runs on. The panel "MemTable" holds one entry, user:5@9 erin. The panel "Level 0, newest first" still holds F2 and then F1, with the same blocks as after write 8, and Level 1 and Level 2 are empty. Snapshot S5 is still alive, so the older versions in F1, such as user:2@2 bob, can still be read at seq 5.

Notice the user:1 row: F1 also holds user:1@1 alice, but the read never gets there, because the newer file is searched first. Here we have only Level 0; with deeper levels, step 3 adds one file per level (Part 6 shows how that one file is found).

Range scans

A range scan returns every live key between lo and hi, in order. The data is spread across the MemTables and the files, each sorted on its own, so we merge them with a merge iterator: one cursor per source, and a min-heap (a priority queue that always gives the smallest entry) holding each cursor's current entry.

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

SCAN returns every live key from lo to hi, in key order, as the reader at read_seq sees them. lo and hi are the first and last keys of the range, and read_seq is the reader's sequence number, as in GET. Each source (every MemTable and every file that overlaps the range) gets a cursor placed at lo, and a min-heap holds each cursor's current entry, ordered by key and, for the same key, newest version first. e is the entry popped from the heap in each round, and last_key remembers the key of the last version considered, so older versions of the same key are skipped. An entry newer than read_seq is skipped because this reader must not see it, and a tombstone is skipped because the key is deleted. SCAN stops at the first key greater than hi, emits each surviving (key, value) pair, and changes nothing.

Trace, SCAN user:1 to user:4 on the state above: emit user:1 alicia (F2), skip user:1@1 alice (older); user:2@6 DEL hides user:2, skip user:2@2 bob (older); emit user:3 carol (F1); emit user:4 dave (F2). Result: alicia, carol, dave. The same scan at snapshot S5 skips everything newer than 5 and returns alicia, bob, carol.

Why scans cost more than point reads: every source that overlaps the range must be visited (a Bloom filter answers questions about one key, so it cannot rule any file out), and every old version and tombstone in the range passes through the heap before being thrown away.

Part 5. Compaction: merging SSTables

Without compaction, the number of files keeps growing: reads check more and more of them, and overwritten and deleted data never leaves the disk. We cannot simply delete old files, because they hold keys that were never overwritten. So we merge files into new files that keep only what some reader can still see.

The merge is a k-way merge of sorted files

Every input file is already sorted, so merging them is one sequential pass, like the merge step of merge sort: keep a cursor in each file and always take the smallest entry next (a k-way merge; with two files it is the familiar two-pointer merge). Two plain rules decide what goes. A reader here means the latest view plus every live snapshot.

• An old version goes when no reader would return it: every reader either sees a newer version of the key or is too old to see this one.
• A tombstone goes when nothing older can exist below it and no live snapshot is older than it. If an older value might sit in a deeper level this compaction does not read, dropping the tombstone would bring that value back. If a snapshot is older than the tombstone, it may still need the value the tombstone hides.

pseudocodeCopy
COMPACT(inputs, output_level, live_snapshots)
    1. merge all inputs in order: key ascending, seq descending
    2. for each version v of each key:
           if no reader would return v:
               drop v
           else if v is a tombstone
                and no live snapshot is older than v
                and no deeper level may hold this key:
               drop v
           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
       fsync them and their directory
    5. one manifest edit: { delete all inputs, add all outputs }   -- atomic switch
    6. delete the input files once no reader still uses them

COMPACT merges sorted files into new files and drops the versions no reader can see, so that reads check fewer files and old data leaves the disk. inputs are the files being merged (in the first compaction below, F2 and F1, all of Level 0, plus any overlapping files of the next level); output_level is the level the new files go to; and live_snapshots are the sequence numbers that readers still hold, such as snapshot S5. v is one version of one key during the merge. A version is dropped when every reader sees a newer version instead; a tombstone is dropped only when no live snapshot is older than it and no deeper level may still hold the key. The kept versions are cut into files of about the target size (4 entries in the tiny store, about 64 MB at real scale), never splitting one key's versions. COMPACT returns nothing; it changes the tree with one atomic manifest edit that removes all inputs and adds all outputs, and afterwards the input files are deleted. In the trace below, 8 entries go in and 7 come out, in F3 and F4.

Trace: the first compaction

The compaction scheduled after write 8 now runs. Its inputs are F2 and F1 (all of Level 0) plus any Level 1 files they overlap (none yet). S5 is alive.

8 entries in, 7 out, cut into files of at most 4 entries: F3 gets 3 and F4 gets 4, so user:2's versions stay together. Level 1 is a single sorted run: its files do not overlap.

Synthesizing vector architecture diagram...

After write 9 and the first compaction: one manifest edit deleted F1 and F2 and added F3 and F4. Level 0 is now empty. The panel "Level 1, no overlap" holds F3, with keys order:7 to user:1, and F4, with keys user:2 to user:4; their ranges do not overlap, so a read needs to search at most one of them. user:1@1 alice is gone, because every reader sees alicia instead, while the user:2 tombstone and bob stay together in F4 because snapshot S5 still needs bob. The MemTable still holds user:5@9 erin.

Trace: writes 10 to 16 push data down to Level 2

Writes 9 to 12 flush as F5 (erin, the user:1 tombstone, lamp, bea), and writes 13 to 16 flush as F6 (finn, cara, the order:7 tombstone, gus). Two Level 0 files again, so they merge with the Level 1 files they overlap, F3 and F4. S5 is still alive.

• 15 entries in, 13 out. order:7@7 pen and user:2@6 DEL are dropped because no reader would return them: the latest view sees the newer order:7@15 DEL and user:2@12 bea, and S5 sees nothing written after seq 5 (for order:7 it sees nothing at all; for user:2 it sees bob). The tombstones user:1@10 and order:7@15 stay (S5 is older than both), and alicia, bob, carol and book stay because S5 reads them.
• The output is four files, F7 to F10, so Level 1 is over its limit of 2 files. The engine picks a Level 1 file and merges it with the Level 2 files it overlaps. Level 2 is empty, so nothing overlaps, and the engine does a trivial move: a manifest edit that relabels the file as Level 2 without rewriting a byte. It does this for F7, then F8.

Synthesizing vector architecture diagram...

After write 16. S5 is released now. The second compaction merged F5, F6, F3 and F4 into F7 to F10, and two trivial moves then relabelled F7 and F8 as Level 2 without rewriting them. The panel "Level 1" holds F9 (user:3 to user:5) and F10 (user:6 to user:7). The panel "Level 2" holds F7 (order:7 to order:9) and F8 (user:1 to user:2). The tombstones order:7@15 DEL and user:1@10 DEL are still stored next to the older values they hide, because S5 was alive when this compaction ran. The MemTable and Level 0 are empty.

Trace: writes 17 to 24 finish a delete

Writes 17 to 20 flush as F11 (vase, hana, dan, the user:5 tombstone), and writes 21 to 24 flush as F12 (ali, mug, ivy, fay). They merge with Level 1's F9 and F10. No snapshot is alive now.

• 14 entries in, 9 out. carol, dave and finn are dropped: newer versions hide them from every reader.
• user:5@20 DEL and user:5@9 erin meet in this merge. No snapshot is alive, and no Level 2 file covers user:5 (F7 covers order:7 to order:9, F8 covers user:1 to user:2), so nothing older can exist below. Both are dropped: that delete is finished, and erin's bytes leave the disk.
• The output is F13, F14 and F15: one file too many for Level 1. The engine picks the file that overlaps least in the next level (RocksDB's default), so F14, which overlaps nothing in Level 2, takes a trivial move.

Synthesizing vector architecture diagram...

After write 24. Notice what stays: book, alicia and bob in Level 2 are no longer needed by anyone (S5 is gone), but they stay on disk until a later compaction reaches F7 and F8. Space comes back only when compaction touches a file. The third compaction merged F11, F12, F9 and F10 into F13, F14 and F15, and a trivial move then took F14 down to Level 2. The panel "Level 1" now holds F13 (order:1 to user:3) and F15 (user:9 only). The panel "Level 2" holds F7, F8 and F14. user:5 no longer appears anywhere: its tombstone and erin were dropped together.

Worked example: a tombstone that must stay

The tiny store never shows the other reason to keep a tombstone, so here is one more merge, also run through the reference implementation. A Level 1 file A merges with the two Level 2 files it overlaps; a snapshot at seq 30 is alive, and a Level 3 file whose key range covers only k:e holds an old k:e@5 e0.

8 entries in, 6 out. k:e@29 DEL can go only when a compaction finally merges it with the Level 3 file.

Leveled vs size-tiered, in one table

The tiny store uses leveled compaction (the default in LevelDB and RocksDB): below Level 0, each level is one sorted run of non-overlapping files, about 10 times bigger than the level above, and a file moves down by merging with only the files it overlaps in the next level. The main alternative, size-tiered compaction (Cassandra's default; RocksDB calls its version "universal"), waits for several files of similar size and merges them into one bigger file.

Why writes stall

Compaction runs in background threads. If it falls behind, Level 0 grows (every read checks every Level 0 file) and the disk fills with data waiting to be merged. So the engine slows writers on purpose, then stops them. This is backpressure (slowing the producer so that the work waiting for a slower stage cannot grow without limit), not a bug.

Synthesizing vector architecture diagram...

The numbers are RocksDB's defaults. Engines apply the same kind of limits to the bytes compaction still owes and to the number of full MemTables waiting to flush. The loop works like this: ingest causes flushes, and each flush adds a Level 0 file. When the Level 0 file count reaches 4, a compaction is scheduled, and each compaction removes files from Level 0. If compaction keeps up, the count stays near 4. If it does not, the count keeps rising: at 20 files the engine delays writes, which reduces ingest, and at 36 files it makes writes wait, which stops ingest until compaction brings the count back down.

Every byte a client writes costs "write amplification" bytes of log, flush and compaction writes, so the disk's write bandwidth sets the ceiling:

Synthesizing vector architecture diagram...

Why writes stop completely. This answers the first question of the drill The Time-Series Database That Froze on Flush. When ingest times write amplification is more than the disk can write, flushes add Level 0 files faster than compaction can merge them away. At RocksDB's defaults, with 64 MB MemTables and 120 MB/s of ingest, a flush lands about every 0.53 s (64 ÷ 120); if compaction drained nothing, Level 0 would grow from 4 files to the slowdown point of 20 in about 16 × 0.53 ≈ 8.5 s, and to the stop point of 36 about 8.5 s later. At the stop point (or when every allowed MemTable is full and waiting for a flush), the engine makes every writer wait, because letting Level 0 grow without limit would make every read check an unbounded number of files and let the disk fill. Writers resume only when compaction brings Level 0 back down, which is the "excellent latency, then a freeze of several seconds" pattern in the drill. Raising the triggers only delays the stall; the durable fixes are the three levers above.

Part 6. How files are tracked and levels are assigned

A flush adds a file; a compaction swaps several files for others. A reader must never see half of that change, a crash in the middle must not lose or duplicate data, and a read must find its one candidate file per level without opening every file. This Part is the small log and the in-memory table that do this.

The manifest is the directory of levels

The manifest is an append-only log of edits. Each edit lists files to add (with their level and key range) and files to delete, plus bookkeeping such as the last sequence number used and the oldest WAL segment still needed. The current shape of the tree is what you get by replaying every edit. One edit is one record, so a flush or a compaction takes effect in one step: before the edit is durable, the old files are the tree; after it, the new ones are.

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

The same rule as the flush covers a compaction: new files durable, then one manifest edit, then delete what it replaced.

How a file gets its level

A file's level is written in the manifest edit that adds it, and it never changes inside the file:

• A flush always writes to Level 0. The new file holds the newest data, so it must be searched before anything older. (LevelDB has one shortcut: if a flushed file overlaps nothing in the first levels, it may be placed a level or two deeper straight away.)
• A compaction from Level N writes its outputs to Level N+1. The inputs are deleted in the same edit.
• A trivial move changes only the level in the manifest, when a file overlaps nothing in the next level.

Synthesizing vector architecture diagram...

The in-memory file metadata routes every read

Opening files to find out what they hold would cost disk reads on every lookup. So the engine keeps, in memory, one small record per live file: its number, its level, its smallest and largest key, and its size. Replaying the manifest builds this table at startup (Part 9), and each new edit updates it. For the tiny store after write 24:

The two kinds of level are routed differently:

• Level 0: ranges overlap, so a read must check every Level 0 file whose range covers the key, newest first.
• Level 1 and deeper: within a level, ranges are disjoint and kept sorted, so one binary search over the files' ranges finds the single file that could hold the key, or shows that none does.

Trace (reads after write 24; Level 0 and the MemTable are empty):

Old files and readers. A reader keeps using the set of files that was current when it started, so a file deleted by a later edit stays on disk until the last reader using it finishes. That is why a scan left open for hours, or a snapshot never released, makes disk use grow while the data does not.

Part 7. B-tree vs LSM tree

An interviewer's next question is almost always "why not a B-tree?". A B-tree is a balanced tree of fixed-size pages (16 KB in MySQL's InnoDB, 8 KB in PostgreSQL) where each key lives in one leaf page, updated in place. Both designs log every write first; they differ in where the rest of the write cost goes.

Choose an LSM tree when writes dominate, keys are random, and the data is much larger than memory. Choose a B-tree when reads and range queries dominate and steady read latency matters most.

Part 8. End to end: from your code to the disk

So far "write a file" and "read a block" were single steps. In reality a request crosses several layers, each with its own cache, and knowing which layer does what explains why a read is sometimes a few microseconds and sometimes a real disk access, and why "written" is not the same as "durable".

The layers

Synthesizing vector architecture diagram...

The files in the data directory

An engine keeps a database as a directory of files. LevelDB and RocksDB name them like this (numbers come from one counter shared by all files, printed with six digits):

A write, traced down to the device

Synthesizing vector architecture diagram...

• write() only copies the bytes into the page cache and returns. The data now survives the process crashing, because the kernel still holds it, but not a power loss or a kernel crash: the kernel writes dirty pages to the device later, on its own schedule.
• fsync() or fdatasync() makes the kernel write the file's dirty pages to the device and ask the device to put them on stable media, and it returns only when that is done. fdatasync() skips metadata that is not needed to read the data back, such as the modification time, so it is usually cheaper; RocksDB uses it where available.
• Whether each write waits for the sync is a setting. RocksDB's default does not sync each write: it gives the "survives a process crash" guarantee of write() alone, and an application asks for a sync per write (or relies on group commit) when it needs to survive power loss. What fsync really guarantees, and how group commit shares it among writers, belongs to the Write-Ahead Log, fsync & Group Commit loop primitive.
• A flush is the same pattern at a larger size: many write() calls fill the page cache with the new SSTable, then one fsync of the file and one of its directory (so the file's name is durable too) before the manifest edit, as in Part 3.

A read, traced down to the device

A GET first searches the MemTables and uses the file metadata to pick candidate files, all in memory. Then, for each candidate file, it needs the filter, the index and one data block:

Synthesizing vector architecture diagram...

pread() reads from a given offset in the file without moving a shared file position, so many threads can read one SSTable at once.

Who does what

Part 9. Restarts and the boot sequence

The process crashes, or the machine reboots. The MemTables are gone, some files may be half-written, and the engine must come back with every acknowledged write and nothing else. This Part is the startup procedure, and why it takes seconds even for a terabyte of data.

The boot sequence

pseudocodeCopy
OPEN()
    1. take the LOCK file
    2. read CURRENT to find the manifest in use
    3. replay the manifest's edits in order
           -> live files per level with their key ranges,
              last sequence number, oldest WAL segment still needed
    4. delete data files the manifest does not list    -- leftovers of unfinished flushes and compactions
       delete WAL segments older than the oldest one still needed
    5. replay the WAL segments still needed into a new MemTable,
       keeping each write's original sequence number and checking each record's checksum
       stop at the first damaged record (Part 10)
    6. next seq = the highest sequence number seen + 1
    7. usually: flush that MemTable to a new Level 0 file and record it (Part 3)
    8. open for traffic
       compaction resumes in the background

OPEN is the startup procedure after a crash or a restart, and its purpose is to bring back every acknowledged write and nothing else. It takes no arguments: everything it needs is in the data directory. The LOCK file stops a second process from opening the same database, and CURRENT names the manifest in use. Replaying the manifest's edits gives the live files per level with their key ranges, the last sequence number, and the oldest WAL segment still needed. Files that the manifest does not list are leftovers of unfinished flushes and compactions and are deleted, together with WAL segments older than the oldest one still needed. The remaining WAL segments are replayed into a new MemTable with each write's original sequence number, stopping at the first damaged record, and the next sequence number is set to the highest one seen + 1 (23 after the crash after write 22 in the trace below). OPEN usually flushes that rebuilt MemTable to a new Level 0 file, then opens the store for traffic; its result is a running store with the same contents it had when the last write was acknowledged.

Synthesizing vector architecture diagram...

Trace: a crash after write 22

The tiny store crashes right after write 22 was acknowledged. What the reference implementation finds on restart:

Everything acknowledged is back, and the engine replayed two log records, not 22.

Why this is fast

• Only the unflushed tail of the log is replayed: at most a MemTable or two worth of writes (about 64 MB each at real scale), no matter how big the database is.
• SSTables are opened, not rebuilt. Their contents are already durable and immutable; the engine reads only a little metadata from each (footer, index, filter), and the key ranges come from the manifest.
• The manifest stays short, because engines start a fresh one from time to time holding just the current file list (LevelDB does it on every open). CURRENT is then switched to it by the atomic rename from Part 8.

A crash in the middle of a compaction

A crash during a flush is the table in Part 3. A crash during a compaction (say F3 to F6 being merged into F7 to F10):

Part 10. Corruption: detecting and recovering

Disks, cables, memory and software all occasionally hand back bytes that are not what was written, and a crash can leave half a record at the end of a file. The engine must notice bad bytes rather than return them as data, and there must be a way to get the data back.

Checksums on everything

Every WAL record and every SSTable block is stored with a checksum of its contents, and the reader recomputes it and compares:

• WAL records: LevelDB's log format puts a CRC32C checksum of each record's type and data in the record's header; RocksDB's WAL uses the same record format.
• SSTable blocks: each block carries a CRC32C or xxHash-family checksum in a small trailer. LevelDB uses CRC32C; RocksDB's current default for new files is XXH3, from the xxHash family, and CRC32C remains an option.

A mismatch means "these bytes are not what was written". The read reports a corruption error instead of returning wrong data.

A damaged WAL

Two very different cases look alike:

• A torn record at the tail. The process or machine died in the middle of an append. When the engine syncs the log before saying "OK", that record was never acknowledged, so recovery simply stops there and drops it. Every engine tolerates this. With the default no-sync setting (Part 8), a power loss can also lose writes at the tail that were acknowledged; that trade-off belongs to the section Durability modes: what "acknowledged" means of the Write-Ahead Log, fsync & Group Commit loop primitive.
• Damage in the middle. Records after the bad one may have been acknowledged. What the engine does is a choice, and RocksDB makes it a setting, wal_recovery_mode:

So with the default, mid-log damage does not stop startup: the database opens at the last consistent point before the damage.

A damaged SSTable

• Found on a read: the block's checksum does not match, and the read returns a corruption error for that key. RocksDB verifies checksums on reads by default.
• Found by compaction: a compaction reads every block of its input files, and RocksDB always verifies checksums while compacting. If a block is bad, the compaction fails rather than writing the damage into new files, and the engine reports a background error and stops accepting writes until someone deals with it. So compaction also works as a background check of old data.
• Found at startup: RocksDB's paranoid_checks option (on by default) makes the database refuse to open if an SSTable cannot be opened, for example because of a wrong size or a corrupt footer. Turned off, the engine opens and serves what it can from the healthy files.

Getting the data back

Cassandra as an example. Its read repair fixes replicas that disagree when a read notices the difference. A corrupt local SSTable is a different problem, handled in three steps:

• disk_failure_policy (default stop) decides what a node does on disk errors. On a single corrupt SSTable found while running, only the stricter settings stop_paranoid and die take the node out of service. Found during startup, the default stop also stops the node.
• nodetool scrub rebuilds the table's SSTables, skipping data it cannot read.
• nodetool repair then streams back from the other replicas whatever this node is missing. Use a full repair after corruption: incremental repair skips data it has already marked as repaired.

Synthesizing vector architecture diagram...

Part 11. On AWS

Our node from Part 0 ran on one gp3 volume. In AWS production, an LSM tree runs in one of two ways: inside a managed service that says publicly it uses one, or on EC2 where you run the engine and size its disk yourself. A third group of services looks like an LSM tree and isn't, and mapping those wrong is a common interview mistake. Everything below is stated only from AWS's public documentation and papers; where AWS publishes nothing about a service's storage engine, this page assumes nothing.

Managed services that use an LSM tree

Running it yourself on EC2

The other way is to run the engine yourself: RocksDB embedded in your own service, or Cassandra, ScyllaDB or HBase on EC2. Then the disk question from Part 0 is yours, with two limits to check, not one: the volume's and the instance's.

Look-alikes that are not an LSM tree

Part 12. What you've learned

Back to the 100,000 writes a second

Our node had to take 100,000 random-key writes a second on a disk that does only 3,000 small random writes a second but streams about 131 MB/s. The LSM tree solved it by never writing in place:

• Each write became a small sequential WAL append and an insert into a sorted MemTable (Part 2).
• Full MemTables became big sequential SSTable writes, flushed in an order that survives any crash (Part 3).
• Reads stayed cheap because they search newest-first and Bloom filters skip files that lack the key (Part 4), and because the manifest and in-memory file metadata send each read to one file per level (Part 6).
• Compaction merges the files in the background (Part 5). Its cost is the write amplification we met in Part 0: at 10, our 10 MB/s of new data becomes about 100 MB/s of disk writes, and compaction reads about as much again, about 200 MB/s against the baseline's 131 MB/s shared by reads and writes. So we provision more gp3 throughput (it goes up to 2,000 MiB/s) or lower the amplification; without either, compaction falls behind and the engine stalls writes (Part 5). If the data keeps growing, shard.
• Below the engine, the kernel's page cache and fsync decide what is durable (Part 8); on restart, only the unflushed log tail is replayed (Part 9); and checksums catch bad bytes before they are served (Part 10).
• On AWS, the same node needs about 300 MiB/s of provisioned gp3 throughput for its 200 MB/s, an instance whose baseline EBS bandwidth covers it (an r7g.2xlarge, not an r7g.xlarge whose burst ends after 30 minutes), and free disk for its biggest merge. If you don't run the engine yourself, Managed Service for Apache Flink and HBase on EMR run one for you; DynamoDB (a B-tree) and Keyspaces (no published engine) are not ones to reason about this way (Part 11).

The cheat card

Failure checklist

• Is ingest × write amplification inside the disk's write bandwidth, with headroom?
• Are Level 0 file count, pending compaction bytes and stall time alarmed?
• Are Bloom filters configured, and do filters and indexes fit in the block cache?
• Is there free space for the compaction policy's biggest merge?
• Do scans run over ranges full of tombstones?
• Are long-lived scans or snapshots holding old files and versions?
• Does the application sync the WAL as often as its durability promise needs?
• Is there a tested way back from corruption: backups, repair tooling or healthy replicas?

Think-first drills

Interview questions

Where to go next

• The Write-Ahead Log loop primitive, Write-Ahead Log, fsync & Group Commit: what fsync really guarantees, group commit and durability modes.
• Bloom Filters & Counting Filters: the filter structure in depth.
• Drill: The Time-Series Database That Froze on Flush, answered in Parts 5 and 7.
• Loops: the distributed key-value store (step 1.2 and compaction) and S3-like object storage (metadata compaction).