Art of Codeartofcode
Lesson 11 of 17

14. Replication

1
The picture to keep in your head
2
14.1 Why keep copies of the same data?
3
14.2 How does leader-follower replication work?
4
14.3 Should the leader wait for followers before confirming a write?
5
14.4 What is replication lag, and why does it happen?
6
14.5 How do you stop lag from confusing users?
7
14.6 How do you use read replicas in practice?
8
14.7 What happens when the leader fails?
9
14.8 What is split brain, and how is a leader safely chosen?
10
14.9 When would you have more than one leader?
11
14.10 How does leaderless replication work, and what are quorums?
12
Memory card and where the analogy breaks
13
Practice: five levels
14
Interview questions
15
Solutions
16
Sources
17
Code lab
14. Replication

14.10 How does leaderless replication work, and what are quorums?

3 min read+10 XP

At the bank: No head office at all. To update a notice, you give it to at least two of three branches. To read it, you ask at least two of three and trust the newest version you're shown. Because any two branches out of three always share at least one, you're always shown the latest notice.

In the system: In leaderless replication (the style of Amazon's Dynamo paper, used by Cassandra and Riak), clients write to and read from several replicas directly, with no leader:

  • N = how many replicas hold each piece of data.
  • W = how many must confirm a write.
  • R = how many are asked on a read; the reader keeps the highest version.

N=3, W=2, R=2: the write set and read set always share a replica.

Figure: with W + R > N, every read overlaps the latest write in at least one replica.

The rule: if W + R > N, every read set overlaps every write set in at least one replica, so a read sees the latest written version (barring some edge cases, like concurrent writes and replicas being replaced). In the chapter's code with N = 3: after a write with W = 2, a read with R = 2 returns the new value even when the stale replica answers first; with R = 1 it can return the old value.

Setting (N = 3)Good forCost
W = 2, R = 2Balanced; survives 1 node down for both reads and writesEvery request waits for 2
W = 3, R = 1Fast readsAny node down blocks writes
W = 1, R = 1Fastest, always availableReads can be stale (W + R = 2, not > 3)

How stale replicas catch up:

  • Read repair: a reader that notices an old version writes the new one back.
  • Anti-entropy: a background process compares replicas (often with Merkle trees of hashes) and copies missing data.
  • Hinted handoff: if a replica is down, another node holds its writes and hands them over when it returns. (With "sloppy" quorums that accept writes on stand-in nodes, the overlap guarantee weakens.)

Cassandra exposes this per query as consistency levels like ONE, QUORUM and ALL.

Memory code: "Write to most, read from most, and the newest version wins." W + R > N.