Part 1 · A single truthful copy
Storage Engines II: LSM-Trees and Columnar Storage
Lesson 03 gave us two answers to "where do bytes live": the append-only log (cheap sequential writes, plus a hash index) and the B-tree (in-place pages, great reads and ranges, but random-write cost). Both still lay one full row next to the next. This lesson pushes on the two places that hurts. First: write-heavy ingestion — feature events, embeddings, click logs — where even the B-tree's page churn is too expensive. The LSM-tree answers it by taking the log idea seriously and never overwriting at all. Second: analytical scans that read millions of rows but only a handful of fields — where storing whole rows means reading bytes that never answer the query. Columnar storage answers that by laying bytes out by column. Same Chapter 3, two layouts the OLTP engines of lesson 03 cannot reach.
Arc drawn from Kleppmann, Designing Data-Intensive Applications, Chapter 3 (“Storage and Retrieval”) — the SSTable/LSM-tree section and the column-oriented storage section. Original synthesis; no DDIA prose or figures reproduced.
Prerequisite: Lesson 03 — the ordered durable log / WAL (write-ahead log: append the change to a sequential file before touching anything else, so a crash can be replayed), compaction of log segments, the hash index, and the B-tree's read/range strengths and write-amplification cost. We build directly on the log; we do not re-derive it.
New capability: Pick a storage layout for a workload — an LSM-tree for write-heavy ingestion, a column store for wide analytical scans — and quantify the bill each one sends: write amplification, read amplification, space amplification, or scan cost.
Five moves. (1) Build the LSM-tree from the log of lesson 03: memtable → immutable SSTable → background compaction, and the Bloom filter that keeps reads honest. (2) Name the amplification triangle — write, read, and space amplification — and contrast it term-by-term with the B-tree. (3) Put a number on it: estimate leveled-compaction write amplification as fan-out × number-of-levels, with a concrete figure, and feel the knob in a widget. (4) Switch layouts: columnar storage, why a scan that touches 3 of 100 columns reads ~3% of the bytes a row-store would, why column compression is so effective, and the on-disk formats that implement it (warehouse modeling on top of this layout — star/snowflake schemas, data cubes — and query execution belong to lesson 21). (5) The OLTP-vs-OLAP split as a layout choice, failure modes, a checklist, and the hand-off into encoding.
1 · The LSM-tree: take the log seriously, never overwrite
Lesson 03 ended on a tension. The append-only log makes writes maximally cheap (sequential append), but reads need an index, and the hash index it used must fit every key in memory and cannot do range scans. The B-tree fixes reads and ranges by keeping keys sorted in pages — at the cost of overwriting pages in place on every write. The LSM-tree (Log-Structured Merge-tree) refuses that overwrite entirely: it keeps the sorted-key advantage and the sequential-write advantage by writing only new immutable files and reconciling them later.
Three structures do the work:
The read path. A point lookup checks the memtable first (newest data), then the SSTables from newest to oldest, and returns the first match. A delete is not an erasure — you cannot edit an immutable file — so the engine writes a tombstone: a marker record meaning “this key is deleted as of now.” A read that hits the tombstone before any older value returns “not found,” and compaction physically drops the key and its tombstone once no older SSTable can still hold it.
That read path has an obvious danger: a key that lives only in the oldest SSTable forces the reader to miss in the memtable and in every newer file first. The fix is a Bloom filter — a small, compact bit-array probabilistic membership test attached to each SSTable. You ask it “could key k be in this file?” and it answers either “definitely not” (skip the file entirely, no disk I/O) or “maybe” (go look). It never gives a false “definitely not,” only occasional false “maybes,” so it is safe: it can save a disk probe but never hide a real key. A 10-bits-per-key Bloom filter has roughly a 1% false-positive rate, so for a key that is absent it lets the reader skip ~99% of the SSTables that cannot contain it.
This is why RocksDB, LevelDB, and Cassandra are the default substrate for write-heavy workloads: ingesting a firehose of feature updates, event/click logs, or freshly computed embeddings. Every write is a sequential memtable insert plus a WAL append — no random page churn — so write throughput is high and write latency is low and predictable.
2 · The amplification triangle
The LSM-tree did not make the cost disappear; it moved it. There are three distinct “amplification” taxes, and an LSM-tree trades them against each other:
Contrast the B-tree of lesson 03 on the same three axes. A B-tree has low read amplification — a point lookup walks root-to-leaf, touching one page per level (~3–4 pages for a huge table), and there is exactly one place a key lives. It has low space amplification — values are updated in place, no version pile-up. But it pays in write amplification of a different shape: updating one record dirties a whole page, an insert can split pages, and every change must also be written to the WAL — so a small write becomes at least a page-sized write plus log. The headline trade:
| Axis | LSM-tree | B-tree (lesson 03) |
|---|---|---|
| Write pattern | Sequential appends + background merges | Random in-place page updates |
| Write amplification | High — compaction rewrites data several times | Moderate — page-granular writes + WAL |
| Read amplification | Several SSTables possible (Bloom filters mitigate) | Low — one root-to-leaf path, one home per key |
| Space amplification | Temporary — old versions until compaction | Low — in-place, plus page fragmentation |
| Best for | Write-heavy ingestion, high throughput | Mixed OLTP, point reads, range scans |
The slogan: a B-tree pays once, at write time, to make reads simple; an LSM-tree pays cheaply at write time and settles the bill later in compaction CPU, disk bandwidth, and read probes. Neither is “faster” — they amplify different things.
3 · Putting a number on write amplification
The most common compaction strategy is leveled compaction (RocksDB, LevelDB). Data lives in levels L0, L1, L2, … Each level is a set of non-overlapping SSTables, and each level is about a fan-out factor larger than the one above it — fan-out 10 is typical, so L1 holds ~10× the data of L0's target, L2 ~10× L1, and so on. A key works its way down: to merge a chunk from level Ln into level Ln+1, compaction reads the chunk plus the overlapping range of Ln+1 and rewrites them together. Because Ln+1 is ~fan-out times bigger, merging in one unit of Ln data drags along ~fan-out units of Ln+1 data — so each level the data passes through costs roughly fan-out rewrites.
Take fan-out f = 10 and a dataset deep enough to fill L = 5 levels. A byte written enters L0, then is rewritten on its way through each of the lower levels, costing about f rewrites per level it traverses:
write amplification ≈ f × L = 10 × 5 = 50×
So one logically written 1 KB record causes on the order of 50 × 1 KB = 50 KB of disk writes over its lifetime. Concretely: an ingestion pipeline accepting 100 MB/s of new feature events makes the disks actually write about 100 MB/s × 50 = 5,000 MB/s = 5 GB/s. That is why an under-provisioned LSM store falls over not on the application's write rate but on the amplified one — and why “tune the fan-out” and “is compaction keeping up?” are the first questions in an LSM postmortem. (The other family, size-tiered compaction, lowers write amplification but raises space and read amplification — the triangle again.)
Use the widget to feel the trade. Raise the fan-out and writes amplify harder per level but you need fewer levels to hold the same data; the product is what hits the disk.
4 · Columnar storage: lay bytes out by column
The LSM-tree and the B-tree both still store a row as a contiguous run of bytes — every field of a record next to the next field. That is exactly right for OLTP (Online Transaction Processing: many small user-facing operations — point lookups and short updates touching whole records, the workload lesson 03 optimized for). It is wasteful for the opposite workload: OLAP (Online Analytical Processing — a few queries that each scan a vast number of rows but read only a handful of columns, computing aggregates and joins).
Picture a 100-column events table with a billion rows, and the query “average revenue by country for the last quarter.” A row store must stream every row off disk to reach the country and revenue fields, dragging along bio, avatar_url, debug_payload, and 95 other columns it will throw away. Columnar storage instead lays out all values of one column contiguously: every country together, every revenue together. Now a scan reads only the columns it projects.
100 columns, 1,000,000,000 rows, columns roughly equal in width. A query that touches 3 columns reads:
3 / 100 = 3% of the bytes a row store would scan.
If the full table is 2 TB, the row store reads ~2 TB to answer the query; the column store reads 2 TB × 0.03 = 60 GB. At a disk scan rate of 1 GB/s that is ~2,000 s versus ~60 s — a ~33× latency drop from layout alone, before any compression. That is the entire reason analytical warehouses (Parquet files, BigQuery, ClickHouse, Redshift) are column-oriented.
Compression makes it even cheaper. Because a column holds values of one type and similar distribution sitting adjacently, compression bites hard:
- Run-length encoding — store “
US× 4,000,” not 4,000 copies ofUS. Hugely effective when the column is sorted, because equal values cluster. - Dictionary encoding — map each distinct value to a small integer code (
US→0,CA→1) and store the compact codes; a 4-byte country string collapses to a 1-byte (or sub-byte) code.
So the column store reads fewer columns and fewer bytes per column. Sort order compounds this: sorting the data by a frequently filtered column makes its runs longer (better RLE) and lets the engine skip whole blocks that fall outside a filter's range. And because each column is a tight, typed array, the CPU can run a vectorized scan — applying one operation across a batch of values in tight loops (and SIMD instructions) — instead of hopping field-to-field through a row.
The columnar layout has standard on-disk homes worth naming: the file formats Parquet and ORC implement exactly the layout above — column chunks, dictionary/RLE encoding, per-block min/max stats for skipping — and are what analytical tables are physically written as in a data lake, while cloud warehouses Amazon Redshift and Google BigQuery store data column-oriented internally. (Do not confuse these with the wide-column stores Bigtable and HBase: despite the name they are LSM-backed key-value systems from section 1, an OLTP workload, not OLAP scans.) How a warehouse then models data on top of this layout — star and snowflake schemas, fact vs dimension tables, data cubes and materialized aggregates — and how its query engine executes those scans are the subject of lesson 21 (analytics and query-execution internals); here we stop at the storage layout itself.
5 · Choosing a layout by workload
The cost columnar pays is the mirror image of its win: writes and point updates. Reconstructing one full row means gathering one value from each of many separate column chunks, and you cannot update a value in place inside a compressed, immutable column block — so lakehouse formats (Parquet, Iceberg, Delta) write immutable files plus metadata and use compaction and delete-vectors to reconcile changes. The append-and-compact bet from the LSM section returns, now at the file level. Point-update-heavy, low-latency serving is precisely where columnar is wrong and a row-oriented OLTP engine (or an LSM key-value store) is right.
This is why one logical dataset often needs two physical homes. A feature store is the canonical example: the online store serving a fraud model at request time is a low-latency key-value system (often LSM-backed) keyed by entity id for point reads; the offline store holding the same features for training and backfills is columnar Parquet, scanned wide and cheap. Same features, opposite access patterns, opposite layouts.
Failure modes
- Compaction falls behind. Write rate × amplification exceeds disk bandwidth, so SSTables pile up. Read amplification climbs (more files to probe) and space amplification balloons (uncollected versions) — the system degrades on reads and storage at once, often right when it is busiest.
- No Bloom filters / wrong sizing. Every point-miss probes many SSTables; a too-small filter raises the false-positive rate and the wasted I/O with it.
- Tombstone build-up. A delete-heavy workload leaves tombstones that cannot be collected until compaction visits every older file holding the key; until then reads still scan them, and range scans slow down.
- Columnar for point updates. Using a column store as an OLTP system: single-row updates rewrite or shadow whole column blocks, and row reconstruction is slow. Wrong layout for the workload.
- Row store for wide scans. Running quarterly analytics on the OLTP primary: every query reads all columns of every row, starving the transactional workload of I/O.
Decision checklist
- Is the bottleneck write throughput? Lean LSM (RocksDB/Cassandra). Mixed point reads + ranges? Lean B-tree.
- Estimated write amplification = fan-out × levels — does disk bandwidth cover (app write rate × that factor)?
- Is compaction provisioned its own CPU/IO headroom, and is its backlog monitored?
- Are Bloom filters on, and sized (bits/key) for your read-miss rate?
- Is the dominant query a wide scan over few columns? Use columnar; pick the sort column to maximize RLE and block-skipping.
- Do you need both? Split into an online row/KV store and an offline columnar store, and define which is the source of truth.
Checkpoint exercise
You are storing clickstream events for a recommender: ~200 MB/s sustained ingest, occasional point lookups of a single user's recent events, and a nightly analytics job that computes click-through rate per ad over a billion events touching 4 of ~60 columns. (1) Choose the ingest/serving layout and estimate its disk write rate assuming leveled compaction with fan-out 10 across 5 levels. (2) Choose the analytics layout and estimate the fraction of bytes the nightly job reads versus a row store. (3) Say which store is the source of truth and how the analytics store stays fresh.
Where this points next
We now have, across lessons 03 and 04, a complete answer to “how does one node lay out bytes for a workload” — logs, B-trees, LSM-trees, columnar. Every layout here, though, stored and read bytes whose meaning it took for granted: a record was just bytes the engine moved around. The moment those bytes outlive the code that wrote them — replayed from a log months later, flushed in an old SSTable, read by a service version that has since rolled forward — their layout has to survive change too. That closes Part 1 and opens Part 2. Lesson 05 takes up encoding and schema evolution: how an object becomes bytes, and how old and new code keep understanding those bytes across a rollout, a replay, and a year on disk.
Both layouts here make the same answer explicit. The system of record is the durable append: in an LSM-tree, the WAL plus the immutable SSTables it flushes to; in a columnar lakehouse, the immutable Parquet/Iceberg/Delta files. Everything fast on top is a derived copy / view rebuilt from those appends — the in-memory memtable, the Bloom filters, the merged lower levels, and (the canonical case) the online feature store that is a derived, point-lookup copy of the offline columnar source of truth. Freshness budget: how far the derived online copy may lag the offline source, and how stale a read may be before compaction reconciles superseded versions. Owner: the storage engine for intra-engine copies; the pipeline team for the online-from-offline derivation. Deletion path: deletes are tombstones (or delete-vectors in lakehouse formats), not in-place erasures — compaction physically reclaims the bytes once no older file can still hold the key. Reconciliation / repair: background compaction merges files and drops superseded versions and tombstones; the online copy is rebuilt from the offline source rather than patched. Evidence it is correct: per-block min/max stats and checksums in the column files, Bloom-filter no-false-negative guarantees, and row-count reconciliation between the offline source and the online derived copy.
An LSM-tree takes the lesson-03 log to its conclusion: writes hit an in-memory sorted memtable (durably logged to the WAL), flush to immutable sorted SSTables, and are reconciled by background compaction, with Bloom filters letting reads skip files that cannot hold a key and tombstones standing in for deletes. That makes writes sequential and cheap — ideal for write-heavy ingestion (RocksDB, Cassandra) — but moves the bill into the amplification triangle: high write amplification (≈ fan-out × levels, so ~50× with fan-out 10 over 5 levels), some read amplification, and temporary space amplification; the B-tree makes the opposite trade. Columnar storage answers the orthogonal pressure of analytical (OLAP) scans by laying bytes out by column, so a query touching 3 of 100 columns reads ~3% of the bytes — and run-length / dictionary compression plus sort order and vectorized scans shrink it further — at the price of slow point updates, which is why OLTP serving and OLAP analytics often live in two physical homes.
Interview prompts
- Walk the LSM write and read paths. (§1 — write → WAL + sorted memtable → flush to immutable SSTable → background compaction; read checks memtable then newest→oldest SSTables, with a Bloom filter skipping files that cannot contain the key; deletes are tombstones.)
- What is the amplification triangle, and how does an LSM-tree trade within it versus a B-tree? (§2 — write/read/space amplification; LSM has high write amp from compaction but cheap sequential writes; B-tree has low read/space amp and one home per key but pays page-granular write amp.)
- Estimate the write amplification of leveled compaction and why it matters. (§3 — ≈ fan-out × levels, e.g. 10 × 5 = 50×; the disk must sustain app-write-rate × that factor, so 100 MB/s ingest means ~5 GB/s of actual writes.)
- What does a Bloom filter buy an LSM read, and why is it safe? (§1 — it answers “definitely not” or “maybe” per SSTable, so a read skips files that cannot hold the key; no false negatives, only occasional false positives, so it never hides a real key.)
- Why is a column store ~33× faster on a wide-scan analytical query? (§4 — it reads only the projected columns (3 of 100 ≈ 3% of bytes), and run-length/dictionary compression plus sort-order block-skipping cut bytes further; row stores must read every field of every row.)
- Why is Parquet great for training-data scans but wrong for online feature serving? (§4–5 — columnar wins on wide scans but point reads must gather one value from each column chunk and updates rewrite immutable blocks; online serving needs a low-latency row/KV (LSM) store.)
- Design online + offline storage for a fraud-model feature. (§5 — online: LSM-backed KV keyed by entity id for low-latency point reads; offline: columnar Parquet for cheap wide training scans; name which is source of truth and how the offline store is refreshed.)