Hinted handoff

Deep dive

How it works

Parts:

• preference list — the N nodes owning a key, from consistent hashing
• failure detector — marks a replica down or up (phi accrual, gossip)
• hint store — per-target append-only log on the holder: target, key, value, version, created time
• holder — the coordinator (Cassandra) or the first healthy node past the preference list (Dynamo)
• replayer — on "target up", streams that target's hints in order, deletes them after the ack
• hint window — maximum outage for which hints are still created

1. Coordinator sends the write to the N replicas of the key's preference list.
2. For each replica the failure detector calls down (or that times out): if its downtime is within the hint window, the holder appends a hint tagged with the target.
3. Count acks. Sloppy quorum: a hinted copy counts toward W. Strict: it does not, so a write may fail with W = N while still leaving hints.
4. On "target up", each holder streams that target's hints.
5. The target applies each hint only if its version is newer than what it holds (idempotent, safe in any order); the holder deletes the hint once acked.
6. Outage longer than the window: no hints; only repair closes the gap.

write k ─► A ✓   B ✗ (down)   C ✓           window: hints only while
           stand-in D stores hint(for B, k, v@t)   now - down_since <= window
 B returns ──► D replays hint ─► B applies if v@t is newer ─► D deletes

Code

use std::collections::HashMap;

#[derive(Clone)]
struct Hint { target: usize, key: u64, version: u64, value: u64 }

#[derive(Default)]
struct Node { store: HashMap<u64, (u64, u64)>, hints: Vec<Hint> } // key -> (version, value)

impl Node {
    // Idempotent: the same or an older version is a no-op.
    fn apply(&mut self, key: u64, version: u64, value: u64) {
        let e = self.store.entry(key).or_insert((0, 0));
        if version > e.0 { *e = (version, value); }
    }
}

struct Cluster { nodes: Vec<Node>, down_since: Vec<Option<u64>>, n: usize, window: u64, now: u64 }

impl Cluster {
    fn new(size: usize, n: usize, window: u64) -> Self {
        Cluster { nodes: (0..size).map(|_| Node::default()).collect(), down_since: vec![None; size], n, window, now: 0 }
    }
    fn up(&self, i: usize) -> bool { self.down_since[i].is_none() }
    fn fail(&mut self, i: usize) { self.down_since[i] = Some(self.now); }

    /// Returns acks counted toward W. Sloppy: the stand-in's hint counts (Dynamo).
    /// Strict: the coordinator keeps the hint but it does not count (Cassandra, except CL=ANY).
    fn write(&mut self, key: u64, value: u64, sloppy: bool) -> usize {
        self.now += 1;
        let (version, size) = (self.now, self.nodes.len());
        let pref: Vec<usize> = (0..self.n).map(|k| (key as usize + k) % size).collect();
        let mut acks = 0;
        for &t in &pref {
            if self.up(t) { self.nodes[t].apply(key, version, value); acks += 1; continue; }
            if self.now - self.down_since[t].unwrap() > self.window { continue; } // window over: no hint
            let stand_in = (self.n..size).map(|k| (key as usize + k) % size).find(|&h| self.up(h));
            let holder = if sloppy { stand_in } else { pref.iter().copied().find(|&h| self.up(h)) };
            if let Some(h) = holder {
                self.nodes[h].hints.push(Hint { target: t, key, version, value });
                acks += sloppy as usize;
            }
        }
        acks
    }

    /// Node is back: holders replay its hints in order, deleting them once applied.
    fn recover(&mut self, i: usize) -> usize {
        self.down_since[i] = None;
        let mut replayed = 0;
        for h in 0..self.nodes.len() {
            let all = std::mem::take(&mut self.nodes[h].hints);
            let (mine, rest): (Vec<Hint>, Vec<Hint>) = all.into_iter().partition(|x| x.target == i);
            self.nodes[h].hints = rest;
            for x in mine { self.nodes[i].apply(x.key, x.version, x.value); replayed += 1; }
        }
        replayed
    }
}

fn main() {
    let mut c = Cluster::new(5, 3, 100);
    c.fail(1); // key 0 lives on nodes 0, 1, 2; node 3 is the stand-in
    assert_eq!(c.write(0, 7, true), 3);  // sloppy: W = N = 3 still met
    assert_eq!(c.write(0, 8, false), 2); // strict: W = N = 3 fails
    assert_eq!(c.recover(1), 2);
    assert_eq!(c.nodes[1].store[&0], c.nodes[0].store[&0]); // caught up
    assert!(c.nodes.iter().all(|n| n.hints.is_empty()));    // deleted after ack
    c.nodes[1].apply(0, 1, 7); // replaying an old hint again changes nothing
    assert_eq!(c.nodes[1].store[&0], (2, 8));

    let mut c = Cluster::new(5, 3, 2); // window of 2 time units
    c.fail(1);
    for v in 0..5 { c.write(0, v, true); } // only the first 2 writes are hinted
    assert_eq!(c.recover(1), 2);
    let (v, val) = c.nodes[0].store[&0];
    assert!(c.nodes[1].store[&0].0 < v);   // stale until repair
    c.nodes[1].apply(0, v, val);           // stand-in for anti-entropy repair
    assert_eq!(c.nodes[1].store[&0], c.nodes[0].store[&0]);
}

Complexity and constants

• Hinted write: one local append (target, key, version, value) per missed replica; the cost drivers are bytes appended and the fsync policy.
• Replay: O(h) for h hinted writes: one sequential read, one stream, one idempotent apply each. Finding the same gap by comparison costs O(n) keys, or O(d log n) hash comparisons with trees.
• Holder storage: record size x writes to that range during the outage.

Efficiency

• Cost: measured on an Apple M4 Pro, std only: appending 1 M 32-byte hint records to a file, buffered with one fsync at the end, 54 ns/hint; fsync every 1000 hints, about 4.1 us/hint; in-memory replay of 600 k hints, 21 ms. A replica that missed 10 k of 1 M keys: replay applied 10 k hints in 205 us; a full compare scanned 1 M keys in 30.5 ms to move the same 10 k records (in memory, no network). Real replay is bound by the network stream and the target's write path.
• Levers:
  • per-target append-only hint segments — sequential I/O, whole segments streamed and deleted (Cassandra ships hint files a segment at a time, docs) — always
  • batch fsync, not per hint — the 54 ns vs 4.1 us gap above — when losing the last few hints to a crash is acceptable (repair covers them)
  • throttle replay — Cassandra hinted_handoff_throttle default 1024 KiB/s per delivery thread (docs) — when targets recover under load
  • compress hint segments — Cassandra defaults to LZ4 (docs) — when disk or network bound
  • size the window to a typical outage and drop hints for removed nodes — bounds disk and replay storms — always
• Naive → standard → state of the art: fail the write when a replica is down · availability lost; hint in memory, replay everything on recovery · fast but lost on holder restart; durable per-target segments + window + throttle + periodic repair as backstop (Cassandra, ScyllaDB) · bounded disk, replay O(missed writes).

Implementation notes

• Keep the original version in the hint; re-stamping on replay lets an old hint overwrite newer data. Cassandra hints keep the mutation timestamp, so replay cannot overwrite a future mutation.
• A holder that crashes before its fsync loses hints: treat them as best effort and still schedule repair.
• A hint must not outlive tombstone retention: replaying a write after a delete's tombstone was purged elsewhere can resurrect data (design reasoning; keep hint age below gc_grace_seconds-style limits).
• ScyllaDB exposes sync points (POST /hinted_handoff/sync_point) to wait until hints for given nodes are replayed.

Pitfalls

• Stale reads: the hinted copy sits on a node reads do not consult, so R + W > N no longer guarantees overlap under sloppy quorum. A returning replica serves old data until replay ends.
• Hint storms: after a rack reboot every holder replays to the same nodes; throttle and cap delivery threads.
• Disk filling on the holder in long outages; the window bounds it.
• Permanent removal: hints for a removed node are garbage; drop them and re-replicate by repair.
• Skipped repair: ScyllaDB's docs say hints do not remove the need for recurring full repair.

Variants and alternatives

In production

• Amazon Dynamo: first N healthy nodes of the preference list, hints in a separate local database scanned periodically.
• Apache Cassandra and ScyllaDB: coordinator-side hints, 3 h window by default.
• Riak: fallback vnodes in the preference list (primary|fallback annotation in riak_core_apl) hand data off to the primary when it returns.
• SMTP relays, MQTT brokers, edge gateways and mobile apps run the same store, retry, delete cycle.

Implementations

Sources

• Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, section 4.6. paper
• Apache Cassandra documentation, Hints. docs
• Apache Cassandra documentation, Dynamo (consistency level ANY). docs
• ScyllaDB documentation, Hinted Handoff. docs
• J. Klensin, Simple Mail Transfer Protocol, RFC 5321, section 4.5.4.1. RFC
• OASIS, MQTT Version 3.1.1, section 4.1 (session state). spec
• OpenRiak, riak_core (riak_core_apl.erl). code