Quorum: The Formula for Consistency

[!NOTE] This module explores the core principles of Quorum: The Formula for Consistency, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Problem

In a Leaderless system (like DynamoDB or Cassandra), you write to multiple nodes at once. But networks are flaky. What if you write to 3 nodes, but only 2 receive it? And then you read from the 3rd node? You get Old Data.

2. The Formula: R + W > N

To guarantee Strong Consistency (that you always read the latest write), you must obey the Quorum Formula:

R + W > N

  • N: Total number of replicas (e.g., 3).
  • W: Write Quorum (How many nodes must confirm a write for it to be successful).
  • R: Read Quorum (How many nodes you must read from to get the data).

Why does it work?

If R + W > N, there must be an overlap of at least one node. That one node has the latest data. The database uses timestamps (or Vector Clocks) to detect which version is newer and returns it.

3. Common Configurations (N=3)

  1. Strong Consistency (Balanced)
    • N=3, W=2, R=2 → 2 + 2 = 4 > 3. (Consistent!)
    • This is the standard default. It tolerates 1 node failure.
  2. Fast Writes (Eventual Consistency)
    • N=3, W=1, R=3 → 1 + 3 = 4 > 3. (Consistent, but slow reads).
    • N=3, W=1, R=1 → 1 + 1 = 2 < 3. (Not Consistent!).
    • W=1 is super fast but risky.

4. Interactive Demo: Quorum Calculator

Tune the parameters to see if your system is Consistent or Eventual. Also observe the Latency Cost. Higher W/R = Higher Latency.

3
2
2
2 + 2 > 3
STRONG CONSISTENCY
Est. Latency: Medium
● Write ● Read ● Overlap

5. Deep Dive: Sloppy Quorum & Hinted Handoff

Sometimes, Availability is more important than Consistency (e.g., Amazon Shopping Cart). If you need W=2 but only 1 node is online, a Strict Quorum would fail the write (Error 503). Sloppy Quorum says: “It’s okay. Write to the 1 online node, and write the 2nd copy to a temporary neighbor (Hinted Handoff).”

Feature Strict Quorum Sloppy Quorum
Availability Lower (Needs W replicas online) Highest (Accepts writes anywhere)
Consistency Strong (if R+W > N) Eventual (Data hidden in handoff)
Use Case Banking, Auth Shopping Carts, Likes

Once the down node comes back, the neighbor hands off the data.

6. Deep Dive: Read Repair

In systems like Cassandra, every Read is an opportunity to fix data. If you do R=2 and get:

  • Node A: v1 (Old)
  • Node B: v2 (New)

The coordinator returns v2 to the client, but in the background, it sends v2 to Node A to fix it. This is Read Repair.

7. Deep Dive: Proof of W + R > N

Let’s prove why W + R > N guarantees strong consistency.

Setup:

  • System has N = 3 replicas (Nodes A, B, C)
  • Client writes with W = 2 (must confirm on 2 nodes)
  • Client reads with R = 2 (must read from 2 nodes)

Write Phase:

  • Write confirmed on Nodes A and B
  • Node C may or may not have the write (network delay, failure, etc.)

Read Phase:

  • Read from R = 2 nodes
  • Possible combinations: (A,B), (A,C), (B,C)

Analysis:

  • W + R = 2 + 2 = 4 > 3 (N)
  • No matter which 2 nodes we read from, at least 1 node was in the write quorum
  • That node has the latest version
  • The coordinator uses timestamps/version numbers to detect and return the newest value

Failure Case (W + R ≤ N):

  • If W = 1, R = 1, N = 3
  • Write only confirmed on Node A
  • Read could be from Node B → stale data!
  • 1 + 1 = 2 ≤ 3 → No guaranteed overlap

[!IMPORTANT] The quorum formula guarantees at least one overlap between the write set and read set. The overlapping node always has the latest data.

8. Production Pattern: Tunable Consistency (Cassandra)

Cassandra allows you to tune consistency per request, not cluster-wide.

Write CL Read CL R + W > N? Latency Use Case
ONE ONE 1+1=2 ≤ 3 🟢 Fastest Analytics, logs (stale OK)
ONE QUORUM 1+2=3 ≤ 3 🟡 Fast writes Shopping cart (eventual OK)
QUORUM QUORUM 2+2=4 > 3 🟡 Balanced User profiles, Orders
QUORUM ONE 2+1=3 ≤ 3 🟡 Fast reads Dashboards (metrics)
ALL ONE 3+1=4 > 3 🔴 Slow writes Financial ledger (write-once)
ONE ALL 1+3=4 > 3 🔴 Slow reads Critical reads (rare)

CL = Consistency Level (ONE < LOCAL_QUORUM < QUORUM < ALL)

  • QUORUM/QUORUM (N=3, W=2, R=2): Balance of consistency, availability, and performance
  • Tolerate: 1 node failure for reads and writes
  • Latency: ~5-10ms (assuming nodes in same datacenter)

[!TIP] Interview Tip: When asked “How would you configure Cassandra?”, say: “Start with QUORUM for both reads and writes to guarantee strong consistency, then dial down to ONE if your use case allows eventual consistency.”

9. Deep Dive: Read Repair vs Anti-Entropy

Both mechanisms fix stale replicas, but they work differently:

Read Repair (Synchronous, per request)

  • When: During every READ operation (if enabled)
  • How: Coordinator compares timestamps from all R replicas
  • Action: If mismatched, sends latest value to stale nodes (background)
  • Latency: No impact on client (async repair)
  • Coverage: Only fixes data that is actively read

Example Flow:

1. Client: SELECT * FROM users WHERE id=1;
2. Coordinator reads from N=3 nodes
3. Node A: version=10 (latest)
   Node B: version=10
   Node C: version=8 (stale)
4. Return version=10 to client
5. Background: Send version=10 to Node C

Anti-Entropy (Background, periodic)

  • When: Periodic background process (e.g., every 24 hours)
  • How: Merkle tree comparison between replicas
  • Action: Streams missing/stale data in bulk
  • Latency: High I/O overhead (runs during low traffic)
  • Coverage: Fixes all data, even rarely-read rows

When to Use:

  • Read Repair: For hot data (frequently-read keys)
  • Anti-Entropy: For cold data, deleted tombstones, or after node recovery

[!WARNING] Anti-Entropy is expensive. In Cassandra, it’s called nodetool repair. Running it on a multi-TB cluster can take hours and saturate network bandwidth. Schedule it during maintenance windows.

10. Production Scenario: DynamoDB Consistency Levels

DynamoDB uses a similar quorum system but exposes it differently:

Eventually Consistent Reads (default):

  • R = 1 (reads from 1 replica)
  • Fast but may return stale data
  • Use Case: Product catalog, non-critical dashboards

Strongly Consistent Reads:

  • R = 2 (Quorum) out of N = 3
  • Always returns latest data
  • Use Case: Inventory checks, account balances

Cost:

  • Strongly consistent reads cost 2x the DynamoDB read capacity units (RCUs)

  • Trade-off: Correctness vs. cost

11. Deep Dive: Conflict Resolution (Vector Clocks)

In a Leaderless system with Eventual Consistency, two users might write to the same key at the same time on different nodes. Who wins?

  1. Last Write Wins (LWW): Use the timestamp. (Simple, but risky—clock skew can cause data loss).
  2. Vector Clocks: Track “Version Vectors” (e.g., [A:1, B:2]). If versions conflict (branches), keep BOTH versions and ask the client to resolve it (like a Git Merge Conflict).

12. Key Takeaways

  1. Quorum Formula: W + R > N guarantees at least one overlap → strong consistency
  2. Tunable Consistency: Cassandra lets you choose per-request (ONE, QUORUM, ALL)
  3. Sloppy Quorum: Prioritizes availability over consistency (hinted handoff)
  4. Read Repair: Fixes stale data during reads (lazy, incremental)
  5. Anti-Entropy: Fixes all data periodically (expensive, thorough)
  6. Production Default: QUORUM/QUORUM for balance; dial down to ONE/ONE only if stale data is acceptable

[!IMPORTANT] Interview Insight: When designing a system, always ask: “Can this data be stale?” If yes (analytics, logs), use W=1, R=1. If no (orders, payments), use W=2, R=2 (QUORUM).