Storage engines

The question underneath every database

A storage engine answers two questions. Where do the bytes go on disk when a write arrives? And how does a key find its bytes again? Two families dominate. B-trees keep data in fixed-size pages that are updated in place: PostgreSQL's pages are usually 8 kB, and its documentation describes every table and index as an array of such pages. Log-structured merge-trees (LSM-trees) never modify data in place: they append, keep recent writes in memory and sorted files on disk, and merge those files in the background. A third family, column stores, changes the layout again for analytics. The databases from earlier chapters pick sides: PostgreSQL and InnoDB are B-tree engines; Cassandra and RocksDB are LSM engines; ClickHouse is a column store with an LSM-like merge.

To compare them you need a vocabulary of costs, the three amplifications:

• Write amplification: bytes the engine writes to storage for each byte the application wrote. It determines SSD wear and the write throughput a disk can sustain.
• Read amplification: how many disk reads or files a lookup touches.
• Space amplification: bytes on disk divided by bytes of live data.

The honest summary of the field, as the paper on RocksDB space amplification puts it, is that it is not possible to reduce space, read and write amplification all at once, so every tuning knob moves something else. This chapter gives each engine's position on that triangle and the arithmetic behind it. How a database exposes its choices to the application is covered in the earlier databases and storage chapters; the isolation rules that MVCC enforces are in the transactions chapter.

The write-ahead log: why both families have one

Memory is fast and volatile; disk is durable and slow to update randomly. Both families solve this the same way: before changing the structure, append a description of the change to a sequential log and force the log to disk. PostgreSQL's manual states the rule directly: changes to data files must be written only after the WAL records describing them have been flushed to permanent storage. Three consequences follow, and the manual lists them: data pages need not be flushed on every commit, because a crash can be repaired by replaying the log (roll-forward, or REDO); only the log needs to reach disk to make a commit durable, and since it is written sequentially, syncing it is much cheaper than flushing many scattered data pages; and one fsync of the log can commit many concurrent transactions at once.

LSM engines use the log for the memtable, which would otherwise vanish in a crash. RocksDB writes each update to the memtable and optionally to a write-ahead log, and when the memtable is flushed to a file, the matching log can be deleted. Durability then depends on a setting: RocksDB's WriteOptions choose whether a write is logged and whether the log is fsynced before the write is acknowledged. Cassandra's commit log defaults to periodic sync every 10 seconds, so a single machine that crashes can lose up to that window or more of acknowledged writes, and the replicas, not the disk, are what save the data; in batch mode a write is not acknowledged until the log is fsynced. This is the single-node view of the durability trade-off discussed across machines in the replication chapter.

B-trees have a second hazard: a page write is bigger than what a disk can write atomically, so a crash can leave half of a page written. InnoDB handles it with a doublewrite buffer: pages flushed from the buffer pool are written first to a separate area, and if a crash interrupts a write to the data file, recovery finds a good copy there. MySQL's documentation notes that although data is written twice, it does not cost twice the I/O, because the first write is one large sequential chunk with a single fsync. PostgreSQL guards against the same hazard differently, by writing full-page images into the WAL after each checkpoint.

B-trees: update in place, read in a few hops

A B-tree is a balanced tree of pages. Interior pages hold keys and pointers to children; leaf pages hold the entries. A lookup walks from the root to a leaf, one page per level. Because each page holds hundreds of entries, the tree is shallow. With an illustrative 400 entries per page, three levels address 400³ = 64,000,000 keys and four levels address 400⁴ = 25,600,000,000. A table of a billion rows needs four levels, and since the root and the next level are hot in memory, a point lookup costs about one or two disk reads for the index (a heap table such as PostgreSQL's needs one more for the row). PostgreSQL's documentation observes that typically over 99% of a B-tree's pages are leaf pages, which is why the upper levels cache so easily.

A write finds the leaf, changes the page in the buffer pool, appends to the WAL, and lets the dirty page reach disk later. If the leaf is full it splits: a portion of its entries move to a new page, and a new pointer goes into the parent, which may split in turn. PostgreSQL's manual says splits cascade upwards, and when the root cannot fit another pointer, a root split adds a new level. Hence the shape of a B-tree's costs: reads are cheap and predictable; writes are random page updates.

What it costs in practice

• Write amplification from page granularity. Changing a 100-byte row can mean writing an 8,192-byte page: 8,192 ÷ 100 ≈ 82 times the user's bytes, plus the WAL record. Many updates to one page are absorbed by the buffer pool before a flush, so 82 is an upper bound on the page-flush term for random updates, not an average, and WAL records, full-page images and InnoDB's doublewrite come on top.
• MVCC leaves dead versions. PostgreSQL's UPDATE does not overwrite a row; the old version stays visible to older snapshots, so VACUUM must later reclaim the dead versions, and a heavily updated table can bloat to the point that VACUUM FULL becomes necessary. Its documentation also recommends moderately frequent ordinary vacuums over rare heavy ones. A heap-only tuple (HOT) update avoids new index entries when no indexed column changes and the page has room, which is why lowering a table's fillfactor can speed up update-heavy tables.
• Clustered or heap. In InnoDB the table is a B-tree keyed by the primary key, and each secondary-index entry stores the primary key columns, so a lookup through a secondary index is two tree walks and a long primary key makes every secondary index bigger. PostgreSQL stores rows in a separate heap and every index points into it.
• Insert order matters. InnoDB's documentation says sequential inserts leave pages about 15/16 full, while random inserts leave them anywhere from 1/2 to 15/16 full. A random primary key such as a UUIDv4 turns every insert into a random page write and wastes space; time-ordered identifiers, covered in the time and ordering chapter, avoid it.

LSM-trees: never update, always append, merge later

The LSM-tree was proposed by O'Neil and colleagues for indexing a table with a very high insert rate, as a memory component plus disk components merged by a rolling merge. They argued that a standard disk B-tree effectively doubles the I/O cost of a transaction to maintain such an index, and that deferring and batching index changes, cascaded from memory through disk components in a way "reminiscent of merge sort", greatly reduces disk-arm movement. Bigtable (2006) put the idea into widespread production, and LevelDB, RocksDB and Cassandra descend from it. The modern form has four parts.

1. Memtable. New writes go into a sorted in-memory structure (RocksDB's default is a skiplist), together with a log record for recovery.
2. Flush. When the memtable fills it becomes immutable, a new one takes over, and the old one is written to disk as a sorted string table (SSTable): a sorted, immutable file. Cassandra's documentation is explicit that SSTables are never written to again.
3. Read. A lookup checks the memtable, then the SSTables, newest first, and stops at the first hit. A key's versions may be spread over many files.
4. Compaction. Background jobs merge SSTables into larger ones, discarding overwritten and deleted versions.

Bloom filters make the many-files read affordable

A Bloom filter is a small bit array that answers "might this file contain key K?" with either "definitely not" or "maybe". It never gives a false negative, so a "no" lets the engine skip the file. RocksDB builds one per SSTable once a filter policy is configured (it is off by default), and recommends about 10 bits per key, which its documentation tabulates as a 1% false-positive rate (9.9 bits per key gives 1%; 4.9 gives 10%; 15.5 gives 0.1%). Bigtable's authors describe the same trick: a small amount of memory for filters drastically reduces disk seeks. Bloom filters help point lookups, especially for keys that do not exist. A range scan must still merge across every sorted run that overlaps the range.

Compaction strategies, and which cost each one buys

Dry run: a point read and a write through a five-level LSM

Take the level sizes in the figure (L1 100 MB, each level ten times the last, a multiplier of 10 that Facebook reports using in most of its production RocksDB installations). Assume L0 has 4 overlapping files, and Bloom filters at the documented 10 bits per key, a 1% false-positive rate.

The write-amplification figure of 20 is an assumption chosen to be in the range RocksDB's documentation describes ("often larger than 10"), and the B-tree figure is an upper bound on one term that the buffer pool lowers. Neither is a benchmark. A real measurement does point the same way: Facebook's review of production MySQL installations found RocksDB used about half the space of compressed InnoDB and wrote between 10% and 15% as many bytes, at the price of 10% to 20% more reads, which it considered well within acceptable limits.

What compaction costs you at 3 a.m.

• Deletes are writes. An LSM engine cannot erase a key from files it never rewrites; it writes a tombstone, and only compaction discards the data and the marker. Cassandra's default tombstone grace period is ten days, which is why deleted data keeps costing reads and why the repair deadline in the replication chapter exists.
• Compaction competes with traffic. It reads and rewrites bytes the application did not ask about. A backlog of unmerged files makes reads slower: RocksDB's documentation notes that too many L0 files hurt read performance in most queries.
• Disk headroom. While files are being merged, the inputs and the output coexist, so a disk close to full can leave the engine unable to compact.

Column stores: lay data out for the question, not the row

Transaction processing reads and writes whole rows, which suits row layout (and B-trees). Analytics asks different questions: "total revenue by country last quarter" touches two or three columns of billions of rows. A column store keeps each column's values together. Parquet files, for instance, divide the data into row groups, each holding one column chunk per column, with columns divided into pages that are the unit of encoding and compression. ClickHouse's MergeTree stores each column in its own file in its wide part format (small parts default to a compact format with one file).

The arithmetic: a table of 100 columns of 8 bytes is 800 bytes a row, so a billion rows is 800 GB. A row store scanning one column still reads about 800 GB of pages; a column store reads that column's 8 GB, a hundredth of it, before compression, which works better still because a column holds values of one type that often repeat. The other half of the trade is that a single-row insert in a wide layout touches every column file, and an in-place update is awkward, so column stores take data in batches. ClickHouse's design shows how: each insert creates a new part, sorted by the primary key, and background merges combine parts, which is the LSM idea applied to columns. Its primary index is sparse, holding one mark per granule of up to 8,192 rows by default, so a billion rows need only about 10⁹ ÷ 8,192 ≈ 122,000 marks and the index stays in memory.

Putting it together: why the four systems behave as they do

Choosing

Recognizing it in an unseen problem

• Signals: "millions of writes a second", "time series", "write-heavy", "append-only log", "analytics over billions of rows", "storage cost". Each is a prompt to name an engine and its amplification.
• The naive design says "use a database" without noticing that a B-tree write is a random page update and an LSM write is a sequential append. Name which cost your workload is dominated by: random writes, read latency or disk space.
• Quantify. Write amplification times user write rate is the real disk load: 1 MB/s of user writes at amplification 20 is 20 MB/s. Space amplification times data size is the disk you buy.
• Mention the maintenance debt. LSM means compaction, tombstones and headroom; B-tree means vacuum, page splits and bloat; column stores mean batching. An answer that names the debt sounds like experience.
• The pitfall to avoid: saying "LSM is faster". It is faster for writes and slower or more variable for reads, and the numbers depend on the compaction strategy.