The LSM Tree — The Ledger<br>Contents → In this chapter The LSM Tree<br>01 Write Path<br>02 Deferred Organization<br>03 The LSM Tree<br>04 Origin<br>05 Read and Write Costs<br>06 The Moving Parts<br>07 Write<br>08 Flush<br>09 Read<br>10 Deletion<br>11 Compaction<br>12 Compaction Backlog<br>13 Tuning<br>14 Performance Trade-offs<br>15 Leveled<br>16 Tiered<br>17 Bloom Filters<br>18 Range Scans<br>19 Applications<br>20 Version Ordering<br>21 Summary<br>Sources & further reading

loading…

Write Path<br>Updating a B-tree may modify pages at several locations in a file. These random writes are expensive on disks and still have latency and write-amplification costs on SSDs.<br>An LSM tree instead batches updates and writes them sequentially before organizing them in the background.

Deferred Organization<br>The on-disk index is not rearranged after every write. Updates accumulate in memory, are appended to a durability log, and are flushed to disk in sorted batches.<br>Reads check recent data before older files. Background compaction merges the files and limits the number of places a read must inspect.

The LSM Tree<br>A log-structured merge tree is not a tree of pointers. It is a pipeline: a mutable in-memory table, immutable sorted files on disk, and compaction jobs that merge those files before they become unmanageable.<br>LevelDB, RocksDB, Cassandra, HBase, and Bigtable all use this pattern to turn scattered updates into long sequential writes.

Origin<br>Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil published the LSM-tree paper in 1996. It addressed indexed files with high insertion rates, where conventional indexes perform many small random updates.<br>Buffering updates and merging them in sorted order converts those updates into longer sequential writes.

Read and Write Costs<br>Appending updates without reorganization increases the number of files that reads must inspect. Reorganizing after every update increases foreground write latency.<br>An LSM tree balances these costs by flushing updates quickly and compacting the resulting files in the background.

The Moving Parts<br>A write first enters a write-ahead log, which can be replayed after a crash. It then goes into an in-memory sorted structure called the memtable — a skip list in LevelDB.<br>Once full, the memtable becomes an SSTable : a sorted file of key-value entries with an index and usually a Bloom filter. Compaction gradually folds newer files into older, larger levels.

Write<br>Put key 42 with value “blue.” The database appends the update to the log, inserts it into the memtable, and returns once durability requirements are satisfied.<br>No disk page is located and rewritten. If key 42 already exists in an older SSTable, the new value simply shadows it. The newest version sits closest to the top of the structure, and compaction removes the stale copy later.

Flush<br>When the memtable reaches its size limit it freezes, and a fresh memtable begins accepting writes. The frozen one is written to disk as a sorted file.<br>That flush is one sequential pass. The memtable was already sorted, so the file is emitted in key order. Many tiny updates have become one large sorted run.

Read<br>Reads proceed from newer components to older ones: the active memtable, immutable memtables awaiting flush, and then successive disk levels.<br>For a point lookup, the first matching entry is the current version. If a file’s Bloom filter reports that the key is absent, the engine skips that file without a disk read.

Deletion<br>A delete cannot immediately remove every older copy because the key may appear in several immutable files.<br>The LSM tree writes a tombstone , which is a deletion marker with a sequence number. Reads use the newest entry for the key. Compaction later removes the tombstone and older values when they are no longer visible.

Compaction<br>Compaction selects overlapping sorted files, reads their entries in key order, merges them, discards safely hidden versions, and writes new files into a lower level.<br>This process reduces the number of files involved in reads, reclaims space from old versions and tombstones, and keeps each level within its configured size.

Compaction Backlog<br>Foreground write performance depends on sufficient background compaction capacity.<br>If compaction falls behind, reads inspect more files, old versions occupy more disk space, and writes may stall because there is insufficient space for new flushes. Compaction scheduling is therefore a major part of an LSM-tree implementation.

Tuning<br>The knobs are level sizes, file sizes, Bloom filter bits, compression, and compaction policy. Enlarge the memtable and flushes become rarer, but recovery time and memory pressure rise. Increase the fanout between levels and writes get cheaper while reads search more data.<br>No setting is universally right. Point reads, range scans, write bursts, delete-heavy workloads, SSD behaviour, cache size, and latency targets each pull the knobs a different way.

Performance Trade-offs<br>Compared with a B-tree, an LSM tree generally handles write bursts better and...