Lesson 5.3• 8 min read

Tunable consistency and quorums

Mathematical quorum overlap ($R + W > N$), replication factor, and anti-entropy repair.

What you will learn

  • Describe a leaderless, Dynamo-style store and its NNwhat its symbols mean, WWwhat its symbols mean and RRwhat its symbols mean settings.
  • Choose WW and RR for fast reads, fast writes or availability, with N=3N = 3.
  • Explain how replicas are repaired and how conflicting writes are resolved.

Leaderless replication (the Dynamo model)

In Dynamo-style systems (Amazon's Dynamo, and Cassandra and Riak, which borrow its techniques), there is no leader: any replica accepts writes directly from clients. Designing Data-Intensive Applications calls this leaderless replication, the third family after single-leader and multi-leader replication; it is also called masterless. Nodes are peers, placed on a ring by consistent hashing, and any node can coordinate a read or write for any key.

To trade response time, durability and consistency against each other, these systems expose tunable quorum parameters:

  • NNwhat its symbols mean (replication factor): How many nodes store a copy of each item.
  • WWwhat its symbols mean (write quorum): How many replicas must acknowledge a write before it succeeds.
  • RRwhat its symbols mean (read quorum): How many replicas must answer a read.

Each operation waits for its WW or RR fastest replicas, so its response time is set by the slowest of those. Cassandra exposes the same idea as consistency levels: ONE, QUORUM (a majority, ⌊n/2⌋+1\lfloor n/2 \rfloor + 1what its symbols mean of the replicas) and ALL.


The quorum condition: R+W>NR + W > N

If

R+W>NR + W > Nwhat its symbols mean

then by the pigeonhole principle any RRwhat its symbols mean replicas you read include at least one of the WWwhat its symbols mean that acknowledged the latest write, so a read normally sees that write. Vogels calls this strong consistency, but it is not linearizability: Abadi notes that Dynamo-style systems fall short of full consistency even when R+W>NR + W > N (concurrent writes and sloppy quorums, below, are two reasons).

Common configurations with N=3N = 3

Strategy WW RR Read and write sets overlap? Writes survive Reads survive
Quorum 2 2 Yes (2+2=4>32 + 2 = 4 > 3) 1 node down 1 node down
Fast writes 1 3 Yes (1+3=4>31 + 3 = 4 > 3) 2 nodes down No node down
Fast reads 3 1 Yes (3+1=4>33 + 1 = 4 > 3) No node down 2 nodes down
Highly available 1 1 No (1+1=2≤31 + 1 = 2 \le 3): stale reads possible 2 nodes down 2 nodes down

Conflict resolution and repair

Replicas drift apart (a write missed a replica, a node was down), so these systems repair them:

  1. Read repair: During a read, replicas that return stale data are updated with the newer value, repairing them at a convenient moment instead of waiting for background repair.
  2. Hinted handoff: If a replica is temporarily unreachable, the write goes to another node along with a "hint"; when the replica returns, the hint is replayed to it. Dynamo combines this with a sloppy quorum: writes go to the first NNwhat its symbols mean healthy nodes on the ring, which keeps writes available during failures but means the quorum is not always the "home" replicas.
  3. Anti-entropy with Merkle trees: Replicas build hash trees over their key ranges, where each leaf is a hash of a key's value, and compare them; only the branches whose hashes differ need to be synchronized.
  4. Last-write-wins vs vector clocks: Cassandra resolves conflicting updates by timestamp (last write wins), so it asks operators to keep clocks synchronized with NTP; clock skew can make the "wrong" write win. Dynamo instead tracks causality with vector clocks and keeps concurrent versions for the application to merge.

Tunable quorum consistency (R + W > N)

Replication factor (N)3 nodes
Write quorum (W)2 (QUORUM)
Read quorum (R)2 (QUORUM)
Replica nodes (click node to simulate outage / partition):3 of 3 healthy
Read and write sets overlap
R + W = 2 + 2 = 4 > 3

Because R + W (4) > N (3), any 2 replicas you read include at least one of the 2 that acknowledged the latest write (the pigeonhole principle), so reads normally see it. It is not a guarantee of linearizability: concurrent writes and failures can still produce surprises.

Write: 14ms (2 acks)
Read: 14ms (2 acks)

Key takeaways

  • Every operation waits for its WWwhat its symbols mean or RRwhat its symbols mean fastest replicas; with R+W>NR + W > Nwhat its symbols mean a read normally sees the latest write, though this is still not linearizability.
  • Raising WW makes writes slower and less available; raising RR does the same to reads; W=R=1W = R = 1what its symbols mean is the most available and can read stale data.
  • Read repair, hinted handoff (with a sloppy quorum) and Merkle-tree anti-entropy bring replicas back in line.
  • Last-write-wins depends on synchronized clocks; vector clocks keep concurrent versions for the application to merge.
Sources6