Quorums & tunable consistency

How R + W > N guarantees overlap

N is the replication factor, the number of copies the store keeps for each key. A write waits for W of those replicas to ack; a read collects responses from R of them. When R + W > N, the read set and the last acknowledged write set cannot be disjoint: by the pigeonhole principle they share at least one replica, and that replica holds the newest acknowledged write. The read compares versions (or timestamps) across what came back and returns the newest, so it observes that write.

The rule needs R + W strictly greater than N. Equal is not enough: R=1, W=2 sums to exactly 3, and a write to {A,B} with a read from {C} shares nothing. The same arithmetic sets fault tolerance, since a configuration keeps working as long as no more than n - max(w, r) replicas are down. For (3,2,2) that is one node.

Tuning R and W for reads vs writes

R and W trade read cost against write cost under the fixed rule R + W > N.

• W = N (so R = 1): reads touch one replica and are fast, but every write must reach all N, so one down replica halts writes.
• W = 1: writes ack after a single replica, fast and highly available, but durability is thin and R must grow to preserve overlap.

The latency of a read or write is set by the slowest of the R (or W) replicas it waits on, which is why production systems usually run R and W below N and accept eventual consistency for lower latency. Dynamo's common configuration is (3,2,2).

Wrong "W=1 is safe, the write is durable once one node has it." If that node crashes before the value replicates, the acknowledged write is gone, and low W also raises the chance a later read misses the newest value. W=1 buys availability, not safety.

Per-operation tunable consistency

Rather than one global setting, the caller picks per operation how many replicas to wait for. Cassandra exposes levels on each read and write: ONE (fastest, weakest), QUORUM (a majority across all datacenters), LOCAL_QUORUM (a majority in the local datacenter, avoiding cross-datacenter latency), and ALL (every replica, strongest, but fails if any replica is down or slow). QUORUM is (sum_of_replication_factors / 2) + 1, so RF=3 gives 2. The server default level is ONE, and many client drivers default to LOCAL_ONE. Riak exposes the same idea as per-request n_val, r, and w, each taking an integer or a symbol like quorum or all.

Why R + W > N is not linearizability

Overlap guarantees only that a read touches at least one replica holding the newest acknowledged write. It orders nothing, so stale reads happen even while R + W > N holds:

• Two concurrent writes have no agreed order, so replicas diverge and a conflict rule (often last-write-wins) settles it after the fact.
• A read concurrent with a write can reach quorum before the write propagates and catch the old value.
• A write that fails partway is not rolled back, and a crashed node restored from an older replica reintroduces a stale value.

Wrong "QUORUM reads plus QUORUM writes give strong consistency." They give overlap, and with blocking read repair monotonic quorum reads, but concurrent operations can still be ordered ambiguously. Right linearizability needs consensus (Paxos or Raft) or an ABD-style read that repairs and writes back before returning. A Cassandra compare-and-set needs a Lightweight Transaction at SERIAL rather than plain QUORUM.

Sloppy quorum and hinted handoff

To stay available during partitions, Dynamo relaxes membership: a read or write goes to the first N healthy nodes on the key's preference list (an ordered set larger than N), which may not be the key's home nodes. A write for a down node A goes to a reachable node D with a hint naming A; D keeps hinted replicas in a separate local database it scans periodically, forwarding the value once A recovers.

This buys write availability at the cost of overlap: the W writes can land entirely on non-home nodes while a read hits the home nodes, so the sets share nothing until handoff completes. Riak makes it explicit, defaulting pr/pw to 0 (sloppy); pr/pw > 0 is a strict quorum that fails rather than use non-primary nodes. Cassandra's ANY write is the extreme, where a hint alone satisfies it. Handoff is best-effort, and a hint is lost if its holder dies first. This describes the 2007 paper, not Amazon DynamoDB, which uses a different leader-per-partition design.

Read repair versus anti-entropy

Interviewers check that you know why both paths exist. Read repair is foreground and opportunistic: on a read above ONE the coordinator asks one replica for data and the rest for a digest (hash); on a mismatch it pulls full copies, reconciles by timestamp, and writes the newest back. It only fixes keys that get read. Cassandra's blocking read repair (the default since 4.0, after the probabilistic read_repair_chance option was removed) blocks the read on those repair writes and so supplies monotonic quorum reads.

Anti-entropy is the background sweep covering every key, cold ones included. Each node keeps a Merkle tree per key range: leaves hash individual key values, parents hash their children. Nodes compare root hashes and, on a mismatch, walk down to the divergent leaves so only those keys transfer (nodetool repair in Cassandra). Skip it and rarely-read keys stay divergent and deleted rows can resurrect, hence tombstones kept for gc_grace_seconds.

Conflict resolution: LWW, version vectors, CRDTs

Last-write-wins keeps the version with the largest physical timestamp and discards the rest with no error. It is Cassandra's only conflict resolution, applied per cell on the write timestamp. Under clock skew a lagging node can stamp a newer write with an older time and lose it, so concurrent updates vanish silently.

Version vectors instead tag each version with (node, counter) pairs that reveal whether one version descends from another or they are concurrent. Concurrent versions are both kept and returned to the client (Dynamo's cart merges the divergent carts); Riak surfaces them as siblings when allow_mult is set. CRDTs (Riak Data Types, Cassandra counters as a narrow case) merge concurrent updates deterministically, with no application logic and no lost write.