Skip to main content

Leaderless Replication (Dynamo-Style)

What This Concept Is​

Leaderless replication abandons the idea of a designated write node entirely. Every replica accepts writes, and clients (or a coordinator) send each request to several replicas in parallel. Popularized by Amazon's Dynamo paper and used by Cassandra, Riak, and ScyllaDB.

Three mechanisms make it work:

  • Quorum reads and writes: a write is "accepted" once W replicas acknowledge; a read is "done" once R replicas respond. If W + R > N (where N is the replication factor), at least one replica in every read overlaps with at least one replica in every write.
  • Read repair: when a reader notices one replica is stale, it writes the fresh value back to the stale replica in the background.
  • Anti-entropy / hinted handoff: when a replica is down, writes destined for it are stashed (as "hints") on a peer; when the replica comes back, the hints are delivered.
  Client
    |
    +---- write(X=5) ---> Replica-A  [ack]
    |                     Replica-B  [ack]
    |                     Replica-C  [down -> hinted on B]
    |
    +--- if W=2, write succeeds as soon as A and B ack
    
  Later: Replica-C returns -> B delivers hinted write

Why It Matters Here​

Leaderless is the canonical AP (under CAP) design. It accepts writes during partitions, tolerates any single node failure without a promotion dance, and achieves very low tail latency (a laggy replica does not block the whole request).

The cost is subtle: without a leader to serialize writes, you need conflict detection (version vectors, Lamport timestamps, or application-level merging). Read-your-writes, monotonic-reads, and other session guarantees are not automatic; you buy them by tuning W, R, and client-side logic.

Concrete Example​

A Cassandra cluster with N=3, W=QUORUM=2, R=QUORUM=2.

Writing user.email = "alice@ex.com":

  1. Client sends write to coordinator node.
  2. Coordinator forwards to the 3 replicas for that partition key.
  3. Replicas respond; coordinator waits for any 2 to ack.
  4. After 2 acks, the client call returns "success."
  5. The third replica receives the write asynchronously (or misses it, and is patched later by read-repair or hinted handoff).

Reading:

  1. Coordinator queries all 3 replicas (or just 2 for QUORUM).
  2. If versions disagree, the highest-timestamp version wins for the client; stale replicas are read-repaired in the background.

Because W=2, R=2, N=3, every read set and write set share at least one replica. You cannot miss the most recent write -- provided no replica drops the write silently.

Common Confusion / Misconception​

"W + R > N guarantees linearizability." No. It guarantees only that every read sees at least one replica that saw the latest write. But the read can still return an older value if it races with the write and the client logic picks the wrong version. True linearizability on top of a quorum system requires additional fencing (Cassandra has "lightweight transactions" for this).

"Leaderless is always available." Only if W and R can be met. If N=3, W=2 and two nodes are down, writes fail. The tradeoff W+R>N is not free; stricter quorums reduce availability during partial failures.

"Hinted handoff is durable." Hints are typically stored locally on the peer, not replicated. If the peer itself crashes before delivery, the hint is lost. Treat hints as a best-effort recovery mechanism, not a guarantee.

How To Use It​

Leaderless fits when:

  1. You need extreme availability: accept writes even during partitions.
  2. You can tolerate last-writer-wins semantics or you have the skill to manage version vectors.
  3. Your tail-latency budget is small (leaderless degrades smoothly; single-leader degrades sharply when the leader struggles).
  4. Operations teams are prepared to tune W, R, N, and compaction.

Avoid leaderless for:

  • Workloads with strict uniqueness (leaderless cannot enforce a unique constraint without a separate consensus layer).
  • Workloads whose correctness depends on "I wrote, then I immediately read my write" unless you raise R to match.
  • Teams who expect the database to linearize for them.

Check Yourself​

  1. Why does W + R > N matter, and what goes wrong if W + R ≤ N?
  2. When does a leaderless cluster stop accepting writes?
  3. What is hinted handoff, and when can a hint be lost?
  4. Why is W = N, R = 1 a fragile configuration even though it satisfies W + R > N?

Mini Drill or Application​

For each setting (N, W, R), say whether writes during partition remain available and whether reads can see stale data:

  1. N=3, W=3, R=1.
  2. N=3, W=2, R=2.
  3. N=5, W=3, R=3.
  4. N=3, W=1, R=1.
  5. N=5, W=1, R=5.

Then: one replica is lost in each. Can the cluster still serve at its specified W, R?

Read This Only If Stuck​