CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 7 of 8 · 5 min read

Sloppy quorums and hinted handoff

Accepting writes on stand-in nodes when the home nodes cannot be reached.

Sloppy quorums and hinted handoff

Think of locking yourself out of your house. You knock on the neighbour's door and ask to stay on their couch until you find your keys. When you find them, you go home. The neighbour was not the right place for you, but gave you shelter in the meantime.

A strict quorum fails if too few of the n home nodes are reachable. A network break can cut a client off from many nodes. In a large cluster with more than n nodes, the client may still reach some nodes, just not the ones that hold this value. The designer must choose: return errors, or accept the write on reachable nodes outside the home set.

Sloppy quorum and hinted handoff

A sloppy quorum accepts writes and reads on any w or r reachable nodes, even if they are not among the n home nodes for that value. Hinted handoff is what happens when the network is repaired: the stand-in nodes send the writes they held to the proper home nodes.

Example: the home nodes for a key are A, B, C. A and B are unreachable. D and E accept the write for them. When A and B return, D and E hand the write over.

The advantage is write availability: as long as any w nodes are reachable, writes are accepted. The cost is that even when w + r > n, a read may not see the latest write, since it may sit on nodes outside the n home nodes until the handoff is done. The book says a sloppy quorum is not a quorum in the traditional sense. It is only an assurance of durability: the data is on w nodes somewhere.

The book notes that sloppy quorums are optional in common Dynamo-style databases. In Riak they are on by default, and in Cassandra and Voldemort they are off by default.

Several data centres. Leaderless replication suits multiple data centres since it tolerates conflicting writes, network breaks and latency spikes. Cassandra and Voldemort count the replicas n across all data centres and let you choose how many go in each. Each write goes to all replicas, but the client waits only for a quorum inside its own data centre, so it is not affected by the slow link between data centres. Writes to the other data centres are usually asynchronous. Riak keeps client communication local, with n replicas in one data centre, and copies between clusters asynchronously in a style like multi-leader.

Detecting concurrent writes. Two clients can write the same key at the same moment. The book's example: node 1 receives the write from A but not B (a transient outage). Node 2 receives A then B. Node 3 receives B then A. If each node simply overwrote its value, the nodes would stay different forever. LWW makes them converge by keeping the write with the highest timestamp, but at the cost of durability: concurrent writes that were reported successful are silently dropped. LWW is the only conflict resolution Cassandra supports. The safe way to avoid losing data is to track which writes are concurrent with version numbers (a version vector holds one version number per replica) and merge concurrent values.

A worked example of a sloppy quorum. Key K is homed on nodes 1, 2, 3 (n = 3, w = 2, r = 2). A partition cuts the client off from nodes 1, 2, 3 but not from 4 and 5.

Step Strict quorum Sloppy quorum
Write K Fails (0 of 3 home nodes reachable) Succeeds on nodes 4 and 5 (w = 2)
Read K at once Fails A read of the home nodes can miss the new value, which sits on nodes 4 and 5
After repair - Hinted handoff sends the value to nodes 1, 2, 3

Common mistake

Treating w + r > n as a guarantee of reading the latest value. With sloppy quorums, concurrent writes, failed writes and clock-based LWW, it is not.

Interview angle

Answer in your head first, then open it.

Why would you use multi-leader replication?

Writes in several regions without crossing the world, survival of a region outage, offline clients. Say you would avoid conflicts by giving each record a home leader.

How do you resolve a write conflict?

Prefer avoiding it. Otherwise merge with a CRDT or custom logic, ask the user, or use LWW and state the data loss.

What are n, w and r?

Replicas, write acknowledgements, read acknowledgements. w + r > n means read and write sets overlap. Give the failures tolerated for n = 5, w = 3, r = 3.

What are read repair and anti-entropy?

Repair of stale replicas on read, and in the background.

What is a sloppy quorum?

Write availability by using stand-in nodes, with hinted handoff afterwards, at the cost of the overlap guarantee.

Check yourself:

  • Which choice does a sloppy quorum make: availability or the overlap guarantee?
  • What does hinted handoff do after the network is repaired?

Words you will meet

Word Plain meaning
Multi-leader replication More than one node accepts writes
Write conflict Two writes to the same data accepted at the same time on different leaders
Last write wins (LWW) Keep the write with the highest timestamp and drop the others
CRDT A data type that merges concurrent changes automatically
Replication topology The paths along which writes pass between nodes
Leaderless (Dynamo-style) replication Any replica accepts writes, with quorums
Read repair Fixing a stale replica when a read finds it out of date
Anti-entropy A background process that copies missing data between replicas
Quorum The number of replicas that must answer a read or write
n, w, r Replicas, write acknowledgements, read acknowledgements
Sloppy quorum A quorum that may use nodes outside the home set
Hinted handoff Stand-in nodes passing writes to the home nodes later
Version vector One version number per replica, used to tell concurrent writes apart