Database Internals and Storage Engines Questions

Direct answer

Postgres implements multi-version concurrency control (MVCC) by never modifying a row in place: every INSERT or UPDATE writes a brand-new physical row version stamped with the id of the transaction that created it (xmin), and an UPDATE or DELETE marks the version it replaces with the id of the transaction that superseded it (xmax) rather than erasing it. A transaction's snapshot is a fixed rule, computed once, for which transaction ids count as already committed, and a row version is visible to that transaction only if its xmin is in that committed set and its xmax, if set, is not. Because old versions are left in place rather than deleted, something has to come back later and physically remove them, that something is autovacuum, and if it falls behind for long enough on a very old row version, the consequence is not just wasted space but a hard correctness deadline called transaction id wraparound.

Structured elaboration

Row versioning and snapshot visibility

Every physical row (a "tuple" in Postgres's heap storage) carries xmin and xmax as hidden system columns. A fresh INSERT sets xmin to the inserting transaction's id and leaves xmax at 0 (unset). An UPDATE does not touch the old row's data; it sets the old row's xmax to the updating transaction's id and writes a completely new row with a new xmin and xmax = 0. A transaction's snapshot, taken once at the start of a REPEATABLE READ or SERIALIZABLE transaction (two isolation levels that pin one snapshot for the whole transaction, so every statement inside it sees the same consistent view) or once per statement under the default READ COMMITTED (which takes a fresh snapshot for each individual statement, so a later statement in the same transaction can see commits made by other transactions in between), is the set of transaction ids already committed as of that instant; a row is visible if xmin is in that set and xmax is either unset or belongs to a transaction not in that set. This is exactly what lets two concurrent transactions get consistent, non-blocking answers from the same table: a writer's new version simply is not in an already-running reader's committed set yet.

Why table bloat happens

Because an UPDATE leaves the old version physically on the page (it is only marked invisible via xmax, not deleted), a table that is updated heavily accumulates dead row versions between vacuum runs. This is "bloat": the table's on-disk size grows to hold both live and dead versions even though the logical row count has not changed, and every sequential scan or index-then-heap lookup has to skip past the dead versions to find the live one.

Detecting bloat

Two views tell you this directly: pg_stat_user_tables.n_dead_tup (dead row versions Postgres's statistics collector currently estimates for a table) versus n_live_tup, and the pgstattuple extension's pgstattuple('table'), which physically scans the table and reports exact dead_tuple_percent and free_percent.

Mitigations and operational knobs

• Autovacuum tuning: autovacuum_vacuum_scale_factor (fraction of the table's live rows that must be dead before autovacuum triggers, default 0.2, i.e. 20 percent) and autovacuum_vacuum_threshold (a flat row-count floor added on top, default 50) together decide how often autovacuum runs on a given table; a large, heavily updated table often needs a lower scale factor set per-table so autovacuum does not wait for 20 percent of a hundred-million-row table to go dead before acting.
• VACUUM does not shrink the file on disk by default; it marks dead-version space as reusable for future inserts or updates on the same table. Only VACUUM FULL (which rewrites the table into a new, smaller file and takes an exclusive lock while doing so) or an online tool like pg_repack actually returns space to the operating system.
• Transaction id wraparound: Postgres transaction ids are a 32-bit counter, so they eventually wrap around. To keep old row versions from becoming ambiguous, Postgres periodically "freezes" old-enough row versions, marking them as permanently visible regardless of transaction id comparisons, and tracks the oldest un-frozen transaction id per table (relfrozenxid) and per database (datfrozenxid). autovacuum_freeze_max_age (default 200,000,000 transactions) is the hard ceiling: if a table's age crosses it, autovacuum is forced to run an aggressive freeze on that table regardless of the normal dead-tuple threshold, specifically to avoid the database refusing new writes to protect against wraparound corruption.
• What to monitor: age(relfrozenxid) per table and age(datfrozenxid) per database, both meaning "how many transactions old is the oldest unfrozen row," watched against autovacuum_freeze_max_age. A long-running transaction is the classic cause of a stuck vacuum, because Postgres cannot freeze or remove any row version a still-open transaction might still need to see, so one forgotten open transaction can single-handedly stall cleanup across the whole database while age keeps climbing.

Worked example

All of this from a live Postgres 16 instance.

Version-chain proof: table acct(id, balance). INSERT gives xmin=749, xmax=0. UPDATE balance=150 gives the new visible row xmin=750, xmax=0. Reading the raw page directly with pageinspect's heap_page_items shows both versions physically present: line pointer 1 has t_xmin=749, t_xmax=750 (the old, now-dead version, its t_ctid pointing forward to the new one), line pointer 2 has t_xmin=750, t_xmax=0 (the live version). That forward-pointing t_ctid chain is literally the version chain this question asks about; nothing was deleted, the old version is still on the page until vacuum removes it.

Bloat proof: a fresh table with 50,000 rows, updated in place 5 times (UPDATE bloat_demo SET v = v + 1, run 5 times, each rewriting every row as a new version). pg_stat_user_tables then shows n_live_tup=50000, n_dead_tup=250000 (5 times 50,000). pgstattuple confirms physically: table_len=10,878,976 bytes, dead_tuple_percent=73.54, free_percent=0.38. Running VACUUM (VERBOSE) reports tuples: 250000 removed, 50000 remain, removes 250,000 dead entries from the index too, and afterward n_dead_tup=0 and free_percent=83.07, but table_len is still exactly 10,878,976 bytes: the space was marked reusable, not returned to the operating system, which only VACUUM FULL would do.

Wraparound proof: on this fresh instance, age(datfrozenxid) for the database reads 32 (only 32 transactions old, essentially no wraparound risk yet), age(relfrozenxid) for the just-vacuumed table reads 2, and autovacuum_freeze_max_age is confirmed at its documented default of 200,000,000. A production table sitting at, say, 150,000,000 and climbing, with no long-running transaction to explain it, is the concrete shape of approaching the point autovacuum will force an aggressive freeze whether or not the maintenance window is convenient.

Trade-offs and pitfalls

The most damaging real-world mistake is a long-running transaction, a reporting query left open, a connection that never commits, an abandoned interactive session, sitting idle for hours or days: because Postgres cannot remove or freeze any row version that transaction's snapshot might still need, one forgotten open transaction silently disables cleanup for every table in the database, not just the one it queried, and both bloat and wraparound age climb together until something is noticed, often as sudden query slowdowns, or, in the worst case, the database refusing new transactions to protect against wraparound. A second pitfall is tuning autovacuum's scale factor globally and assuming it is fine everywhere: a flat 20 percent dead-tuple threshold is reasonable on a small table and much too lax on a hundred-million-row table, where 20 percent dead is tens of millions of bloated rows before cleanup even starts.

Direct answer

Binary search needs random access to comparable elements, which a naive whole-file compression scheme destroys, since it is not possible to decompress just the middle of a compressed stream without decompressing everything before it. The fix is to split the sorted array into fixed-size blocks, compress each block independently, and keep a small, always-in-memory sparse index mapping each block's first key to that block's byte offset in the file. A lookup binary-searches the tiny in-memory sparse index, never touching disk, to find the one block that could contain the target key, then decompresses and searches only that one block, which is the same layout idea behind a sorted-string table's (SSTable's) block index in engines like RocksDB (an embeddable key-value store built on a log-structured merge-tree, or LSM-tree, which buffers writes in memory and periodically merges them into new sorted files rather than updating in place) and LevelDB (the earlier, simpler LSM-tree key-value store RocksDB was originally forked from), and behind a full-text search library's term-dictionary blocks.

Structured elaboration

On-disk layout

The file is a sequence of independently compressed blocks, each holding a contiguous, sorted slice of the full key set, a fixed number of keys per block, or a fixed compressed-size budget per block. Each block is self-contained: decompressing block 400 never requires anything from block 399 or block 401.

The block index

For each block, record its first key and its byte offset, and length, in the file. Because there is one entry per block rather than one per key, this index is small, commonly a small fraction of a percent of the data size, and small enough to hold entirely in memory even for a very large underlying array, which is exactly what removes disk I/O from the binary-search step itself.

Lookup algorithm

1. Binary-search the in-memory sparse index for the last entry whose first key is less than or equal to the target key; that identifies the one block that could contain the target, since every other block's entire key range is provably on the wrong side.
2. Seek to that block's recorded offset, read exactly that block's bytes, and decompress only it.
3. Binary-search, or linear-scan for small blocks, inside the decompressed block for the target key.

Compression scheme considerations

Block-level, not element-level, compression is the key trade: compressing each block as one unit, rather than compressing each element individually, gets much better compression ratios, because compression algorithms exploit redundancy across nearby values, but it means the minimum unit of decompression work is one whole block, so block size is a direct trade between compression ratio (bigger blocks compress better) and wasted decompression work (bigger blocks mean more irrelevant data decompressed to find one key).

Worked example

Built and ran this exactly as described: 200,000 sorted integer keys, split into blocks of 128 keys each, each block's keys joined and compressed independently with a standard general-purpose compressor, plus a sparse index of first key, byte offset, and byte length per block.

import bisect, zlib, struct

def build_blocks(sorted_keys, block_size=128):
    blob, sparse_index = bytearray(), []
    for i in range(0, len(sorted_keys), block_size):
        block_keys = sorted_keys[i:i + block_size]
        raw = b"\x00".join(str(k).encode() for k in block_keys)
        compressed = zlib.compress(raw, level=6)
        offset = len(blob)
        blob.extend(struct.pack(">I", len(compressed)))
        blob.extend(compressed)
        sparse_index.append((block_keys[0], offset, len(compressed) + 4))
    return bytes(blob), sparse_index

def lookup(blob, sparse_index, target):
    first_keys = [e[0] for e in sparse_index]
    pos = bisect.bisect_right(first_keys, target) - 1
    if pos < 0:
        return False
    _, offset, _ = sparse_index[pos]
    (comp_len,) = struct.unpack(">I", blob[offset:offset + 4])
    raw = zlib.decompress(blob[offset + 4:offset + 4 + comp_len])  # only this block
    block_keys = [int(x) for x in raw.split(b"\x00")]
    lo = bisect.bisect_left(block_keys, target)
    return lo < len(block_keys) and block_keys[lo] == target

n = 200_000
sorted_keys = list(range(0, n * 2, 2))
blob, sparse_index = build_blocks(sorted_keys, block_size=128)
print(f"{n:,} keys -> {len(sparse_index):,} blocks, "
      f"sparse index = {len(sparse_index) * 16:,} bytes in memory")
print(f"compressed size {len(blob):,} bytes vs raw ~{sum(len(str(k))+1 for k in sorted_keys):,} bytes")
print("hit  40000 ->", lookup(blob, sparse_index, 40_000))
print("miss 40001 ->", lookup(blob, sparse_index, 40_001))

Output:

200,000 keys -> 1,563 blocks, sparse index = 25,008 bytes in memory
compressed size 349,987 bytes vs raw ~1,344,445 bytes
hit  40000 -> True
miss 40001 -> False

1,563 blocks for 200,000 keys at 128 keys per block, matching 200,000 divided by 128 exactly; the entire sparse index fits in about 25 KB, small enough to keep resident even for a much larger underlying array; the compressed file is about 26 percent of the raw size; and every lookup, hit or miss, decompresses exactly one of the 1,563 blocks, found via roughly 11 comparisons, log base 2 of 1,563 is about 10.6, against the in-memory index, never touching the other 1,562.

Trade-offs and pitfalls

The main tuning knob, block size, is a direct trade and there is no universally correct answer: smaller blocks mean less wasted decompression per lookup and a finer-grained, but bigger, sparse index; bigger blocks mean better compression ratios and a smaller sparse index, at the cost of decompressing more irrelevant data per lookup. The common mistake is picking a block size for compression ratio alone without checking what it does to point-lookup cost, or the reverse, picking a tiny block size for lookup speed and giving up most of the compression benefit the whole design exists to capture alongside fast access. A second pitfall specific to compressed blocks: a block's compressed length is not predictable from its uncompressed length, so the index must store each block's actual byte length and offset explicitly, as this design does, rather than assuming fixed-size blocks the way an uncompressed page-based layout could.

Direct answer

Crash recovery replays the write-ahead log (WAL, the append-only record of every change, written before it was applied), starting from the most recent checkpoint rather than the beginning of the log, and decides whether to reapply each logged change by comparing the log record's position, its log sequence number (LSN, a monotonically increasing pointer into the WAL stream), against the log sequence number already stamped on the affected page on disk: if the page's own stamped LSN is older than the log record's, the change never made it to disk and must be redone; if the page's LSN is already at or past the log record's, the change is already reflected and redoing it would be wrong, not just redundant. Checkpoints exist purely to give recovery a later, safe starting point than the beginning of time; fsync (the operation that forces buffered writes out of the OS's page cache and onto physical storage) frequency and group commit, batching several transactions' WAL flushes into one physical fsync, control how expensive each individual commit's durability guarantee is, trading a small amount of added per-commit latency for a large increase in sustained commit throughput.

Structured elaboration

How recovery uses WAL, concretely

Every dirty page carries the LSN of the last WAL record that modified it. The engine enforces a strict rule while running normally: a page is never written to its data file until the WAL record describing that page's most recent change has itself been durably written first, sometimes called the WAL-before-data invariant. This single invariant is what makes recovery correct: on restart, recovery scans forward from the last checkpoint's recorded LSN, and for each WAL record, compares that record's LSN to the current on-disk page's stamped LSN; only records newer than the page's stamped LSN get reapplied. This per-page LSN comparison, the same idea the classic ARIES crash-recovery algorithm that most WAL-based engines descend from is built around, is what makes redo safe to run unconditionally over every committed change since the checkpoint, including changes that had actually already made it to disk before the crash, without risk of double-applying a non-idempotent operation like an increment.

Checkpoints, from the recovery algorithm's point of view

A checkpoint records a WAL position and guarantees all pages dirtied before that position have been flushed to disk. Recovery's starting point is exactly that recorded position: everything before it is provably already durable in the data files, by the checkpoint's own guarantee, so replaying it again would be wasted work at best and, without the LSN-comparison rule above, actively unsafe at worst.

Fsync frequency and group commit: quantifying the trade-off

An fsync is a physical, comparatively slow storage operation, not a memory copy, so treating every single transaction's commit as its own fsync caps total commit throughput at one over the fsync latency, no matter how many client connections are committing concurrently, because they are all serializing on the same physical operation. Group commit batches multiple transactions' pending WAL flushes into one fsync: if b transactions share one fsync, the achievable commit throughput multiplies by b, at the cost of each transaction in the batch waiting for the fsync to actually happen rather than triggering its own immediately.

Concretely, with illustrative, not measured here, assumptions of a single fsync taking on the order of 1 millisecond, a commonly cited order of magnitude for enterprise flash storage with a well-behaved write cache, and no other bottleneck:

$\text{throughput}_{\text{no batching}} = \frac{1}{t_{fsync}} = \frac{1}{0.001\text{ s}} = 1{,}000 \text{ commits/s}$

$\text{throughput}_{\text{batch size } b=20} = \frac{b}{t_{fsync}} = \frac{20}{0.001\text{ s}} = 20{,}000 \text{ commits/s}$

The same single fsync device goes from a 1,000-commit-per-second ceiling to a 20,000-commit-per-second ceiling purely by batching 20 transactions' worth of durability into each physical operation; the cost is that a transaction now waits up to roughly one batching window, however long the engine waits to accumulate a batch, longer than it would have with its own dedicated fsync.

Trade-offs when tuning WAL behavior for high throughput

• Relaxing synchronous commit (Postgres's synchronous_commit = off; conceptually similar knobs exist elsewhere) removes the fsync wait from the commit path entirely: throughput is no longer capped by fsync latency at all, but a crash can lose the last window's worth of acknowledged commits, a real durability trade a team has to choose deliberately, not inherit by accident.
• Widening the group-commit batching window (Postgres's commit_delay/commit_siblings) trades a small, bounded amount of added latency per transaction for a large throughput gain under concurrent commit load, as shown above; it does nothing for a workload with only one commit in flight at a time, since there is nothing to batch with.
• Larger WAL buffers and background WAL writers reduce how often the WAL-writing process itself becomes a bottleneck independent of the fsync cost, relevant at very high write concurrency even before fsync latency is the limiting factor.
• None of these tuning knobs change what redo has to do on recovery; they only change how much unflushed, at-risk work exists at any given moment before a crash, which is exactly the durability side of the trade.

Worked example

The group-commit arithmetic above is the worked example: given the same physical fsync cost per operation, batching 20 commits into one fsync moves the sustained-throughput ceiling from 1,000 per second to 20,000 per second, a 20x improvement that comes entirely from amortizing one expensive operation across more logical work, not from making the operation itself faster.

Trade-offs and pitfalls

The common mistake is treating relaxed synchronous commit and group commit as interchangeable "make commits faster" knobs: they solve different problems. Group commit keeps the full durability guarantee, a reported-successful commit really did reach durable storage, and buys throughput by batching; disabling synchronous commit buys throughput and lower latency by weakening the guarantee itself, an acceptable trade for some workloads, a cache-like table that can tolerate losing its last few seconds of writes on a crash, and an unacceptable one for others, financial transaction records, and the two should never be confused when deciding which to reach for. The second pitfall is tuning fsync frequency in isolation from checkpoint frequency: a system that fsyncs rarely, or not at all, but checkpoints frequently is paying checkpoint I/O cost for a durability guarantee it is not actually providing on the commit path.

Direct answer

A B-tree index (in almost every production database this really means a B+-tree: a self-balancing tree where every row pointer lives at the leaf level, and leaf pages are linked to their neighbors) keeps keys sorted at every level. Because the leaves are sorted and linked, finding a range's start takes one root-to-leaf descent (height, typically 2 to 4 levels even for hundreds of millions of rows), and after that the engine walks sideways along the leaf chain instead of re-descending for each row, which is why range queries are cheap. Inserts and deletes stay balanced by splitting a page that overflows and allowing a page to run under capacity rather than aggressively merging on every delete, so the tree's height only grows when the root itself splits, keeping lookups at roughly log(n) page reads.

How B-tree balance, splits, and concurrency interact

• Structure: every page holds a sorted array of (key, pointer) entries. Internal pages point to child pages; leaf pages point to the actual row (or, for a clustered index like InnoDB's primary key, contain the row itself). Fanout, how many entries fit in one page, determines height: with fanout F, a tree over N keys needs roughly ceil(log base F of N) levels.
• Insert: the engine descends to the correct leaf and inserts in sorted order. If the leaf has room, this is a single page write. If it is full, the leaf splits: half its entries move to a new page, and a separator key is inserted into the parent, pointing at the new sibling. If the parent is also full, the split cascades upward; the tree only grows a level when the root itself splits, which is what keeps height balanced rather than letting the tree degrade into an unbalanced structure.
• Delete: the entry is removed from its leaf. Well-behaved implementations let a leaf run under its target fill percentage rather than merging on every delete (merging on every delete would thrash under mixed insert/delete workloads); many engines instead reclaim mostly-empty pages lazily.
• Why splits cost more than the one write they look like: a split has to write the original page, the new sibling page, and the parent page that now holds one more separator key. Under write-ahead logging (WAL, the mechanism where every page change is described in a log record and forced to disk before the change is considered durable) each of those pages generates its own log record, so one logical insert can produce a page's worth of extra durable writes: that is the "write amplification" indexes add on top of the base table's own write. Concurrency-wise, a split has to briefly hold an exclusive lock (a short, in-memory latch, not a transactional row lock) on the splitting page and its parent while it moves entries and updates the parent's pointer; concurrent readers that land mid-split are not blocked in most modern engines (Postgres's B-tree implementation, for example, lets a reader who arrives at a just-split page follow a temporary "right link" to the new sibling instead of waiting), but concurrent writers targeting the same page do queue briefly.

Worked example

I built this on a live Postgres 16 instance: a 3,000,000-row orders table with a plain B-tree index on order_date, then ran EXPLAIN (ANALYZE, BUFFERS) (Postgres's command to show the actual, executed query plan, including real row counts and I/O, not just the planner's estimate) for a 7-day range predicate (order_date >= '2021-06-01' AND order_date < '2021-06-08'), matching 11,669 of the 3,000,000 rows.

Without the index (parallel sequential scan): Buffers: shared hit=16056 read=6003 dirtied=7080 written=5907, filtering out 996,110 rows per worker, 70.977 ms.
With the index (a bitmap index scan, which uses the index to find matching row locations instead of reading the whole table, then a bitmap heap scan to fetch just those rows): Buffers: shared hit=1252 read=526 written=464 for the base table plus shared read=13 for the index itself, roughly 1,791 buffer touches total (1,252 + 526 + 13), against about 22,059 without the index, 7.037 ms.

pageinspect's bt_metap('idx_orders_date') reports the index root is at level = 2, meaning the tree has 3 levels (root, one internal level, leaf level) over those 3,000,000 rows: 2,615 leaf-level pages at 8 KB each (20 MB total), and the root page held only 13 downlink entries (checked with bt_page_stats), because at the root you only need enough entries to address every second-level page, not every leaf. That 13-entry root points directly to those same 13 second-level pages, and each second-level page in turn addresses roughly 201 leaf pages (2,615 leaf pages / 13 second-level pages is about 201): together that is the concrete shape of "height stays logarithmic": adding a million more rows would not add a fourth level until fanout at the second level was exhausted too.

Trade-offs and pitfalls

Every additional B-tree index is a second (or third, or tenth) sorted copy of a subset of the table's columns: each insert into the base table now also does an insert into every index on it, each of those inserts can itself trigger a split, and each split is extra write-ahead-log volume and extra page writes on top of the row's own write. On a workload that mixes a frequent-write pipeline (an extract-transform-load, ETL, job loading rows continuously) with frequent ad hoc dashboard reads, this is a real trade-off: the indexes that make the dashboard's queries fast are the same indexes slowing down the ETL job's inserts and growing on-disk size roughly in proportion to how many columns are indexed. The common mistake is treating "add an index" as free because one SELECT got faster; the honest comparison is against the write path's added cost, not just the read path's benefit. A second pitfall is assuming insert cost is independent of key shape. Monotonically increasing keys (an auto-increment ID, a timestamp) mostly append at the rightmost leaf, which splits far less often than a workload inserting uniformly random keys across the whole key space, because random inserts hit a different, potentially already-full leaf every time.

Direct answer

A transactional storage engine prototype with ACID guarantees (atomicity, consistency, isolation, durability: the four properties a transaction is supposed to provide) needs five cooperating pieces: an in-memory buffer pool holding cached pages, a write-ahead log (WAL) for durability and crash recovery, a concurrency-control mechanism, locking or multi-version concurrency control (MVCC), that keeps concurrent transactions from corrupting each other's view of the data, a background checkpoint (periodically flushing recent changes to durable storage and marking how far crash recovery would need to replay from) and compaction process (merging accumulated on-disk files together so read cost does not grow unbounded) that bounds how much log has to be replayed after a crash, and a crash-recovery routine that rebuilds correct state from the WAL plus whatever made it to durable pages before the crash. The core design decision that shapes everything else is page-oriented in-place storage with a B-tree (favoring predictable read latency, higher per-write cost) versus log-structured storage with an LSM-tree (favoring high write throughput, higher and more variable read cost); this prototype describes the architecture in page and B-tree terms, since it generalizes cleanly to either.

Structured elaboration

graph TD
  C[Client transaction] --> BUF[Buffer pool: cached pages]
  C --> WAL[WAL: append change record + fsync at commit]
  WAL --> BUF
  BUF --> PAGES[Data pages / SSTables on disk]
  CK[Checkpoint process] -->|flushes dirty pages| PAGES
  CK -->|advances redo start point| WAL
  CC[Concurrency control: 2PL or MVCC] --> C
  CRASH[Crash recovery] -->|replay from last checkpoint| WAL
  CRASH -->|reconstruct| PAGES

Core data structures

• Pages: fixed-size units (commonly 4 to 16 KB) holding either index entries (a B-tree's internal and leaf pages) or row data; the unit of I/O and of the buffer pool's caching.
• Buffer pool: an in-memory hash table of page id to cached page, with a dirty flag per page (has this page been modified since it was last written to disk) and an eviction policy (commonly a variant of least-recently-used) to decide what to evict under memory pressure.
• WAL: an append-only log of transaction id, page or key change, and before/after or redo/undo information, plus commit and abort markers.
• Index and data files: a B-tree, or, in the LSM variant, a memtable (in-memory write buffer) plus immutable sorted files merged by compaction.

Transaction logging (WAL)

Every change is written to the WAL and fsynced (forced out of the OS's write buffer and confirmed durably on disk, not just handed to the kernel) before the transaction is allowed to report success: the in-memory page can be modified immediately, but the durability guarantee comes entirely from the log record having reached disk, not from the page write, which can happen later.

Concurrency control: locking versus MVCC

• Two-phase locking (2PL: every transaction acquires all the locks it needs before releasing any of them, guaranteeing serializability but making readers and writers block each other) is simpler to reason about and gives strong isolation directly, at the cost of read and write contention: a long-running writer blocks readers of the same rows, and vice versa.
• MVCC (multi-version concurrency control: each transaction sees a consistent snapshot of committed data as of when it started, while writers create new versions rather than overwriting in place) lets ordinary readers and writers proceed without blocking each other, at the cost of needing a mechanism to garbage-collect old versions and, depending on the isolation level chosen (the rule governing how much of other transactions' concurrent changes a transaction is allowed to see), still needing some locking or conflict detection to prevent write-write conflicts and anomalies like write skew (two transactions each reading a valid individual snapshot but together violating an invariant neither would have permitted alone).
• This prototype's default: MVCC for reads, non-blocking, since read-heavy contention is the common case, combined with row-level or key-range locking specifically for write-write conflicts, the same hybrid most production engines actually use rather than a pure implementation of either extreme.

Checkpointing and background compaction

A checkpoint periodically forces all dirty pages up to some WAL position out to disk and records that position; crash recovery then only needs to replay WAL from the most recent checkpoint forward, not from the beginning of the log, which is what bounds recovery time. In the LSM variant, this same role is partly played by memtable flushing, turning in-memory writes into an immutable file, after which the WAL for those writes can be discarded, plus background compaction merging files together to keep read cost from growing unbounded as more files accumulate.

Crash recovery algorithm

A standard three-phase approach: (1) analysis, scan forward from the last checkpoint to determine which transactions were in progress and which pages were dirty at crash time; (2) redo, replay every logged change from the checkpoint forward, regardless of whether its transaction eventually committed, to bring the data files back to exactly the state they were in at the moment of the crash; (3) undo, roll back the changes made by any transaction still in progress, never committed, at crash time, using the before-image or inverse-operation information the WAL recorded for exactly this purpose. Redoing everything first and undoing incomplete transactions second, rather than trying to skip redoing transactions that look uncommitted, is deliberate: it is simpler and more robust, because it does not require correctly identifying every in-flight transaction before touching any data, only after reconstructing the full crash-time state.

Worked example

Trace a single transaction through this design: begin; update a row, modifying the cached page in the buffer pool and appending a WAL record describing the change, not yet fsynced; commit, which fsyncs the WAL up through this transaction's commit record and only then reports success to the client; the modified page in the buffer pool stays dirty and gets written to disk later, either because it is evicted under memory pressure or because the next checkpoint flushes it. If the process crashes one second after that commit, before the page itself was ever written to disk: on restart, recovery's redo phase replays the WAL record for this transaction's change, since its commit record is present, and reconstructs the modified page in memory correctly, even though the on-disk page file never physically received the write, exactly the property that a WAL record is what is durable and the page write is a lazy optimization on top of it.

Trade-offs and pitfalls

Durability, latency, and throughput pull against each other at almost every decision point here: fsyncing every commit's WAL individually gives the strongest per-transaction durability guarantee but the worst latency and throughput under concurrent load, unless group commit, batching multiple transactions' WAL flushes into one fsync, is implemented; choosing 2PL over MVCC gives simpler correctness reasoning but worse concurrency for read-heavy workloads; a short checkpoint interval bounds recovery time tightly but adds continuous background I/O competing with foreground traffic. The common design mistake is picking each of these independently, tightest possible durability, most concurrent possible reads, shortest possible checkpoint interval, without recognizing they compound: a system tuned that way pays every latency and I/O cost simultaneously instead of choosing where it can actually afford to spend budget for the workload it is built for.