A B-tree updates a page where the row lives, which means a random-key write pattern turns into a random-page write pattern. An LSM tree refuses that trade: it appends, and rewrites in bulk later. Everything else about the design — the memtable, the bloom filters, the compaction policy — follows from that one refusal.

The measurement that motivates it is easy to reproduce. Applying the same 200,000 in-place updates to the same 200,000-row sqlite table, with a 2 MB page cache and a durable commit, takes 0.17 s when the keys arrive in sorted order and 2.60 s when they arrive shuffled: 15.25x, on identical rows and identical page counts. The extra time is scattered page rewrites and the cache evictions they cause.

Buffer, flush, merge

Writes go to a write-ahead log for durability and into an in-memory table for speed. When the memtable fills it is flushed as one immutable sorted run; in RocksDB that run lands in level 0, and every level below it holds exactly one sorted run whose size target grows exponentially. A workload that is random at the key level therefore becomes entirely sequential at the disk level, and the write path is a large ordered append no matter what the application is doing.

The bill for that is paid on the read path. A point lookup has to consider each level, so the engine keeps a per-run bloom filter to answer “not here” cheaply. In a 400,000-write simulation over 60,000 distinct keys, 20,000 point lookups probed a mean of 8.9 runs but actually read only 0.6 of them: bloom filters rejected 166,622 of 177,937 probes, 93.6%. Absent-key lookups still probed 11.0 runs each before returning empty — a bloom filter makes a miss cheap, and does nothing at all for a hit.

Compaction is the tax

The write path is cheap because nothing is ever updated in place; the price is that every logical value gets written more than once. In the same simulation, 56,000,000 logical bytes became 149,031,040 physical bytes across 54 flushes and 4 compactions — a write amplification of 2.66x, and that is with a deliberately generous compaction budget.

RocksDB names the dial explicitly. Level-style compaction merges one file in Ln with all its overlapping files in Ln+1, which minimises the files involved and therefore optimises space amplification. Universal-style compaction merges many files and levels at once, which lowers write amplification but raises space and read amplification. There is no setting that lowers all three; you are choosing which one your workload can afford.

When it breaks

The first failure is compaction falling behind the write rate. Compaction throughput is a hard floor: with a 64 MiB/s ingest and a 2.66x write amplification, the background has to move 170 MiB/s just to stand still. Run it at 145 MiB/s and the backlog is 25.5 MiB/s, which accumulates 91,973 memtable-sized runs per hour and fills a 1 TiB disk in 11.4 hours. Measured against 2,000 level-0 runs, a point lookup probes 775 runs on average instead of 8.9. Reads degrade, then disk fills, and both symptoms trace to the same number.

The second failure is the tombstone-heavy workload. A delete is not a removal, it is a write of a tombstone that must outlive the value it hides. Inserting 40,000 keys and then deleting all of them wrote 12,160,000 bytes for 5,720,000 bytes of live data, and left 40,000 tombstones holding 5,600,000 bytes of dead payload — space amplification of 0.98x the live data size, on data that no longer exists. Lookups for deleted keys still probed runs to discover the absence. Only a compaction that reaches the tombstone reclaims the space, so a workload that deletes as fast as it writes keeps paying for both.

Check it quickly

Measure the B-tree cost you are avoiding, then read the compaction counters:

sqlite3 kv.db "PRAGMA cache_size=-2000; PRAGMA synchronous=FULL; PRAGMA journal_mode=WAL;"
sqlite3 kv.db "SELECT count(*) FROM kv; PRAGMA page_count;"
ldb --db=./db stats | sed -n '/Compaction Stats/,/^$/p'
ldb --db=./db stats | grep -i stall
python3 -c "import rocksdb; d=rocksdb.DB('./db'); print(d.get_property(b'rocksdb.num-files-at-level0'))"

Insert the same keys twice, once sorted and once shuffled, and the first two lines give you the baseline gap: same row count, same page count, very different wall time. The Compaction Stats block reports W-Amp and R-Amp per level — write amplification that climbs as the dataset grows means the fanout is too small, and read amplification that climbs means compaction is behind. Any stall count above zero is the debt signal, and level-0 files sitting near the compaction trigger means the background is only just keeping up.

Sources