Log-Structured Merge-Trees (LSM-Trees) (RocksDB, Cassandra)

When write throughput reaches hundreds of thousands of operations per second, traditional B-Trees collapse under the weight of random disk writes and high write amplification.

To solve this, modern distributed databases (Apache Cassandra, RocksDB, Google Bigtable, CockroachDB, TiKV, ScyllaDB) replace page-based storage with Log-Structured Merge-Trees (LSM-Trees).

By converting all inserts, updates, and deletes into sequential in-memory writes and immutable disk flushes, LSM-Trees deliver unparalleled write performance.

1. The LSM-Tree Write Path: Zero Random I/O

An LSM-Tree writes data in three sequential stages:

2. Anatomy of an SSTable (Sorted String Table)

An SSTable is an immutable, append-only file stored on disk, structured into sequential blocks:

Why Immutability Matters:

• SSTables are never modified in place.
• Concurrency requires zero read locks: Readers can scan an SSTable concurrently without blocking writer threads.
• Deletions are implemented as Tombstones (an explicit delete record appended to the log).

3. The Read Path and Bloom Filters

Because a key might reside in the active MemTable, an immutable MemTable, or any of dozens of SSTables across multiple levels, reading data requires searching multiple locations.

4. The Mathematics of Bloom Filters

A Bloom Filter is a space-efficient probabilistic data structure that answers set membership queries with zero false negatives:

• It can answer: "Key definitely does NOT exist" ($⟹$ skip disk read).
• Or: "Key PROBABLY exists" ($⟹$ perform disk read).

The Math:

For a dataset of $n$ keys with a bit array of size $m$ and $k$ independent hash functions:

$\text{False Positive Probability }p\approx {\left(1-e^{-kn/m}\right)}^k$

$\text{Optimal Number of Hashes }k=\frac{m}{n}\ln (2)\approx 0.693\cdot \frac{m}{n}$

With only 10 bits per key in RAM (just $1.2\text{MB}$ of RAM for 1,000,000 keys), 99.2% of non-existent key lookups are rejected instantly without touching disk!

5. Compaction: Leveled vs Size-Tiered

Because SSTables accumulate continuously on disk, background Compaction threads merge overlapping SSTables, discard overwritten historical versions, and purge deleted tombstones.

6. The RUM Conjecture

In 2016, researchers at Harvard formulated the RUM Conjecture:

$\text{A storage engine can optimize for at most TWO of the following: Read Overhead (R), Update Overhead (U), or Memory Overhead (M).}$

• B+ Trees: Optimize Read Performance at the cost of Update Overhead (high write amplification).
• LSM-Trees: Optimize Update Performance at the cost of Read Overhead (mitigated by Bloom filters).

7. Production Failure Postmortem: Write Stalls Under Compaction Backpressure

Incident Overview:

In 2021, a high-throughput gaming analytics platform running RocksDB experienced abrupt $5\text{-second}$ client write freezes, causing edge ingest gateways to drop millions of telemetry events.

What Happened:

1. A viral marketing campaign doubled ingestion traffic to $180,000\text{ writes/sec}$.
2. MemTables flushed to Level 0 faster than the single background compaction thread could merge them into Level 1.
3. Level 0 SSTable count exceeded the safety threshold of level0_slowdown_writes_trigger = 20.
4. RocksDB automatically engaged Write Stalls, deliberately throttling incoming client writes by injecting sleep delays to prevent out-of-memory disk exhaustion.

Remediation:

• Increased background compaction thread worker pool from 1 thread to 8 dedicated NVMe worker threads (max_background_compactions = 8).
• Partitioned the storage engine across 4 independent RocksDB column families to eliminate thread contention.

8. Landmark Capstone #4: Build an LSM-Tree Storage Engine ⚔️

Put your storage engine fundamentals to the test by implementing a complete Log-Structured Merge-Tree from scratch:

👉 Launch Capstone: Build an LSM-Tree Storage Engine

• Supported Languages: TypeScript & Python 3
• Challenge Focus:
  • Implement an in-memory MemTable with threshold flushing.
  • Generate sorted immutable SSTables with binary-searchable block indexes.
  • Implement a Bloom Filter with bitwise hashing to eliminate redundant disk lookups.
  • Execute a multi-way Compaction Merge reconciling tombstones and key overwrites.

9. Chapter Summary & LSM-Tree Storage Invariants