Implementing Anti-Entropy and Repair
1. Understanding Anti-Entropy Mechanisms
| Mechanism | When | Cost |
|---|---|---|
| Read repair | On read divergence detected | Lazy; bounded to active keys |
| Hinted handoff | Replica temporarily down | Buffered writes replayed |
| Background repair | Scheduled scan | Full data sweep, expensive |
| Merkle-tree sync | Periodic comparison | O(log n) tree traversal |
2. Implementing Read Repair
| Step | Action |
|---|---|
| 1 | Coordinator queries R replicas |
| 2 | Detect divergent versions (timestamp / vector clock) |
| 3 | Return latest to client |
| 4 | Async write latest to stale replicas |
3. Implementing Write Repair
| Pattern | Detail |
|---|---|
| Definition | Coordinator writes to all replicas; failed writes hinted |
| Async replication tail | Background catches up missing writes |
| Combined with hinted handoff | Standard Cassandra/Dynamo flow |
4. Implementing Merkle Trees for Synchronization
| Property | Value |
|---|---|
| Structure | Binary tree; leaves = chunk hashes; internal = hash of children |
| Compare cost | O(log n) per diff; O(diff) bytes transferred |
| Used by | Cassandra, Dynamo, Git, BitTorrent |
Example: Merkle tree leaf hash
byte[] leafHash(byte[] key, byte[] value) {
return Hashing.sha256()
.newHasher()
.putBytes(key).putBytes(value)
.hash().asBytes();
}
byte[] internalHash(byte[] left, byte[] right) {
return Hashing.sha256()
.newHasher()
.putBytes(left).putBytes(right)
.hash().asBytes();
}5. Implementing Hinted Handoff
| Step | Action |
|---|---|
| 1 | Coordinator writes to replicas; one is down |
| 2 | Store hint (target, key, value, ts) on alive replica |
| 3 | Periodically retry forwarding hint to recovered node |
| 4 | Bound TTL (Cassandra default 3h) to avoid unbounded growth |
6. Understanding Repair Scheduling Strategies
| Strategy | Frequency | Impact |
|---|---|---|
| Full repair | Weekly or after partition | High I/O |
| Incremental | Continuous | Lower per-cycle cost |
| Subrange | Slice token range | Bounded duration |
| Reaper-style orchestration | Coordinated across cluster | Avoids overlap |
7. Implementing Background Repair Jobs
| Aspect | Detail |
|---|---|
| Throttling | Limit MB/s and concurrent ranges |
| Off-peak windows | Schedule during low traffic |
| Idempotent restarts | Resume from checkpoint |
| Tools | Cassandra Reaper, Yugabyte Anywhere |
8. Handling Inconsistency Detection
| Method | Use |
|---|---|
| Checksum / digest read | Cheap divergence check before full read |
| Merkle tree diff | Bulk reconciliation |
| Vector-clock compare | Identify causally divergent versions |
| Audit jobs | Periodic full-row checksums |
9. Implementing Full vs Incremental Repair
| Mode | Scope | When |
|---|---|---|
| Full | Entire dataset re-validated | After major outage; periodic safety net |
| Incremental | Only un-repaired SSTables | Routine; faster cycles |
| Combination | Incremental + occasional full | Production best practice |
10. Understanding Repair Trade-offs
| Factor | Trade |
|---|---|
| More frequent repair | Lower divergence; higher cost |
| Wider parallelism | Faster completion; more I/O contention |
| Stronger read consistency | Reduces need for repair; higher read latency |