LSM-Trees and Write-Optimized Storage

Every insert into a B-tree is a random write: find the right leaf page (random read), modify it (random write), update WAL (sequential write). Under high write load, that random leaf access becomes the bottleneck. Worse, page splits propagate upward, dirtying multiple pages per insert.

Write amplification measures how many bytes hit disk per byte of user data. A B-tree under heavy random-insert load can exhibit 10–30x write amplification just from splits and WAL. On flash storage, write amplification directly shortens SSD lifespan and saturates the write bandwidth.

Log-Structured Merge-trees (LSM-trees) eliminate the random-write problem by converting all writes into sequential appends — at the cost of more complex reads and background compaction.

An LSM-tree never writes a user record directly to disk. Every write goes into the memtable — an in-memory sorted data structure (typically a red-black tree or skip list) that accepts random insertions in $O(\log n)$ time while maintaining sort order.

The memtable is also backed by a WAL on disk (append-only), so writes are durable immediately: the client gets a confirmation after the WAL append, not after the memtable is flushed. If the process crashes, the WAL replays into a fresh memtable on startup.

Write path:
  client write
    -> append to WAL (sequential disk write, fast)
    -> insert into memtable (in-memory, O(log n))
    -> ACK to client

The memtable grows until it reaches a size threshold (RocksDB default: 64 MB), then it is frozen and a new, empty memtable takes over.

When the memtable is full, it is flushed to disk as an SSTable (Sorted String Table) — a file of key-value pairs in sorted key order, written sequentially in a single pass. SSTables are immutable once written; updates and deletes are represented as new entries (tombstones for deletes).

An SSTable on disk has two sections:

• Data blocks: compressed key-value pairs, typically 4–64 KB each.
• Index block: sparse index mapping every Nth key to its block offset — allows binary search within the SSTable.

# RocksDB-style SSTable read (pseudocode)
def lookup(key, sstable):
    block_offset = sstable.index.search(key)  # binary search in index
    block = sstable.read_block(block_offset)   # one sequential disk read
    return block.search(key)                   # binary search within block

Immutability is key: concurrent reads need no locks, and the OS page cache naturally caches hot SSTables.

Without compaction, the number of SSTables grows without bound, and a point lookup must search every SSTable from newest to oldest — $O(N)$ disk reads. Compaction merges SSTables: read two (or more) SSTables, merge-sort their entries (resolving overwrites and tombstones), write one new SSTable, delete the old ones.

Two dominant strategies:

Size-tiered compaction: accumulate N SSTables of similar size, then merge them into one larger SSTable. Writes are cheap; reads and space amplification can be high (multiple copies of a key live in different tiers simultaneously).

Leveled compaction (RocksDB default): SSTables are organized into levels L0–L6. Each level is 10x larger than the previous. Key ranges in L1+ are non-overlapping within a level. Reads only need to check 1 SSTable per level after L0. Space amplification ~1.1x; write amplification ~10–30x.

Even with leveled compaction, a point lookup for a non-existent key would have to check every level. Bloom filters prevent this: each SSTable carries a compact probabilistic filter (typically 10 bits per key) that answers "is key $k$ definitely NOT in this SSTable?" with zero false negatives.

# Bloom filter sketch
import mmh3, bitarray

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.bits = bitarray.bitarray(size)
        self.k = num_hashes
    def add(self, key):
        for i in range(self.k):
            self.bits[mmh3.hash(key, i) % len(self.bits)] = 1
    def maybe_contains(self, key):
        return all(self.bits[mmh3.hash(key, i) % len(self.bits)] for i in range(self.k))

With a 1% false positive rate, a lookup for a missing key reads zero SSTable blocks in 99% of cases. RocksDB stores bloom filters in block cache; they're typically sub-millisecond to check.

The three competing metrics every LSM-tree design trades off:

Write amplification (WA): bytes written to disk / bytes of user data. Compaction re-writes data repeatedly. Leveled compaction: WA ~10–30x. Size-tiered: WA ~5–10x but with higher space amplification.

Read amplification (RA): disk reads per point lookup. Leveled: RA ~level count (6–7) plus bloom filter checks. Size-tiered: RA can be $O(N)$ without bloom filters.

Space amplification (SA): disk bytes used / bytes of live data. Size-tiered: up to 2x during compaction (old + new SSTable coexist). Leveled: ~1.1x steady-state.

RocksDB exposes all three via db.GetProperty('rocksdb.stats'). Tuning compaction style, level multiplier, and bloom filter bits per key is the primary lever for balancing these.

Neither is universally superior. Pick based on your workload:

Surprise: at high write rates, B-tree and leveled LSM have similar write amplification — but LSM's amplification is sequential, while B-tree's is random, making LSM far more SSD-friendly.

LSM-trees power most of the write-intensive systems you use:

• RocksDB (Meta): the reference LSM implementation, embedded in MySQL (MyRocks), TiKV, CockroachDB.
• Cassandra/ScyllaDB: wide-column store with size-tiered compaction, tunable bloom filter FP rate.
• LevelDB (Google): original open-source LSM; basis for RocksDB.
• ClickHouse MergeTree: LSM-inspired, with parts (SSTables) merged in the background.

Common production gotchas:

• Compaction falling behind: if write rate exceeds compaction throughput, L0 SSTable count grows, reads degrade, and eventually writes are throttled (L0_slowdown_writes_trigger). Monitor rocksdb.num-files-at-level0.
• Tombstone accumulation: deleted keys linger until compaction reaches their level. A delete-heavy workload on a rarely-compacted level can waste significant disk space.