Read Repair

How read repair works

A Dynamo-style store replicates each key to N replicas, but writes don't always land everywhere. A write at W = 3 against N = 5 leaves two replicas unpatched. A network hiccup or a brief node restart can leave gaps even at higher W. Over hours and days, replicas drift apart — same key, different versions, depending on which replica you ask.

Read repair closes the drift cheaply. Whenever a coordinator runs a read at quorum R, it has already collected R replica responses with their version metadata. Comparing those responses tells you which replicas are stale; pushing the freshest value back to the laggards is one extra write per laggard. The cost is amortized over read traffic you were going to do anyway.

The mechanic:

1. Coordinator sends a read to all N replicas (or to R explicitly, depending on speculative-execution config).
2. Responses come back with (value, timestamp_or_vclock).
3. The coordinator picks the freshest version — by max timestamp for LWW, or by vector-clock dominance.
4. For every replica that returned an older version, the coordinator sends a repair write with the fresh value.
5. The freshest value is returned to the client (foreground: after repairs ack; background: before).

Foreground, background, and probabilistic

• Foreground (blocking) read repair. The coordinator waits for the repair writes to acknowledge before returning the response to the client. Guarantees read-monotonicity: a subsequent read at the same consistency level sees the repaired state. Costs an extra round-trip on every read with divergence (~1–5 ms intra-DC).
• Background (async) read repair. The coordinator returns the response immediately and fires the repair writes as fire-and-forget. No latency penalty, but a follow-up read might hit a not-yet-patched replica. Cassandra's default for ONE-level reads.
• Probabilistic read repair. Repair only fires with some probability p per read (Cassandra's read_repair_chance, historically 0.1). Caps overhead on hot keys while still ensuring eventual convergence. Deprecated in newer Cassandra in favor of DC-local versus global controls.
• Speculative read repair. The coordinator pre-emptively reads from all N replicas at every quorum read (not just R). Wastes bandwidth on the extra N - R reads but eliminates the gap on lower consistency levels. Used in DynamoDB's strongly-consistent reads.
• Selective digest read. Cassandra optimization — first replica returns full data, the rest return only digests (hashes); only on mismatch does the coordinator re-fetch full data. Cuts bandwidth ~75% for the common case.

When read repair earns its keep

• Hot-key workloads. Frequently-read keys converge within seconds even at low write quorums. Read repair scales with read traffic, so it naturally pours effort into the keys that need it.
• Sloppy quorum environments. When writes can land on temporarily-substituted replicas (hinted handoff in flight), read repair stitches the actual replica set back together once the substitutes drain.
• Partition recovery. When a partition heals, the two sides have divergent state. Read repair catches the discrepancy on the first read of any key touched during the partition.
• Cross-DC consistency at LOCAL_QUORUM. Each DC's quorum reads catch divergence within the DC; cross-DC consistency comes from eventual replication plus read repair when a global read happens.

Read repair is the wrong fit when divergence is concentrated on cold keys (a key never read won't converge), when latency budgets exclude an extra round-trip for stragglers (use async only), or when application semantics demand siblings be surfaced rather than auto-resolved (then disable LWW and propagate vector-clock siblings).

Read repair vs alternatives

	Read repair	Hinted handoff	Merkle tree repair	Synchronous replication
Triggered by	Reads with divergence	Writes to down replicas	Scheduled sweeps	Every write
Latency overhead per op	1–5 ms blocking; 0 async	0 (background)	0 (offline)	Slowest replica fsync
Bandwidth cost	R - 1 extra writes per divergent read	One replay per missed write	O(keyspace) per sweep	N × value size per write
Covers cold keys?	No	No	Yes	Yes
Convergence time	Seconds (hot) → never (cold)	Minutes after replica returns	Hours per sweep cycle	Real-time
Operational cost	Built-in	Built-in	Manual scheduling	Throughput hit

The pragmatic answer is to combine. Cassandra uses all three of the eventual-consistency techniques: read repair for hot paths, hinted handoff for brief outages, Merkle tree repair (nodetool repair) for the long tail. None of them alone is sufficient; together they bound replica drift in practice.

Pseudo-code

// Foreground read repair — runs at quorum read
read_with_repair(key, R):
    replicas = replicas_for(key)
    futures  = [send_read(r, key) for r in replicas]
    responses = await_first(futures, count=R, timeout=read_timeout)

    if len(responses) < R:
        return TIMEOUT

    // Determine the freshest version
    winner = max(responses, key=lambda r: r.timestamp)

    // Identify laggards
    laggards = [r for r in responses if r.timestamp < winner.timestamp]

    // Push repair writes (blocking variant — wait for ack)
    repair_futures = [send_write(r.node, key, winner.value, winner.timestamp) for r in laggards]
    await_all(repair_futures, timeout=repair_timeout)

    return winner.value

// Background variant — fire and forget
async_read_with_repair(key, R):
    responses = collect_replicas(key, R)
    winner = max(responses, key=...)

    // Fire-and-forget repair
    for r in responses:
        if r.timestamp < winner.timestamp:
            schedule_async_write(r.node, key, winner.value, winner.timestamp)

    return winner.value

JavaScript implementation

class QuorumCoordinator {
  constructor(replicas, N) {
    this.replicas = replicas; // node URLs
    this.N = N;
  }

  // Foreground (blocking) read repair
  async readWithRepair(key, R, opts = { foreground: true }) {
    const responses = await this.collectReplicas(key, R);
    if (responses.length < R) throw new Error('quorum not met');

    // Pick latest (LWW)
    const winner = responses.reduce((a, b) => (b.ts > a.ts ? b : a));

    // Identify and patch laggards
    const laggards = responses.filter(r => r.ts < winner.ts);
    const repairs = laggards.map(r =>
      this.sendWrite(r.node, key, winner.value, winner.ts)
    );

    if (opts.foreground) {
      // Block on repair acks (1-5 ms intra-DC)
      await Promise.allSettled(repairs);
    }
    // else: fire-and-forget — caller doesn't wait

    return winner.value;
  }

  async collectReplicas(key, R) {
    const allReads = this.replicas.map(node => this.sendRead(node, key));
    const responses = [];
    const settled = await Promise.allSettled(allReads);
    for (const s of settled) {
      if (s.status === 'fulfilled' && s.value) responses.push(s.value);
    }
    return responses;
  }
}

Common pitfalls

• Background repair on critical reads. If consistency matters for follow-up reads, use foreground (blocking). Otherwise the next read can hit a still-stale replica even after the "successful" repair from the prior call.
• Ignoring tombstones. A deleted value is represented as a tombstone (a value with the delete flag and a timestamp). Read repair must propagate tombstones the same way as live values — a buggy repair that treats "no value" as "older" will resurrect deleted keys. Cassandra's gc_grace_seconds determines how long tombstones live before being collected.
• Read repair on time-skewed clusters. LWW conflict resolution uses timestamps. If your clocks are skewed, "latest" might actually be a write from a node with a wrong clock — and repair propagates that wrong version everywhere. Always synchronize NTP and use HLC if drift is a concern.
• Repair amplification under high write contention. A frequently-updated counter with low read traffic can churn its repairs faster than they propagate, creating waves of "winner" oscillations. Counters are better stored as CRDTs (PN-counter, G-counter) that merge by union rather than LWW.
• Skipping the digest optimization. Sending full values from every replica wastes 75%+ of the bandwidth for small clusters. Have stragglers return only a hash of their value; only re-fetch full data on hash mismatch.

Performance characteristics

• Latency: blocking adds 1–5 ms intra-DC, 30–80 ms cross-DC. Single extra round-trip from coordinator to laggard. Async adds zero observable latency but loses the read-monotonicity guarantee.
• Write amplification: 10–30% during normal drift, 50%+ after partition. Each divergent read becomes 1 read + up to (R - 1) writes. Cassandra historically capped this with read_repair_chance = 0.1 — meaning only 10% of reads triggered the repair branch.
• Bandwidth: digest-mode cuts payload ~75%. Only the first replica sends full data; others send hashes. Full-data re-fetch only on hash mismatch — the common case (no drift) costs N × hash_size + 1 × value_size.
• Convergence: hot keys within seconds, cold keys never. A key read once per second converges almost as fast as it's written. A key never read drifts indefinitely until Merkle repair runs.
• Read repair load is self-tuning. More drift = more divergent reads = more repairs = faster convergence. Less drift = less work. Naturally elastic with cluster health.