B-trees pay for fast reads with random in-place writes. Log-structured storage inverts the bet: never modify a file after writing it, append every change to the newest component, and merge components in the background. Writes become sequential and cheap, reads must consult several components, and a merge process (compaction) does the work a B-tree does at insert time. This is the design behind RocksDB, LevelDB, Cassandra, HBase, ScyllaDB and the storage layers of CockroachDB and TiKV.

Almost every operational property of these systems (write stalls, read latency tails, disk usage at twice the data size, tombstone storms, the advice to keep the WAL on a separate device) follows from a handful of mechanisms covered here, including the fact that the SSD underneath is itself log-structured.

In one minute

• An LSM tree buffers writes in an in-memory memtable (backed by a WAL), flushes it as an immutable sorted SSTable, and merges SSTables through compaction.
• Updates and deletes are appends; a delete writes a tombstone. Reads reconcile versions of a key across components by timestamp, using merge iteration over sorted sources with a min-heap.
• Leveled compaction keeps non-overlapping tables per level with 10x growth: low space and read amplification, high write amplification. Size-tiered merges similar-sized tables: low write amplification, high space amplification. Time-window groups by write time so expired data is dropped whole.
• Read, write and space amplification cannot all be minimised; the RUM conjecture says lowering two raises the third.
• An SSTable has sorted data blocks, an index block, a Bloom filter (no false negatives, about 1% false positives at 10 bits per key) and a footer. Memtables are usually skiplists, which allow lock-free concurrent inserts.
• Unordered stores skip the sorted memtable: Bitcask keeps an in-memory hash of key to file offset; WiscKey keeps keys in an LSM tree and values in a separate value log so compaction never rewrites large values.
• SSDs run a flash translation layer that is itself log-structured; stacking a filesystem journal and an LSM tree on it multiplies write amplification (log stacking). LLAMA shows the benefit of coordinated layers; open-channel and zoned SSDs let the database manage flash directly.

LSM tree structure

Components

The log-structured merge tree (O'Neil, Cheng, Gawlick and O'Neil, 1996) takes its name from log-structured filesystems, which wrote all changes sequentially, and from the merge-sort-like process that combines its components. It has three kinds of parts: the memtable, a mutable in-memory sorted structure (usually a skiplist) that receives all writes and is consulted first on reads; the write-ahead log, to which every write is appended before it reaches the memtable (recovery replays the log into a fresh memtable); and disk-resident tables, immutable sorted files that are read but never modified. Writes therefore never locate or modify existing data on disk, and readers of a table never see it change.

Two-component and multicomponent trees

The original paper described a two-component tree: an in-memory component C0 and one on-disk component C1. When C0 fills, a rolling merge takes leaf pages of C1, merges in the overlapping part of C0 and writes new C1 pages. That keeps one disk component to search but makes the merge intricate, since reads must cope with pages mid-merge. Modern engines are multicomponent: the memtable is flushed whole into a new table, many tables coexist on disk, and compaction bounds their number. The flush is one sequential file write, and reads become a search across components.

The flush

A flush is triggered by memtable size (64 MB by default in RocksDB) or time, and keeps every record readable throughout:

1. Memtable switch. A new empty memtable atomically becomes the write target; the old one becomes an immutable memtable that still serves reads.
2. Flush. Its contents are written in order into a new table file, which does not participate in reads until complete.
3. Flush finalisation. The table is registered in the manifest as readable and the immutable memtable is discarded.
4. WAL truncation. The log segment covering the flushed writes is deleted.

At any moment the current memtable serves reads and writes, a flushing memtable serves reads, the flush target serves nothing, flushed tables serve reads, and compacting tables keep serving reads until the compacted result replaces them.

Updates, deletes and lookups

Updates and tombstones

An update is a new record for the same key appended to the memtable; the older record remains in some table until compaction removes it. A delete cannot remove anything from an immutable table, and omitting the key would let the old value reappear from an older table, so a delete writes a tombstone: "key K was deleted at time T". A reader that meets a tombstone newer than any value returns not-found; compaction drops the older versions it shadows. The tombstone itself can be dropped only when no older version can survive anywhere: in leveled compaction, at the bottom level; in Cassandra, after gc_grace_seconds, which gives it time to reach every replica, since a replica that never saw it would otherwise resurrect the value during repair.

A range tombstone records deletion of a whole key range in one record. Delete-heavy workloads (queue-like tables) suffer tombstone accumulation: reads skip thousands of tombstones to find a live record.

Lookups and merge iteration

A point read checks the memtable, the immutable memtable, then tables newest to oldest, returning the first version found, with Bloom filters (below) skipping tables that cannot contain the key. A range read must merge records from every component. Because each is sorted, this is a k-way merge: open an iterator per component at the range start, put the heads into a min-heap keyed by (key, version descending), repeatedly pop the smallest, advance that iterator and push its new head. It costs O(n log k) comparisons for n records and k components and reads each component sequentially once. Compaction is the same merge iteration with its output written to a new table.

Reconciliation

When the same key appears in several components, reconciliation picks the winner using metadata carried by each record: RocksDB assigns a global sequence number per write, Cassandra uses per-cell timestamps. Newest wins, with a tombstone of equal or newer timestamp beating a value. RocksDB's merge operator lets partial updates such as counter increments be appended as deltas and combined during reconciliation instead of requiring read-modify-write.

Compaction and amplification

Why compaction is necessary

Without compaction tables accumulate forever: reads touch more of them and shadowed versions and tombstones are never reclaimed. Compaction reads several tables with merge iteration, reconciles versions, drops what tombstones permit, writes the survivors as new tables and atomically swaps inputs for outputs in the manifest; inputs are deleted once no reader references them.

Leveled compaction

Leveled compaction (LevelDB; RocksDB's default) organises tables into levels L0, L1, ..., Ln with target sizes growing by a fan-out, 10 by default. L0 holds freshly flushed tables whose ranges overlap. Each deeper level is one sorted run partitioned into fixed-size tables with non-overlapping key ranges, so a key is in at most one table per level. When a level exceeds its target, compaction merges one of its tables with the overlapping tables in the next level and writes the result there.

A point read touches at most one table per level plus the L0 tables, so read amplification is bounded and mostly filtered away by Bloom filters. Each level holds mostly unique data, so space amplification is low: with fan-out 10 about 90% of data sits in the last level and obsolete versions above add roughly 10%. The price is write amplification: a record is rewritten once per level, each time merged with about 10x as much data from the next level, so total amplification is on the order of 10 per level and 30 to 50 overall.

Size-tiered compaction

Size-tiered compaction (Cassandra's STCS, HBase's default, RocksDB's universal compaction) groups tables by size. When enough similar-sized tables exist (four by default in Cassandra) they merge into one larger table, which later meets others of its size and merges again; tables within a tier overlap freely. Each record is rewritten about once per size class, so write amplification is several times lower than leveled. But a key may exist in every table of every tier, so read amplification is higher (filters are essential), and because a merge needs inputs and output on disk at once, space amplification can approach 2x. It suits write-heavy, insert-mostly workloads with cheap disk.

Time-window compaction

Time-window compaction (Cassandra's TWCS) targets time-series data with TTLs. Tables are grouped by the window in which their records were written; within the current window they merge size-tiered, and a closed window's tables merge into one table that is never compacted again. Records in a window expire together, so the whole table is deleted when its newest TTL passes, with no rewrite and no tombstones; late-arriving data breaks the model.

Comparing strategies

Strategy	Write amplification	Read amplification	Space amplification	Best for
Leveled	High (about fan-out per level)	Low (one table per level)	Low (about 10%)	Read-heavy and update-heavy loads, limited disk
Size-tiered	Low	High (many overlapping tables)	High (up to 2x during merges)	Write-heavy, insert-mostly, cheap disk
Time-window	Low	Low for time-range queries	Low once windows expire	Time series with TTL and in-order arrival

Compaction competes with foreground traffic for I/O and CPU. If flushes outrun it, L0 fills and the engine applies write stalls (RocksDB slows and then stops writes at configurable L0 counts and pending-compaction bytes). Partitioning compaction by key range across threads is how engines keep up.

Read, write and space amplification

Any immutable-data structure pays three overheads. Read amplification: the components and I/Os a read touches beyond the ideal single read. Write amplification: bytes written to the device per byte the application wrote, because compaction rewrites records as they move between levels (a B-tree has it too: a 100-byte update dirties a 16 KB page). Space amplification: bytes on disk per logical byte, from shadowed versions, tombstones and compaction scratch space.

RUM conjecture

The RUM conjecture (Athanassoulis et al., 2016) generalises this to all access methods: every structure has a Read, an Update and a Memory (space) overhead, and minimising two forces the third up. A B-tree minimises read cost at the price of update cost (random in-place writes, splits) and space (fill-factor slack). A leveled LSM tree minimises update cost with tight space at the price of reads; a size-tiered tree pushes update cost lower by accepting more space. Bloom filters and Bε-trees move along the triangle rather than escaping it, which turns "which storage engine" into "which overhead can this workload afford".

Implementation details

Sorted string tables

An SSTable (Sorted String Table, from Bigtable) is an immutable file of records in key order, divided into data blocks (RocksDB default 4 KB before compression). Behind them sit the structures that let a reader find a key in one or two block reads: an index block mapping each data block's separator key to its offset and size, binary searched to find the one block that can contain a key (partitioned into two levels for large tables); a filter block holding the Bloom filter; a metaindex; and a fixed-size footer with the index offsets plus a magic number, read first on open. Data blocks use prefix compression with periodic restart points holding a full key, so a reader binary searches the restart points and scans a few entries. The index block is in effect a one-level B-tree built bottom-up, the bulk load of Chapter 4.

Bloom filters

A Bloom filter is a probabilistic set-membership structure with no false negatives: it answers "definitely absent" or "possibly present". It is a bit array of m bits and k hash functions; adding a key sets the k bits its hashes select, and testing checks whether all k are set. Any clear bit means the key was never added; all set means it may have been, or other keys set those bits: a false positive.

Each table carries a filter over its keys. A point lookup consults the filter before touching the table, so a key present in one of twenty tables costs one read instead of twenty. The false-positive rate with n keys is approximately (1 - e^(-kn/m))^k, minimised at k = (m/n) ln 2: about 1% at 10 bits per key with k = 7, about 0.05% at 16 bits. RocksDB defaults to 10 bits per key. Filters do not help range queries, since a range is not a key; prefix Bloom filters recover part of the benefit. Filters are built once at table write time and live in memory, a direct cost per table; deletion from a Bloom filter is impossible but never needed, because tables are immutable.

Skiplists

The memtable needs ordered iteration, fast inserts and concurrency. A skiplist (Pugh, 1990) is a sorted linked list in which each node also joins some higher-level lists that skip over fractions of the nodes below; heights are chosen randomly at insert (probability 1/2 or 1/4 per extra level), so the structure is balanced in expectation without rotations. A search starts at the top level, moves right while the next key is smaller than the target, drops a level otherwise, and reaches the bottom at or just before the target in O(log n) expected steps. Insertion is a pointer splice per level that can be made lock-free with a compare-and-swap per link, and a reader that sees a partially linked node still sees a correct sorted list at each level; LevelDB and RocksDB (InlineSkipList) use this as the default memtable; the drawback is poor cache locality.

Disk access, caching and compression

Since tables are immutable, readers need no latches on their contents. Engines rely on the OS page cache (via mmap or buffered reads) or keep their own block cache of uncompressed blocks (RocksDB does both). A compaction must not unlink a file a reader is iterating, so table objects are reference counted and old files are removed when their count reaches zero after the manifest swap. Because a table is written once and read by block, records may span block boundaries, and the block is the unit of I/O and of compression.

Compression is per block, applied during flush and compaction when the block is complete. Compressed blocks have variable sizes, so the index records each block's compressed offset and length; a reader fetches exactly that range, decompresses into the block cache and searches. Blocks are never updated, so no space is reserved for growth, which makes compression far simpler than for in-place B-tree pages (Chapter 4). RocksDB lets each level choose its codec: a fast one (LZ4, Snappy) for frequently rewritten upper levels, a strong one (zstd) for the bottom level holding 90% of the data.

Concurrency in LSM trees

Immutability reduces LSM concurrency to a few switch points. The memtable switch must be atomic with respect to writers, and writers holding the old memtable must finish before the flush. Flush finalisation publishes the new table and retires the immutable memtable, kept alive by reference counts for in-flight reads. WAL truncation happens only after the flush is durable, or a crash would lose writes that exist in neither log nor table. Compaction publication swaps the manifest atomically; readers holding the old set continue on the old files until their counts drop to zero.

Unordered LSM storage

Bitcask

Bitcask (Basho, 2010; Riak's default backend) has no memtable. A write appends the record (key, value, timestamp, CRC) to the current log file and updates the keydir, an in-memory hash from key to (file ID, offset, size, timestamp). A read is one hash lookup and one seek; the keydir always points at the newest record, so no reconciliation is needed. Background merging copies live records into a new file, updates the keydir and deletes the old file, also writing hint files (key-to-offset listings) that rebuild the keydir at startup without scanning data. Writes are purely sequential and point reads are one I/O, but every key must fit in memory and there are no range queries.

WiscKey and key-value separation

WiscKey (Lu et al., FAST 2016) observed that compaction cost is dominated by rewriting values, typically much larger than keys, and that SSDs make random value reads cheap enough. It keeps the LSM tree for keys, each entry holding a small pointer into a separate append-only value log (vLog). Compaction moves keys and pointers, not values, so write amplification drops by an order of magnitude for large values and the small tree fits in cache. The costs: a range scan fetches values from random vLog positions, so WiscKey prefetches them in parallel; the vLog needs its own garbage collection, which checks each value at the tail against the tree for liveness and re-appends survivors; and crash consistency must span both structures. Key-value separation is now standard, with a size threshold keeping small values inline: Badger, Titan (TiKV) and RocksDB's BlobDB.

Log stacking

SSD internals and the flash translation layer

NAND flash cannot be overwritten in place: a page (4 to 16 KB) can be written only after the erase block containing it (hundreds of pages) is erased, and each block survives a limited number of erases. The controller's flash translation layer (FTL) maps logical addresses to physical pages, writes every incoming page to a fresh location (out-of-place, like a log), marks the old page stale, and runs garbage collection that copies live pages out of mostly stale blocks and erases them, with wear levelling and over-provisioned capacity for headroom. The SSD is a log-structured store with its own compaction and write amplification: 1 GB of random 4 KB writes may erase and rewrite several gigabytes of flash. Log-structured databases suit it, writing large sequential chunks that become stale together when a table is compacted away.

Filesystem logging and stacked write amplification

The layers between database and flash do not know about each other: an LSM engine writes files, a journaling filesystem (ext4, or a log-structured one such as F2FS) places them on logical blocks, and the FTL places those on flash.

Each layer adds its own log and garbage collection. Record sizes at one layer rarely align with the block boundaries of the one below, so a logical append becomes partial-page writes and read-modify-write at the FTL. Interleaving unrelated streams (WAL appends, flushes, compaction output, filesystem metadata) in the same erase blocks means they become stale at different times and the FTL must copy live pages around; data the LSM tree already moved during compaction is moved again. The result is stacked write amplification, roughly the product of each layer's. This is why vendors recommend a separate device for the WAL, why engines use O_DIRECT and large aligned writes, and why journaling of file data is usually disabled under a database.

LLAMA and mindful stacking

The fix is not to abandon layering but to make layers aware of each other. LLAMA (Latch-free, Log-structured, Access-Method Aware; Levandoski, Lomet and Sengupta, 2013) is the storage subsystem built for the Bw-tree (Chapter 6). It provides the mapping table and page abstraction, with pages living in memory and in a log-structured flash store, and flushes deltas rather than whole pages, so storage writes mirror the access method's incremental updates. Its garbage collection, which relocates live pages from the log's tail, consolidates a logical page's scattered deltas into one contiguous image as it goes, so the storage layer's cleaning does useful work for the access method instead of fighting it. The lesson is mindful stacking: layered logs are fine, even beneficial, when each layer knows the other's write granularity and logical units.

Open-channel SSDs

The radical alternative removes the FTL's independent judgement. An open-channel SSD exposes its geometry (channels, parallel units, blocks, pages) and lets host software decide placement, garbage collection and wear levelling. A database can place a whole SSTable in erase blocks of its own, so compacting it away frees the blocks with no copying, and can physically separate the WAL stream from the table stream. The productised descendant is the zoned namespace (ZNS) SSD, divided into zones written sequentially and reset as a unit, exactly how an LSM engine writes files; RocksDB's ZenFS plugin targets it. Compaction becomes the only garbage collector, eliminating a layer of write amplification at the cost of owning responsibilities the firmware used to have.

Design trade-offs

Decision	Options	Trade-off
B-tree vs LSM	In-place B-tree; leveled LSM; tiered LSM	B-tree: lowest read cost, random writes. Leveled: sequential writes, low space, high write amplification. Tiered: lowest write amplification, highest space and read amplification
Compaction strategy	Leveled, size-tiered, time-window	Choose by which amplification the workload can afford
Key-value separation	Inline values vs value log	Value log cuts compaction write amplification for large values but randomises range scans and adds a second GC
Storage interface	Conventional, open-channel, ZNS	Conventional is portable; host-managed flash removes a GC layer but moves wear and placement into the engine

Interview angle

• Why are LSM trees good for write-heavy workloads, and what is the catch? Writes are a memtable insert plus a sequential WAL append; no disk page is modified in place, so throughput approaches sequential bandwidth. The work is deferred to compaction, which rewrites each record several times, and reads must consult several components.

• How does a delete work when files are immutable, and why can deleted data come back? A delete appends a tombstone shadowing older versions. If the tombstone is dropped before every older version is gone (in a distributed store, before all replicas received it), an older value is no longer shadowed and the key resurrects. That is why Cassandra keeps tombstones for gc_grace_seconds and requires repair within that window.

• Compare leveled and size-tiered compaction for 90% writes to a 5 TB dataset on a 6 TB disk. Size-tiered has the lowest write amplification but space amplification approaching 2x during large merges, which does not fit. Leveled keeps space near 1.1x but rewrites each record about 10x per level. The realistic answer is leveled with a plan for the compaction I/O, or more disk.

• How do you size a Bloom filter, and what does it not help with? Choose bits per key for the target false-positive rate and set k about (m/n) ln 2: 10 bits per key gives roughly 1% with k = 7, 16 bits roughly 0.05%. Filters answer single-key membership only; range scans still touch every overlapping table unless a prefix filter applies.

• What is the RUM conjecture, and where do B-trees and LSM trees sit? Read, update and memory overheads cannot all be minimised; improving two worsens the third. B-trees minimise read overhead and pay in update cost and space slack; leveled LSM trees minimise update cost with tight space and pay in reads; tiered LSM trees push update cost lower by accepting more space.

• Explain key-value separation and when it backfires. Keys and small pointers live in the LSM tree, values in an append-only log, so compaction rewrites only the small tree. It backfires with small values and scan-heavy workloads (values come from random positions), and it adds a value-log garbage collector that must consult the tree for liveness.

Pitfalls and misconceptions

• "LSM trees do not need a write-ahead log." The tables are durable but the memtable is not; the WAL recovers it. It is simpler than a B-tree's log but no less necessary.
• "A delete frees space." It adds a tombstone and temporarily increases space. Space returns only when compaction drops the shadowed versions and, later, the tombstone.
• "A Bloom filter can return a false negative under load." Never. The only error is a false positive; a negative is definitive.
• "Leveled compaction has the lowest write amplification because it is the default." It has the lowest space and read amplification; its write amplification is the highest of the common strategies.
• "Sequential writes on an SSD are only a filesystem concern." The FTL does out-of-place writes and garbage collection regardless; write patterns that let whole erase blocks become stale together reduce the device's own write amplification and wear.

Key terms

Term	Meaning
LSM tree	Log-structured merge tree: buffered writes, immutable sorted disk components, background merging
SSTable	Immutable sorted file with data blocks, index block, filter block and footer
Tombstone	Record marking a key or range as deleted at a given time
Compaction	Merging tables, dropping shadowed versions and tombstones, writing new tables
Leveled compaction	Levels of non-overlapping tables growing by a fan-out; low read and space amplification
Size-tiered compaction	Merging similar-sized tables; low write amplification, high space amplification
Read / write / space amplification	Extra reads per lookup; extra bytes written per byte stored; extra bytes on disk per logical byte
RUM conjecture	Read, update and memory overheads cannot all be minimised together
Bloom filter	Bit array with k hashes; no false negatives, tunable false positives
WiscKey / value log	Key-value separation: keys and pointers in the LSM tree, values in an append-only log
Flash translation layer	SSD firmware mapping logical addresses to flash pages with out-of-place writes, GC and wear levelling

Further reading

• Database Internals, Chapter 7 ("Log-Structured Storage"); Chapter 6 for the Bw-tree that LLAMA serves and Chapter 4 for B-tree compression and bulk loading.
• Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil, "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996.
• Lanyue Lu et al., "WiscKey: Separating Keys from Values in SSD-Conscious Storage", FAST 2016: https://www.usenix.org/conference/fast16/technical-sessions/presentation/lu
• Manos Athanassoulis et al., "Designing Access Methods: The RUM Conjecture", EDBT 2016.
• Justin Levandoski, David Lomet and Sudipta Sengupta, "LLAMA: A Cache/Storage Subsystem for Modern Hardware", VLDB 2013.
• RocksDB Wiki (Leveled Compaction, Universal Compaction, Bloom Filter): https://github.com/facebook/rocksdb/wiki
• Chen Luo and Michael J. Carey, "LSM-based Storage Techniques: A Survey", VLDB Journal 2020: https://arxiv.org/abs/1812.07527