Storage Engines: Pages, Logs, and Compaction

1. Start with the contract, then follow the bytes

The query layer decides which records a request needs. The storage engine decides how to locate those records, make updates durable, and recover a consistent state after interruption. “The write succeeded” needs a boundary: process memory, stable local storage, or a required set of replicas? Those are different promises.

Disk devices transfer data in blocks. Engines organize records into pages or sorted files. A buffer pool keeps recently used data in memory. A modified page is a dirty page because memory and the data file disagree. Dirty means “needs eventual writeback,” not “corrupt.”

2. B+ trees turn sorted keys into a small number of page visits

A B+ tree keeps routing keys in internal pages and indexed entries in leaf pages. Each internal page points to many children, so a large index can stay shallow. For an illustrative tree with 200 child pointers per internal page, three branching steps can address up to 200³ = 8 million leaf pages when full. Real occupancy is lower; the point is high fanout keeps the path short.

An insertion changes a leaf. When space runs out, a split redistributes entries and adds a separator to the parent; that can propagate upward. Updating an indexed column may also change secondary index entries, so “one row write” is not necessarily one storage operation. See the PostgreSQL B-tree chapter for one mature implementation.

3. Write-ahead logging separates durable commit from page writeback

Suppose a transfer must debit one account page and credit another. If the engine wrote the first page to the data file and then crashed before writing the second, recovery would see a half-applied transfer unless it had independent evidence of the intended change. A WAL is that evidence. The engine appends redo information describing both page changes, then forces the relevant log — including the commit record for a synchronous durable commit — onto stable storage before it is allowed to consider the transaction durable. Only after that ordering rule is satisfied may the dirty data pages be written back, and they need not be written back before the client hears success.

That design is why commit latency is dominated by sequential log durability rather than by random page I/O for every touched row. It is also why a buffer pool full of dirty pages is normal rather than alarming: dirty means “memory is ahead of the data file,” not “the database is corrupt.” The trade you accept is that crash recovery must replay committed log records the data files still lack, and that an incomplete transaction with no durable commit record must never become visible as committed.

Group commit batches several commit records behind one durability flush so many waiters share the cost of a single fsync. That raises throughput and can add a small batching delay; it does not weaken the rule that a returned success already has a durable commit record. Checkpoints persist enough dirty data and checkpoint metadata to give recovery a later starting point, which bounds restart time without forcing every later commit to wait for every dirty page. Replica shipping, backups, and archival retention can still require older log segments after local crash recovery no longer does. PostgreSQL's WAL introduction is a concrete walkthrough of one mature instance of this pattern.

4. An LSM tree makes writes sequential, then organizes them later

An LSM tree takes the same appetite for sequential durability and pushes it further into the data layout itself. Incoming updates first land in an ordered in-memory structure called a memtable. A WAL can make those memory updates recoverable under the acknowledgment policy you chose. When the mutable memtable fills, the engine freezes it into an immutable memtable, opens a fresh mutable one so writers can continue, and later flushes the frozen contents into an immutable sorted file, commonly called an SSTable. The important consequence is deferred organization: updating key K does not immediately seek out and overwrite every older K on disk.

Newer and older versions therefore coexist until compaction merges sorted files, preserves versions still required by readers or snapshots, and drops obsolete data when it is safe to do so. A flush and a compaction are different jobs. Flush moves one frozen memory table onto disk. Compaction rewrites existing files, which is where much of the steady-state write amplification comes from. If you confuse the two, you will misread both capacity charts and latency incidents.

Making a new file visible also requires a recoverable metadata transition that names which files belong to the current database version. If the process creates a new SST and crashes before that metadata commits, recovery must not lose live data or expose the wrong file set. Copying arbitrary SST files out of a live directory is therefore not a consistent backup. RocksDB documents this role through its MANIFEST metadata.

5. Reads reconcile versions; filters only avoid unnecessary work

A point lookup in an LSM engine is a newest-first search across evidence, not a single file open. The engine checks the mutable memtable, then any immutable memtables still waiting to flush, then candidate files from newer levels toward older ones, using sequence numbers or equivalent versioning to decide which value is visible for the reader's snapshot. Freshly flushed level-zero files often overlap in key range, so several of them may be relevant. Later levels, after leveled compaction, usually arrange files so a key maps to at most one file per level. A backlog of overlapping level-zero files therefore raises read amplification on every lookup until compaction catches up.

A Bloom filter answers a cheaper question first: could this candidate file contain K at all? A negative answer lets the engine skip the file. A positive answer is only “maybe,” so the engine still has to consult the file's index and, on a real candidate, read the block. Under correct construction and the supported lookup semantics, an inserted key is not falsely reported absent; false positives are the price you pay for a compact filter. Filters consume memory and help a lot when many files cannot contain the key. They cannot shrink a scan that genuinely returns a million rows.

A range scan makes the version problem even more visible. Imagine three sorted streams that together cover keys 40 through 50. The engine merges those streams by key and version, suppresses obsolete values and deletions according to the snapshot, and emits only the visible result. In the diagram above, key 45 disappears because a newer tombstone wins for that snapshot, while an older snapshot might still need the previous live value. “Keep only the newest value everywhere” is safe only relative to the visibility rules of every retained reader. See RocksDB's filter documentation for one concrete filter implementation and its memory trade-offs.

6. A deletion marker protects you from resurrecting old data

Suppose an older file contains user:7 = active, while a newer file contains a tombstone for that key. The marker tells reads to suppress the old value. If compaction removes the marker but leaves the older file eligible for future reads, the deleted value can reappear.

A replicated store adds another boundary: a lagging replica might later send back an older live value. Repair and rejoining rules must prevent that resurrection too. Cassandra's tombstone documentation is a concrete example of why local deletion and distributed deletion have different safety conditions.

7. Compaction policies move cost between writes, reads, and space

Compaction has no free universal setting. Merging more aggressively can reduce the files a read must inspect and remove stale versions sooner, but it rewrites bytes now. Keeping more sorted runs avoids some immediate rewriting while leaving more candidates for future reads.

8. Calculate amplification before declaring the disk fast enough

Write amplification compares bytes written below a chosen layer with logical bytes accepted above it. Read amplification describes extra reads for a logical read. Space amplification compares stored bytes with live logical data. Always name the boundary.

The advertised sequential benchmark is not a safe substitute for this mixed write path. Three replicas accepting the same stream multiply aggregate engine writes again.

Large values deserve separate attention. Rewriting a large value through multiple compactions can dominate bandwidth even when keys are small. Separating values from the sorted key structure can reduce that rewriting, but introduces another garbage-collection problem. The WiscKey paper explores that design.

9. Compaction debt becomes a latency incident

If writes create compaction work faster than background workers can finish it, debt accumulates. Larger memory buffers may absorb a burst; they do not fix a permanent throughput deficit. More frozen memtables or level-zero files eventually force a write stall so the engine can protect bounded resources. RocksDB documents this as write stalls.