Anti-entropy repair

Deep dive

How it works

Parts:

• replica store — key → (version, value or tombstone) for one range (range-partitioning)
• hash tree — fixed shape over key-space buckets; leaf = hash of its entries, inner = hash of children (Merkle tree)
• tree builder — one scan per repair, or an update per write
• diff walker — exchanges hashes level by level, descends only on mismatch
• resolver — per key: higher version (last-writer-wins), vector clock siblings, or CRDT merge
• scheduler — picks ranges, throttles streaming, beats the tombstone grace period

1. Pick a shared key range; both sides use the same tree shape (boundaries, depth).
2. Hash each entry (key, version, value or tombstone) into its leaf; parents hash children.
3. Exchange roots. Equal: done after one comparison.
4. Unequal: exchange both child hashes, recurse into children that differ; a leaf mismatch names a key sub-range.
5. Exchange the entries of each differing leaf; per key the higher version wins, ties break deterministically; a tombstone is an entry with a version.
6. Write winners to the stale side; repeat per range on a schedule, throttled.

 A: root ≠ B: root      roots differ
      /      \
   left =    right ≠    descend only into the mismatch
              /   \
          l2 =     l3 ≠ leaf range: stream both sides, merge per key

Bucket by fixed key-space bits or agreed token boundaries, never data-dependent splits, so trees line up. Dynamo keeps one tree per key range; when nodes join or leave, affected ranges need new trees.

Code

Std only; hand-written FNV-1a (64-bit); leaf = top depth key bits.

use std::collections::BTreeMap;

pub type Entry = (u64, Option<u64>); // (version, value); None = tombstone
pub type Replica = BTreeMap<u64, Entry>;

const SEED: u64 = 0xcbf29ce484222325; // FNV-1a 64-bit offset basis
fn fnv(mut h: u64, x: u64) -> u64 {
    for b in x.to_le_bytes() {
        h = (h ^ b as u64).wrapping_mul(0x100000001b3); // FNV-1a prime
    }
    h
}

/// Fixed-depth hash tree over the key space: leaf = top `depth` bits of the key.
pub struct Tree { depth: usize, levels: Vec<Vec<u64>> } // levels[0] = [root]

impl Tree {
    /// One full scan; leaf = hash of its entries in key order.
    pub fn build(r: &Replica, depth: usize) -> Tree {
        assert!((1..=32).contains(&depth));
        let mut leaves = vec![SEED; 1 << depth];
        for (&k, &(ver, val)) in r {
            let h = &mut leaves[(k >> (64 - depth)) as usize];
            *h = fnv(fnv(*h, k), ver);
            *h = match val { Some(v) => fnv(fnv(*h, 1), v), None => fnv(*h, 0) };
        }
        let mut levels = vec![leaves];
        while levels.len() <= depth {
            let up = levels[0].chunks(2).map(|c| fnv(fnv(SEED, c[0]), c[1])).collect();
            levels.insert(0, up);
        }
        Tree { depth, levels }
    }
}

/// Descend only into differing subtrees; collect differing leaf indexes.
fn diff(a: &Tree, b: &Tree, lvl: usize, i: usize, cmps: &mut usize, out: &mut Vec<usize>) {
    *cmps += 1;
    if a.levels[lvl][i] == b.levels[lvl][i] { return; }
    if lvl == a.depth { out.push(i); return; }
    diff(a, b, lvl + 1, 2 * i, cmps, out);
    diff(a, b, lvl + 1, 2 * i + 1, cmps, out);
}

#[derive(Default, Debug)]
pub struct Stats { pub cmps: usize, pub leaves: usize, pub streamed: usize, pub applied: usize }

/// Diff the trees, then merge per key (higher version wins) in differing leaves only.
pub fn repair(a: &mut Replica, b: &mut Replica, depth: usize) -> Stats {
    let (ta, tb) = (Tree::build(a, depth), Tree::build(b, depth));
    let (mut s, mut leaves) = (Stats::default(), Vec::new());
    diff(&ta, &tb, 0, 0, &mut s.cmps, &mut leaves);
    s.leaves = leaves.len();
    let width = 64 - depth;
    for l in leaves {
        let (lo, hi) = ((l as u64) << width, ((l as u64) << width) | ((1u64 << width) - 1));
        let mut both: Vec<(u64, Entry)> = a.range(lo..=hi).map(|(k, e)| (*k, *e)).collect();
        both.extend(b.range(lo..=hi).map(|(k, e)| (*k, *e)));
        s.streamed += both.len();
        for (k, e) in both {
            for r in [&mut *a, &mut *b] {
                                if r.get(&k).map_or(true, |c| e > *c) { r.insert(k, e); s.applied += 1; }
            }
        }
    }
    s
}

#[cfg(test)]
mod tests {
    use super::*;
    fn fill(n: u64) -> Replica { // keys spread over the whole u64 space
        (0..n).map(|i| (i.wrapping_mul(0x9E3779B97F4A7C15), (1, Some(i)))).collect()
    }
    #[test]
    fn repair_touches_only_differing_leaves() {
        let (mut a, mut b) = (fill(10_000), fill(10_000));
        assert_eq!(repair(&mut a, &mut b, 8).cmps, 1);        // identical: root only
        let k = *a.keys().nth(5).unwrap();
        a.insert(k, (2, None));                               // delete on A (tombstone)
        let s = repair(&mut a, &mut b, 8);
        assert_eq!((s.leaves, s.cmps), (1, 1 + 2 * 8));       // one leaf, depth+1 levels
        assert!(s.streamed < 100);                            // not the 20 000 stored
        assert_eq!(a, b);
        assert_eq!(b[&k], (2, None));                         // tombstone won on B
    }
}

Complexity and constants

• Build O(n): a sequential range read; hashing is cheap next to the I/O.
• Diff at most 1 + 2·d·depth comparisons (8 B each here); tree memory 2^(depth+1) × 8 B (depth 20: 16 MiB); n / 2^depth keys streamed per differing leaf.
• Measured, Apple M4 Pro, code above, 1M keys, 1,000 differing (0.1 %): depth 16 gave 14,047 comparisons and 30,090 keys streamed; depth 20 gave 22,047 comparisons and 1,968 keys streamed.

Efficiency

• Cost: in memory on the M4 Pro, one tree over 1M keys took 11 ms (depth 20) to 26 ms (depth 16); diffing prebuilt trees 20-37 µs; building both, diffing and repairing 33-64 ms against 29 ms for a naive lockstep compare. The tree wins in bytes, not in-memory time. Bound: disk scan to build, network to stream.
• Levers:
  • maintain the tree on every write — repair skips the scan (Riak updates on-disk trees in real time, Riak docs) — scan-bound clusters
  • deeper tree — 30,090 → 1,968 streamed keys for a 2^21-node tree (measured) — scattered differences
  • incremental repair — compares only data written since the last repair (Cassandra docs) — steady writes
  • primary-range scheduling with throttling — no duplicate work (Cassandra docs, -pr) — large clusters
  • per-row checksums plus set reconciliation — x6.78 faster than range checksums when little differs (ScyllaDB blog 2019) — big partitions
• Naive → standard → state of the art:
  • ship every (key, version) pair and compare · 32 MB per replica pair for 1M keys (measured)
  • hash-tree descent, rebuilt per repair · 0.2 MB at depth 20 (about 150x less), a full scan each run
  • trees kept current on write, or row-level checksums with set reconciliation · cost follows d, data read once

Implementation notes

• Hash key, version, value and tombstone flag. A 64-bit non-cryptographic hash suffices against accidental drift (ScyllaDB moved from SHA-256 to 64-bit); use a cryptographic one against adversaries.
• Cost drivers: bytes scanned, hashes per level (send both children in one message), bytes streamed. Read each differing leaf once; one fsync per leaf.
• Merge must be idempotent and commutative: live writes may deliver the same data mid-repair.
• Throttle repair bandwidth with a token bucket; schedule per range (Cassandra docs: every node at least every 7 days, with the 10-day grace period).

Pitfalls

• Missing the grace period: after tombstones are purged, repair copies a missed delete's old value back.
• Too shallow a tree: ScyllaDB's pre-3.1 unit was about 100 partitions; one differing byte could stream 10 GB.
• Repairing every range on every node repeats work; restrict to primary ranges.
• Incremental repair never rechecks data marked repaired: disk corruption slips through.
• Last-writer-wins repair spreads the wrong winner when clocks are skewed.

Variants and alternatives

In production

• Key-value and wide-column stores: Amazon Dynamo, Apache Cassandra (nodetool repair), ScyllaDB, Riak KV (active anti-entropy, trees regenerated weekly by default).
• Object storage: OpenStack Swift replicators. Blockchains: Ethereum state roots.

Implementations

Sources

• Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, section 4.7. paper
• Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, CRYPTO 1987 (LNCS 293). paper
• Apache Cassandra documentation, Repair. docs
• Riak KV documentation, Active Anti-Entropy. docs
• ScyllaDB, Efficiently Maintaining Consistency with Row-Level Repair, 2019. blog
• OpenStack Swift documentation, Replication. docs
• ethereum.org, Merkle Patricia Trie. docs