Chapter 10: Write-Optimized Storage — LSM Trees

Curriculum: Distributed Systems from First Principles Chapter: 10 of 24 Part: 4 — Performance Prerequisites: Chapter 1 (latency, sequential vs random I/O), Chapter 2 (B-Trees, pages, buffer pool), Chapter 3 (indexes, write amplification), Chapter 9 (bloom filters) Estimated reading time: 80–90 minutes

Opening

In Chapter 2 you learned that a B-Tree maintains sorted order on disk by rewriting pages in-place — whenever a row is inserted or updated, the database reads the relevant 8 KB page into memory, modifies it, and writes it back. This in-place update model is what makes B-Trees excellent for reads: you can find any row in O(log N) page reads, and range scans traverse sorted leaf pages sequentially. But it comes with a fundamental write penalty. A single logical row write can trigger multiple physical page writes — the data page, the index pages, the WAL record — and those writes are often to random locations on disk. From Chapter 1: a random write to an SSD costs about 100 microseconds; a sequential write costs about 1 microsecond. Random writes are 100× slower than sequential writes. This is not an implementation detail — it is a physical reality. No amount of clever B-Tree engineering can make random writes as fast as sequential writes, because randomness is what is expensive, and B-Trees need it for in-place updates.

Now ask: what if you never wrote randomly? What if every write, regardless of what it's doing, always appended to the end of a file — the fastest possible disk operation? What would you have to give up, and how would you recover it cheaply? The answer to this question is the Log-Structured Merge Tree (LSM Tree), the storage engine behind Cassandra, RocksDB, LevelDB, HBase, and parts of InfluxDB and TiKV. Understanding LSM Trees means understanding why the highest-write databases in the world are built the way they are.

Part 1: The B-Tree Write Problem — Made Concrete

Before we build LSM Trees, let's quantify exactly what we're escaping.

In Chapter 3 you encountered write amplification: the ratio of bytes written to disk divided by bytes in the logical write. For a B-Tree with several indexes, a single row insert might require:

• Writing the WAL record (sequential — fast)
• Writing the modified heap page (potentially random — slow)
• Writing each modified index page (random — slow, one per index)
• Possibly writing a new page and updating parent pointer pages if a page split occurs

For a table with 3 indexes, a single 100-byte row insert might trigger 4 random page writes of 8 KB each — a write amplification of (4 × 8192) / 100 ≈ 327×. You write 100 bytes of real data; the storage engine writes 32,768 bytes to disk.

The SSD has a hardware-level write amplification on top of this (SSD's internal garbage collection rewrites flash blocks), compounding the amplification further. At high write throughput — say, 100,000 rows/second — you're doing 100,000 × 4 random 8 KB writes per second. That's 3.2 GB of random writes per second. A high-end NVMe SSD does roughly 500 MB/s of random writes. You're attempting 6× its capacity. The database can't keep up.

The bottleneck is not the CPU, not the network, not RAM — it's random I/O on the storage device. And it's fundamental to the B-Tree's in-place update model.

Part 2: The Core Insight — Turn All Writes Into Sequential Appends

The insight behind LSM Trees, stated simply: instead of finding the right place on disk and writing there (random write), always write to the end of a file (sequential write). Defer the work of organising data for reads until after the write has been safely recorded.

This sounds like it would destroy read performance. If you just append everything in arrival order, finding a specific key means scanning the entire file — an O(N) full scan instead of O(log N). The genius of LSM Trees is the set of mechanisms they use to recover reasonable read performance while keeping writes sequential. Let's build those mechanisms from scratch.

Part 3: The Memtable — Sorting in RAM First

The first component: the memtable. This is an in-memory sorted data structure — typically a red-black tree or skip list — that holds recent writes.

When a write arrives, it goes into the memtable. The memtable maintains all entries sorted by key. This sorting is cheap — it happens in RAM with no disk I/O. RAM writes are ~100 nanoseconds; disk writes are ~100 microseconds. Sorting in RAM before touching disk is 1,000× faster than sorting on disk.

Write: PUT user:42, {name: "Alice", email: "alice@example.com"}
Write: PUT user:17, {name: "Bob"}
Write: PUT user:99, {name: "Charlie"}
Write: DEL user:17

Memtable (sorted by key):
  user:17  → TOMBSTONE  (deletion marker)
  user:42  → {name: "Alice", email: "alice@example.com"}
  user:99  → {name: "Charlie"}

Deletions are handled with tombstones — a special marker that says "this key was deleted." The key is not immediately removed (it might exist in older on-disk structures we haven't read yet). The tombstone propagates through the system until compaction removes both the tombstone and any older version of the key.

Reads check the memtable first. Since the memtable is in RAM and sorted, a lookup is O(log N) — fast.

The memtable also writes every operation to the WAL (Write-Ahead Log) before acknowledging the write to the client. This is the same WAL mechanism from Chapter 5 — if the process crashes before the memtable is flushed to disk, the WAL allows recovery. The WAL write is sequential (always append), so it's fast.

Write path:
  1. Append to WAL (sequential disk write, ~microseconds)
  2. Insert into memtable (RAM write, ~nanoseconds)
  3. Acknowledge to client

Both steps are fast. No random I/O anywhere.

Part 4: The SSTable — Flushing Sorted Data to Disk

The memtable grows until it reaches a configured size threshold (typically 64 MB – 256 MB). At that point, it is flushed to disk as an SSTable (Sorted String Table).

An SSTable is a file containing key-value pairs in sorted key order, written sequentially from beginning to end. The flush is one large sequential write — writing 64 MB to disk sequentially. At sequential write speed (~500 MB/s for an SSD), this takes about 130 milliseconds. No random writes involved.

Memtable flush:
  [user:17=TOMBSTONE, user:42={...}, user:99={...}]
        ↓  (sequential write, fast)
  SSTable file: sstable_001.sst
    ┌────────────────────────────────────────┐
    │ user:17  → TOMBSTONE                   │
    │ user:42  → {name: "Alice", email: ...} │
    │ user:99  → {name: "Charlie"}           │
    └────────────────────────────────────────┘
    (sorted by key, written once, never modified)

SSTables are immutable. Once written, they are never modified. This immutability is what allows LSM Trees to use sequential writes exclusively — you don't need to find the old location and overwrite it. You just write a new file with the new data. Old versions of a key can exist in older SSTables; the system knows to take the newest version.

Over time, multiple SSTables accumulate on disk:

Time →
  sstable_001.sst  [user:17=TOMB, user:42=v1, user:99=v1]
  sstable_002.sst  [user:42=v2, user:55=v1, user:77=v1]
  sstable_003.sst  [user:10=v1, user:42=v3, user:99=v2]
  memtable:        [user:33=v1, user:42=v4]

User 42 has 4 versions spread across 3 SSTables and the memtable. The current value is v4 in the memtable — the most recently written version. Older versions in the SSTables are superseded but still present on disk.

Part 5: Reading From an LSM Tree — The Cost You Pay

Reads are where LSM Trees pay for their write speed. To read a key, the system must check:

1. The memtable (in RAM — fast, O(log N))
2. Each SSTable from newest to oldest (potentially many disk reads)

For each SSTable, a naive check requires scanning the entire file to see if the key is present — O(N) per SSTable, O(N × num_files) total. With hundreds of SSTables accumulated since the last compaction, this is terrible.

Two optimisations recover reasonable read performance.

Sparse index per SSTable

Each SSTable maintains a sparse in-memory index: a sample of (key, file_offset) pairs, roughly one entry per 4 KB of SSTable data. To find key user:42 in a 64 MB SSTable, the sparse index narrows the search to a 4 KB block within the file, and a single sequential read of that block finds the key (or confirms its absence). This turns the O(N) scan into a binary search on the sparse index (O(log N) in RAM) plus one 4 KB disk read.

SSTable sparse index (in RAM):
  user:10  → offset 0
  user:42  → offset 4096
  user:77  → offset 8192
  user:99  → offset 12288
  ...

Looking up user:42:
  1. Binary search sparse index → offset 4096
  2. Read 4 KB block at offset 4096 from disk
  3. Scan block for user:42 → found

With the sparse index, reading one SSTable requires one disk read. But you still need to check every SSTable. If the key was last written 50 SSTables ago, you read 50 disk blocks — a significant overhead.

Bloom filter per SSTable

This is where Chapter 9's bloom filter connects. Each SSTable has its own bloom filter — built when the SSTable is written and kept in RAM. Before reading any SSTable, check its bloom filter: if the bloom filter says "definitely not in this SSTable," skip the file entirely without any disk I/O.

With bloom filters, most SSTables are skipped with zero disk I/O. Only SSTables that actually contain the key (or have false positives — rare) require a disk read. In practice, point reads on a well-compacted LSM Tree require 1–3 disk reads — competitive with B-Tree performance, though not as fast.

The read profile: B-Trees are better for point reads (1 disk read typically) but worse for write-heavy workloads. LSM Trees are better for write-heavy workloads but slightly worse for point reads. Range scans are where LSM Trees hurt most: a range scan must check multiple SSTables (each has part of the key range), merge the results, and resolve version conflicts — significantly more work than a B-Tree's sequential leaf scan.

Part 6: Compaction — The Debt That Must Be Paid

SSTables accumulate. Without any maintenance, you'd eventually have thousands of SSTables on disk, reads would require checking hundreds of bloom filters and doing dozens of disk reads, disk space would be wasted by obsolete versions and tombstones that were never cleaned up, and performance would degrade monotonically over time.

Compaction is the process of merging multiple SSTables into fewer, larger SSTables, resolving version conflicts (keeping only the newest version of each key) and removing tombstones for deleted keys.

BEFORE COMPACTION:
  SSTable_001: [user:17=TOMB, user:42=v1, user:99=v1]
  SSTable_002: [user:42=v2, user:55=v1, user:77=v1]
  SSTable_003: [user:10=v1, user:42=v3, user:99=v2]

COMPACTION (merge, keep newest version, drop tombstones):
  SSTable_merged: [user:10=v1, user:42=v3, user:55=v1, user:77=v1, user:99=v2]
  (user:17 dropped — tombstone resolved against older versions)
  (user:42 v1, v2 dropped — v3 is newest)

Compaction is a sequential read + sequential write operation — it reads the source SSTables and writes the merged result. No random I/O. But it does consume significant I/O bandwidth, which can compete with serving read and write traffic. This is called write amplification from compaction: the same data is written to disk multiple times as it is repeatedly merged into larger SSTables.

Different compaction strategies make different trade-offs between write amplification, read amplification, and space amplification.

Size-tiered compaction

Group SSTables by size. When you have N SSTables of roughly the same size, merge them into one larger SSTable. Small SSTables get merged first, producing medium SSTables, which get merged into large SSTables.

Level 0 (tiny, ~2MB each):  [S1] [S2] [S3] [S4]
                                    ↓ (merge when 4 accumulate)
Level 1 (small, ~8MB each):  [S1+2+3+4]  [S5+6+7+8]
                                    ↓ (merge when 4 accumulate)
Level 2 (medium, ~32MB):     [S1..8]  [S9..16]
                                    ↓
Level 3 (large, ~128MB):     [S1..16] [S17..32]

Characteristics: simple, good write throughput (compaction is deferred until enough files accumulate), but poor space efficiency (multiple versions of a key can exist across many same-size SSTables simultaneously) and poor worst-case read performance (a key might be in any of many same-tier SSTables).

Cassandra uses size-tiered compaction by default for write-heavy workloads.

Leveled compaction

Organise SSTables into levels (L0, L1, L2, ...). Level 0 holds freshly-flushed SSTables. Level N+1 is approximately 10× larger than Level N. Within each level (except L0), key ranges are non-overlapping — no two SSTables in the same level contain the same key.

When a level exceeds its size limit, one SSTable is selected and merged into the overlapping SSTables in the next level. This ensures that at any time, a key exists in at most one SSTable per level.

L0: [user:10-50] [user:30-80] [user:60-100]   (overlapping, just flushed)
                         ↓ (compact into L1)
L1: [user:1-20] [user:21-40] [user:41-60] [user:61-80] [user:81-100]
    (non-overlapping, 10× total size of L0)
                         ↓ (compact into L2 as L1 fills)
L2: (non-overlapping, 10× total size of L1)

Characteristics: excellent read performance (a key is in at most one SSTable per level, so a point read checks at most L levels — typically 5–7 disk reads worst case), good space efficiency (only one live version per key on a given level), but high write amplification (the same data is rewritten many times as it cascades through levels). Leveled compaction's write amplification can be 10–30× compared to size-tiered's 5–10×.

LevelDB, RocksDB, and newer Cassandra versions use leveled compaction for read-heavy workloads.

TWCS (Time-Window Compaction Strategy)

For time-series data, a specialised strategy: compact SSTables within the same time window together, and never compact across window boundaries. Since time-series data is typically queried by time range and old data is eventually deleted (TTL-based), TWCS enables efficient whole-window drops and avoids the write amplification of re-compacting old immutable data.

InfluxDB and time-series Cassandra workloads use this pattern.

Part 7: The Three Amplification Trade-offs

Every storage engine design is a negotiation between three types of amplification: write amplification (WA), read amplification (RA), and space amplification (SA). Understanding these three lets you reason about any storage engine, not just LSM Trees.

Write amplification: How many bytes are physically written to disk per byte of logical write? Low WA = fast writes, less SSD wear. High WA = slow writes, faster SSD wear.

Read amplification: How many disk reads are needed to satisfy a single logical read? Low RA = fast reads. High RA = slow reads.

Space amplification: How much disk space is used per byte of logical data? SA=1 means no space wasted. SA=2 means twice the data is on disk as logically exists (due to old versions, tombstones, compaction overlap).

The fundamental insight, sometimes called the RUM Conjecture: you cannot minimise all three simultaneously. Any storage engine is making a trade-off.

Storage engine comparison:

              Write Amp    Read Amp    Space Amp
B-Tree        High (~10×)  Low (1-3)   Low (~1.1×)
LSM (tiered)  Low  (~5×)   Medium (5)  High (~1.5×)
LSM (leveled) Medium (~20) Low  (1-3)  Low (~1.1×)
Heap file     Lowest (1×)  Highest (N) Lowest (1×)

(approximate — workload dependent)

B-Trees are read-optimised: low read amplification, low space amplification, but high write amplification (random I/O on updates). LSM Trees with size-tiered compaction are write-optimised: low write amplification on fresh writes, but read amplification grows as SSTables accumulate. Leveled LSM Trees are a middle ground: moderate write amplification but low read amplification, at the cost of higher I/O during compaction.

This is why databases exist on a spectrum rather than converging to one design. OLTP databases (many small reads and writes on mutable data) use B-Trees. Write-heavy time-series or event databases use size-tiered LSM. Systems needing good read and write performance use leveled LSM. The right engine depends on your workload.

Part 8: RocksDB — The LSM Engine That Runs Everywhere

RocksDB is Meta's (Facebook's) fork of Google's LevelDB, released as open-source in 2013. It is the most widely deployed LSM storage engine in the world. Understanding RocksDB is understanding the internals of: Cassandra (optional RocksDB backend via JNI), TiKV (the storage layer of TiDB), MyRocks (MySQL with RocksDB storage), MongoRocks (deprecated), InfluxDB v2, LinkedIn's Voldemort, and dozens of other systems.

RocksDB's architecture:

Key RocksDB features beyond basic LSM:

Column families: Logical separation of key spaces within one RocksDB instance. Each column family has its own memtable, SSTable files, and compaction policy. They share the WAL. Useful for multi-tenant storage where different data types have different access patterns.

Block cache: An in-memory cache of recently-read SSTable blocks (analogous to Postgres's buffer pool). Frequently-read blocks stay in RAM, turning subsequent reads into RAM hits. This is the equivalent of the buffer pool from Chapter 2 — even though LSM Trees are write-optimised, the block cache makes reads fast for hot data.

Prefix iterators: For range scans on a prefix (e.g., all keys starting with user:42:), RocksDB can skip SSTables that don't contain that prefix using prefix bloom filters — a more targeted version of per-SSTable bloom filters for prefix-keyed data.

Rate limiter: Compaction I/O can be rate-limited to prevent it from starving read and write traffic. This is critical in production — an uncontrolled compaction storm can saturate disk I/O and spike read latency.

Write stalls: If the write rate exceeds the compaction rate, L0 SSTable count grows unboundedly. RocksDB protects itself by slowing writes (a "write stall") when L0 count exceeds a threshold, and stopping writes entirely if it exceeds a higher threshold. This is a crucial safety valve — without it, a write spike could accumulate so many SSTables that reads become impossibly slow.

Part 9: Cassandra — LSM Trees in a Distributed System

Apache Cassandra combines the distributed architecture of Chapter 5-8 with an LSM storage engine. Understanding how Cassandra writes data connects the storage and distribution layers.

When a Cassandra write arrives:

1. The coordinator node (consistent hashing, Chapter 8) routes the write to the correct replica nodes.
2. Each replica appends the write to its local CommitLog (Cassandra's WAL — sequential write).
3. The write is inserted into the MemTable (Cassandra's name for memtable — in-memory sorted structure).
4. When the MemTable is full, it flushes to disk as an SSTable.
5. Compaction periodically merges SSTables.

Cassandra's replication factor (typically 3) means the write goes to 3 nodes. Each node has its own independent LSM tree. There's no shared storage — each replica is a complete, independent LSM storage engine.

The tension: Cassandra's eventual consistency model (Chapter 6) means a write might reach only 1 of 3 replicas before acknowledgement (consistency level ONE). Later reads might go to a different replica that hasn't received the write yet. The LSM Tree's tombstones introduce a subtle consistency hazard: if a delete tombstone is compacted away before all replicas receive it, the delete can be "resurrected" on a replica that had the old value but never got the tombstone. Cassandra mitigates this with gc_grace_seconds — tombstones are kept for a minimum duration (default 10 days) before compaction can remove them, giving all replicas time to receive the delete before the tombstone disappears.

This is an interaction between the storage engine (LSM compaction schedule) and the distributed consistency model (Chapter 6's eventual consistency guarantees). The two layers are not independent — getting compaction wrong in a distributed eventually-consistent system causes data corruption.

Part 10: When to Use LSM vs B-Tree — The Decision Framework

After chapters 2, 3, and this one, you have enough context to choose between B-Tree and LSM storage engines deliberately.

Choose B-Tree (Postgres, MySQL InnoDB) when:

• Reads and writes are roughly balanced, or reads dominate
• You need strong read performance with low latency — OLTP, user-facing APIs
• You need efficient range scans (B-Tree leaf traversal is extremely efficient)
• You need foreign keys, complex joins, and rich SQL — B-Tree systems have much better SQL maturity
• Your write throughput fits within a single machine's random I/O capacity

Choose LSM (Cassandra, RocksDB, HBase) when:

• Writes dominate heavily — time-series, event logging, IoT sensor data, activity tracking
• Write throughput exceeds what a single B-Tree instance can handle even after vertical scaling
• You're writing to many keys that are rarely or never updated (append-only workloads — LSM space amplification is low when tombstones are rare)
• You need horizontal write scaling (Cassandra distributes writes across nodes, each with its own LSM engine)
• You can tolerate slightly worse read latency in exchange for much better write throughput

The hybrid (RocksDB-backed relational — TiDB, CockroachDB, MyRocks) when:

• You need SQL semantics and horizontal scaling simultaneously
• These systems put a SQL layer on top of a distributed LSM engine, getting write scale at the cost of some read and join performance

The common mistake: using Cassandra because it "scales" when the real bottleneck is read latency on complex queries. Cassandra's scatter-gather reads across multiple SSTables, combined with the lack of server-side joins, make it poor for complex query patterns. The correct tool for complex analytical queries at scale is a columnar store (Chapter 24 territory) or a horizontally-scaled relational database, not Cassandra.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

A Cassandra cluster uses leveled compaction with gc_grace_seconds = 864000 (10 days). A user account is deleted on Day 1. The tombstone is written to all 3 replicas. On Day 5, Replica 3 experiences a disk failure and is replaced with a fresh node. The replacement node runs repair to copy data from Replica 1 and Replica 2.

On Day 9, compaction runs on Replica 1 and removes the tombstone (it has been 9 days — within gc_grace_seconds). On Day 11, a user looks up the deleted account. Trace the full sequence of what happens: which replica serves the read, what data it returns, and why. This is called "data resurrection" or "zombie data." Why does gc_grace_seconds prevent this when followed correctly? What would need to change in the operational procedure above to prevent the bug?

Problem 2 — Design from Scratch

Design the storage engine for a real-time IoT telemetry system. 10,000 devices each emit sensor readings every second: {device_id, timestamp, temperature, humidity, pressure}. That's 10,000 writes/second. The most common reads are: "last 24 hours of readings for device X" and "current reading for device X". Occasional reads: "all readings across all devices in the last hour" (for anomaly detection).

Choose: B-Tree or LSM? Which compaction strategy? What is your SSTable flush threshold and why? What bloom filter false-positive rate would you configure? How does TWCS (time-window compaction) help for this workload specifically? Trace one "last 24 hours for device X" read through the storage engine: how many SSTables might it touch, how do bloom filters help, and what does the merge step look like?

Problem 3 — Synthesis

Connect LSM Tree compaction to Chapter 3's write amplification and Chapter 1's I/O latency numbers.

You have a RocksDB instance with leveled compaction, 7 levels, and a 10× multiplier between levels. Level 0 is 64 MB, Level 1 is 640 MB, Level 2 is 6.4 GB, up to Level 6 at 640 GB. A piece of data starts at Level 0 and cascades to Level 6 through compaction.

Calculate the total amount of data physically written to disk for a single 1 KB logical write as it cascades from L0 to L6 (at each level, the key is read from the source SSTable and written into the merged Level N+1 SSTable). This is the write amplification. Then, using Chapter 1's SSD sequential write speed of 500 MB/s, calculate: at what logical write rate (KB/s) does compaction I/O consume 50% of available sequential I/O bandwidth? At what rate does it consume 100%? What does RocksDB do when write rate exceeds compaction capacity?

Problem 4 — Go Deeper

The memtable is described as a "sorted in-memory structure." Two data structures are commonly used: red-black trees and skip lists. Both provide O(log N) insert and O(log N) lookup.

From first principles, why might a skip list be preferred over a red-black tree for a memtable specifically? Consider: concurrent writes (multiple threads writing to the memtable simultaneously), the operation of flushing the memtable to disk as a sorted SSTable (which requires an in-order traversal), and the cache behaviour (Chapter 1's memory hierarchy) of pointer-heavy tree traversals vs. the more contiguous memory layout of a skip list's top-level index. Then research: what does RocksDB actually use for its memtable? What does Cassandra use? Do their choices match your reasoning?

Problem 5 — Connect to Previous Chapters

Connect LSM Trees to Chapter 6's consistency models and Chapter 8's consistent hashing.

A distributed LSM-based database (Cassandra) uses consistent hashing to place data and replication factor 3. Consider the following sequence:

1. Write W1: SET user:42.balance = 1000 → reaches all 3 replicas (strong write).
2. Write W2: SET user:42.balance = 950 → reaches only 2 replicas (one was temporarily partitioned).
3. Compaction runs on all 3 replicas independently.

In an LSM Tree, "newer" is determined by the timestamp embedded in each entry. If the partitioned replica's clock is 2 seconds behind the other replicas (clock skew, Chapter 6's discussion of LWW), trace what happens during read repair: which version does the system consider "latest"? Does user 42's balance end up as 1000 or 950? Connect this to Chapter 6's discussion of Last-Write-Wins (LWW) and why LWW + clock skew + LSM compaction is a data correctness hazard in production Cassandra deployments. What is the production mitigation?

What's Coming Next

You've now completed the storage layer trilogy: B-Tree storage (Chapter 2), indexes (Chapter 3), and LSM Trees (this chapter). You understand how data is physically stored and retrieved in both read-optimised and write-optimised engines. The next fundamental problem in distributed systems is one you've encountered hints of throughout: how do multiple nodes agree on anything? In Chapter 5 you saw that a primary election requires someone to decide who the new leader is. In Chapter 6 you learned that strong consistency requires nodes to coordinate. In Chapter 7 you saw that distributed transactions require agreement on commit/abort. All of these reduce to the same underlying problem: distributed consensus — getting N independent machines to agree on a single value despite network partitions and failures. Chapter 11 examines why this problem is hard. Chapter 12 solves it with Raft, the consensus algorithm used in etcd, CockroachDB, TiKV, and Consul.

Chapter 10 complete. Problem 3 (write amplification arithmetic through compaction levels) is the most technically grounding — do the multiplication. When you see the write amplification numbers for leveled compaction, the existence of size-tiered compaction as an alternative stops being a curiosity and becomes an obvious engineering necessity. Problem 5 (LWW + clock skew + compaction) is the most dangerous real-world failure mode — it has caused silent data corruption in production Cassandra clusters. Know it cold.