Phase 6: Anti-Entropy Repair, Hinted Handoff & Distributed Safety¶

Audience: Principal Distributed Systems Architect & High-Availability Engineer
Source References: src/java/org/apache/cassandra/repair/, src/java/org/apache/cassandra/hints/, src/java/org/apache/cassandra/service/paxos/

1. Anti-Entropy Repair & Merkle Trees¶

Because writes in Cassandra can succeed with LOCAL_QUORUM without waiting for all replicas, network blips, disk timeouts, and transient down nodes cause replicas to drift over time.

Anti-Entropy Repair (nodetool repair) is the background distributed process that synchronizes all replicas to 100% data parity.

Anti-Entropy Merkle Tree Diffing:
               [ Root Hash: 0x8F9B ]
                  /              \
         [ Left: 0x4A11 ]      [ Right: 0x9B2C ]
           /         \            /         \
      [Leaf 1]     [Leaf 2]   [Leaf 3]    [Leaf 4]  <--- Hashes of Token Sub-ranges

1.1 The Merkle Tree Generation Protocol¶

The repair coordinator assigns a token range to be repaired (e.g. [Token A, Token B)).
All participating replicas scan their local SSTables and construct an in-memory cryptographic binary hash tree (Merkle Tree) of depth 15 (\(2^{15} = 32,768\) discrete sub-ranges).
The root hashes are compared:
If Root A == Root B: The datasets are mathematically identical! Zero network data transfer required.
If Root A != Root B: The coordinator traverses down the tree branches in \(O(\log N)\) steps until it isolates the exact microscopic token range with mismatched hashes.
The missing data for only that specific token range is streamed across the network using Netty zero-copy streaming.

1.2 Enterprise Repair: Full vs. Incremental¶

Full Repair (nodetool repair -full): Scans all SSTables on disk, constructs trees, and streams deltas. Heavy I/O; run weekly.
Incremental Repair (nodetool repair -inc): Segments SSTables into "repaired" vs "unrepaired" sets, scanning only newly created SSTables.
Cassandra Reaper: Open-source industry standard tool to orchestrate small sub-range repairs continuously, preventing I/O spikes.

2. Hinted Handoff Mechanics: Surviving Transient Outages¶

When a client writes data with a consistency level like ONE or LOCAL_QUORUM, what happens if one of the natural replicas is dead or unreachable?

┌────────────────────────────────────────────────────────┐
│ Coordinator Node Receives Write for 3 Replicas        │
├────────────────────────────────────────────────────────┤
│ Replica A: Active  ──► Write succeeds                  │
│ Replica B: Active  ──► Write succeeds                  │
│ Replica C: DEAD    ──► Coordinator saves a "Hint"!     │
└───────────────────────────────────┬────────────────────┘
                                    │
                                    ▼
┌────────────────────────────────────────────────────────┐
│ Local Hints Storage (/var/lib/cassandra/hints/)        │
├────────────────────────────────────────────────────────┤
│ Mutation payload serialized to local disk with:        │
│ - Target Node UUID (Replica C)                         │
│ - Original Timestamp                                   │
│ - TTL expiration window (default: 3 hours)             │
└────────────────────────────────────────────────────────┘

2.1 The Replay Lifecycle¶

The coordinator detects that Replica C has returned to life (via Gossip HeartBeatState).
A background thread pool (HintsDeliveryExecutor) opens the local hint file and streams the buffered mutations to Replica C.
Replica C applies the mutations to its local Memtable and CommitLog using their original timestamps, maintaining chronological ordering.

2.2 Hint Failure Invariants¶

max_hint_window_in_ms (Default: 3 Hours): If Replica C stays down for longer than 3 hours, the coordinator stops creating hints to prevent local disk exhaustion.
Once Replica C revives after 3 hours, it is missing data and MUST be healed using nodetool repair.
Hints do NOT count toward satisfying the client's Consistency Level (except for ANY).

3. Paxos & Lightweight Transactions (LWT)¶

Standard CQL writes do not lock data and follow Last-Write-Wins (LWW). When an application requires Linearizable Consistency (e.g. INSERT ... IF NOT EXISTS), Cassandra invokes a 4-phase Paxos consensus protocol.

4-Phase Paxos Protocol over the Storage Engine:
Phase 1: PREPARE (Ballot Generation)
Coordinator ──► Sends Prepare(ballot) to all natural replicas.
Replicas    ──► Promise: "I will reject any ballots older than this ballot."
                Returns previously accepted proposal (if any).

Phase 2: PROPOSE (Condition Evaluation)
Coordinator ──► Evaluates condition (e.g., IF balance >= 100).
                If satisfied, sends Propose(ballot, new_mutation).

Phase 3: ACCEPT (Consensus Commitment)
Replicas    ──► Accept mutation and persist state in system.paxos table on disk.
                Returns Ack to Coordinator.

Phase 4: LEARN / COMMIT (Data Materialization)
Coordinator ──► Sends Commit to all replicas.
Replicas    ──► Writes mutation to normal table Memtable/CommitLog.

3.1 The Performance Tax of LWT¶

A normal Cassandra write requires 1 round-trip network hop to replicas.
A Paxos Lightweight Transaction requires 4 round-trip network hops and multiple disk writes to system.paxos.
Under high concurrent contention on the same partition key, Paxos ballots conflict, forcing exponential backoff retries. Use LWT judiciously for critical identity/fencing operations, not high-velocity streaming data!