4.2 Leaderless Replication, Quorum, and Replica Recovery

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 long-term recovery processes.

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.

W + R > N ensures that the read and write sets overlap, W > N/2 ensures that the successful write sets overlap. Overlap increases the likelihood that a read will see a version that has been confirmed, but it does not constitute a complete proof of linearizability.

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

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, compares versions, and returns the winning result. 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.

Without periodic repair, eventual consistency remains merely a theoretical goal. The repair interval must also be shorter than the tombstone and deletion reclamation window; otherwise, deleted data might "resurrect" from long-term offline replicas.

Last-write-wins Dependency Timestamp Semantics

If conflicts are resolved by selecting the latest value based on a timestamp, clock drift or incorrect client timestamps can cause older business writes to be overwritten by newer ones. While LWW (last-write-wins) guarantees convergence, it does not ensure that the resulting state aligns with business causality.

To reduce conflicts, strategies such as single-write ownership, server-side timestamps, version numbers, conditional updates, or CRDTs (Conflict-Free Replicated Data Types) can be employed. Before selecting a strategy, it's essential to distinguish between:

• 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

Distributed replicas cannot be physically deleted immediately, or else offline replica recovery would re-propagate the old values. Instead, deletion begins with writing a tombstone marker, and the actual removal occurs only after meeting both recovery and retention conditions.

A large number of tombstones increases read scan and compaction overhead. TTLs, time-sorted logs, 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, oldest unreplicated 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