Quorums and leaderless replication

Leaderless replication drops the leader: every replica of a key accepts reads and writes, and the client, or a coordinator node acting for it, decides success by counting replies. A quorum is that count. With N copies of each key, a write succeeds once W replicas acknowledge it and a read once R replicas answer, and versioning, repair and failure detection keep the copies converging in the background.

Picture it first: three credit notebooks

A grocer keeps her customers’ credit in three identical notebooks, held by three family members in different parts of town. There is no master copy.

• To record a purchase, she phones all three and moves on as soon as two confirm.
• To check a balance, she calls two and believes whichever entry has the later time.
• If one is travelling, a neighbour writes the entry on a slip marked “give this to Raju when he’s back”.
• If two notebooks disagree during a call, she corrects the stale one on the spot.
• Every Sunday they compare page totals and only read the pages whose totals differ, line by line.

Map it back: the notebooks are replicas (N = 3), “two confirm” is W = 2, “call two” is R = 2, the neighbour’s slip is hinted handoff, correcting during a call is read repair, and the Sunday comparison is anti-entropy with Merkle trees. The trouble starts when two family members write different entries at the same moment, or when someone’s watch is wrong.

How a leaderless write and read flow

Each key is hashed onto a consistent-hashing ring. Its preference list is the next N distinct physical nodes clockwise from the key’s position, skipping extra virtual nodes of a machine already chosen. Every node can compute this list, so any node can take a request.

The node handling a request is the coordinator. In Dynamo it is normally the first node in the preference list: a partition-aware client library sends requests straight to it, while a generic load balancer may hit any node, which then forwards. Cassandra lets any node coordinate.

A write. The coordinator sends the write to all N replicas and reports success once W have acknowledged. Cassandra is explicit that writes always go to every replica; the consistency level only decides how many acknowledgements the coordinator waits for.

A read. The coordinator asks enough replicas to reach R, compares what comes back and returns the newest version. Cassandra saves bandwidth by requesting the full row from the fastest replica and only a hash (a digest) from the others.

The quorum rule is a counting argument: if R + W > N, any R replicas you read include at least one of the W that took the latest acknowledged write, and the reader keeps the newest version it sees. The CAP theorem and PACELC article walks through the overlap with a picture. The latency rule matters as much: a request is as slow as the W-th (or R-th) fastest replica, which is why the Dynamo paper sets R and W below N.

Choosing N, R and W

N sets durability and how many failures you can ride out; R and W trade latency, availability and freshness. The Dynamo paper reports (N, R, W) = (3, 2, 2) as the common setting, and describes read-heavy services that used R = 1 with W = N, buying fast reads with fragile writes. Setting W = 1 means a write is accepted while any node can take it, but a write acknowledged by one node is lost if that node dies before passing it on.

Cassandra hides the arithmetic behind named consistency levels. With one data centre and a replication factor of 3:

QUORUM writes plus QUORUM reads give 2 + 2 > 3, so reads overlap writes. ONE with ONE gives 1 + 1 = 2, so a read can miss a write that was acknowledged a moment ago.

Across data centres

Now spread the keyspace over two data centres, Mumbai and Frankfurt, with three replicas in each: six replicas per key. QUORUM means a majority of all six, 6 ÷ 2 + 1 = 4, and the local data centre holds only three, so every QUORUM request waits for at least one replica across the WAN. For a client in Mumbai:

LOCAL_QUORUM is the usual default for multi-region apps: users homed to one data centre read their own writes at local latency, and a whole remote region can vanish without stopping them. EACH_QUORUM writes are for the rare data that must be durable in every region before you say yes, at the price of the WAN round trip and of failing whenever any region is unreachable.

Versions and conflicts

With no leader to order writes, two clients can write the same key at the same time through different coordinators, and replicas can receive writes in different orders. Every leaderless store needs a rule for deciding which version wins, or for keeping both.

Last write wins, by timestamp

Cassandra attaches a timestamp to every write, taken from the client or, if the client sends none, from the coordinator’s clock, and keeps the highest. It does this per column, so two clients updating different columns of the same row both survive; only writes to the same cell compete.

Last-write-wins (LWW) is simple, needs no client code and always converges. Its flaw is in the name: “last” means the highest timestamp, not the most recent event. If one app server’s clock runs fast, its writes beat genuinely later writes, and the loser vanishes without an error. Cassandra’s documentation states plainly that correctness depends on synchronised clocks.

Live with LWW by keeping clocks tight (NTP or chrony on every node and client, with alerts on drift), avoiding read-modify-write cycles on a single hot cell, and modelling changes as new rows (an append-only status log keyed by a time-based UUID) instead of overwriting one cell. When an overwrite truly must not be lost, use a lightweight transaction, below.

Vector clocks and siblings

The Dynamo paper took the other route: detect concurrency instead of guessing. Each version carries a vector clock, a list of (node, counter) pairs. Version X descends from version Y if every counter in Y is ≤ the matching counter in X; then Y can be thrown away. If neither descends from the other, the writes were concurrent, and the store keeps both as siblings.

A read returns all siblings plus an opaque context summarising their clocks. The application merges them and writes the result back with that context, which collapses the branches. Here is the shopping-cart case:

PUT [milk]                    coordinated by A  ->  {A:1}
PUT [milk, bread]             coordinated by A  ->  {A:2}
-- two devices both read {A:2}, then write without seeing each other
PUT [milk, bread, eggs]       coordinated by B  ->  {A:2, B:1}
PUT [milk]  (bread removed)   coordinated by C  ->  {A:2, C:1}
GET -> 2 siblings: neither clock is >= the other in every entry
merge = union of items  ->  [milk, bread, eggs]   {A:3, B:1, C:1}

The union never loses an add-to-cart, which is exactly why Amazon chose it, and the paper admits the cost: deleted items can resurface, as bread did above. Merges that get removals right need richer types such as CRDT sets, covered in clocks, ordering and conflict resolution.

Two practical notes. Siblings are rare: over 24 hours, 99.94% of requests to Amazon’s cart service saw exactly one version, and the paper attributes most divergence to concurrent automated clients rather than failures. And clocks grow when many nodes coordinate writes, so Dynamo truncated the oldest pair once a clock held about 10 entries. Riak exposes this model directly: with allow_mult set to true, concurrent writes become siblings (Riak recommends this), and with it off, Riak falls back to timestamps. Since Riak 2.0, dotted version vectors tag each sibling with the exact write that created it, which keeps the number of siblings in check.

Repair: read repair, hinted handoff, anti-entropy

Replicas miss writes all the time: a node restarts, a packet is dropped, a write times out. Three mechanisms bring them back in line, each covering a different gap.

Read repair

When a read finds replicas that disagree, the coordinator fixes the stale ones it just talked to.

Cassandra’s read repair is blocking by default: the client does not get its answer until the repair write has reached the consistency level. That buys monotonic quorum reads, so two successive QUORUM reads never go backwards, even after a write that reached only a minority. Reads at ONE or LOCAL_ONE compare nothing and repair nothing. Rarely read keys are never repaired this way, which is why it cannot be the only mechanism.

Hinted handoff and sloppy quorums

When a replica is down during a write, someone holds the write for it and delivers it later. The Dynamo paper goes further with a sloppy quorum: if a home replica is unreachable, the write goes to the next healthy node on the ring, which stores it with a hint naming the intended owner and hands it over when that node recovers. Writes keep succeeding through failures, which is the point of an always-writeable store.

The price is the overlap guarantee. W acknowledgements from stand-ins are not W acknowledgements from the key’s home replicas.

Systems differ here, so check which kind of quorum you have:

• Riak uses sloppy quorums by default. Setting PR and PW (primary read and write counts) above zero requires that many acknowledgements from the key’s home replicas: a strict quorum, with more failed requests during outages.
• Cassandra keeps quorums strict. The coordinator stores the hint on its own disk, and hints count towards nothing except the ANY level. Hints are kept for a node that has been down up to 3 hours (max_hint_window); after that, only repair can bring it up to date.

Hints can pile up. Cassandra’s docs work an example: a node taking 100 Mbit/s of writes that restarts for 10 minutes accumulates about 7 GiB of hints, which at the default 1,024 KiB/s delivery throttle takes about 2 hours to replay.

Anti-entropy with Merkle trees

Read repair only fixes keys someone reads, and hints expire or die with their holder. The safety net is anti-entropy: replicas compare their whole datasets in the background. Shipping every key would be absurd, so they compare Merkle trees: each leaf is a hash of one slice of a token range, and each parent is a hash of its children.

In Cassandra this is nodetool repair. It is not automatic in the classic setup: operators schedule it. Incremental repair (the default) only covers data written since the last incremental run, while full repair rehashes everything and should still run occasionally, because incremental repair won’t catch disk corruption or operator mistakes in data already marked repaired. Adding -pr on every node repairs each range once instead of once per replica. The docs suggest incremental repair every 1–3 days and a full repair every 1–3 weeks as a starting point.

Deletes, tombstones and zombies

Deletes are the hardest write to replicate. If a replica simply removed the value while another replica was down, repair would later find the value on the returning node and copy it back: the delete is undone. So Cassandra writes a delete as a tombstone, a timestamped marker that travels and repairs like any other write.

Tombstones can’t live forever, so each one becomes purgeable after gc_grace_seconds, 864,000 seconds (10 days) by default, at the next compaction. Here is the trap: if a replica misses the tombstone and is not repaired within those 10 days, the other replicas drop the tombstone, and the next repair treats the old value on the lagging node as live data and spreads it back. That resurrected value is a zombie. The rule from the docs: repair every node at least once within gc_grace_seconds, and in practice every 7 days to leave slack.

Failure detection without a leader

Nobody is in charge, so every node decides for itself which peers are alive. In Cassandra, every second each node bumps its own heartbeat counter and swaps state with one random peer, plus occasionally an unreachable node and a seed node. That is the gossip protocol, and it spreads membership, token ownership and schema versions in a few rounds.

Deciding “down” uses a phi accrual failure detector. Instead of a fixed timeout, each node tracks how regularly heartbeats from a peer arrive and computes a suspicion value, φ, that grows the longer the next heartbeat is overdue relative to that history. Cassandra convicts a peer when φ reaches phi_convict_threshold, 8 by default; it then stops routing reads there and stores hints for its writes. A node on a jittery network is judged against its own history, so it is not convicted by a timeout tuned for quiet nodes.

Two design choices keep this sane. UP and DOWN are local opinions, not gossiped facts: A may consider B down while C still talks to it. And a down node is not a departed node: Dynamo and Cassandra add and remove nodes only by explicit operator action, so a node that reboots for five minutes does not trigger a costly rebalance of its data.

When R + W > N still returns stale data

The overlap argument is sound, but it assumes things production doesn’t promise. Each of these breaks it:

1. Sloppy quorums. Acknowledgements from stand-ins don’t overlap a read of the home replicas, as in the figure above.
2. Partially failed writes. A write reaches one replica and then times out; the client sees an error. Nothing rolls it back, so later reads may or may not return it, and it may spread through repair. Blocking read repair at least stops it from appearing and then disappearing.
3. Concurrent writes under LWW. Two writes land at once; one silently loses, whatever the quorums.
4. Clock skew under LWW. A newer write with an older timestamp loses to an older write, as in the order-status example.
5. Reads racing a write. While a write is in flight, one quorum read may see the new value and a later one the old value from different replicas, unless read repair is blocking. Either way, the system does not behave like one copy.
6. Losing the fresh replicas. If one of the W replicas that took the latest write dies and is rebuilt from a replica that missed it, the latest value may now sit on fewer than W nodes, and the overlap is gone.
7. Expired tombstones. Skip repair past gc_grace_seconds and deleted data comes back.

So quorums give you a probably fresh read, which is enough for a profile, a feed or a cart. They don’t give you linearizability: “reads that start after a write is acknowledged see it, and nobody ever sees it go away”.

Lightweight transactions for the few that need them

Cassandra’s lightweight transactions (LWT) add compare-and-set to a single partition by running the Paxos consensus protocol among that partition’s replicas:

-- Claim a username exactly once; [applied] = false tells the loser who has it
INSERT INTO usernames (name, user_id) VALUES ('priya_k', 8812) IF NOT EXISTS;

-- Move a balance only if nobody changed it since we read it
UPDATE wallets SET balance = 450 WHERE user_id = 8812 IF balance = 500;

They are linearizable, and they are expensive. The classic Paxos implementation (paxos_variant: v1, still the default) needs about 4 round trips for a write and 3 for a read, against 1 for a plain quorum write. Cassandra 4.1 added Paxos v2, recommended in the configuration reference, at about 2 round trips for a write and 1–2 for a read. Do the arithmetic for your network: at 1 ms per round trip inside a data centre, a v1 LWT costs about 4 ms, which is fine for sign-ups. With replicas 70 ms apart across regions, it costs about 4 × 70 = 280 ms, and contended keys retry on top of that.

Use LWT for usernames, seat holds, idempotency keys and balances, and plain quorum writes for everything else. Never mix LWT and plain writes on the same cells: the plain write skips Paxos and can overwrite the value Paxos just agreed on. For “one seat, many buyers” at scale, see contention and double booking.

DynamoDB is not leaderless

The names invite confusion. Dynamo is the 2007 internal system from the paper, and it was leaderless. Amazon DynamoDB, the managed service launched later, took Dynamo’s partitioning ideas but not its replication model. The 2022 USENIX ATC paper on DynamoDB describes each partition as a replication group that uses Multi-Paxos to elect a leader:

• Only the leader serves writes and strongly consistent reads. A write is acknowledged once a quorum of peers has persisted its log record; with three replicas in three availability zones, the healthy write quorum is two of three.
• Any replica can serve eventually consistent reads, which is why those may be stale.
• The leader holds a lease. A newly elected leader serves nothing until the old leader’s lease expires, a couple of seconds, so two leaders never accept writes at once.

So DynamoDB is a consensus-replicated, single-leader-per-partition store with no siblings and no read repair to think about, and it offers conditional writes instead of vector clocks. Cassandra, ScyllaDB and Riak are the leaderless ones. More on both in Cassandra and DynamoDB.

Leaderless vs single leader vs consensus

Leaderless shines when every write must succeed somewhere and the data tolerates a merge: carts, sessions, time series, activity feeds, IoT readings. It struggles with invariants across keys (“balance never negative”, “one seat, one buyer”), which is why those parts of a design usually sit on a consensus-backed or single-leader store. The data replication article covers leader-based replication in depth, and consensus and leader election covers Raft and Paxos.

Cheat sheet

How to say it in the interview

“For the activity store I’d use a Dynamo-style database like Cassandra with replication factor 3 per region. Each key maps to three nodes on the hash ring; writes go to all three and return after two acks, reads ask two and take the newest, so with LOCAL_QUORUM users read their own writes without a cross-region round trip. There’s no failover: if a node dies, the other two still form a quorum, hints replay its missed writes, and weekly Merkle-tree repair, inside the 10-day tombstone grace period, catches the rest. Conflicts resolve last-write-wins per column, so I keep clocks synced and model changes as appends. Quorums aren’t linearizable, so the one check-then-set operation, claiming a username, uses a lightweight transaction.”

Does R + W > N make the store strongly consistent? No. It makes a read likely to see the latest acknowledged write. Sloppy quorums, partially failed writes, LWW with skewed clocks and rebuilt replicas all break it. For linearizable operations, use a Paxos-based compare-and-set.

What is a sloppy quorum, and when would you avoid it? Counting acknowledgements from stand-in nodes when home replicas are down, so writes keep succeeding. Avoid it when reads must see writes: in Riak, set PR and PW; Cassandra’s quorums are strict, and its hints don’t count.

How do deletes work, and what goes wrong? A delete writes a tombstone. After gc_grace_seconds (10 days by default) compaction may purge it; a replica that missed the delete and wasn’t repaired in time resurrects the data. Repair every node more often than the grace period.

Why not just use vector clocks everywhere? They detect concurrency, but every read path must handle siblings and every data type needs a merge. LWW is simpler and fine when overwrites are rare or losing one is acceptable; CRDTs are the middle ground.

Is DynamoDB leaderless? No. Each partition is a Multi-Paxos group with a leased leader that takes all writes and strongly consistent reads. Only the original Dynamo, and Cassandra, ScyllaDB and Riak, are leaderless.

Where to go next

• Data replication: leader-based replication, lag anomalies and failover.
• CAP theorem and PACELC: the overlap argument and why quorums trade latency for consistency.
• Consistent hashing: how keys map to the preference list.
• Clocks, ordering and conflict resolution: version vectors, hybrid clocks and CRDTs.
• Gossip protocol: how membership and liveness spread.
• Cassandra and DynamoDB: the two stores side by side in production.
• Design a key-value store: every idea here assembled into one design.

References and further reading

1. Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007)allthingsdistributed.comPreference lists, coordinators, sloppy quorums and hinted handoff, vector clocks and their truncation, Merkle-tree anti-entropy, the common (3,2,2) setting and production version counts.
2. Apache Cassandra documentation: Dynamo architecturecassandra.apache.orgConsistency levels including LOCAL_QUORUM and EACH_QUORUM, per-column last-write-wins timestamps, gossip every second and the phi accrual failure detector.
3. Apache Cassandra documentation: Hintscassandra.apache.orgHow coordinators store and replay hints, the 3-hour hint window, the 2-second write timeout and the hint replay arithmetic after a restart.
4. Apache Cassandra documentation: Read repaircassandra.apache.orgFull and digest reads, blocking read repair, monotonic quorum reads, and which consistency levels trigger repair.
5. Apache Cassandra documentation: Repaircassandra.apache.orgMerkle-tree anti-entropy with nodetool repair, incremental versus full repair, and repairing within the 10-day gc grace period.
6. Apache Cassandra documentation: Tombstonescassandra.apache.orgWhy deletes are written as tombstones, the 864,000-second gc_grace_seconds default, and how zombies come back.
7. Apache Cassandra documentation: cassandra.yaml referencecassandra.apache.orgRound trips per lightweight transaction for Paxos v1 and v2, the phi_convict_threshold default of 8 and the CAS contention timeout.
8. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (Elhemali et al., USENIX ATC 2022)usenix.orgEach DynamoDB partition is a Multi-Paxos replication group with a leased leader that serves writes and strongly consistent reads.
9. Riak KV documentation: Replication propertiesdocs.riak.comSloppy quorums by default, and PR and PW for strict quorums on primary replicas.
10. Riak KV documentation: Causal contextdocs.riak.comVector clocks, dotted version vectors, siblings and the allow_mult setting.