1
Price a replication factor
Read capacity, write capacity, write work and storage for N replicas, and the read/write ratio that Capacity Estimation taught you to measure, which decides whether that trade pays.
Course · System Design
Replication and Consistency
Replication is bought in three currencies — write work, latency and staleness — and the course prices each. Reads scale by N and writes do not; a synchronous write waits for the slowest replica and a quorum for the W-th fastest; a follower read is stale with a probability read off the lag distribution; and “consistency” becomes a count — of concurrent pairs in a vector-clock diagram, of valid linearizations of a history, of updates a last-writer-wins merge throws away.
N replicas: N× reads, 1× writes, N× write work and storage
P(all N−1 acked by t) = F(t)^(N − 1) the slowest, not the average
R + W > N ⟹ overlap ≥ R + W − N
miss probability = C(N−W, R)/C(N, R) 2/3 at N = 3, R = W = 1
2f + 1 tolerates f a fourth node adds nothing to three
What this course is about
- Subject
- System Design
- Lessons
- 13
- Format
- Interactive
Overview
What you will be able to do
By the end you can price a replication factor in four currencies, read a staleness probability off a lag distribution, decide whether a quorum configuration overlaps, and turn three consistency questions into counts you can check.
2
Compute replication's two latencies and its staleness
The p99 of a synchronous write as the maximum of N − 1 replicas, the p99 of a quorum as the W-th fastest, and the probability a follower read at delay t is stale.
3
Decide and size a quorum
Whether (N, R, W) overlaps and by how much, the miss probability when it does not, and the fault tolerance and availability of a majority.
4
Turn consistency into a count
Lamport and vector timestamps from a message diagram with the concurrent pairs counted, the valid linearizations of a short history enumerated, and the updates a last-writer-wins merge discards against a counter CRDT that discards none.
Lessons
13 lessons
What replication costs first, then its two latencies and its staleness, then quorums, and last the three questions that turn “consistent” into something countable.
Reads Scale, Writes Do NotCompute the four multipliers a replication factor buys, and the ceiling the read/write ratio puts on them.Not marked
Synchronous Writes Wait for the SlowestCompute a synchronous write's p99 as the maximum of N − 1 replicas, and price the asynchronous alternative in bytes.Not marked
Replication Lag and Stale ReadsRead the probability that a follower read is stale off a lag distribution, at a chosen delay and at the mean.Not marked
Quorums OverlapDecide whether a configuration overlaps, and compute the minimum overlap it actually guarantees.Not marked
Quorum Latency: the W-th FastestCompute a quorum write's p99 as a binomial tail, and say which way it moves when N grows.Not marked
Sloppy Quorums and the Miss ProbabilityCompute the exact probability that a read misses the write when R + W ≤ N.Not marked
Majorities and Fault ToleranceCompute the failures a cluster size tolerates and the availability of its majority, and say what an even size buys.Not marked
Randomised Election TimeoutsCompute the probability that an election round is clean, and the number of rounds it takes.Not marked
Lamport ClocksStamp a message diagram by the Lamport rule and exhibit a pair the stamps order wrongly.Not marked
Vector Clocks and ConcurrencyStamp a diagram with vectors and count the pairs of events that are concurrent.Not marked
Physical Clocks and DriftCompute the clock uncertainty window from a drift rate and a sync interval, and the commit-wait it forces.Not marked
Linearizability by EnumerationCount the total orders of a short history that real time allows and a register would accept.Not marked
Conflict Resolution, CountedCount the updates each merge rule discards on a trace of concurrent updates.Not marked
Recommended background
Latency and the tail and availability and failure from this path, plus combinations, the pigeonhole principle, partial orders, permutations, the binomial distribution, computing probabilities and independence from discrete mathematics.
Practice suggestions
Compute the binomial tail in “Quorum Latency: the W-th Fastest” before reading its conclusion. That more replicas make a fixed-W quorum faster is the one result on this course that most readers refuse until they have computed it.
Draw the message diagram yourself before stamping it. Vector clocks are mechanical once the happens-before edges are on the page and confusing before.
Take the six-operation cap on the linearizability lab seriously. It is there because the enumeration is factorial, and that fact is a lesson about why real checkers do not enumerate.
What it does not cover
Consensus log mechanics — Raft replication, snapshots, membership change. Only the quorum arithmetic, majority availability and election timing are here.
Transactions and isolation levels; CAP and PACELC as slogans. What this course carries instead are the measurable consequences — lag, staleness, overlap and the sloppy-quorum miss.
CRDT design beyond the counter of “Conflict Resolution, Counted”.