LSM Trees: Why Some Engines Favour Writes

Take an event table receiving 400,000 inserts per second with keys that are not monotonic — (device_id, ts) across two million devices, or UUIDs. In a B+ tree each insert lands on a different leaf page. The buffer pool absorbs the change in memory, but at the next checkpoint every dirtied page must be written back: an 8 KB page write for each 100-byte row that touched it. If the working set of leaves is larger than RAM, the descent itself needs a random read first. The engine is limited by random IOPS, and random IOPS are the scarcest thing a disk has.

Sequential writes are a different order of magnitude: an NVMe SSD sustains a few GB/s sequentially but only a few hundred thousand random 4 KB operations per second; a hard disk manages ~150 MB/s sequential and ~100 random operations. The design question is therefore not "how do we make random writes faster?" but "how do we stop doing random writes at all?".

Step one: append every write to a log. That alone makes writes sequential and durable, but a read would have to scan the whole log. Step two: keep the latest value per key in a sorted in-memory structure — the memtable — so reads of recent data are a map lookup, and so the data can be written out *sorted*. Step three: when the memtable reaches a threshold (64 MB in RocksDB by default), write it to disk as one SSTable (Sorted String Table): an immutable file of key/value pairs in key order, with an index and a bloom filter. Step four: because every flush produces another file, and the same key may now sit in several, run compaction in the background: merge files, keep the newest version of each key, drop the rest.

The memtable needs ordered iteration and cheap concurrent inserts. RocksDB and LevelDB use a Skip List: O(log n) insert, lock-free readers, in-order traversal for the flush. A Red-Black Tree works equally well for a single writer. A hash map would not — it cannot be flushed in sorted order.

A point read checks the memtable, then each level-0 file from newest to oldest, then one file per deeper level (their ranges do not overlap, so at most one can hold the key). The first version found is the answer, because anything older was overwritten. Without help this would be a block read per file; the Bloom Filters: Skipping Files That Cannot Contain the Key lesson shows how a few bits per key let the reader skip almost every file that does not hold the key, and SSTables: The Immutable Sorted File shows how a sparse index turns the remaining candidates into one block read each.

Range scans get no such help. WHERE ts BETWEEN a AND b must open every file whose range intersects [a, b] and merge their sorted streams, skipping tombstones. This is the read cost an LSM engine cannot hide, and the reason Storage Engine Comparison: B+ Tree vs LSM Tree gives the B+ tree the range-scan column.

An SSTable is immutable, so DELETE k cannot remove k from any file. Instead it writes a tombstone: a version of k whose value means "deleted", with a fresh sequence number. Reads that find the tombstone first report "not found" and stop, so older values below are hidden. Compaction drops the older values when it merges them with the tombstone — but the tombstone itself can only be dropped once no file below it can still contain the key, which in practice means when it reaches the bottom level.

This has a famous consequence: a workload that deletes heavily grows for a while before it shrinks, and a range scan over a heavily deleted region reads tombstones for rows that no longer exist. Cassandra's gc_grace_seconds (default ten days) is exactly the tombstone-retention window, and "tombstone overwhelming" warnings are the failure mode.

LevelDB (Google) and RocksDB (Meta's fork) are embedded LSM key-value libraries; RocksDB is the storage layer under MyRocks, CockroachDB (until Pebble), TiKV, Kafka Streams state stores and many others. Apache Cassandra and ScyllaDB are LSM engines by design with size-tiered compaction by default. HBase stores memstores and HFiles on HDFS with the same shape. WiredTiger (MongoDB's engine) implements both a B+ tree and an LSM layout.

Redis is not an LSM tree — data lives in memory in hash tables and skip lists — but its durability options rhyme with this lesson: the AOF is an append-only log replayed at start-up, RDB is a periodic snapshot, and AOF rewrite is a compaction of the log. See Redis: Data Structures, Not a Cache for the in-memory side.