CAP Theorem & Consistency Models
The precise statement behind the slogans: what consistency and availability mean in CAP, why partition tolerance is not optional, why "CA" is a myth, the normal-operation trade-off PACELC adds, and the consistency spectrum from linearizable through causal to eventual. Read it carefully, because every later protocol in this path buys one point on that spectrum, and the page's brute-force quorum proof sets up the quorum steps.
CP vs AP Databases
What CAP means when you actually pick a database: CP systems refuse some requests during a partition, while AP systems keep serving possibly stale or conflicting data, and real platforms choose per data type, as the worked cart-versus-checkout scenario shows. It prepares you to justify a store choice in a design review and to explain why the trade-off only bites during an actual partition.
Partitioning, Sharding & Replication
Placement and copying, the two halves of every replicated store: partitioning schemes, consistent hashing with virtual nodes, hot partitions, and the single-leader, multi-leader and leaderless replication topologies that quorums tie together. In this path it bridges CAP and consensus, so read the replication table closely and note where one leader keeps things simple and where leaderless replication pushes conflict handling onto the application.
Consensus, Transactions & Coordination
The core problem stated properly: why agreement is hard to guarantee when messages can be delayed and nodes can crash, how majority quorums and leader election make progress in practice, what coordination services provide, two-phase commit versus sagas, and idempotency. It prepares you to say when a problem truly needs consensus and when a weaker tool, such as an idempotency key, will do.
Raft vs Paxos
The two consensus protocols compared on one design commitment: Raft's strong leader, which splits consensus into leader election, log replication and safety, against Paxos's value-at-a-time formulation with no built-in persistent leader. It covers their lineage, why etcd chose Raft, and which to reach for, so you can answer "why not Paxos?" with a reason rather than a reputation.
Raft: The Election
Run a five-node Raft cluster: followers wait on randomized election timers, the first to time out becomes a candidate, bumps the term and requests votes, and a majority makes it leader, which then sends heartbeats. Kill the leader and watch a fresh election, then use what you saw to explain why randomized timeouts make split votes rare and why each term has at most one leader.
Raft Leader Election (Majority)
Implement election_result(n, grants): count the candidate's own vote plus the granted ones and return whether that reaches a strict majority of the whole cluster, including even-sized clusters where half is not enough. The discussion after you solve it covers what a real node adds, such as one vote per term, the log up-to-date check and stepping down on a higher term, and how skipping any of them produces two leaders.
The Quorum Dial
Dial N, R and W, write a value to W replicas, read from R, and watch whether the two sets overlap. The pigeonhole argument becomes visible: when R + W exceeds N the read must touch a replica holding the latest write, and when it does not, you can produce a stale read on demand and see exactly why it happened.
Quorum (N/R/W) Explorer
The calculator companion to the simulator: for any N, R and W it reports whether reads are strongly consistent, how many failures reads and writes survive, and where the setting falls on the latency spectrum. Use it to work through the classic settings, majority, fast reads and fast writes, and to predict before you look what each one buys and gives up.
Concurrency, Locks & Isolation Levels
Coordination inside a single database before coordination across many: the races behind lost updates, pessimistic and optimistic locking, isolation levels and their anomalies, MVCC, and distributed locks with fencing tokens. It sits here because the fencing-token idea returns in the distributed lock design, and because seeing what serializable isolation costs on one machine explains why coordination across machines is expensive.
Vector Clock Merge
Implement the receive rule of vector clocks, receive(local, incoming, pid): take the element-wise maximum of your clock and the message's clock, then increment your own entry. Getting this one function right is what preserves causality, and it prepares you to explain how a system detects that two writes were concurrent instead of silently picking one of them.
Vector Clocks: Who Caused What
Trace three processes with no shared clock as they record local events, send messages carrying their vectors, and merge on receipt. Then compare vectors to decide which events happened before which and which were truly concurrent, the same comparison a replicated store makes when deciding whether two versions conflict or one simply supersedes the other.
CRDT: Grow-Only Counter
Compute the converged value of a grow-only counter, gcounter_value(payloads): merge every replica's per-replica vector by element-wise maximum, then sum the result. The small exercise carries the big idea, since a merge that is commutative, associative and idempotent lets replicas sync in any order, any number of times, and still agree without coordination.
CRDT Merge: No Conflict
Increment three replicas of a counter independently, merge them in whatever order you choose, and watch every replica land on the same value. It turns strong eventual consistency into something you have observed, and it prepares you to explain where CRDTs fit, such as counters and offline collaborative edits, and why they avoid conflicts rather than resolving them after the fact.
The Rumor Mill: Gossip
Start a rumor at one node and let every informed node tell a random peer each round: the informed set roughly doubles, so the whole cluster knows in about log N rounds, with no coordinator and no single point of failure. It prepares you to explain how stores like the key-value design at the end of this path track membership, and why a lost message barely matters.
Consistent Hashing Ring
Build a hash ring with virtual nodes using the provided hash32, then route each key to the first ring point at or after its hash, wrapping past the end. Implementing it settles details that hand-waving skips, such as the wrap-around, why production rings binary-search the sorted points instead of scanning them, and why too few virtual nodes leave the load uneven.
Consistent Hashing Visualizer
After implementing the ring, watch one rebalance: add and remove nodes, change virtual-node counts, and see which keys move and how load per node shifts. Use it to verify your mental model of the challenge you just solved, especially the claim that adding a node moves only about K/N keys and that more virtual nodes smooth out hot spots.
Design a Distributed Lock
Why a "locked = true" row fails, then the repairs in order: atomic acquire, TTL leases, ownership tokens, fencing tokens that make a lock actually safe, consensus-backed locks for high availability, renewal and granularity, and the clock and pause problems that remain. It prepares you to argue when a lock needs consensus, and when you should avoid a distributed lock altogether.
Design an ID Generator
Unique IDs without coordinating on every ID: a Snowflake-style 64-bit layout with timestamp, machine ID and sequence, safe one-time assignment of node bits, and what to do when the clock moves backward. In this path it shows the opposite strategy to consensus, coordinating once at startup instead of on every operation, and it prepares you to explain why the IDs are only roughly ordered.
Design a Key-Value Store
The capstone that assembles the path: consistent hashing for placement, replication along a preference list, quorum reads and writes, conflict resolution, gossip membership, hinted handoff and read repair. Read it as a review of every earlier step, and test yourself on the hard questions it ends with, such as how a read can return stale data even when R + W exceeds N.