Skip to content

Quorum and NWR#

Problem statement (interviewer prompt)

A replicated key-value store has N replicas per key. Define read and write thresholds (R, W) so that every read observes the latest acknowledged write while still tolerating replica failures. Discuss the trade-off when R+W > N is relaxed.

Quorum systems let you pick durability, latency, and consistency per request by choosing how many replicas must acknowledge a write (W) and how many must respond to a read (R) out of N total copies.

flowchart LR
  C([Client]) -->|write| Coord((Coordinator))
  Coord -->|replicate| R1[Replica 1]
  Coord -->|replicate| R2[Replica 2]
  Coord -->|replicate| R3[Replica 3]
  R1 -. ack .-> Coord
  R2 -. ack .-> Coord
  Coord -->|W=2 acks received| C

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class C client;
    class Coord service;
    class R1,R2,R3 datastore;

The rule R + W > N guarantees any read quorum overlaps any write quorum by at least one replica, so the read set contains the newest value.

Replicated stores like Dynamo, Cassandra, and Riak expose the three knobs (N, R, W) directly. Picking them is how operators dial in the consistency vs availability trade-off.

The numbers#

  • N is the replication factor for a key (typically 3 or 5).
  • W is the number of replicas that must persist a write before the client gets success.
  • R is the number of replicas a read must contact to assemble a response.
flowchart TB
  subgraph Write[Write path]
    C1([Client]) --> Co1((Coord))
    Co1 --> A[Replica A]
    Co1 --> B[Replica B]
    Co1 --> Cc[Replica C]
    A -. ack .-> Co1
    B -. ack .-> Co1
    Co1 -->|W=2 met| C1
  end

  subgraph Read[Read path]
    C2([Client]) --> Co2((Coord))
    Co2 --> A2[Replica A]
    Co2 --> B2[Replica B]
    A2 -. v=7 .-> Co2
    B2 -. v=8 .-> Co2
    Co2 -->|R=2 picks v=8| C2
  end

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class C1,C2 client;
    class Co1,Co2 service;
    class A,B,Cc,A2,B2 datastore;

Configurations that matter#

Setting R W N Property
Strong read consistency 2 2 3 R+W>N; reads see latest acked write
Read-heavy, fast reads 1 3 3 W=N, every replica current; tolerates 0 write failures
Write-heavy, fast writes 3 1 3 R=N, slow reads; tolerates 0 read failures
Eventual only 1 1 3 R+W<=N; cheapest, may read stale

Sloppy quorum and hinted handoff#

If the "home" replicas are unreachable, Dynamo-style systems forward writes to any N healthy nodes. The receiving node holds a hint that says "this row belongs to node B; deliver when B comes back." This trades a strict quorum for higher write availability.

sequenceDiagram
  participant C as Client
  participant N1 as Node 1 (home)
  participant N2 as Node 2 (home, down)
  participant N4 as Node 4 (sloppy)
  C->>N1: PUT k=v
  N1->>N2: replicate
  Note over N2: timeout
  N1->>N4: replicate with hint(N2)
  N4-->>N1: ack
  N1-->>C: 200 OK (W met)
  Note over N4: when N2 returns, replay hint
  N4->>N2: PUT k=v (handoff)

Conflict resolution#

When R+W<=N, replicas can hold divergent values. Resolution strategies:

  • Last-write-wins with wall-clock timestamps. Simple but loses concurrent updates.
  • Vector clocks: keep all causally-concurrent versions; client merges. Used by Dynamo and Riak.
  • CRDTs: type-aware merge function; no client involvement. See CRDTs.

Tuning examples#

  • Cassandra: consistency=QUORUM sets R=W=ceil((N+1)/2). ONE is fast but eventually consistent. LOCAL_QUORUM keeps the quorum inside one DC for latency.
  • DynamoDB: hidden internally, but ConsistentRead=true forces a strong read from the leader replica.
  • Riak: per-bucket n_val, r, w, dw (durable writes; must hit disk).

How NWR fits with neighbouring fundamentals#

flowchart TB
  CH[Consistent hashing<br/>picks the N replicas]
  NWR((Quorum<br/>and NWR))
  HH[Hinted handoff<br/>when fewer than W reachable]
  CAP[CAP and PACELC<br/>the formal trade space]
  CRDT[CRDTs<br/>merge concurrent writes]
  REPL[Replication: leader/follower<br/>single-leader alternative]
  CH --> NWR
  NWR --> HH
  NWR --> CRDT
  NWR --> CAP
  REPL -. alternative .- NWR

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class NWR service;
    class CH,HH,CAP,CRDT,REPL datastore;

Click the row to navigate; each fundamental has its own deep dive.

Glossary & fundamentals#

Tag Concept What it is Page
HLD Consistent hashing place keys on a ring of N replicas consistent-hashing
HLD Hinted handoff sloppy-quorum follow-up delivery hinted-handoff
HLD CAP and PACELC the trade space NWR navigates cap-pacelc
HLD CRDTs conflict-free merge for concurrent writes crdts
HLD Replication leader/follower single-leader alternative replication-leader-follower

Quick reference#

Core rule#

R + W > N  ⇒  every read sees the latest acknowledged write

Common recipes#

Goal N W R
Strong consistency, balanced 3 2 2
Fast writes, slower reads 3 1 3
Fast reads, slower writes 3 3 1
Eventual (cache-like) 3 1 1
Quorum with 5 replicas 5 3 3

Sloppy quorum#

Accept writes on any healthy N nodes when the home replicas are down; replay via hinted handoff later. Maximises availability, weakens "strict" quorum semantics.

Conflict resolution#

  • Last-write-wins (wall-clock or HLC)
  • Vector clocks - keep sibling versions, client resolves
  • CRDTs - merge-by-construction

Watch-outs#

  • Clock skew breaks last-write-wins; use NTP-disciplined HLC or stick to vector clocks
  • W=N makes writes fragile - any node down blocks writes
  • LOCAL_QUORUM (Cassandra) keeps quorum inside a DC for latency
  • Quorum reads don't read-repair by default - enable async repair

Refs#

  • Amazon Dynamo paper (SOSP 2007)
  • Cassandra docs - consistency levels
  • Riak docs - tunable consistency

FAQ#

What does R + W > N guarantee?#

It guarantees the read set and the write set always overlap on at least one replica, so a quorum read sees the latest acknowledged quorum write.

How do you pick N, R, and W?#

Pick N for durability, usually 3 or 5. Then trade latency for consistency: W=1, R=N is fast writes; W=N, R=1 is fast reads; W=R=majority is balanced and strongly consistent.

What is a sloppy quorum?#

When some preferred replicas are unreachable, the coordinator accepts writes on substitute nodes to keep going. Reads may miss the latest write until hinted handoff replays.

Strict quorum vs sloppy quorum?#

Strict requires the write to land on R of the N owning replicas. Sloppy lets it land on any N healthy nodes, trading the R+W>N guarantee for availability.

Which databases use NWR tuning?#

Amazon Dynamo, Cassandra, ScyllaDB, and Riak expose per-request N, R, and W. Operators set the defaults; clients can override for stronger or faster operations.

Further reading#