Database Internals

Contents

• Part 01 · Storage Engines
  01Introduction and Overview
  02B-Tree Basics
  03File Formats
  04Implementing B-Trees
  05Transaction Processing and Recovery
  06B-Tree Variants
  07Log-Structured Storage
• Part 02 · Distributed Systems
  08Introduction and Overview
  09Failure Detection
  10Leader Election
  11Replication and Consistency
  12Anti-Entropy and Dissemination
  13Distributed Transactions
  14Consensus

Introduction and Overview

Establishes the conceptual map of a DBMS, decomposing it into transport, query processor, execution engine, and storage engine, then introduces the taxonomies — memory vs. disk resident, row vs. column, OLTP vs. OLAP, mutable vs. immutable — that classify every storage engine in the book.

DBMS Architecture Layers

A database is split into a transport subsystem (client and peer communication), a query processor (parser, optimizer), an execution engine, and a storage engine. Understanding these boundaries clarifies where each design decision lives — the storage engine alone owns durability, concurrency, recovery, and on-disk layout.

Memory-Resident vs. Disk-Resident

In-memory engines treat RAM as primary and disk as a log/backup; disk-based engines treat disk as primary and RAM as a cache. This single choice cascades into data-structure selection: T-trees and skip lists for memory-resident, B-trees and LSM-trees for disk-resident.

Row-Oriented vs. Column-Oriented

Row stores keep all fields of a record contiguous, which is ideal for OLTP point lookups and full-row reads. Column stores keep values of the same attribute contiguous, which is ideal for OLAP scans, aggregations, and aggressive compression because columns are homogeneous in type.

OLTP vs. OLAP vs. HTAP

OLTP is many small, latency-sensitive transactions touching few rows; OLAP is long-running aggregate queries over huge data sets; HTAP systems try to serve both from one engine. Workload shape — not the data model — determines which storage engine fits.

Mutable vs. Immutable Storage

Engines that update records in place (B-trees) optimize for read latency and predictable space use. Engines that only append (LSM-trees) optimize for write throughput by turning random writes into sequential ones, at the cost of background compaction work.

Comparing Databases Is Hard

Benchmarks, feature lists, and CAP-style labels mislead more than they inform. The only reliable basis for comparison is understanding how an engine actually handles writes, indexes, durability, and concurrency under your specific workload.

Storage engine

The DBMS layer that organizes data on the underlying medium and exposes read/write/update/delete primitives.

Query optimizer

Transforms a parsed query into an efficient execution plan by choosing join order, access paths, and indexes.

OLTP

Online Transaction Processing — many short, latency-sensitive transactions.

OLAP

Online Analytical Processing — long-running, read-mostly queries over large data sets.

HTAP

Hybrid Transactional/Analytical Processing — one engine serving both workloads.

Buffer pool

In-memory cache of disk pages managed by the storage engine to amortize I/O.

Page

The fixed-size unit of disk-to-memory transfer, aligned to filesystem or hardware block size.

Transport subsystem

The layer that manages client and inter-node communication.

Multiple choice

Your team is benchmarking three databases for a workload of long-running aggregate queries across billions of rows with very few writes. Which storage-engine property matters most for picking a winner?

• AWhether records are stored row-oriented or column-oriented
• BWhether the engine uses a B-tree or LSM-tree
• CWhether the engine is memory-resident or disk-resident
• DWhether the engine supports HTAP labels in its marketing

Multiple choice

A vendor claims their engine is "the fastest database" based on a generic benchmark and a CAP-style label. According to the chapter, what is the most reliable way to actually compare engines?

• ATrust independent third-party benchmark suites
• BCompare advertised feature lists side by side
• CUnderstand how each engine handles writes, indexes, durability, and concurrency under your workload
• DPick whichever has the strongest CAP guarantees

Spot the issue

A team picks an LSM-tree engine for a read-latency-critical OLTP workload with very few writes, citing "LSM is the modern choice." What's the main risk?

• ALSMs cannot durably persist data without a separate WAL service
• BLSMs cannot store row-oriented data, so OLTP point lookups will fail
• CLSMs require column-oriented schemas that OLTP rarely uses
• DLSMs optimize for write throughput at the cost of read amplification, so a read-heavy workload pays for an optimization it doesn't need

True / False

The storage engine is the DBMS layer responsible for parsing SQL and choosing an execution plan.

• TrueTrue
• FalseFalse

B-Tree Basics

Motivates why B-trees became the dominant on-disk index by contrasting them with binary search trees and hash indexes, then walks through their core invariants: high fanout, balanced height, and block-aligned nodes. Establishes the vocabulary needed before the operational treatment in Chapter 4.

Why Not Binary Search Trees on Disk

A BST has fanout 2 and unpredictable balance, so on disk it means deep trees and many random I/Os per lookup. Worse, each node is far smaller than a disk block, wasting almost the entire page on every read.

Block-Oriented Design

B-trees pack hundreds or thousands of keys per node so a single page read yields many comparisons. Node size is deliberately matched to the underlying page/block size — the unit of physical I/O — so no read is ever wasted.

High Fanout, Low Height

Because each internal node has hundreds of children, even billion-record B-trees are only 3-4 levels deep. Tree height is logarithmic in the number of records but with an enormous base, which bounds the number of I/Os per lookup.

Balanced by Construction

B-trees guarantee that all leaves sit at the same depth. Splits propagate upward toward the root rather than letting one path grow long, so worst-case and average-case lookup latencies stay close.

B+ Tree Variant

In the variant used by virtually every modern database, all data lives in the leaves and internal nodes hold only separator keys. Leaves are linked into a sequence so range scans walk the leaf chain instead of re-traversing the tree.

Occupancy Invariants

Each node must stay between a minimum (often half full) and maximum capacity. Violations trigger splits or merges, which is what keeps the tree both balanced in height and reasonably full on disk.

B-tree

A self-balancing, block-oriented search tree with high fanout, designed for block-addressable storage.

B+ tree

A B-tree variant where data lives only in leaves and internal nodes hold only separators; leaves are typically linked.

Fanout

The number of children an internal node can have; high fanout gives B-trees their shallow depth.

Separator key

A key in an internal node used to route searches to the correct child subtree.

Occupancy

The fraction of a node's capacity in use, bounded above and below.

Tree height

The number of edges from root to leaf; logarithmic in record count with base equal to fanout.

Root, internal node, leaf

The three structural roles — entry point, router, and data holder.

Node (page)

One tree node corresponds to one page on disk; the unit of allocation and I/O.

Multiple choice

A B-tree indexes one billion records with a fanout of roughly 500 per internal node. Approximately how many disk page reads does a single point lookup require in the worst case?

• AAbout 30 (log base 2)
• BAbout 10 (log base 10)
• CAbout 3-4 (log base 500)
• DAbout 500 (one read per fanout slot)

Multiple choice

Why is a balanced binary search tree a poor on-disk index, even though it gives O(log n) lookups in memory?

• ABSTs cannot store variable-length keys
• BEach BST node is far smaller than a disk block, so every read wastes nearly an entire page and tree depth is large
• CBSTs cannot be balanced once stored on disk
• DBSTs do not support range scans

Multiple choice

A workload runs frequent range scans over sorted ranges of keys. Which B-tree variant trait makes these scans cheap?

• AStoring data only in leaves and linking leaves into a sequence, so scans walk the leaf chain
• BStoring all data in internal nodes so scans never touch leaves
• CUsing fanout 2 to keep range scans simple
• DRequiring readers to re-descend from the root for every range step

Spot the issue

A custom B-tree implementation skips occupancy invariants — nodes are allowed to become arbitrarily empty after deletes and arbitrarily full before splits. What's the main consequence?

• AThe tree loses balance guarantees and either wastes massive disk space or degrades to deep, unbalanced paths
• BThe tree silently corrupts data on reads
• CRange scans stop working because sibling links break
• DInternal nodes can no longer hold separator keys

File Formats

Zooms out from the tree algorithm to the bytes on disk: how database files are organized into pages, how pages hold variable-length records, and how slotted pages, headers, cell pointers, checksums, and magic numbers make files self-describing, robust, and version-evolvable.

Files as Page Arrays

A database file is a sequence of fixed-size pages identified by page IDs. A page ID translates directly to a file offset by multiplication, so any page can be located in O(1) without an index.

Slotted Page Layout

The canonical solution for variable-length records: an array of slot pointers grows from one end of the page while cell payloads grow from the other, with free space in the middle. This decouples logical order (slot order) from physical layout.

Cells and Cell Pointers

Variable-length payloads are stored as cells. An indirection array of slot pointers holds the byte offsets of cells, so the page can reorder its logical contents without physically moving bytes — and external pointers can target a slot without breaking on in-page reorganization.

Page Header

Every page begins with a fixed-size metadata block: page type, free-space pointers, cell count, checksum, and sometimes sibling pointers. The header is what makes a page self-identifying after a crash or upgrade.

Magic Numbers, Checksums, Versioning

Files embed magic bytes identifying the format, a version number so the engine can evolve the layout, and per-page checksums (often CRC) to detect silent corruption. Together they make the file format both robust and forward-compatible.

Logical vs. Physical Pointers

Within a page, cells reference one another by slot index (logical), so in-page compaction never invalidates references. Across pages, references use page IDs (physical), which decouples in-page reorganization from cross-page links.

Page

A fixed-size, contiguous region of a database file; the unit of I/O.

Slotted page

A page layout with a header, slot pointers growing from one end, and cell payloads growing from the other.

Cell

The on-page representation of a single record, variable in size.

Cell pointer (slot)

A small fixed-size entry giving the offset and length of a cell.

Page header

Fixed-size metadata block at the start of a page.

Checksum

Value computed over a page's bytes, stored in the header to detect corruption.

Magic number

Byte sequence at the start of a file identifying its format and version.

Varint

Variable-length integer encoding using fewer bytes for small values.

Page ID

Logical identifier that maps to a page's offset in the file.

Multiple choice

A database file is laid out as a sequence of fixed-size pages. How does the engine locate page N within the file?

• AIt maintains a separate index file mapping page IDs to offsets
• BIt scans page headers sequentially until it finds the one with matching ID
• CIt multiplies the page ID by the page size to get a direct file offset
• DIt hashes the page ID into a bucket-indexed lookup table

Multiple choice

Why does the slotted page layout grow the slot pointer array from one end of the page and cell payloads from the other, leaving free space in the middle?

• AIt allows the engine to compress the page on the fly
• BIt decouples logical (slot) order from physical layout, so cells can be reordered or compacted without breaking external pointers
• CIt is required by the underlying filesystem's block layout
• DIt makes checksums cheaper to compute

Multiple choice

An on-disk database file silently has a few bits flipped by a failing storage device. Which mechanism described in the chapter detects this corruption?

• AThe magic number at the start of the file
• BThe version number in the file header
• CThe per-page checksum stored in the page header
• DThe slot pointer array at the bottom of each page

Spot the issue

An engineer proposes that, within a page, cells should reference each other by absolute byte offset rather than by slot index, "to save one level of indirection on reads." What goes wrong?

• ACells can no longer be variable-length
• BPage IDs can no longer be translated to offsets
• CThe page header can no longer store a checksum
• DAny in-page compaction that moves a cell invalidates every reference pointing into the page

Implementing B-Trees

The operational counterpart to Chapter 2: how the abstract algorithms (search, insert, delete, split, merge) actually run on top of the slotted-page format from Chapter 3, plus the engineering refinements real systems use — sibling links, rightmost-append optimization, key compression, bulk loading, and free-page management.

Page Splits

When an insert would overflow a node, the node is split in two: roughly half the entries go to each half and a new separator is promoted to the parent. The split can cascade up to the root, which is the only way a B-tree grows taller.

Page Merges and Redistribution

When a delete leaves a node under-occupied, the engine either redistributes entries with a sibling (cheap) or merges two siblings into one and removes the separator from the parent (more expensive). Like splits, merges can cascade upward and reduce tree height.

Sibling Links Between Leaves

Leaves carry pointers to the next (and sometimes previous) sibling, so a range scan walks the leaf chain without re-descending the tree. These links must be maintained carefully through splits and merges, especially under concurrent access.

Rightmost-Leaf Optimization

Monotonically increasing keys — autoincrement IDs, timestamps — always hit the rightmost leaf. Engines special-case this path to append or split sparsely instead of doing 50/50 splits that would leave half-empty pages forever.

Key Compression

Adjacent keys on a node usually share a prefix. Prefix compression stores only the differing bytes; suffix truncation picks the shortest separator that still distinguishes children. Both pack more keys per page and raise fanout.

Bulk Loading

Building a B-tree from sorted input by filling leaves to capacity and constructing internal levels bottom-up produces a denser, better-balanced tree than repeated inserts. Used when restoring backups or building a new index.

Latch Coupling

Operations that change tree structure must coordinate access to multiple pages. Latch coupling (crabbing) acquires a child latch before releasing the parent's, ensuring safe navigation even as splits and merges run concurrently.

Page split

Structural modification that creates a new sibling when a node overflows, promoting a separator upward.

Page merge

Structural modification that combines two under-occupied siblings into one.

Redistribution

Moving entries between siblings to restore occupancy without merging.

Sibling pointer

A pointer linking a node to its same-level neighbor, used for scans.

Prefix compression

Storing only the differing suffix of each key against a shared page-wide prefix.

Suffix truncation

Choosing the shortest separator key needed to split left from right.

Bulk loading

Building a B-tree bottom-up from sorted input rather than via insertions.

Latch vs. lock

Latches are short-lived primitives on in-memory pages; locks are transactional and protect logical data.

Latch coupling (crabbing)

Holding a child latch before releasing the parent's during traversal.

Multiple choice

A table's primary key is a monotonically increasing autoincrement ID, and the engine uses standard 50/50 splits on every insert at the rightmost leaf. What inefficiency does the chapter call out?

• AInserts will deadlock with concurrent reads on the rightmost leaf
• BThe root node grows uncontrollably tall
• CThe rightmost leaf's sibling link breaks each time a split occurs
• DEvery split leaves roughly half-empty pages that never refill, wasting disk space and lowering fanout

Multiple choice

Building a fresh B-tree index from a large already-sorted dataset, which approach produces the densest and most balanced result?

• AInserting records one at a time into an empty tree
• BInserting records in random order to avoid the rightmost-leaf hot spot
• CFilling leaves to capacity from the sorted input and constructing internal levels bottom-up
• DPre-splitting the root into a fixed number of subtrees, then inserting

Multiple choice

Concurrent inserts are running on a B-tree while another thread is descending it for a lookup. Which technique ensures the descending thread does not navigate into a page mid-split?

• ALatch coupling: hold the child's latch before releasing the parent's during descent
• BAcquiring a single tree-wide write latch for any structural change
• CAborting and restarting the lookup whenever any insert is in progress
• DReplacing latches with full transactional locks for the duration of the descent

Spot the issue

A team disables prefix compression and suffix truncation on internal nodes, arguing the code is simpler and "modern disks are fast." What's the main downside the chapter highlights?

• AWithout compression the tree no longer satisfies occupancy invariants
• BSplits can no longer cascade up to the root
• CSibling links between leaves stop being maintained correctly
• DFewer keys fit per page, so fanout drops and the tree becomes taller, increasing I/Os per lookup

Transaction Processing and Recovery

Explores how databases guarantee ACID through the interplay of buffer manager, lock manager, page cache, and log manager. Walks through buffer policies (steal/no-steal, force/no-force), the ARIES recovery algorithm with its three phases, and concurrency control mechanisms from 2PL through OCC to MVCC.

ACID Properties

Atomicity guarantees all-or-nothing; Consistency preserves invariants; Isolation hides concurrent effects; Durability ensures committed data survives crashes. These four guarantees are the contract a transaction manager must honor.

Write-Ahead Log

A durable append-only log where every change is recorded before being applied to data pages. Durability falls out of WAL persistence, and recovery falls out of WAL replay — without a WAL there is no ACID.

Steal and Force Policies

Steal allows dirty (uncommitted) pages to be flushed (requires UNDO logging); No-Force lets committed pages stay in memory at commit (requires REDO logging). Most modern systems pick steal + no-force for performance, which mandates both UNDO and REDO in the WAL.

ARIES Recovery

A three-phase algorithm: Analysis scans forward from the last checkpoint to rebuild the dirty-page and transaction tables; Redo repeats history by reapplying all logged updates; Undo rolls back losers using compensation log records (CLRs) so undo itself is idempotent and can be redone if recovery is interrupted.

Concurrency Control Approaches

Pessimistic (lock-based, e.g., 2PL) assumes conflicts and prevents them up front; Optimistic (OCC) lets transactions proceed and validates at commit; Multi-version (MVCC) keeps multiple versions so readers don't block writers. Each trades latency, throughput, and abort rate differently.

Isolation Levels and Anomalies

Read Uncommitted, Read Committed, Repeatable Read, Snapshot Isolation, and Serializable progressively rule out anomalies — dirty reads, non-repeatable reads, phantom reads, lost updates, and write skew. Snapshot isolation prevents most anomalies but still allows write skew.

Latches vs. Locks

Locks are logical, protect rows or tables, last for the whole transaction, and live in the lock manager. Latches are physical, protect in-memory page structures, last microseconds, and are essentially mutexes — confusing them is one of the classic database bugs.

LSN

Log Sequence Number — monotonically increasing WAL record ID; orders operations and tracks which records have been applied.

Checkpoint

A persisted snapshot of dirty-page and active-transaction state that bounds recovery work.

CLR

Compensation Log Record — a record written during undo that makes undo idempotent.

Dirty Page Table

In-memory structure tracking buffer-pool pages with unflushed modifications.

Snapshot Isolation

MVCC level where each transaction reads from a consistent snapshot taken at its start.

Phantom Read

Range query returns rows inserted by another transaction between executions.

Deadlock detection

Building a waits-for graph and breaking cycles by aborting a victim.

Buffer pool

In-memory page cache whose eviction policy interacts with the WAL via steal.

Multiple choice

A storage engine uses the steal + no-force buffer policy. Which combination of logging is mandatory for correct recovery?

• AREDO only — committed data may still be in the buffer pool at crash time
• BUNDO only — dirty uncommitted pages may have been flushed to disk
• CBoth UNDO and REDO — uncommitted pages can hit disk and committed pages can be lost from memory
• DNeither — the WAL alone is sufficient regardless of buffer policy

Multiple choice

During ARIES recovery, why are Compensation Log Records (CLRs) written during the Undo phase rather than simply rolling back in memory?

• ACLRs compress the log to reduce recovery time
• BCLRs let the lock manager re-acquire row locks for aborted transactions
• CCLRs make undo idempotent so a crash mid-recovery can safely re-redo the undo work
• DCLRs let the DBA inspect which transactions were rolled back

Spot the issue

A team debugging a deadlock decides to hold page latches for the duration of each transaction instead of just for the page operation, hoping this will serialize access. What's wrong?

• ALatches don't serialize at all — they're just hints to the buffer manager
• BLatches protect physical in-memory structures and aren't meant to span transactions; this will collapse throughput and still won't fix logical deadlocks
• CLatches can't be held longer than 1ms by the kernel scheduler
• DLatches and locks are interchangeable; the real bug is using 2PL at all

Multiple choice

A workload runs at Snapshot Isolation. Two concurrent transactions each read the same two on-call rows, then each updates a different row to preserve the invariant "at least one doctor must remain on call." Both commit, and the invariant is violated. Which anomaly occurred?

• ADirty read
• BPhantom read
• CNon-repeatable read
• DWrite skew

B-Tree Variants

Surveys alternative B-tree designs that address shortcomings of the classic B+Tree — concurrency bottlenecks, write amplification from in-place updates, and poor fit for flash. Variants include copy-on-write trees, lazy B-trees, FD-trees, Bw-trees, and the B-link concurrency optimization.

Copy-on-Write B-Trees

Instead of mutating pages in place, modifications write new copies of affected pages and propagate up to a new root. This yields wait-free reads and crash safety without a WAL (used by LMDB), at the cost of write amplification and shadowing the entire path on every write.

Shadow Paging

The mechanism underlying copy-on-write: a shadow version of the tree is built, then committed by atomically swapping the root pointer. Old versions remain readable until garbage collected, which is what enables snapshot reads for free.

B-link Trees

Each node carries a right-sibling link, and node splits become a two-step process: link the new node into the sibling chain first, then register it in the parent. A descending reader that lands on a node that has since split can simply follow the link, allowing lock-free or minimally-locked descent.

Lazy B-Trees

Each node has an in-memory write buffer that absorbs small random writes; buffers are flushed in bulk. This amortizes I/O cost across many operations and is the strategy used by buffered-tree designs like WiredTiger.

FD-Trees

Designed for flash storage: a small head B-tree sits over a cascade of sorted runs on flash, using fractional cascading so lookups stay efficient while writes become sequential. This reduces write amplification, which matters because flash wears out with random writes.

Bw-Trees

A latch-free B-tree variant from Microsoft Research that maps page IDs to memory via a mapping table, with updates installed as delta records chained via compare-and-swap. Periodic consolidation flattens chains; the design is well-suited to multicore in-memory workloads where latches become the bottleneck.

Copy-on-write

Writes create new pages instead of mutating; the root swap is the commit point.

Shadow paging

The mechanism behind copy-on-write — build a shadow tree, atomically swap the root.

B-link tree

B-tree with right-sibling pointers enabling concurrent descent through in-progress splits.

Delta chain

Bw-tree's linked list of update records prepended to a base page.

Mapping table

Bw-tree's indirection layer mapping page IDs to in-memory pointers.

Consolidation

Bw-tree process of flattening a delta chain back into a single base page.

Write amplification

Bytes physically written per byte logically written by the application.

Fractional cascading

Inter-level pointer hints that reduce multi-level search cost from O(log²n) to O(log n).

Multiple choice

A copy-on-write B-tree like LMDB modifies a leaf record. Which set of pages physically gets rewritten on disk before the commit becomes visible?

• AOnly the leaf containing the modified record
• BThe leaf and every page on the path from root to that leaf, plus a new root pointer swap
• CEvery page in the tree, since immutability requires a full snapshot
• DThe leaf plus its left and right siblings

True / False

In a B-link tree, a reader that descends to a node which has since been split by a concurrent writer must restart its traversal from the root.

• TrueTrue
• FalseFalse

Multiple choice

What is the role of the mapping table in a Bw-tree, and why does it enable latch-free updates?

• AIt maps keys to disk offsets so writers never collide on the same key
• BIt maps page IDs to in-memory pointers, so an update installs a new delta chain head via a single compare-and-swap on the table entry
• CIt caches recent reads so writers can skip the buffer pool
• DIt maps transaction IDs to versions for MVCC visibility checks

Spot the issue

An engineer picks a copy-on-write B-tree for a workload of many small random updates, expecting "no WAL means faster writes." A month later they're seeing terrible write throughput and far more bytes hitting disk than expected. What's the chapter-level diagnosis?

• ACopy-on-write requires an external WAL anyway; they should add one
• BThe shadow paging root swap can't keep up with random updates
• CEach small update rewrites the entire root-to-leaf path, so write amplification is large — exactly the wrong fit for high-rate small random updates
• DRotating disks can't support atomic root pointer swaps

Log-Structured Storage

Introduces log-structured merge trees as an alternative to in-place B-tree updates, optimizing for write-heavy workloads by buffering in a memtable and flushing immutable SSTables. Covers compaction strategies, bloom filters, the three amplification factors, and the read-path machinery (tombstones, sparse indexes, merge iterators) that makes LSMs viable.

LSM Tree Architecture

Writes go to an in-memory memtable (skip list or balanced tree); when full, the memtable is flushed to disk as an immutable SSTable. Reads must consult the memtable and potentially many on-disk SSTables, merged at read time.

SSTables

Sorted String Tables — immutable on-disk files with key-sorted entries, a sparse index, and a metadata footer. Immutability means reads need no locking, writes are pure sequential I/O, and compaction can merge files cheaply.

Compaction Strategies

Size-tiered (Cassandra) groups same-size SSTables and merges them — high write throughput, more space amplification. Leveled (RocksDB, LevelDB) keeps non-overlapping SSTables per level — lower space and read amplification, more write amplification.

The Three Amplifications

Write amplification is bytes written to disk per byte of user write; read amplification is on-disk reads per user lookup; space amplification is disk space per byte of live data. LSM tuning is fundamentally about trading these three off — you cannot minimize all simultaneously.

Bloom Filters

Per-SSTable probabilistic structures that definitively say a key is absent (no false negatives) and may give "possibly present" for hits. They eliminate disk seeks for misses, which is what keeps point-lookup read amplification manageable.

Tombstones

Special delete markers that suppress earlier values during merges. A tombstone can only be discarded once compaction guarantees no older shadowed value of the key remains — which is why deletes in LSMs are not free.

Merge Iterators

A read consults the memtable and SSTables newest to oldest, using a priority-queue-style merge iterator that yields the newest version of each key while skipping shadowed entries and tombstones. The same machinery powers range scans and compaction.

Memtable

In-memory sorted buffer (skip list) absorbing writes before flush.

SSTable

Sorted String Table — immutable, key-sorted on-disk file with data, sparse index, metadata.

Compaction

Background merge of SSTables that drops tombstoned/superseded keys.

Leveled compaction

Strategy with non-overlapping SSTables per level and size ratios between levels.

Size-tiered compaction

Strategy that buckets SSTables by size and merges full buckets.

Sparse index

One index entry per data block, scanned linearly within a block.

Tombstone

Delete marker that persists until compaction guarantees no older value remains.

Bloom filter

Probabilistic set with no false negatives, used to skip absent-key SSTables.

Read amplification

Physical reads per logical read; minimized via bloom filters and sparse indexes.

Multiple choice

On a point lookup for a key that does not exist, what keeps an LSM tree's read amplification from blowing up across many SSTables?

• AThe merge iterator stops at the first SSTable level
• BThe memtable always contains a negative cache of recent misses
• CA per-SSTable bloom filter rules out most SSTables with a single in-memory probe, so disk reads only happen for SSTables that might contain the key
• DLeveled compaction guarantees keys never appear in more than one SSTable per level

Multiple choice

A team picks size-tiered compaction for an analytics store with frequent overwrites of the same keys. They later complain that disk usage is roughly 2x the live data set. What's the chapter's explanation?

• ASize-tiered compaction tolerates higher space amplification because multiple superseded copies of a key sit in different size tiers until a large merge happens
• BSize-tiered compaction never reclaims tombstones
• CSize-tiered compaction duplicates every key in every level by design
• DThe bloom filters are storing too many false positives, consuming the extra space

Multiple choice

Why can a tombstone in an LSM not be discarded as soon as compaction merges it with a value?

• ATombstones are needed for replication consistency, not for compaction
• BThe tombstone might still need to shadow an older value that lives in a deeper SSTable not involved in this compaction
• CTombstones are immutable by design and never get discarded
• DBloom filters depend on every tombstone remaining in place

Spot the issue

A team migrates a heavy-write, point-lookup-dominated workload from B-tree to LSM and disables bloom filters to save the per-SSTable memory overhead. Reads collapse to a few hundred QPS. What's the diagnosis?

• AWithout bloom filters, each point lookup may read every SSTable from disk, multiplying read amplification by the number of SSTables
• BWithout bloom filters, the memtable becomes the bottleneck
• CDisabling bloom filters disables compaction
• DBloom filters are needed for sequential scans, not point lookups

Introduction and Overview

Opens Part II by framing the fundamental challenges of distributed systems: independent nodes coordinating over unreliable networks with partial failures. Surveys the foundational concepts — concurrency, asynchrony, partial failure, time — and the theoretical bounds (FLP, CAP) that define what is achievable.

Fallacies of Distributed Computing

Peter Deutsch's classic list of false assumptions: the network is reliable, latency is zero, bandwidth is infinite, the network is secure, topology doesn't change, there is one administrator, transport cost is zero, the network is homogeneous. Every distributed database must be designed assuming each is false.

Two Generals Problem

Two parties communicating over a lossy channel cannot achieve guaranteed consensus on a coordinated action using any finite number of messages. The proof motivates why perfect agreement is impossible and why real systems settle for acknowledgments, retries, and probabilistic guarantees.

FLP Impossibility

Fischer, Lynch, and Paterson proved that in a purely asynchronous system with even one crash-faulty process, no deterministic consensus algorithm can guarantee termination. Real systems sidestep FLP with timeouts, randomization, or partial synchrony.

System Models

Synchronous systems have known bounds on message delay; asynchronous systems have none; partially synchronous systems behave asynchronously sometimes but eventually become synchronous. Most real systems are designed under partial synchrony — it is the assumption that makes consensus protocols terminate.

Failure Models

Categorize how processes can fail: crash-stop (halts forever), crash-recovery (restarts with state), omission (drops messages), Byzantine (arbitrary or malicious). The chosen model determines algorithm complexity — Byzantine tolerance, for example, requires 3f+1 nodes instead of 2f+1.

Safety vs. Liveness

Safety means "nothing bad ever happens" (two leaders are never elected); Liveness means "something good eventually happens" (a leader is eventually elected). FLP shows you cannot always have both in asynchrony, which is why every consensus protocol leans on a timing assumption for liveness.

Logical vs. Physical Time

Physical clocks drift and skew between nodes; logical clocks (Lamport timestamps, vector clocks) capture causal ordering without depending on wall-clock accuracy. Distributed databases rely on logical time for correctness and physical time only as a hint.

Distributed system

A collection of independent processes communicating by message passing, presented as a single coherent system.

Partial failure

Failure mode where some components fail while others continue, often indistinguishably.

Consensus

The problem of getting processes to agree on a single value despite failures.

Quorum

A subset of nodes whose agreement suffices to make a decision, typically a majority.

Asynchrony

No upper bound on message delivery or processing time.

Crash fault

A process simply stops; contrast with Byzantine where it behaves arbitrarily.

State machine replication

Replicate a deterministic state machine by applying the same ordered inputs.

Partial synchrony

Bounds on delay eventually hold, even if not always.

Multiple choice

A team designs a consensus protocol and assumes "if a node hasn't replied in 50ms, it has crashed" everywhere in the code, with no notion of timeouts being only hints. Which fallacy of distributed computing are they most directly violating?

• AThe network is reliable (and by extension, latency is zero)
• BBandwidth is infinite
• CTopology doesn't change
• DThere is one administrator

Multiple choice

Which statement most accurately summarizes the FLP impossibility result and how real systems cope with it?

• AConsensus is impossible in any system with crash faults, so practical systems use Byzantine algorithms instead
• BIn a purely asynchronous model with even one crash fault, no deterministic protocol guarantees termination; real systems add timeouts, randomization, or partial synchrony
• CConsensus is possible only if fewer than one third of nodes fail, regardless of timing assumptions
• DFLP shows that asynchronous consensus is impossible without cryptographic signatures

Spot the issue

A storage engineer argues: "Our leader election protocol guarantees both safety (never two leaders) and liveness (a leader is always elected) under any network conditions, including fully asynchronous ones." What's wrong with this claim?

• ALiveness is impossible to guarantee for any algorithm, even synchronous ones
• BSafety requires Byzantine tolerance, which the protocol presumably lacks
• CLeader election is not a consensus problem, so FLP does not apply at all
• DFLP rules out guaranteeing both safety and liveness simultaneously under pure asynchrony with crash faults — one must be relaxed or a timing assumption added

Multiple choice

A team needs to tolerate up to f arbitrary (Byzantine) faults in their replicated system. What is the minimum number of nodes they must deploy, and why does it differ from a crash-only design?

• A2f+1 nodes, because any majority quorum handles all failure modes equivalently
• Bf+1 nodes, since Byzantine faults are just a stricter form of crash faults
• C3f+1 nodes, because Byzantine nodes can send conflicting messages and must be outvoted by an honest super-majority
• D4f+1 nodes, the same threshold required for omission failures

Failure Detection

Explains how nodes detect peer failure despite the impossibility of distinguishing a slow node from a dead one in an asynchronous network. Walks from naive timeouts through adaptive Phi Accrual detectors to gossip-based SWIM, and the fundamental trade-off between completeness and accuracy.

Heartbeats and Pings

The two basic primitives: a heartbeat is a periodic "I'm alive" pushed by the monitored node; a ping is a request-reply from the monitor. Both rely on timeouts, which conflate slowness with failure — the central problem of detection.

Completeness vs. Accuracy

Chandra and Toueg's classification: completeness is the guarantee that crashed processes are eventually suspected; accuracy is the guarantee that healthy processes are not wrongly suspected. No detector in an async system has strong accuracy, so practical detectors are eventually perfect (◇P).

Phi Accrual Failure Detector

Used in Cassandra and Akka: instead of a boolean alive/dead verdict, it outputs a continuous suspicion level φ based on the statistical distribution of past inter-arrival times. Applications choose their own threshold to balance speed against false positives.

SWIM Protocol

Scalable Weakly-consistent Infection-style process group Membership: each node periodically pings a random peer; if that ping fails, it asks k other peers to probe indirectly before declaring suspicion. Membership changes spread epidemically, giving O(1) load per node regardless of cluster size.

Indirect Probing

When a direct ping fails, the monitor asks intermediaries to probe on its behalf, distinguishing a failed local link from a failed node. This is the single most effective trick for cutting false-positive rates in real clusters.

Suspicion vs. Failure

Many systems use a two-stage state machine: a node first becomes "suspected," and only after corroboration or a longer timeout does it transition to "failed." This dampens flapping during transient network issues or GC pauses.

Failure detector

Subsystem giving each process a list of currently suspected peers.

Eventually perfect detector (◇P)

Complete and eventually accurate; sufficient for consensus under partial synchrony.

False positive

Declaring a live node dead, often from GC pauses or transient network delays.

Inter-arrival time

Interval between consecutive heartbeats; the basis of statistical detectors.

Suspicion level (φ)

Continuous value derived from the probability a heartbeat is still in flight.

Indirect ping

Probe routed through intermediaries to disambiguate link from node failure.

Membership protocol

Mechanism by which nodes learn the current cluster roster.

Epidemic dissemination

Gossip-style spread of information, achieving full coverage in O(log N) rounds.

Multiple choice

Operators tune their boolean alive/dead timeout aggressively to detect failures faster, but now they get a flood of false positives during GC pauses. Which failure detector design directly addresses this by replacing the boolean verdict with a tunable, statistical signal?

• ABully algorithm
• BPhi Accrual failure detector
• CTwo-phase commit's prepare phase
• DRing-based heartbeat

Multiple choice

In Chandra and Toueg's classification, which property does a practical failure detector in an asynchronous network typically achieve, given that strong accuracy is impossible?

• AStrong accuracy and strong completeness
• BStrong accuracy and weak completeness
• CEventually perfect (◇P): complete and eventually accurate
• DPerfect: complete and always accurate, given enough retries

Spot the issue

A monitor pings node N and the ping times out. The monitor immediately marks N as failed and removes it from the cluster. What's the most likely problem with this design, and what mechanism would fix it?

• AThe monitor should use TCP keepalives instead of pings, which never produce false positives
• BThe monitor cannot distinguish a failed local link or transient delay from a dead N; using indirect probes through k peers cuts false positives dramatically
• CThe monitor should require a quorum of monitors to vote on every failure, which is the only correct fix
• DThe monitor needs Byzantine fault tolerance to handle this scenario

True / False

SWIM scales because the per-node load grows with cluster size, since every node must heartbeat every other node every interval.

• TrueTrue
• FalseFalse

Leader Election

How a group agrees on a single coordinator to serialize decisions, drive replication, or commit writes. Contrasts classical algorithms (Bully, Ring) with the practical mechanisms real systems use — leader leases, stable leaders, epoch numbers — and warns about split-brain and fencing.

Why Elect a Leader

A single leader serializes writes, orders operations, and avoids running consensus per action. The trade-off is that the leader is a bottleneck and a failure point — so re-election must be fast and safe enough to keep the cluster alive.

Bully Algorithm

When a node notices the leader is gone, it sends an ELECTION message to all higher-ID nodes; if none reply, it declares itself leader. Simple but produces O(N²) messages and can run multiple concurrent elections during partitions.

Ring-Based Election

Nodes are arranged in a logical ring; election messages carry the highest ID seen so far and circulate until one returns to its originator. Lower message count than Bully but assumes the ring topology is intact, which is fragile under partitions.

Leader Leases

A leader holds a time-bounded lease and must renew it before expiry; other nodes will not elect a new leader until the lease is known to have expired. Leases bound the window of dual leadership and rely on bounded clock drift rather than perfect synchrony.

Stable Leader Optimization

Once elected, the leader stays in place across many rounds of operations, amortizing the cost of election. Most real systems — Raft, Multi-Paxos, ZooKeeper's ZAB — keep the leader until it visibly fails.

Split Brain

A partition causes two subsets to each elect their own leader, both accepting writes. Mitigated by requiring a leader to hold a majority quorum (so at most one partition can elect) and by fencing tokens that invalidate stale leaders' writes downstream.

Fencing Tokens

A monotonically increasing identifier issued with each new leadership term; downstream systems reject operations bearing stale tokens. This is what ensures a deposed leader cannot corrupt state after a new one takes over.

Leader / coordinator

A node granted authority to serialize decisions for the group.

Term / epoch

Monotonically increasing integer identifying a leadership tenure.

Lease

Time-bounded grant of authority that must be renewed.

Quorum-based election

Requires a majority vote, ensuring at most one leader per term.

Split brain

Simultaneous leaders in disjoint partitions.

Fencing token

Monotonic ID that lets downstream resources reject stale leaders.

Election timeout

Duration after which a follower starts a new election.

Stable leader

A leader that persists across operations to amortize election cost.

Multiple choice

A cluster of 5 nodes loses network connectivity between two subgroups of sizes 3 and 2. Each subgroup runs the Bully algorithm and elects a leader; both leaders begin accepting writes. What's the cleanest structural fix to make split brain impossible?

• ARequire a leader to hold a majority quorum so at most one partition can elect
• BIncrease the election timeout so only the larger partition finishes first
• CSwitch to ring-based election, which is partition-tolerant by construction
• DUse heartbeats instead of ELECTION messages to detect the failed leader

Multiple choice

A leader holds a 10-second lease and crashes 1 second into it. The cluster waits for the lease to expire before electing a new leader. What core safety property does the lease provide, and what physical assumption does it require?

• ABounded dual-leadership window; requires bounded clock drift between nodes
• BLinearizable reads; requires synchronized atomic clocks
• CLiveness under any asynchrony; requires no clock assumption at all
• DByzantine tolerance; requires cryptographic lease tokens

Spot the issue

A new leader is elected, but the deposed previous leader (whose lease has expired in the cluster's view, but whose local clock thinks it's still leader) sends a write to the storage layer. The storage layer accepts it, corrupting state. What mechanism would have prevented this?

• AUse the Bully algorithm so only the highest-ID node can ever lead
• BIncrease heartbeat frequency until detection is instantaneous
• CIssue a monotonically increasing fencing token with each leadership term and have downstream storage reject writes bearing stale tokens
• DRequire the deposed leader to ack its own deposition before stepping down

Multiple choice

A team complains that their consensus cluster runs an election before every single client write, eating throughput. Which optimization, used by Raft, Multi-Paxos, and ZAB, directly addresses this?

• ASwitch to the Bully algorithm to make elections cheaper
• BRun elections in parallel on every node so one always wins quickly
• CReduce election timeout to nearly zero
• DKeep the elected leader stable across many operations until it visibly fails, amortizing election cost

Replication and Consistency

How multiple replicas hold copies of data and still present a coherent view despite concurrent updates, failures, and partitions. Walks through the consistency hierarchy from linearizability down to eventual consistency, introduces CAP and PACELC, and the practical tools — quorums, read repair, hinted handoff, vector clocks — that real systems use.

CAP Theorem

Under a network partition, a system must choose between consistency and availability — only two of three are guaranteed. CAP applies only during partitions, which is why PACELC was introduced to capture the normal-operation trade-off too.

PACELC

Extends CAP: under Partition, choose Availability or Consistency; Else (normal operation), choose Latency or Consistency. Captures the fact that even healthy systems trade strong consistency for lower latency — Dynamo-style stores are PA/EL; HBase is PC/EC.

Consistency Models

A ladder of guarantees: linearizability (atomic and respecting real-time order globally), sequential (one order consistent with each client's program order), causal (cause-and-effect preserved; concurrent operations may differ across observers), eventual (replicas converge absent new writes).

Quorums and R+W>N

With N replicas, a write quorum W and read quorum R with R+W>N ensures every read overlaps the latest write, giving strong consistency for single keys. Tuning R and W trades read vs. write latency and durability.

Read Repair and Anti-Entropy

Read repair fixes stale replicas opportunistically when a quorum read detects divergence. Anti-entropy (e.g., Merkle-tree sync) runs in the background to converge all replicas regardless of read pattern. Together they provide convergence in eventually consistent systems.

Hinted Handoff

When a target replica is unreachable, the coordinator stores the write locally as a hint and replays it once the target recovers. Improves availability and durability without blocking the writer — though unbounded hint queues become their own problem.

Vector Clocks

A vector of per-node logical counters attached to each value; comparing vectors classifies updates as causally prior, later, or concurrent. Concurrent versions are siblings that must be reconciled by the application, by CRDTs, or by last-write-wins.

Session Guarantees

Per-client middle-ground promises proposed by Terry et al.: read-your-writes, monotonic reads, monotonic writes, and writes-follow-reads. They are weaker than linearizability but eliminate the worst surprises in eventually consistent systems.

Linearizability

Strongest single-object consistency — atomic, respects real-time order globally.

Eventual consistency

Liveness guarantee — replicas converge once writes stop.

Strong eventual consistency

Replicas with the same updates are in the same state (CRDTs).

Quorum (N, R, W)

Total replicas, read quorum, write quorum; R+W>N is the strong-consistency condition.

Conflict / sibling version

Two concurrent updates incomparable under vector clocks.

Read repair

Synchronous reconciliation triggered by a divergent quorum read.

Anti-entropy

Background reconciliation that converges replicas independent of foreground requests.

Hinted handoff

Local storage of a write for an unreachable replica, replayed when it returns.

Tunable consistency

Per-operation choice of R and W (Cassandra/Dynamo style).

Spot the issue

A team configures a Dynamo-style store with N=3, R=1, W=1 and expects "strong consistency" because every key has 3 replicas. What's wrong?

• AN=3 is too small; strong consistency requires at least 5 replicas
• BR+W=2 is not greater than N=3, so a read may not overlap the latest write; strong single-key consistency needs R+W>N
• CDynamo-style stores cannot provide strong consistency at any setting
• DW=1 is fine, but R must equal N for strong consistency

Multiple choice

A vendor markets a "CA" database that gives both consistency and availability and "doesn't trade off anything." According to PACELC, what real trade-off does even a healthy, partition-free deployment face?

• ALatency vs. consistency in normal operation, even when no partition exists
• BThroughput vs. durability, regardless of consistency choice
• CRead amplification vs. write amplification, like an LSM tree
• DSafety vs. liveness, like FLP

Multiple choice

Two clients concurrently update the same key on different replicas. A vector clock comparison shows neither version's vector dominates the other. What does this mean and what should the system do?

• AOne client's clock is broken; pick the one with the larger physical timestamp
• BThe updates are causally ordered; apply them in vector order and drop the earlier
• CThe updates are concurrent (siblings); reconcile via application logic, CRDTs, or last-write-wins
• DThe replicas are out of sync; force a Merkle-tree anti-entropy pass to pick a winner

Multiple choice

A user reports that after writing a comment on their phone, refreshing the page sometimes shows the comment missing, then it reappears on a later refresh. Which session guarantee would, if enforced, eliminate this surprise without requiring full linearizability?

• AMonotonic writes
• BWrites-follow-reads
• CCausal consistency across all clients
• DRead-your-writes

Anti-Entropy and Dissemination

How distributed databases keep replicas in sync over time, compensating for missed writes, dropped messages, and node failures. Contrasts foreground techniques (read repair, hinted handoff) with background reconciliation (Merkle-tree anti-entropy) and gossip-style epidemic protocols used for cluster metadata.

Read Repair

When a coordinator reads from multiple replicas and detects divergence, it asynchronously writes the freshest version back to stale replicas. Cheap to bolt onto the read path, but only repairs keys that are actually being read — cold data drifts forever without anti-entropy.

Digest Reads

To save bandwidth, the coordinator requests a full value from one replica and lightweight hash digests from the others, fetching the full value from a disagreeing replica only when needed. This is the standard optimization layered on top of read repair (used by Cassandra).

Hinted Handoff

If a replica is unreachable at write time, another node temporarily stores a hint containing the write and replays it once the target recovers. Preserves durability without blocking the writer, but unbounded hint queues become a liability under long outages.

Merkle Trees

A hash tree over a key range where each parent is the hash of its children. Two replicas can compare just the roots and recursively descend only into subtrees that differ, exchanging O(log n) hashes instead of all keys — the workhorse of anti-entropy.

Gossip Dissemination

Each node periodically picks a random peer and exchanges state, so updates spread exponentially through the cluster in O(log N) rounds. Used for membership, failure detection, and schema rather than user data, because gossip is eventually consistent and bandwidth-cheap.

Push, Pull, Push-Pull

In push, infected nodes proactively send updates; in pull, susceptible nodes ask peers for news; push-pull combines both and converges fastest. The choice trades convergence speed against wasted messages once most nodes already know the update.

Plumtree

Push-Lazy-Push Multicast: builds a spanning tree over a gossip overlay so the bulk of payloads travels along tree edges while only small "I have message X" announcements gossip on the remaining links. Heals the tree when nodes fail and cuts redundant payload traffic dramatically.

Anti-entropy

Background process reconciling replica divergence.

Entropy (replication)

Accumulated drift between replicas from lost messages or failed writes.

Hint

Locally persisted record of a write intended for an unreachable replica.

Digest

Hash summary of a value used to detect disagreement without transferring the data.

Merkle tree

Binary hash tree enabling logarithmic-cost reconciliation.

Dotted version vector

Version vector extended with per-event dots for precise concurrency tracking.

Gossip protocol

Randomized peer-to-peer state exchange.

SWIM

Gossip-based failure detector with indirect pings and disseminated state events.

Hybrid logical clock

Clock combining physical time with a logical counter for causality plus wall-clock proximity.

Multiple choice

Two Cassandra replicas have drifted apart over months because the keys involved are rarely read. The operator wants to reconcile them while exchanging the minimum amount of data over the wire. Which mechanism is designed for exactly this case?

• ARead repair triggered by a quorum read
• BHinted handoff replay from a peer
• CMerkle-tree anti-entropy comparing roots and descending only into mismatched subtrees
• DDigest reads with a coordinator-side hash compare

Multiple choice

A gossip protocol is propagating a small membership update through a 10,000-node cluster. Pure "push" wastes messages because infected nodes keep pushing to peers that already know, while pure "pull" is slow at the start when almost no one has the update. Which variant converges fastest by combining both?

• APush
• BPull
• CPush-pull
• DPlumtree without gossip backup

Spot the issue

A node went offline for three days during a Black Friday event. The coordinator dutifully accumulated hinted writes for it the entire time, and the hint queue grew to hundreds of gigabytes. When the node returned, replaying the hints overwhelmed it and the cluster destabilized. What's the underlying problem the chapter warns about?

• AHinted handoff should never be used in production
• BHints cannot be replayed and must be discarded after one hour
• CThe coordinator should have used read repair instead of hints during the outage
• DUnbounded hint queues turn a temporary outage into a durability and capacity liability when the target returns

Multiple choice

Plumtree improves on naive gossip by routing the bulk of payload traffic along a particular structure while still using gossip for resilience. What is that structure, and what travels on the non-tree links?

• AA spanning tree carrying payloads, with small "I have message X" announcements gossiped on remaining links
• BA ring carrying full payloads, with heartbeats on chord links
• CA DHT carrying payloads, with Merkle digests on remaining links
• DA token ring carrying payloads, with vector clocks on remaining links

Distributed Transactions

Generalizes ACID transactions across multiple nodes, where a single commit decision must be reached despite partial failures. Walks through atomic commitment protocols (2PC, 3PC), the systems that make distributed transactions practical (Spanner, Calvin, Percolator), and long-running alternatives like sagas.

Atomic Commitment

The requirement that all participants either commit or abort, with no participant deciding differently. Unlike consensus, it must respect any single "abort" vote — which is what makes it strictly harder to make non-blocking under failures.

Two-Phase Commit

The coordinator first asks all participants to prepare (durably promise they can commit); on unanimous yes it sends commit, otherwise abort. Correct under no-failure but blocking: if the coordinator crashes after some participants vote yes, they hold locks indefinitely.

Three-Phase Commit

Inserts a pre-commit phase between prepare and commit so that a recovering participant can infer the outcome from peers without the coordinator. Solves blocking under fail-stop but is not safe under network partitions and is rarely used in practice.

Calvin and Deterministic Transactions

Calvin pre-orders transactions through a replicated sequencing layer; all replicas then execute the same ordered batch deterministically. Eliminates 2PC entirely — but requires knowing read/write sets up front, which constrains transactional flexibility.

Spanner and TrueTime

Google Spanner uses GPS- and atomic-clock-backed TrueTime, which returns a bounded interval [earliest, latest] for "now". Spanner assigns commit timestamps and waits out this uncertainty before releasing locks, giving externally consistent distributed transactions.

Percolator

Google's snapshot-isolation layer over BigTable using per-row lock columns, a primary lock as the commit point, and a Timestamp Oracle for global ordering. Commit is effectively client-driven 2PC whose atomicity hinges on a single atomic write that releases the primary lock.

Sagas

A long-lived business transaction is decomposed into local transactions, each with a compensating action. Sagas trade ACID atomicity for availability and progress, accepting that intermediate states are visible and that compensation, not rollback, restores invariants.

Distributed transaction

Transaction whose operations span multiple nodes and must satisfy ACID as a whole.

Prepare phase

First phase of 2PC; participants durably vote yes/no.

In-doubt transaction

Participant state after voting yes but before learning the outcome — locks held.

Presumed abort / commit

2PC optimization treating missing logs as a default outcome.

TrueTime

Spanner's clock API exposing uncertainty as an interval.

Commit wait

Stalling at commit until TrueTime guarantees the timestamp is in the past everywhere.

Timestamp oracle

Centralized service handing out monotonic timestamps (Percolator).

Snapshot isolation

Each transaction reads from a consistent start-time snapshot; commits if no write-write conflict.

Compensating transaction

Operation that semantically undoes a previously committed saga step.

Spot the issue

A team runs 2PC across five participants. Three have voted yes and durably logged their prepare records when the coordinator's machine catches fire and won't be recoverable for hours. What's the practical problem this exposes?

• AAtomicity is violated — the three yes-voters will spontaneously commit on their own
• BThe yes-voters are stuck in-doubt and continue holding locks indefinitely, blocking unrelated work
• C3PC would have prevented the crash from happening
• DThe two non-voters can safely commit because they never said yes

Multiple choice

Google Spanner achieves externally consistent distributed transactions despite running across data centers. The key idea is that TrueTime exposes clock uncertainty as a bounded interval, and Spanner does what at commit time to make timestamps safe?

• APicks the earliest bound of TrueTime so commits feel fast
• BWaits out the TrueTime uncertainty interval before releasing locks so the commit timestamp is guaranteed to be in the past everywhere
• CFalls back to vector clocks when TrueTime drifts
• DUses a centralized timestamp oracle like Percolator instead of TrueTime

Multiple choice

A team is designing a long-running booking workflow (reserve flight, reserve hotel, charge card) that may take minutes and span independent services. Holding distributed locks for that long is unacceptable. Which pattern fits, and what does it give up?

• A2PC across all services — gives up nothing
• B3PC across all services — gives up only network-partition safety
• CSagas: decompose into local transactions, each with a compensating action — gives up ACID atomicity in exchange for availability and progress
• DPercolator client-driven 2PC with per-row locks — gives up nothing because the primary lock makes it non-blocking

Multiple choice

3PC inserts a pre-commit phase between prepare and commit to let participants infer the outcome from peers if the coordinator dies. Why is 3PC still rarely used in real systems?

• AIt requires hardware atomic clocks like Spanner
• BIt is unsafe under network partitions, which are the failure mode practitioners actually care about
• CIt cannot be combined with snapshot isolation
• DIts message complexity grows quadratically with participants

Consensus

The final chapter: how a group agrees on a single value (and, by extension, a sequence of values forming a replicated log) despite crashes, message loss, and reordering. Develops Paxos and its variants, Raft, ZAB, and Viewstamped Replication, all under the shadow of FLP.

FLP Impossibility

In a purely asynchronous system with even one crash-faulty process, no deterministic consensus protocol can guarantee both safety and liveness. Real systems sidestep FLP via partial synchrony, randomization, or failure detectors — every working consensus protocol relies on at least one.

Basic Paxos

A proposer runs a two-phase ballot: phase 1 (prepare/promise) acquires a quorum's promise not to accept lower-numbered proposals and learns any previously accepted value; phase 2 (accept/accepted) gets a quorum to accept a value. Safety is unconditional; liveness can be lost to dueling proposers.

Multi-Paxos

Amortizes Paxos over a log by electing a stable leader who skips phase 1 for subsequent slots and runs only phase 2 per command. This is what production "Paxos" deployments actually mean and is structurally close to Raft.

Fast Paxos

Lets clients send proposals directly to acceptors, skipping the leader on the fast path. The cost is a larger fast quorum (3f+1 acceptors to tolerate f faults instead of 2f+1) and a recovery path on collisions.

EPaxos

Egalitarian Paxos: any replica can commit non-interfering commands in one round-trip; only conflicting commands need an extra dependency-resolution round. Improves latency in geo-distributed deployments and avoids the single-leader bottleneck entirely.

Raft

A consensus protocol designed for understandability, decomposed into leader election, log replication, and safety. The leader is the sole point of log appends, terms monotonically increase, and a strict log-matching property plus restricted leader election guarantee committed entries are never lost.

ZAB

ZooKeeper Atomic Broadcast: a leader assigns monotonically increasing zxids to proposals and broadcasts them in order; after leader failure, a recovery phase synchronizes followers to the new leader's history. Provides primary-order atomic broadcast — a totally ordered, FIFO-per-client log.

Viewstamped Replication

One of the earliest leader-based consensus protocols (Oki & Liskov), organized around views, each with a designated primary. A view change protocol elects a new primary and transfers state when the previous one is suspected. Structurally equivalent to Paxos and a direct ancestor of Raft.

Consensus

Agreement on a single value satisfying agreement, validity, and termination.

Quorum

A subset large enough that any two such subsets intersect (typically a majority).

Proposer / acceptor / learner

The three Paxos roles, usually co-located in one process.

Ballot number

Unique, monotonically increasing Paxos proposal ID.

Term

Raft's analog of a ballot; a logical period with at most one leader.

Leader election

Sub-protocol choosing a node to coordinate within a term/view.

Log replication

Leader propagates ordered command entries to followers.

Replicated state machine

Abstraction that consensus implements — same inputs, same state, everywhere.

View change

VR/ZAB recovery procedure installing a new primary and reconciling state.

Partial synchrony

Eventually-bounded delay assumption that recovers liveness despite FLP.

Multiple choice

You're explaining to a junior engineer why every working consensus protocol — Paxos, Raft, ZAB, VR — relies on at least one of: timeouts, randomization, or a failure detector. Which theoretical result are you invoking?

• AThe CAP theorem
• BFLP impossibility, which forbids deterministic termination of consensus under pure asynchrony with even one crash-faulty process
• CThe Two Generals Problem
• DThe PACELC trade-off

Multiple choice

A distributed log service is built on Multi-Paxos. After electing a stable leader, each subsequent log entry is committed with only the second phase of Paxos. What did the leader save by being stable, and why is this safe?

• APhase 1 (prepare/promise) is amortized across all subsequent slots, and safety holds because the leader's ballot number was already promised by a quorum
• BPhase 2 (accept/accepted) is skipped, with safety from leader leases
• CBoth phases are skipped on the fast path, with safety from a larger 3f+1 quorum
• DPhase 1 is skipped only for non-interfering commands, like in EPaxos

Spot the issue

A team wants the latency benefit of Fast Paxos in a small 3-node cluster (f=1, so 2f+1=3 acceptors). They're confused because their fast path keeps failing. What constraint of Fast Paxos are they missing?

• AFast Paxos requires a leader, so leader election still adds a round-trip
• BFast Paxos requires a larger fast quorum — to tolerate f faults it needs 3f+1 acceptors, not 2f+1
• CFast Paxos cannot replicate logs, only single values
• DFast Paxos requires synchronized clocks like Spanner

Multiple choice

Raft was designed for understandability and decomposes consensus into three sub-problems. Which decomposition is correct?

• APrepare, accept, learn
• BView, primary, view change
• CLeader election, log replication, and safety (with log-matching and election restriction)
• DPush, pull, push-pull

True / False

Two proposers in basic Paxos can keep pre-empting each other's ballots forever ("dueling proposers"), and when this happens the protocol's safety guarantee — that no two acceptors decide different values — is violated.

• TrueTrue
• FalseFalse