Read and Write Quorums - Quorum Based Replication | OneNoughtOne

0/273

System Design (HLD)Quorum-Based Replication

Quorum-Based Replication

LevelAdvanced

Duration75 mins

TopicQuorum-Based Replication

1 / 5

Read and Write Quorums

The Fundamental Challenge of Distributed Consensus

Imagine you're designing a distributed database that stores critical financial data across five servers in different data centers. A client writes a new account balance of $10,000. Before even acknowledging the write as successful, you face a profound question: How many servers must confirm this write before you can safely tell the client it succeeded?

If you wait for all five servers, you achieve perfect consistency—but if even one server is down or slow, your entire system stalls. If you acknowledge after just one server confirms, you gain speed and availability—but what happens if that one server fails before propagating the data? The client's $10,000 might vanish into the void.

This is the essential tension at the heart of distributed systems, and quorum-based replication provides an elegant mathematical solution that lets you navigate this tradeoff with precision and predictability.

What You Will Learn

By the end of this page, you will deeply understand the mathematical foundations of quorum systems, grasp why the formula W + R > N guarantees consistency, analyze how quorums enable distributed systems to tolerate failures while maintaining data integrity, and recognize the strategic tradeoffs involved in configuring quorum-based systems for different use cases.

The Origins of Quorum Systems

The concept of quorums in distributed computing traces back to the seminal 1979 paper by David K. Gifford, "Weighted Voting for Replicated Data." Gifford recognized that traditional approaches to distributed data management—requiring either unanimous agreement or accepting inconsistency—presented a false dichotomy. His insight was to apply the concept of voting to distributed operations.

In political systems, a quorum is the minimum number of members required to conduct official business. Gifford adapted this concept: instead of requiring all replicas to participate in every operation, a system could define minimum thresholds (quorums) for reads and writes that, when properly configured, mathematically guarantee that readers will always see the most recent write.

Historical Context

Gifford's weighted voting scheme emerged from practical necessity. By the late 1970s, distributed systems were becoming unavoidable, but the theory for managing replicated data was immature. His quorum approach provided a principled way to reason about consistency and availability tradeoffs—a framework that remains foundational in systems like Cassandra, DynamoDB, and Riak decades later.

The Core Insight:

Consider a system with three replicas (N = 3). If every write operation must succeed on at least two replicas (W = 2), and every read operation must query at least two replicas (R = 2), then any read is guaranteed to contact at least one replica that participated in the most recent successful write.

Why? Because 2 + 2 = 4 > 3. The write quorum and read quorum must overlap by at least one node. That overlapping node carries the latest data, ensuring the read returns the most recent write.

This is the foundational principle: W + R > N guarantees that reads and writes intersect, providing consistency without requiring all nodes to participate in every operation.

quorum-visualization.txt

N = 3 replicas: [Node A] [Node B] [Node C]
 
Write Quorum (W = 2):
  Write succeeds on: [Node A ✓] [Node B ✓] [Node C ✗]
  
Read Quorum (R = 2):
  Read queries:      [Node A ✓] [Node B ✗] [Node C ✓]
 
Intersection Analysis:
  Write touched: {A, B}
  Read  touched: {A, C}
  Overlap:       {A} ← This node has the latest write!
  
Mathematical Guarantee:
  W + R = 2 + 2 = 4 > 3 = N
  ∴ Read and write quorums MUST overlap by at least 1 node
  ∴ Read WILL see the latest write (from the overlapping node)

The Mathematics of Quorum Overlap

Understanding why W + R > N guarantees overlap requires thinking through the mathematics carefully. This isn't just a formula to memorize—it's a logical proof that underlies the correctness of quorum systems.

The Pigeonhole Principle Applied:

The guarantee relies on a fundamental mathematical concept: the pigeonhole principle. If you have N boxes and you place more than N items into them, at least one box must contain more than one item.

In quorum terms:

We have N nodes (boxes)
Write quorum places W "write markers" on W nodes
Read quorum must "look" at R nodes
If W + R > N, then the read must look at at least one node that has a write marker

More formally: if writes touch W nodes and reads touch R nodes, and W + R > N, then by the pigeonhole principle, the intersection cannot be empty.

Quorum Overlap Analysis for N = 5 Replicas
W (Write)	R (Read)	W + R	Overlap?	Min Overlap Size	Consistency
5	1	6	Yes	1	Strong read-one consistency
4	2	6	Yes	1	Strong consistency
3	3	6	Yes	1	Balanced quorum
3	2	5	No	0	Possible stale reads
2	2	4	No	0	Possible stale reads
1	5	6	Yes	1	Write-one, read-all
1	1	2	No	0	Eventually consistent

Calculating Minimum Overlap:

The minimum number of nodes in both quorums is given by:

Minimum Overlap = W + R - N

This formula tells you exactly how many nodes are guaranteed to be in both the write quorum and the read quorum. When W + R - N > 0, you have guaranteed overlap and thus guaranteed consistency. When W + R - N ≤ 0, there's no guarantee—reads might miss the latest write entirely.

Example Calculations:

N=5, W=3, R=3: Overlap = 3 + 3 - 5 = 1 (minimum one node overlap)
N=5, W=4, R=2: Overlap = 4 + 2 - 5 = 1 (minimum one node overlap)
N=5, W=3, R=2: Overlap = 3 + 2 - 5 = 0 (no guaranteed overlap)
N=5, W=4, R=3: Overlap = 4 + 3 - 5 = 2 (at least two nodes overlap)

The Overlap Edge Case

When W + R = N exactly, mathematically the quorums could be exactly complementary with zero overlap (e.g., W writes to nodes {A, B}, R reads from nodes {C, D, E}). This is why the strict inequality W + R > N is required, not W + R ≥ N. The pigeonhole principle only guarantees an intersection when we have more "slots" than "boxes."

Write Quorums in Depth

A write quorum is the minimum number of replicas that must acknowledge a write before the system considers it successful. This is not merely a configuration parameter—it determines the fundamental durability and consistency guarantees of your system.

The Write Process:

Client sends write request to coordinator node
Coordinator forwards write to all N replicas
Each replica attempts to write and responds (success/failure)
Coordinator waits for W successful acknowledgments
Once W acknowledgments received, coordinator responds to client
Remaining N-W replicas may complete asynchronously

The choice of W creates a spectrum of durability guarantees:

Write Quorum Spectrum

•W = 1 (Single Acknowledgment) — Fastest writes, but data exists on only one node before acknowledgment. If that node fails immediately after, data may be lost. Suitable for logs, metrics, or data that can be regenerated.
•W = N/2 + 1 (Majority Quorum) — The classic choice. Data persists on more than half of nodes. System can lose up to (N-1)/2 nodes without data loss. Most common for production systems requiring durability.
•W = N (All Nodes) — Maximum durability—data on all nodes before acknowledgment. Any single node failure blocks all writes. Rarely used except for critical configuration data or when N is small.
•W between 1 and majority — Trades durability for availability. Writes succeed even when more than half of nodes are down, but data might be lost if the minority of nodes that received the write all fail.

write-quorum-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
interface WriteResult {
  nodeId: string;
  success: boolean;
  timestamp: number;
}
 
interface QuorumWriteResult {
  success: boolean;
  writeTimestamp: number;
  acknowledgedNodes: string[];
  pendingNodes: string[];
  failedNodes: string[];
}
 
async function writeWithQuorum(
  key: string,
  value: any,
  replicas: Replica[],
  writeQuorum: number,
  timeout: number
): Promise<QuorumWriteResult> {
  const timestamp = Date.now();
  const versionedValue = { value, timestamp, version: generateVersion() };
  
  // Send write to ALL replicas (not just W)
  const writePromises = replicas.map(replica =>
    replica.write(key, versionedValue)
      .then(result => ({ nodeId: replica.id, success: true, timestamp }))
      .catch(err => ({ nodeId: replica.id, success: false, timestamp, error: err }))
  );
  
  // Wait for quorum with timeout
  const results = await waitForQuorum(writePromises, writeQuorum, timeout);
  
  const successful = results.filter(r => r.success);
  const failed = results.filter(r => !r.success);
  
  if (successful.length >= writeQuorum) {
    return {
      success: true,
      writeTimestamp: timestamp,
      acknowledgedNodes: successful.map(r => r.nodeId),
      pendingNodes: replicas
        .filter(r => !results.find(res => res.nodeId === r.id))
        .map(r => r.id),
      failedNodes: failed.map(r => r.nodeId),
    };
  }
  
  // Quorum not achieved - write failed
  throw new QuorumNotAchievedError(
    `Write quorum not met: ${successful.length}/${writeQuorum} required`,
    { successful, failed, timeout }
  );
}
 
// Critical: Wait for W responses, not all N
async function waitForQuorum<T>(
  promises: Promise<T>[],
  quorum: number,
  timeout: number
): Promise<T[]> {
  return new Promise((resolve, reject) => {
    const results: T[] = [];
    let completed = 0;
    let succeeded = 0;
    
    const timeoutId = setTimeout(() => {
      resolve(results); // Return what we have after timeout
    }, timeout);
    
    promises.forEach(promise => {
      promise.then(result => {
        results.push(result);
        completed++;
        if ((result as any).success) succeeded++;
        
        // Early return once quorum achieved
        if (succeeded >= quorum) {
          clearTimeout(timeoutId);
          resolve(results);
        }
        
        // All completed - return regardless
        if (completed === promises.length) {
          clearTimeout(timeoutId);
          resolve(results);
        }
      });
    });
  });
}

Write to All, Wait for W

A critical implementation detail: the coordinator sends writes to ALL N replicas, not just W. It then waits for W acknowledgments before responding to the client. The remaining N-W writes continue in the background. This ensures data reaches as many nodes as possible while providing low-latency acknowledgments once the quorum is satisfied.

Read Quorums in Depth

A read quorum is the minimum number of replicas that must respond to a read request before the system can return a value to the client. Unlike writes, reads involve additional complexity: when multiple replicas respond with different versions of data, the system must determine which version is "correct."

The Read Process:

Client sends read request to coordinator node
Coordinator forwards read to all N replicas (or at least R)
Replicas respond with their current value and version/timestamp
Coordinator waits for R responses
Coordinator selects the most recent version based on timestamp/version vector
Coordinator returns the value to client
Optionally: coordinator initiates read repair for stale replicas

read-quorum-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
interface VersionedValue<T> {
  value: T;
  timestamp: number;
  version: string;  // Could be vector clock for causality
  nodeId: string;
}
 
interface QuorumReadResult<T> {
  value: T;
  timestamp: number;
  version: string;
  respondedNodes: string[];
  staleNodes: string[];  // Nodes that returned older versions
}
 
async function readWithQuorum<T>(
  key: string,
  replicas: Replica[],
  readQuorum: number,
  timeout: number
): Promise<QuorumReadResult<T>> {
  // Query all replicas (or at least R)
  const readPromises = replicas.map(replica =>
    replica.read(key)
      .then(result => ({ ...result, nodeId: replica.id }))
      .catch(err => null)  // Failed reads don't count toward quorum
  );
  
  const responses = await waitForQuorum(readPromises, readQuorum, timeout);
  const validResponses = responses.filter(r => r !== null) as VersionedValue<T>[];
  
  if (validResponses.length < readQuorum) {
    throw new QuorumNotAchievedError(
      `Read quorum not met: ${validResponses.length}/${readQuorum} required`
    );
  }
  
  // Find the most recent version
  const latestResponse = validResponses.reduce((latest, current) => {
    // Compare timestamps, or use vector clock comparison for causality
    return current.timestamp > latest.timestamp ? current : latest;
  });
  
  // Identify stale nodes for potential read repair
  const staleNodes = validResponses
    .filter(r => r.version !== latestResponse.version)
    .map(r => r.nodeId);
  
  // Trigger async read repair if stale nodes detected
  if (staleNodes.length > 0) {
    triggerReadRepair(key, latestResponse, staleNodes).catch(console.error);
  }
  
  return {
    value: latestResponse.value,
    timestamp: latestResponse.timestamp,
    version: latestResponse.version,
    respondedNodes: validResponses.map(r => r.nodeId),
    staleNodes,
  };
}
 
// Read repair: update stale replicas with latest value
async function triggerReadRepair<T>(
  key: string,
  latestValue: VersionedValue<T>,
  staleNodeIds: string[]
): Promise<void> {
  const staleReplicas = replicas.filter(r => staleNodeIds.includes(r.id));
  
  await Promise.allSettled(
    staleReplicas.map(replica =>
      replica.write(key, latestValue)
    )
  );
  
  console.log(`Read repair completed for key ${key} on ${staleNodeIds.length} nodes`);
}

Version Resolution Strategies:

When multiple responses arrive with different versions, the system must choose which one to return. Common strategies include:

Timestamp-based (Last Write Wins): The value with the highest timestamp wins. Simple but can lose concurrent writes.
Version vectors/Vector clocks: Track causality between updates. Can detect concurrent writes that need application-level resolution.
Logical clocks (Lamport timestamps): Provide total ordering but may not reflect real-time order.
Application-specific merge: For certain data types (counters, sets), semantically merge conflicting values rather than choosing one.

Read Repair: Healing Inconsistencies

When a read quorum reveals that some replicas have stale data, the system can perform 'read repair'—asynchronously updating the stale replicas with the latest value. This opportunistic healing reduces entropy in the system without requiring dedicated anti-entropy processes. Amazon's Dynamo paper popularized this technique, which is now standard in Cassandra, Riak, and similar systems.

Quorum Intersection Guarantees

The intersection property (W + R > N) provides what we call strong consistency in a specific sense: if a write completes before a read begins, the read is guaranteed to see that write. But this guarantee requires careful understanding of what it does and doesn't provide.

What Quorum Guarantees:

✓ Read-your-writes (for a single client): If you write and then read, you'll see your write ✓ Sequential consistency (with careful implementation): All clients see operations in some consistent order ✓ Latest write visibility: Any read sees at least one node with the latest write

What Quorum Doesn't Automatically Guarantee:

✗ Linearizability: Requires additional coordination (e.g., Paxos/Raft) ✗ Conflict resolution: Concurrent writes may still conflict ✗ Atomicity across keys: Multi-key transactions need separate mechanisms

Consistency Achieved

•Reads always see latest completed write
•No stale reads from outdated replicas
•Predictable behavior under partial failures
•Mathematical proof of correctness
•Tunable consistency levels

Limitations to Understand

•Concurrent writes may conflict
•Network partitions may block operations
•Higher quorums = lower availability
•No ordering across independent operations
•Clock synchronization affects version ordering

The Consistency Window:

Even with W + R > N, there's a subtle window where inconsistency is possible. Consider:

Client A writes value V1, waits for W=2 acknowledgments from nodes {1, 2}
Before node 3 receives the write, Client B reads from nodes {3, 4} (assuming R=2)
If node 4 also hasn't received the write yet, Client B reads stale data

This scenario is impossible if W + R > N, but the key insight is that the write must complete (receive W acknowledgments) before the read begins. During the write operation itself, there's a brief window where quorum guarantees don't apply.

To achieve true linearizability (real-time ordering), systems like Spanner use synchronized clocks (TrueTime) or consensus protocols (Paxos/Raft) in addition to quorums.

quorum-proof.txt

THEOREM: If W + R > N, then WriteQuorum ∩ ReadQuorum ≠ ∅
 
PROOF BY CONTRADICTION:
 
Assume Write Quorum and Read Quorum do NOT intersect.
 
Let WriteQuorum = set of W nodes that acknowledged the write
Let ReadQuorum = set of R nodes that responded to the read
 
If they don't intersect:
  |WriteQuorum ∪ ReadQuorum| = |WriteQuorum| + |ReadQuorum|
                              = W + R
 
But WriteQuorum ∪ ReadQuorum ⊆ AllNodes
So: |WriteQuorum ∪ ReadQuorum| ≤ N
 
This means: W + R ≤ N
 
But we're given: W + R > N  ← CONTRADICTION!
 
Therefore, our assumption is false.
∴ WriteQuorum ∩ ReadQuorum ≠ ∅  QED
 
PRACTICAL IMPLICATION:
At least one node exists that:
  1. Received and acknowledged the write
  2. Will be queried by the read
  
This node carries the latest write, ensuring the read sees it.

Failure Tolerance Analysis

One of the most important aspects of quorum configuration is understanding how many node failures the system can tolerate. This varies based on the operation type and your quorum settings.

Write Availability:

Writes can succeed as long as at least W nodes are available. Maximum tolerable failures for writes = N - W

Read Availability:

Reads can succeed as long as at least R nodes are available. Maximum tolerable failures for reads = N - R

Combined Availability:

For the system to handle both reads and writes:

Writes need: ≥ W nodes up
Reads need: ≥ R nodes up
For strong consistency: W + R > N must still hold

Failure Tolerance for Common Quorum Configurations (N = 5)
Configuration	W	R	Write Failures Tolerated	Read Failures Tolerated	Both Operations Tolerated
Read-optimized	4	2	1 node	3 nodes	1 node
Write-optimized	2	4	3 nodes	1 node	1 node
Balanced	3	3	2 nodes	2 nodes	2 nodes
Strong consistency	5	1	0 nodes	4 nodes	0 nodes
Write-one (eventual)	1	5	4 nodes	0 nodes	0 nodes

Understanding the Tradeoff Matrix:

The balanced configuration (W = R = 3 with N = 5) is often chosen because it provides:

Tolerance for 2 node failures while maintaining both reads and writes
Equal optimization for read and write operations
Symmetric behavior under failure conditions

However, if your workload is heavily read-biased (common in web applications), a read-optimized configuration (W = 4, R = 2) may be better:

Reads remain available with 3 nodes down
Writes are more durable (4 confirmations)
Trade: writes are slower and less available

Conversely, for write-heavy workloads (logging, event sourcing):

W = 2, R = 4 prioritizes write availability
Accept that reads may require more nodes

The CAP Theorem Connection

Quorum systems provide a way to tune your position on the CAP spectrum. With strict quorums (W + R > N), you choose Consistency over Availability during partitions—operations fail rather than return stale data. By relaxing quorums (W + R ≤ N), you choose Availability over Consistency—operations succeed but may return stale data. There is no configuration that provides both during a network partition.

Practical Implementation Considerations

Moving from theory to practice, implementing quorum systems in production introduces several challenges that academic papers often gloss over.

Implementation Challenges

•Timeout Selection: How long to wait for quorum responses? Too short = unnecessary failures. Too long = poor latency. Adaptive timeouts based on percentile latencies often work best.
•Coordinator Selection: Which node coordinates reads/writes? Strategies include client-selected (closest node), token-aware routing (owner of the partition), or load-balanced selection.
•Replica Set Management: When nodes join or leave, how do you maintain quorum calculations? Membership changes must be coordinated carefully to avoid split-brain scenarios.
•Version Conflicts: When multiple versions arrive at read time, how do you resolve them? LWW (Last Write Wins), vector clocks, and application-level merge functions are common approaches.
•Read Repair Throttling: Too aggressive read repair can overwhelm recovering nodes. Too passive leaves the system inconsistent longer. Rate limiting and prioritization are essential.

quorum-config.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
interface QuorumConfiguration {
  // Core quorum parameters
  replicationFactor: number;  // N
  writeQuorum: number;        // W
  readQuorum: number;         // R
  
  // Timeout configurations
  writeTimeout: number;       // ms
  readTimeout: number;        // ms
  
  // Behavior under degraded conditions
  allowDegradedWrites: boolean;  // Accept W-1 if one node is known down
  allowDegradedReads: boolean;   // Accept R-1 if one node is known down
  
  // Version resolution
  conflictResolution: 'lww' | 'vector-clock' | 'custom';
  customMerge?: (versions: VersionedValue[]) => VersionedValue;
  
  // Repair policies
  readRepairEnabled: boolean;
  readRepairProbability: number;  // 0.0 - 1.0, for sampling
  backgroundRepairInterval: number; // ms
}
 
const productionConfig: QuorumConfiguration = {
  replicationFactor: 5,
  writeQuorum: 3,
  readQuorum: 3,
  
  writeTimeout: 500,
  readTimeout: 100,
  
  // Accept degraded quorum when we know a node is down
  // (prevents unnecessary failures during maintenance)
  allowDegradedWrites: true,
  allowDegradedReads: true,
  
  conflictResolution: 'lww',
  
  readRepairEnabled: true,
  readRepairProbability: 0.1,  // 10% of reads trigger repair check
  backgroundRepairInterval: 3600000,  // Every hour
};
 
// Validate configuration at startup
function validateQuorumConfig(config: QuorumConfiguration): void {
  const { replicationFactor: N, writeQuorum: W, readQuorum: R } = config;
  
  if (W + R <= N) {
    console.warn(`WARNING: W(${W}) + R(${R}) = ${W+R} ≤ N(${N})`);
    console.warn('This configuration does NOT guarantee consistency!');
  }
  
  if (W > N || R > N) {
    throw new Error(`Invalid config: W(${W}) or R(${R}) cannot exceed N(${N})`);
  }
  
  if (W < 1 || R < 1) {
    throw new Error('W and R must be at least 1');
  }
  
  console.log(`Quorum config valid: N=${N}, W=${W}, R=${R}`);
  console.log(`  Write failures tolerated: ${N - W}`);
  console.log(`  Read failures tolerated: ${N - R}`);
  console.log(`  Min quorum overlap: ${W + R - N}`);
}

Summary: Read and Write Quorums

We've covered the foundational concepts of quorum-based replication. Let's consolidate the essential insights:

Key Takeaways

•Quorums enable consistency without unanimity — By requiring W acknowledgments for writes and R responses for reads, systems can tolerate failures while maintaining data integrity.
•The formula W + R > N guarantees overlap — This mathematical property ensures every read contacts at least one node that participated in the most recent write, providing consistency.
•Minimum overlap = W + R - N — This formula tells you exactly how many nodes are guaranteed to bridge reads and writes, helping you reason about failure scenarios.
•Write quorums determine durability — Higher W means data persists on more nodes before acknowledgment, trading write availability for durability.
•Read quorums determine freshness — Higher R means reading from more nodes, increasing confidence in data currency but reducing read availability.
•Failure tolerance is calculable — Write availability = N - W failures tolerable; Read availability = N - R failures tolerable.
•Implementation details matter — Timeouts, version resolution, read repair, and coordinator selection all affect real-world behavior beyond theoretical guarantees.

Page Complete

You now understand the fundamental mechanics of read and write quorums. In the next page, we'll dive deeper into the N, W, R parameters—exploring how to choose optimal values for different workloads, the implications of various configurations, and how production systems like DynamoDB and Cassandra expose these parameters to operators.