Sloppy quorum with hinted handoff

The idea

In a Dynamo-style system, every key has an ordered preference list of N replica nodes on a hash ring. A write needs W acknowledgements to count as durable. A strict quorum only ever talks to the home replicas — so if W of them are down during a partition, the write simply fails.

A sloppy quorum relaxes that: the coordinator walks the ring past the home set to the next healthy nodes and routes the write there instead. Those stand-ins store a small hint recording who the data really belongs to. When the original node recovers, hinted handoff replays the buffered write back to it and the temporary copy is dropped. You trade a window of weaker consistency for writes that keep succeeding.

See it work

How it works

The coordinator collects W acks. If a home replica is unreachable, it keeps walking the ring to the next healthy node, parks the write there with a hint, and a background loop later replays each hint to its rightful owner.

N, R, W = 3, 2, 2            # tunable replication factor and quorums

def preference_list(key):
    # first N distinct healthy-or-not owners clockwise from hash(key)
    return ring.successors(hash(key), count=N)

def put(key, value):
    targets, hints = [], {}
    walk = ring.walk_from(hash(key))     # owners first, then ring overflow
    owners = preference_list(key)
    for node in walk:
        if len(targets) == W:
            break
        if not node.reachable():
            continue
        if node in owners:
            node.store(key, value)       # lands on its real home
        else:
            owner = next_unfilled(owners, targets)
            node.store(key, value, hint=owner)   # sloppy: park + remember
            hints.setdefault(node, []).append((owner, key))
        targets.append(node)
    if len(targets) < W:
        raise Unavailable                # even sloppy can't reach W
    return Ok(targets)

def hinted_handoff_loop():               # runs in the background
    while True:
        for holder in nodes_with_hints():
            for (owner, key) in holder.hints():
                if owner.reachable():
                    owner.store(key, holder.read(key))   # replay
                    holder.drop_hint(owner, key)         # then forget

Trade-offs

Watch out for

• Treating a sloppy quorum like a strict one — it does not guarantee that read and write sets overlap, so stale reads are possible while hints are pending.
• Hint backlog growing without bound during a long outage, filling up the temporary holders' storage.
• Hinted handoff storms when many nodes recover at once and every holder tries to replay simultaneously.
• Losing a hint entirely if the temporary holder dies before it gets a chance to hand off.
• Assuming handoff alone converges everything — read repair and anti-entropy are still needed to catch what hints missed.

Worked example

Take N = 3, W = 2. A key's preference list is n1, n2, n3. A partition takes n2 and n3 offline, so only n1 can ack — a strict quorum would fail the write because it can't reach W = 2 home replicas.

With a sloppy quorum the coordinator gets n1's ack, then walks the ring to the next healthy nodes, n4 and n5. n4 accepts the write with a hint "for n2" and n5 accepts it with a hint "for n3". Now two acks are gathered, so the write succeeds — it just lives on stand-ins for the moment. When n2 and n3 come back, the background loop replays n4's buffered copy to n2 and n5's to n3, then both holders drop their hints. The home replicas are consistent again and no hints remain. Step through the animation above to watch exactly this play out.

Check yourself