4.2 Leaderless Replication, Quorum, and Replica Repair

Leaderless systems allow coordinators to distribute read and write operations across a group of replicas without relying on a fixed leader per shard. They can continue serving requests even when some replicas are unavailable, but require explicit handling of concurrent versions, stale replicas, and ongoing replica repair.

N, W, R Describe Only the Set of Confirmed Replicas

• N: the number of replicas for a partition;
• W: the number of replica acknowledgments required for a write to be considered successful;
• R: the number of replica responses required for a read to return a result.

If replies come from distinct replicas in the same fixed set of N, W + R > N guarantees read/write intersection, and W > N/2 guarantees write/write intersection. That intersection is a deterministic set property; obtaining the correct read result from the versions still depends on the protocol. Do not use a global multi-datacenter N directly for LOCAL_QUORUM, or count sloppy-quorum substitute nodes as though they belonged to the original set.

Consider a simplified protocol without read repair: N=3 and R=W=2, but a new write reaches only A before timing out. One read of A and B returns A’s new value. The next read of B and C returns the old value. Both reads obtained quorums, yet the history is not linearizable. This illustrates what the formula leaves unspecified; it is not a measured failure of a Cassandra configuration. Cassandra’s read_repair=BLOCKING adds repair for monotonic quorum reads, while NONE does not provide that guarantee.

The system still needs to address: concurrent coordinators, clock skew, failed write persistence, read repair, deletion, and client retries. When compare-and-set semantics are required, use the product's explicit LWT or consensus mechanisms.

Cassandra Write Path

The coordinator locates replicas using the partition key and waits for the required number of acknowledgments based on the requested consistency level. Replicas typically first append to the commit log, then update their in-memory structures, and finally flush the data into immutable SSTables.

client
  → coordinator
      ├→ replica A: commit log + memtable
      ├→ replica B: commit log + memtable
      └→ replica C: commit log + memtable

Acknowledgment count and disk durability are separate. With commitlog_sync=periodic, writes can be acknowledged before the next log sync; batch and group wait for the relevant sync. Replication does not automatically eliminate loss if all acknowledging replicas lose power together. Check both durability settings and the failure model.

After memtables are flushed and become SSTables, background compaction processes merge these files. Append-only writes improve throughput but introduce amplification of read latency, storage footprint, and compaction tail latency, adding significant operational costs.

Reading Paths Require Version Merging

The coordinator retrieves data or summaries from replicas that meet the consistency level, merges according to cell timestamps and related rules, and returns the result. It does not simply choose one "latest whole row." Out-of-date replicas can gradually catch up through read repair, hinted handoff, and anti-entropy repair.

These mechanisms serve distinct roles:

• hinted handoff temporarily stores write hints for replicas that are briefly unavailable;
• read repair detects and corrects discrepancies during read operations;
• the repair system systematically compares replica ranges and resolves long-term divergence.

Hints expire, and read repair covers only data that is read. Neither replaces complete anti-entropy repair. Ensure repair of the relevant replica ranges finishes within the tombstone gc_grace_seconds window, allowing margin for failures and delays. Starting a job on schedule is insufficient. If a long-offline replica missed a deletion and other replicas have already purged its marker, stale data can return; follow the recovery procedure before rejoining that replica.

Last-Write-Wins Depends on Timestamp Semantics

If conflicts are resolved by selecting the latest value based on a timestamp, clock drift or incorrect client timestamps can cause an older business write to overwrite a newer one. LWW determines a convergent result without ensuring business causality. Suppose an earlier write carries timestamp 1000 from a fast clock, while a later correction carries 900. Selecting the larger timestamp retains the older business value.

A single write owner can reduce concurrency, but server clocks can also be wrong, and an ordinary version column does not implement CAS. Rejecting stale updates needs a real conditional-update protocol. Merging needs a CRDT (Conflict-Free Replicated Data Type) whose behavior fits the business; renaming a field cannot supply those semantics. Before choosing, distinguish:

• Whether concurrent updates to the same field can arbitrarily resolve in favor of one;
• Who wins when a delete and an update occur concurrently;
• Whether merging operations satisfy commutativity, associativity, and idempotency;
• Whether the system needs to expose conflicts to end users.

Partition Design Determines Performance Boundaries

Cassandra tables are designed around query patterns. The partition key determines data routing and co-location, while clustering columns dictate sorting within a partition.

Too small partitions increase metadata overhead and cross-partition fan-out; too large partitions lead to hotspots, prolonged GC and compaction times, and difficult recovery. Avoid using ALLOW FILTERING to obscure unmodeled queries, and don't treat cross-partition batch operations as general transactions.

Deletion is more complex than writing

Deleting a value immediately from available replicas would allow an offline replica to propagate its old copy later. Instead, deletion writes a tombstone, which is reclaimed only when repair, retention, and compaction conditions permit it. Expiring gc_grace_seconds makes reclamation possible; it does not delete the marker immediately. Older values covered by it must not remain in SSTables excluded from the necessary compaction.

A large number of tombstones increases read scan and compaction overhead. TTLs, time-series tables, and frequent deletions must be considered during schema design, not as afterthoughts addressed by setting a single threshold after deployment.

Monitoring Signals

• Latency and unavailability errors for each consistency level;
• Partition size, hot keys, and coordinator fan-out;
• Pending compaction, SSTable count, and disk amplification;
• Repair progress, longest-unrepaired range, and streaming throughput;
• Tombstone scanning, tombstone discarding, and GC window behavior;
• Dropped mutations, hint backlog, and replica version differences.

Next lesson, we compare large file systems with global transactional databases to understand why distributed storage systems adopt such fundamentally different coordination costs.

References

• Apache Cassandra, Dynamo architecture
• Apache Cassandra, Guarantees
• Apache Cassandra, Read repair
• Apache Cassandra, Tombstones
• Apache Cassandra, Commit log synchronization