Distributed Storage Engines: LSM-Trees (Cassandra/RocksDB) vs B+ Trees (Spanner/CockroachDB)

Why You Need This in Real Life

When designing a time-series telemetry platform processing 500,000 write operations per second, using a traditional B+ Tree storage engine (like MySQL InnoDB) creates a severe disk I/O bottleneck.

Because B+ Trees write data by overwriting 16KB disk pages in place, random write workloads trigger continuous random disk page fetches and heavy write amplification (writing 16KB to disk just to update a 50-byte record).

Under heavy write volumes, disk throughput saturates, and database write latencies spike from 2ms to 800ms.

Log-Structured Merge-Trees (LSM-Trees) were created to transform random disk write workloads into ultra-fast sequential disk appends.

Understanding the internal mechanics of LSM-Trees versus B+ Trees is essential for choosing the right storage engine for high-throughput write workloads versus read-heavy analytical databases.

Part 1: B+ Tree Architecture (In-Place Updates)

B+ Trees structure data into fixed-size disk pages (typically 4KB to 16KB) organized in a balanced tree.

                           [ Root Page ]
                          /             \
             [ Internal Page ]       [ Internal Page ]
             /               \       /               \
       [ Leaf Page A ]  [ Leaf Page B ] [ Leaf Page C ]  [ Leaf Page D ]
       (Contains sorted key-value data tuples)

Read vs Write Mechanics

Reads: Fast $\mathcal{O}(\log N)$ page traversal. Index pages guide the disk head directly to the exact target leaf page.
Writes: Must locate the specific leaf page on disk, read it into memory, modify the tuple, and write the 16KB page back to disk (in-place update). If the page is full, it triggers an expensive page split.

Part 2: LSM-Tree Architecture (Append-Only Out-of-Place Updates)

LSM-Trees (used in Apache Cassandra, RocksDB, LevelDB, and Google Bigtable) decouple write operations from disk layout using three primary components:

1. Write Path
Client Write ---> WAL (Disk Append) ---> MemTable (In-Memory ConcurrentSkipListMap)
                                                  |
                                                  | Flushes when full
                                                  v
                                         SSTable Level 0 (Immutable Disk Files)
                                         SSTable Level 1
                                         SSTable Level 2 (Compacted via Merge Sort)

The 4 LSM-Tree Components

Write-Ahead Log (WAL): Sequential append to disk for crash recovery durability.
MemTable: An in-memory sorted structure (e.g., SkipList). All writes hit the MemTable in memory ( $\mathcal{O}(\log N)$ RAM speed).
SSTable (Sorted String Table): When MemTable exceeds size threshold (e.g., 64MB), it is flushed to disk as an immutable sorted file (sequential I/O).
Compaction Engine: Background threads continuously merge-sort smaller SSTable files into larger, consolidated SSTable levels to remove deleted/overwritten records.

Part 3: Read Acceleration with Bloom Filters

Because SSTables are immutable on disk, a record’s latest value could reside in the MemTable or any of 10 SSTable files. Reading a key without optimization would require checking every SSTable file on disk!

LSM-Trees solve read latency using Bloom Filters:

Client Read Key "user_42"
       |
       v
Check Bloom Filter for SSTable_1 ---> Returns FALSE! (Skip disk read!)
Check Bloom Filter for SSTable_2 ---> Returns TRUE!  ---> Read SSTable_2 from disk!

A Bloom Filter is a space-efficient probabilistic data structure that tests set membership:

If Bloom Filter returns FALSE: Key is 100% guaranteed NOT to be in the SSTable. (Saves disk I/O!).
If Bloom Filter returns TRUE: Key might be in the SSTable (requires disk check).

Part 4: Storage Engine Comparison Matrix

Dimension	B+ Tree (InnoDB, Spanner)	LSM-Tree (Cassandra, RocksDB)
Primary Workload	Read-Heavy ( $\sim 70\%$ reads / $30\%$ writes).	Write-Heavy ( $80\%+$ writes / $20\%$ reads).
Write Type	In-Place updates (Random disk I/O).	Append-only flushes (Sequential disk I/O).
Write Amplification	High (Writes 16KB page for small updates).	Lower during writes; higher during Compaction.
Read Amplification	Very Low ( $\mathcal{O}(1)$ page lookup via index).	Higher (May check Bloom Filters & multiple SSTables).
Space Amplification	Low (Dead tuples cleaned up immediately).	Higher (Duplicate key versions held until Compaction).

Next Steps

Now that we understand LSM-Trees vs B+ Trees, we will examine Multi-Region Geographical Replication in Part 17: dissecting Active-Active vs Active-Passive cross-datacenter replication.

References & Further Reading

IETF. RFC 2697 — A Single Rate Three Color Marker (Token Bucket Algorithm). Internet Engineering Task Force.
Stripe Engineering. (2017). Scaling your API with Rate Limiters and Load Shedders. Stripe Engineering Blog.
Tanenbaum, A. S., & Wetherall, D. J. (2011). Computer Networks (5th Edition). Pearson.