Module P-2·26 min read

Write vs read amplification, memtables, SSTables, and compaction stalls — the direct payoff of F-2, and why your write-heavy table hates a B-tree.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module P-2 — Storage Engines: B-Trees vs LSM-Trees

Q: An event-ingestion service on an LSM store has held a flat 4 ms write p99 for two weeks. Over one hour, throughput collapses and p99 reaches several seconds. Disk is 40% full, CPU has headroom, nothing was deployed. What is the most likely mechanism?

Compaction has fallen behind ingest, L0 files have accumulated past the slowdown and stop thresholds, and the engine is throttling writes on purpose to let it catch up. Write amplification grows as the tree deepens, so the background I/O required rose over the two weeks until it crossed what the device could spare — and because the throttle is a threshold, not a gradient, the graph is flat until it is vertical. — This is the compaction stall, and all three parts of its signature are present: the latency is injected deliberately once L0 crosses the slowdown trigger, the compaction throughput required grows with data volume because a deeper tree rewrites each byte more times, and the transition is abrupt because the trigger is a step function sitting on Module F-4's utilisation curve. The leading indicator is pending compaction bytes or L0 file count — not disk utilisation, not write latency. Option A is the near-miss: memtable sizing genuinely governs flush frequency and RAM use, but the memtable is bounded by configuration rather than growing silently, and shrinking it produces *more* small L0 files and a worse stall. Option B misplaces bloom filters, which serve reads and are not consulted on writes. Option C is an HDD-era concern that cannot explain a cliff on an append-only layout.

Q: A team used a Cassandra table as a job queue, deleting each row after processing — roughly two million deletes in one partition. Weeks later `SELECT * FROM job_queue WHERE tenant_id = ? LIMIT 100` fails, though the partition holds no live rows. Why, and what is the structural fix?

Each delete appended a tombstone rather than removing data; tombstones are retained until compaction and `gc_grace_seconds` have let every replica learn of the delete, and the read must scan them all to prove there is nothing to return — enough of them that Cassandra refuses the query outright. The fix is to delete at file granularity: TTLs plus time-windowed partitions, so whole SSTables expire and drop. — An immutable file cannot have a row removed from it, so a delete is a write — a tombstone — and it must survive long enough for compaction to merge it against every older file and for every replica to hear about it via hinted handoff or repair. Purging early resurrects deleted data, which is why the grace period defaults to something as long as ten days. Reads pay for every tombstone on their path, so a query returning zero rows becomes the most expensive on the cluster, and the warn and failure thresholds turn "slow" into "refused". The fix moves deletion from row granularity to file granularity, at the stated cost that retention now dictates the partition key. Option C is the respectable near-miss — replica divergence and consistency level are real Cassandra failure modes — but lowering consistency does not reduce the tombstones a replica must scan locally. Option B invents a hard partition-size limit. Option D misuses bloom filters, which are per-file membership hints and cannot exclude tombstones the read is obliged to consider.

Q: An engineer moves a write-heavy table from Postgres to an LSM store on the strength of "LSM-trees turn random writes into sequential ones." Throughput improves substantially, but device write bandwidth is now roughly 15× the bytes the application sends. Has something gone wrong?

No — that is write amplification working as designed. A levelled LSM rewrites each byte as it merges down through the levels, commonly 10–30× in total, and the trade was never "less I/O": it was more total I/O, converted into large sequential writes and moved off the critical path. The cost is real device bandwidth, which is why the ceiling is compaction throughput rather than ingest rate. — The module is explicit that an LSM does not reduce total I/O and usually increases it considerably; what it buys is that nearly all of that I/O is a large sequential write issued in the background rather than a scattered write on the commit path. Fifteen times sits inside the range a levelled configuration produces, and recognising it as expected is what lets you plan capacity against compaction throughput instead of ingest rate. Option C inverts the strategies — tiered has *lower* write amplification, paid for with roughly double the space and worse reads — and no strategy approaches 1×. Option A misreads the arithmetic: the WAL contributes about one extra copy, not fourteen, and disabling it trades durability for a rounding error. Option D is the seductive one, because Module F-2 really does say a sequential write delivers far more useful bytes per second — but cheaper per byte is not free, device bandwidth and endurance are finite, and provisioned IOPS is a line item on the bill (Module O-8).

What this module covers: Underneath the database you chose is a storage engine you probably didn't, and the two families fail in completely different shapes. This module covers what a B-tree costs to write — page splits, WAL, torn-page protection, a scattered write pattern — and what an LSM-tree does instead: memtable, immutable SSTable flush, compaction levelled or tiered, bloom filters, tombstones. It covers the three-way amplification trade where you pick two, the compaction stall that makes "it was fine for two weeks" a diagnosis rather than an excuse, and a decision rule that names its own cost.

You Didn't Choose Your Storage Engine, You Inherited It

Almost nobody picks a storage engine. You pick Postgres because it's the sane default (Module F-14), or Cassandra because someone needed multi-region writes, or you adopt a stream processor and inherit RocksDB under its state store. The engine arrives as a side effect, and then it decides the shape of your worst production day.

A B-tree engine degrades on a slope. Insert throughput sags as the index outgrows memory, hit ratio slides, bloat accumulates (Module F-13) — months of warning on a graph nobody was watching.
An LSM engine degrades as a cliff. Write throughput is flat and excellent for two weeks, then falls off a ledge inside an hour, p99 going from milliseconds to seconds. Disk isn't full, CPU isn't pegged, nothing was deployed: a background process fell behind.

Both behaviours come from one decision at the bottom of the stack: does a write modify data where it already lives, or append it somewhere new and reconcile later?

Update in Place: What a B-Tree Costs to Write

Module F-13 covered the read side — sorted leaves, four or five page reads for a hundred million rows, sideways scans along the leaf links. The costs hide on the write side. To write one row the engine finds the leaf page the key belongs on, modifies it in memory (in Postgres an 8 KB page in shared_buffers, now dirty), appends the change to the WAL and fsyncs at commit, then eventually writes that page back to its own location at checkpoint time. The WAL part is sequential and cheap. The write-back is not: the page lives wherever the key sorts, so the physical pattern is dictated by your key distribution.

Two further costs are large and easy to miss.

Page splits. When a new entry doesn't fit on its leaf page, the engine allocates a new page, moves half the entries into it, and updates the parent — which may itself be full, cascading upward, occasionally to the root. One logical insert becomes several page writes plus the WAL records describing them, and the index is now fragmented, so later range scans walk leaves that are no longer physically adjacent.

Torn-page protection. A power cut mid-write can leave an 8 KB page half-old and half-new, which no delta-style WAL record can repair. Postgres with full_page_writes on therefore copies the entire page into the WAL the first time it's touched after a checkpoint; InnoDB uses its doublewrite buffer. Updating 200 bytes can put 8 KB into the log.

So B-trees have write amplification too — just bounded, predictable, and paid at commit rather than in the background. It's much of why a single Postgres node with fsync-on-commit sits around 1,000–5,000 write transactions per second.

Why this matters in production: the cost is proportional to how scattered your keys are. Sequential keys concentrate inserts onto the last few leaf pages, which stay cached and rarely split. Random keys spread inserts across the whole index, so the set of pages being dirtied is the index — hit ratio collapses, splits multiply, WAL traffic climbs. That is the random-UUID-primary-key disaster, and Module P-3 is about nothing else.

An LSM-Tree Is Module F-2's Fact Turned Into an Engine

Module F-2 established the counterintuitive number: in useful bytes per second, a sequential SSD write (~3 GB/s) beats a random access pattern in DRAM (~80 MB/s). A log-structured merge tree is that sentence built into an engine. It refuses to write anything in place, on the grounds that a large sequential write is so much cheaper than a scattered one that it's worth doing substantially more total I/O to get one.

The write path has three steps and no page updates in it:

Append to a write-ahead log for durability. Sequential.
Insert into the memtable — a sorted in-memory structure, usually a skip list. The write is complete from the client's point of view here, which is why LSM write latency is so low: a log append and a memory insert, no page read.
When the memtable hits its size limit, freeze it and write it out as one SSTable — a sorted, immutable file — in a single sequential pass, then discard the matching WAL segment. A fresh memtable takes over immediately.

Immutability is load-bearing: nothing on disk is ever modified, so there are no splits, no torn pages, no random write pattern, and no locking between readers and writers. The cost is that many files may each hold a version of the same key, recency decided by file age — so reads must reconcile them, and something must reduce the file count.

Analogy: a B-tree is a librarian who reshelves every returned book the moment it arrives — the shelves are always exactly right, and she spends the day walking the building to keep them that way. An LSM-tree is the returns trolley: books go in as they come, and a night shift merges the trolleys into the shelves after closing. The front desk gets far faster, but finding one book now means checking the trolleys before the shelves — and if the night shift falls behind, trolleys stack up in the corridor until you have to stop accepting returns.

Compaction Is the Bill, Paid Later in Background I/O

Compaction reads several sorted SSTables, merges them, keeps the newest version of each key, drops the shadowed ones, and writes new sorted files. All sequential, and all pure overhead from the application's view, competing with foreground reads for one device. Two strategies dominate and trade cleanly:

	Levelled	Tiered (size-tiered)
Structure	L0 holds overlapping fresh flushes; each level below holds non-overlapping files ~10× the size of the one above	Similar-sized files merge into a bigger one; overlapping files coexist at every size
Write amp	High — each byte rewritten once per level, ~10–30×	Lower, often single digits
Read amp	Low — below L0, one file per level at most holds the key	Higher — several files per size class to check
Space amp	~1.1× — the bottom level holds ~90% of the data	Up to ~2× or worse; a merge needs room for inputs and outputs at once
Typical home	RocksDB default, LevelDB	Cassandra's default STCS, HBase

The write-amplification arithmetic predicts the cliff, so do it once. With a level ratio of 10, a byte is rewritten as it merges L1→L2, L2→L3 and onward, each merge rewriting on the order of 10× its input in the destination level. Ingesting 20 MB/s of application data can mean a few hundred MB/s of device writes once the tree is deep.

That is the honest framing: an LSM does not reduce total I/O. It usually increases it, considerably, while converting nearly all of it into the pattern the device is best at and moving it off the critical path. The second half of that sentence is what breaks.

"It Was Fine for Two Weeks" — the Compaction Stall

A service ingesting events into Cassandra or RocksDB runs beautifully; write p99 is a few milliseconds. Then, somewhere between week two and month three, throughput collapses within an hour, p99 hits seconds, and clients time out. Disk isn't full. CPU has headroom. Deploy history is clean.

Compaction stopped keeping up, and the engine applied backpressure on purpose.

javascript

// Illustrative RocksDB-family options. Exact defaults vary by build.
const options = {
  write_buffer_size: 64 << 20,            // memtable size before it is frozen and flushed
  max_write_buffer_number: 4,             // frozen memtables allowed to queue for flush
  level0_file_num_compaction_trigger: 4,  // L0 file count that starts L0 -> L1 compaction
  level0_slowdown_writes_trigger: 20,     // engine begins DELAYING writes on purpose here
  level0_stop_writes_trigger: 36,         // engine STOPS accepting writes entirely here
  max_background_jobs: 4,                 // compaction + flush threads: your real lever
};
// Those two trigger lines are the cliff: past them, write latency is a scheduler's
// decision rather than a property of your disk.

Ingest exceeds compaction throughput, L0 accumulates, the engine throttles writes, and if L0 keeps growing it stops them altogether. Flushes back up behind it: a frozen memtable can't be written out while L0 is over its limit, the flush queue fills, and the active memtable has nowhere to go.

Why the two-week delay — the signature:

Write amplification grows with data volume. At 10 GB you have two or three levels; at 500 GB, five or six. The same ingest rate demands more compaction I/O over time while the device stays what it was.
You were near saturation and couldn't see it. Compaction and foreground reads share one queue, and Module F-4's curve W = S/(1−ρ) is fine at ρ = 0.7 and vertical at ρ = 0.95. Crossing that band takes a few percent of extra load — exactly what a growing tree supplies. The cliff is the curve.
The trigger is a step function, so nothing degrades gently — and the events that tip it are mundane: a backfill, a migration replaying rows, a retry storm, a hot partition, one node down so survivors take its share.

Why this matters in production: the leading indicator is not disk utilisation and not write latency — both look fine until they don't. It's pending compaction bytes and L0 file count (nodetool compactionstats in Cassandra), which climb for hours or days before the throttle engages. That is your entire warning window, and every mitigation costs something nameable: more background threads steal CPU and IOPS from queries, raising compaction throughput limits does the same, larger memtables cost RAM and slower crash recovery, and fewer writes per node means more nodes (Module P-6).

The Read Path: One Key, Several Files

An LSM read searches a stack of sorted files in recency order: active memtable, frozen memtables, every file in L0 (they overlap, so all are candidates), then at most one file per level below. First hit wins, because newer shadows older. Three structures keep that affordable:

Bloom filters. Each SSTable carries a probabilistic membership filter over its keys, answering definitely not or probably yes. A no skips the file at zero I/O cost, and at around ten bits per key the false-positive rate is on the order of 1% — so a lookup for an absent key touches almost no data blocks, which makes it cheaper than a B-tree's descent to the leaf.
Sparse index blocks inside each file, so a candidate is binary-searched rather than scanned.
A block cache holding hot data and filter blocks in memory.

The asymmetry that catches people: bloom filters do nothing for range scans. A filter answers a question about one key, and WHERE ts BETWEEN x AND y isn't one. The engine opens an iterator on every level and merges them, reading real data from all of them, so range cost is set by the number of overlapping sorted runs — precisely the number compaction exists to keep small.

Operation	B-tree	LSM-tree
Point read, key present	~4–5 page reads	Filters reject most files; 1–2 block reads
Point read, key absent	Full descent to the leaf	Near-free — the filters reject everything
Short range scan	Sequential walk along linked leaves	Merge across levels; scales with sorted-run count

So one degradation drives both symptoms: when compaction falls behind, writes get throttled and range scans slow, because both are functions of the sorted-run count.

Deletes Don't Delete: Tombstones and the Scan That Times Out

You cannot remove a row from an immutable file, so an LSM delete writes: it appends a tombstone meaning "this key is deleted as of now." A delete costs what a write costs.

The tombstone must survive until compaction has merged it against every older file that might still hold the key — drop it sooner and the row comes back. In a distributed store the window is longer: Cassandra keeps tombstones for gc_grace_seconds, ten days by default, because a replica that was down during the delete has to learn of it via hinted handoff or repair. The default is long because the failure it prevents is silent data resurrection. Meanwhile every read pays for every tombstone in its path, which produces the classic Cassandra failure:

sql

-- The anti-pattern: a work queue, deleted row by row.
DELETE FROM job_queue WHERE tenant_id = 'acme' AND job_id = ?;   -- x2,000,000

-- Weeks later, this reads two million tombstones to return zero rows.
-- Cassandra warns at 1,000 tombstones scanned in one read and fails the query
-- at 100,000 by default, so this doesn't get slow -- it gets refused.
SELECT * FROM job_queue WHERE tenant_id = 'acme' LIMIT 100;

Every signal misleads: the table looks empty, the data volume looks trivial, and the cheapest-looking query on the cluster is the most expensive. It catches teams who used a wide-partition store as a queue, and equally any "soft delete, then hard delete" job that removes rows individually at scale.

The fix is to make deletion happen at file granularity — partition by time, set TTLs, and let a time-window compaction strategy drop whole SSTables once everything in them has expired. The cost: retention policy now dictates your partition key, which is the hardest thing to change later (Module F-14). Pay it deliberately; it is far cheaper than the alternative.

Pick Two of Three, Then Pick a Side

Everything above collapses into one three-way trade. Write amplification is bytes written to the device per byte written by the application; read amplification is data units read per logical read; space amplification is bytes stored per byte of live data. You can optimise any two at the third's expense — sometimes called the RUM conjecture, and a good design filter.

Engine / setting	Write amp	Read amp	Space amp	What you gave up
Levelled LSM	High (~10–30×)	Low	Low (~1.1×)	Device write bandwidth, and the stall risk with it
Tiered LSM	Low	High	High (~2×+)	Read consistency, and double the disk you budgeted
B-tree	Moderate but random	Low	Moderate (bloat)	Write throughput — scattered pattern, not large volume

So "is an LSM faster than a B-tree?" has no answer, and every knob in a RocksDB or Cassandra config file is a request to move along one of these axes. Compaction turned down to protect foreground latency raises space and read amplification; turned up to reclaim space, it steals IOPS from queries. An engine that appears to be free has moved the cost somewhere you aren't measuring.

The decision rule that survives contact with production is narrower than the marketing:

Write-heavy with access patterns known in advance → LSM. Time-series, event ingestion, counters, feeds — high volume where every query is a point lookup or a bounded range on a key you designed for. The cost: you own compaction operationally, which means pending-compaction dashboards, capacity planning that budgets background I/O and not just ingest, and the discipline never to mass-delete rows. Ad-hoc queries will be bad and no index added later rescues them.

Mixed workload with ad-hoc reads → B-tree. Anything relational and transactional, anything where analysts and future features ask questions nobody anticipated. The cost: a lower write ceiling, sensitive to key ordering, so the primary key becomes load-bearing (Module P-3), plus ongoing vacuum and index maintenance (Module F-13).

You rarely choose directly, though — you choose an engine by choosing a database, so the live question is usually "given that we're on Postgres, will this workload fight the engine?" A firehose of randomly-keyed append-only events is fighting it, which argues for a different store for that one table (Module P-9), not a rewrite.

Family	Systems
B-tree, update in place	PostgreSQL, MySQL/InnoDB, SQL Server, SQLite
LSM-tree, append and compact	RocksDB, LevelDB, Cassandra, ScyllaDB, HBase

Where This Shows Up in Your Stack

PostgreSQL: a B-tree engine, so the levers are F-13's plus checkpoint tuning. full_page_writes explains why a small UPDATE produces surprising WAL volume, and pg_stat_bgwriter shows whether checkpoints write dirty pages in lumps. There's no compaction, but VACUUM is the same category — a background reclaimer that degrades everything when it falls behind.
Redis: RAM-resident, so no engine in this sense, but AOF rewrite is exactly the compaction shape: an append-only file that grows until a background process rewrites it compactly, competing for the same disk and CPU as foreground commands. auto-aof-rewrite-percentage is a compaction-aggressiveness knob in different clothes.
Node.js: embed a RocksDB binding in-process and compaction threads run inside your service, taking CPU the event loop needs — a background flush surfaces as unexplained event-loop lag. Against a remote LSM store, instrument the gap between server-reported write time and client-side queue wait: during a stall the server looks fine for the writes it accepts, and the damage is all in your driver's queue.
Cassandra / ScyllaDB: pick the compaction strategy for the workload rather than taking the default — size-tiered for write-heavy, levelled for read-heavy at the price of far more write amplification, time-window for TTL'd time-series. Treat a rising pending-task count as an incident precursor.

Summary

You inherit a storage engine when you pick a database, and the family sets your failure shape: B-trees degrade on a slope, LSM engines fall off a cliff.
A B-tree writes in place, costing page splits, full-page WAL records for torn-page protection, and a write pattern scattered by your key distribution — bounded amplification, paid at commit.
An LSM-tree is F-2's sequential-beats-random result built into an engine: WAL append, memtable insert, immutable SSTable flushed in one sequential pass. It does more total I/O to make nearly all of it sequential and deferred.
Compaction is the deferred bill. Levelled buys low read and space amplification with 10–30× write amplification; tiered buys low write amplification with double the space and worse reads.
The compaction stall is the symptom to know cold: ingest outruns compaction, L0 grows, the engine throttles and then stops writes. "Fine for two weeks" is the signature, because write amplification grows with data volume and the throttle is a step function on F-4's utilisation curve. Alert on pending compaction bytes.
An LSM read may touch memtables, every L0 file, and one file per level. Bloom filters make misses nearly free and do nothing for range scans, whose cost is the sorted-run count.
Deletes are writes. Tombstones persist until compaction and repair have propagated them, so a row-by-row mass delete leaves range scans reading millions of markers to return nothing — which Cassandra refuses outright. Delete at file granularity instead, accepting that retention now dictates your partition key.
Write, read and space amplification are a pick-two, and the honest rule follows from it: write-heavy with known access patterns → LSM, and you own compaction operationally; mixed with ad-hoc reads → B-tree, and you own a lower write ceiling sensitive to key order.

The next module, Primary Keys and Distributed ID Generation, takes that last clause and makes it the whole subject. A B-tree's write cost depends on where new keys land, so the identifier you generate is a storage-engine decision wearing a data-modelling costume — and a random UUID wrecks insert throughput on a large table by exactly the page-scattering mechanism described here.

Knowledge Check

An event-ingestion service on an LSM store has held a flat 4 ms write p99 for two weeks. Over one hour, throughput collapses and p99 reaches several seconds. Disk is 40% full, CPU has headroom, nothing was deployed. What is the most likely mechanism?

A team used a Cassandra table as a job queue, deleting each row after processing — roughly two million deletes in one partition. Weeks later SELECT * FROM job_queue WHERE tenant_id = ? LIMIT 100 fails, though the partition holds no live rows. Why, and what is the structural fix?

An engineer moves a write-heavy table from Postgres to an LSM store on the strength of "LSM-trees turn random writes into sequential ones." Throughput improves substantially, but device write bandwidth is now roughly 15× the bytes the application sends. Has something gone wrong?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule P-1: ACID, Transactions, and Isolation Levels Next Module P-3: Primary Keys and Distributed ID Generation

Discussion

Join the discussion

Loading comments...