Cassandra repair architecture — Merkle trees, incremental, subrange, preview

Where repair sits among the anti-entropy mechanisms

Cassandra converges replicas through three independent paths, and they cover disjoint failure windows. Hinted handoff replays writes that a coordinator held for a replica that was down at write time, but only for a bounded hint window and only if the coordinator itself survived - see Cassandra hinted handoff architecture. Read repair reconciles the replicas that participated in a read when their digests disagree, which means it only ever touches data somebody queried - see Cassandra read repair architecture. Both are opportunistic. Neither is a guarantee.

Repair is the guarantee. It compares the full contents of a token range across every replica and reconciles whatever differs, regardless of whether anyone has read it, whether hints expired, or whether a node was down long enough that hints were never written at all.

The reason repair is mandatory rather than merely nice is deletion: a replica that missed a delete and is not repaired before the tombstone is purged will resurrect the row. That argument - tombstones, gc_grace_seconds, and zombie data - is developed in full in Cassandra tombstones, and this article does not repeat it. What follows assumes you have accepted that a repair schedule is compulsory and asks what running one actually does to the cluster.

The architecture: every piece explained

The top strip is the mechanism. The replica set is the group of nodes holding a given token range. The Merkle tree is a per-range hash tree each replica builds so the coordinator can locate disagreements without shipping the data. The streaming session moves the differing rows between replicas. The repair scheduler - cron around nodetool, or a purpose-built tool such as Cassandra Reaper - decides when and where sessions run.

The middle row is the variants, and each is a different answer to the same question: how much of the dataset do we hash this time. Full repair hashes everything in the range, so its cost tracks total data size rather than divergence. Incremental repair tracks which SSTables have already been proven consistent and skips them. Subrange repair shrinks the range so a single session is small, bounded, and retryable. Preview repair builds the trees and computes the difference but declines to stream it, turning repair into a measurement. The anti-entropy service is the internal machinery that carries the validation requests and sync tasks between nodes.

The lower rows are the operational surface, and they are where repair is actually won or lost: concurrency caps that keep validation from crowding out foreground work, throughput throttles on both compaction and streaming, and observability that tells you which ranges have been covered rather than merely which commands exited zero.

The repair session lifecycle

The node you run nodetool repair on becomes the coordinator for that repair, and it stays the coordinator for the entire run. It first resolves which token ranges it is a replica for, then, for each of those ranges, the full replica set that must participate. That produces a parent repair session holding one child session per range.

Each child session runs the same four phases. The coordinator sends a validation request to every replica of the range. Each replica independently builds a Merkle tree over its own copy of that range and returns the tree. The coordinator differences the trees pairwise, producing, for each pair of replicas, the list of leaf ranges on which they disagree. It then issues sync tasks: for every disagreeing pair, each side streams its version of the affected ranges to the other. When all sync tasks complete, the session succeeds.

Two structural consequences follow. First, the session is only as fast as its slowest replica, because differencing cannot start until every tree has arrived; one node with a compaction backlog stalls the whole range. Second, the coordinator is a single point of failure for the run - if it restarts mid-session, the child sessions orphan and the participating replicas are left holding state until timeouts fire. Session outcomes are recorded in the system_distributed repair history tables, which is where you look when a run reports failure without telling you which range.

Validation compaction - why repair is disk and CPU heavy

The phase people underestimate is building the tree. A replica cannot hash a range by reading an index; it has to reconstruct the current logical contents of that range first. That means opening every SSTable whose token span overlaps the range, merging them the way a read would - newest cell timestamp wins, tombstones shadow older data - and hashing the merged result. Cassandra runs this as validation compaction: a real compaction-shaped pass over the data that produces a hash tree instead of a new SSTable.

So repair is not primarily a network operation. Before a single byte is streamed, every replica has performed a full sequential read of the range's data on every SSTable that covers it. On a table under size-tiered compaction, where a given token can appear in many SSTables at once, that read amplification is exactly the amplification described in Cassandra compaction strategies, paid again for the whole range.

Because validation runs on the compaction path, it is governed by the same throughput ceiling as ordinary compaction and shares that executor. This produces the most common repair complaint: during repair, pending compactions climb and flushes back up, because validation is consuming the budget that normal compaction needed. The second-order effect is subtler - validation drags cold data through the page cache, evicting the hot working set, so read latency degrades for a while after the repair has finished. The -j option, which validates multiple tables concurrently, multiplies both effects; it is a throughput knob, not a free speedup.

What Cassandra specifically does with Merkle trees

The property being exploited is standard: hashing data into a tree lets two parties find where they differ by exchanging a number of hashes proportional to the tree depth rather than to the data size. That structure, and the general trade between leaf granularity and build cost, is covered in Merkle trees and Merkle tree architecture. What matters here is how Cassandra parameterises it.

Cassandra builds one tree per token range per replica, from scratch, on every session. The trees are not maintained incrementally as writes land - they are a byproduct of the validation pass and are discarded when the session ends. On a cluster using vnodes, where each node owns many small ranges rather than one contiguous one, that means a repair produces many small trees instead of one large one, which is generally the cheaper shape; see Cassandra vnodes architecture.

The critical detail is what a leaf represents. A leaf is a sub-range of the token space, not a row. Two replicas that disagree about one column of one row disagree at the leaf that contains that row's token, and the reconciliation unit is the whole leaf. Since the tree has a bounded size, a range holding more data gets coarser leaves - each leaf covers proportionally more partitions - so the amount of data shipped to fix one row grows with the size of the range being repaired.

Streaming the differences, and why over-streaming happens

Once differencing identifies the disagreeing leaves, the replicas exchange the underlying data over the same streaming machinery that moves data during bootstrap and decommission, described in Cassandra bootstrap architecture. It is throttled independently of compaction by the outbound stream throughput setting, and nodetool netstats is where you watch it progress.

This is where over-streaming shows up as a real bill. Because the unit is a leaf range and not a row, a table where a handful of rows diverged can still move gigabytes, and the ratio of bytes streamed to bytes actually stale is often terrible. Worse, the cost has a tail: streamed data arrives as new SSTables on the receiving node, which then have to be compacted into the existing set. A repair that finished an hour ago is frequently still generating compaction load.

Over-streaming is the strongest practical argument for repairing smaller ranges. A smaller range gets finer leaves for the same tree budget, so the same divergence resolves into less transferred data.

Full vs incremental repair and the repaired-set split

Full repair hashes every row in the range every time. Its cost is a function of how much data you have, not of how much of it has drifted, which means a cluster that is almost perfectly consistent pays the same validation bill as one that is badly diverged. On a large table that bill eventually stops fitting in the maintenance window.

Incremental repair attacks exactly that. Each SSTable carries a marker recording whether its contents have already been proven consistent by a successful repair. After a session succeeds, the SSTables it covered are marked repaired, and subsequent incremental sessions validate only the unrepaired data - the SSTables written since. Steady-state cost then tracks the write rate rather than the dataset size, which is the whole point.

What the split actually costs

The mechanism has a price that is easy to miss. An SSTable whose token span only partially overlaps the repaired range cannot be marked wholesale, so Cassandra performs anticompaction: it rewrites the file, splitting it into a repaired portion and an unrepaired portion. That is a full rewrite of the file's data - additional write amplification attributable purely to the repair strategy.

From then on, repaired and unrepaired SSTables are never compacted together, a constraint noted in Cassandra SSTable format architecture. Each table effectively maintains two parallel SSTable pools that compact independently. A read may therefore touch files from both, so the SSTables-per-read distribution widens, and the compaction strategy's assumptions about tier sizes are computed over each pool separately rather than the whole table.

The other operational wrinkle is failure. A session that dies partway can leave data in a pending state, neither repaired nor cleanly unrepaired, and the next session will refuse to proceed on those ranges until it is resolved. nodetool repair_admin is the tool for listing and cancelling stuck sessions, and knowing it exists before you need it saves an outage. The honest summary: incremental repair pays off on append-mostly tables with a large stable history, and pays off least on tables that rewrite most of their rows, where almost nothing stays marked repaired for long.

Bounding the blast radius - subrange and primary-range repair

By default, nodetool repair on a node repairs every range that node replicates. With RF=3 each range is replicated by three nodes, so running the default command on all of them repairs every range three times. That is not a subtle inefficiency; it is triple the validation cost of the correct schedule.

The -pr option restricts a run to the ranges for which the node is the primary replica. Run once on every node, that covers the ring exactly once. The constraint is exactly that: it must run on every node, and it must be a complete pass, because a node skipped is a set of ranges never repaired. The same caution applies across data centres - a run confined to the local DC never reconciles cross-DC divergence, which is a trap worth checking against your topology, discussed in Multi-DC Cassandra topology.

Subrange repair goes further by taking explicit start and end tokens (-st and -et) and repairing only that interval. It buys three distinct things. Failure is contained - one bad segment fails alone instead of taking a multi-hour run down with it. Merkle leaves are finer for the same tree budget, so less data over-streams. And the work becomes resumable, because a scheduler can retry an individual segment without redoing the ring.

This is the shape purpose-built schedulers implement: split the ring into segments, run them with a bounded concurrency, retry the ones that fail, and track coverage per segment. The counter-pressure is per-session overhead - every session has fixed setup and coordination cost, so segments that are too small spend their time on bookkeeping rather than on data.

Preview repair - measuring divergence without paying to fix it

Preview mode runs validation and differencing and then stops, reporting how much data would have been streamed without streaming any of it. That turns repair into an instrument: you get a number for how far apart your replicas actually are.

Three uses justify it. Before committing to a full repair on a table you have never repaired, preview tells you whether the streaming phase is going to be minutes or days. On a cluster running incremental repair, preview against the repaired set answers the question incremental repair cannot answer for itself - whether the data it has been skipping is genuinely consistent. And after an incident, preview sizes the damage before you decide on a remediation window.

It is not free. Preview still pays the entire validation compaction cost, which is usually the larger half of a repair; only the streaming and the resulting compaction tail are avoided. Budget it as a substantial fraction of a real repair, not as a dry run.

Coordinating repair across a cluster

Two repair sessions covering the same token range at the same time are a conflict, not a speedup - the participating replicas are being asked to validate and stream the same data twice, and with incremental repair the marking of the repaired set becomes ambiguous. The scheduling invariant is therefore simple to state and easy to violate by accident: at most one session per range in flight. A cron entry that fires nodetool repair on all nodes at midnight violates it immediately.

Above that invariant sits a capacity decision. Validation consumes the compaction budget, so the number of nodes validating simultaneously should be a deliberate fraction of the cluster rather than whatever the schedule happens to produce. Then a deadline: the entire ring must be covered within the gc_grace_seconds window. That gives an arithmetic check most teams never perform - segment count times mean segment duration, divided by cluster-wide concurrency, must be comfortably under the grace window. If it is not, no amount of tuning individual sessions helps; you need more concurrency, a longer grace window, or less data per node.

Track that with coverage rather than exit codes. The question worth alerting on is not "did last night's repair job succeed" but "what is the oldest token range in this cluster by last-successful-repair time". The repair history tables and repair-specific metrics are what feed that, alongside the broader instrumentation in Cassandra operational metrics.

Failure modes on a large cluster

The session that never ends. A single replica with a deep compaction backlog can take hours to return its tree, and every other participant sits idle waiting. The symptom is a session showing no progress with no error; the cause is usually on a node the operator is not looking at.

The orphaned session. A node restarts mid-repair - a rolling upgrade, an OOM, a hardware event - and the sessions it was participating in hang until timeouts fire. With incremental repair the range can be left pending, which blocks the next attempt rather than merely losing this one.

The stalled stream. Streaming connections that die without closing cleanly can sit until a socket-level timeout expires. nodetool netstats showing a transfer frozen at a fixed byte count is the tell, and it is worth checking before assuming a session is merely slow.

The compaction cascade. This is the one that ends schedules. Repair generates anticompaction rewrites and streamed SSTables; those raise the pending compaction queue; a deeper queue makes the next repair's validation slower; slower validation means the ring takes longer to cover; and eventually coverage time crosses the grace window. Each step is individually unremarkable, which is why the failure is usually noticed only when zombie data appears.

Silent incomplete coverage. A repair that reports success can still have skipped ranges - a node was down and its ranges were never attempted, or -pr was run on a subset of nodes. Nothing surfaces this except per-range coverage tracking.

Disk headroom. Anticompaction rewrites files and streaming lands new ones, so a repair needs free space proportional to the data it touches. A node comfortable at steady state can fail repair, and a node that fails repair keeps diverging.

End-to-end flow

A working schedule looks like this. A scheduler splits the ring into subrange segments sized so that a single segment completes in minutes rather than hours. It runs segments with a cluster-wide concurrency cap chosen so that only a small fraction of nodes are performing validation compaction at any moment. For each segment, the coordinator requests trees from the replicas, which each perform a validation pass over the SSTables covering that range; the coordinator differences the returned trees and issues sync tasks; the replicas stream the leaf ranges on which they disagree; the streamed SSTables compact into place over the following minutes. Failed segments are retried individually rather than failing the run. Incremental repair keeps steady-state validation cost proportional to the write rate, with a periodic full or preview pass to confirm the repaired set is genuinely consistent. The metric that matters throughout is not job success but the age of the least recently repaired range, watched against the grace window it must stay under.