Quorum and Consensus

In a distributed system, data is often replicated across multiple nodes to ensure high availability and fault tolerance. But this replication introduces a new problem: how do you ensure that all the nodes agree on the state of the data, especially when failures occur?

This is the problem of consensus. A consensus algorithm is a process for a group of nodes to agree on a single value or state. Quorum is a core concept used in many consensus protocols.

What is a Quorum?

A quorum is the minimum number of nodes in a cluster that must participate in an operation for it to be considered successful. It's a form of voting. Instead of requiring all nodes to agree (which would make the system unavailable if even one node failed), you only require a majority.

This concept is most famously used in leaderless replication systems (like Cassandra or DynamoDB) to provide tunable consistency.

Quorum for Reads and Writes

Let's define the variables:

• N = The number of replicas for a piece of data.
• W = The write quorum. The minimum number of replicas that must acknowledge a write for it to be considered successful.
• R = The read quorum. The minimum number of replicas that must respond to a read request.

By tuning W and R, you can control the trade-off between consistency and performance.

The Quorum Overlap Formula: W + R > N

This is the key to achieving strong consistency in a leaderless system. If the sum of your write quorum and your read quorum is greater than the total number of replicas, you are guaranteed that your read set will have at least one node in common with your write set. This ensures that any read will always see the most recent successful write.

Example:

• N = 3 (We have 3 replicas for our data).
• We can choose W = 2 and R = 2.
• W + R = 4, which is greater than N = 3. This configuration guarantees strong consistency.

How it works:

1. Write Operation: A client wants to write a new value. It sends the write request to all 3 replicas. The write is considered successful only after at least W=2 replicas have confirmed they have stored the data.
2. Read Operation: A client wants to read the data. It sends a read request to all 3 replicas. It waits for responses from at least R=2 replicas.
3. Guarantee: Because of the overlap, at least one of the two nodes that responded to the read request must have been part of the successful write quorum. The client can then look at the version numbers of the data from the responding nodes and return the one with the most recent timestamp, confident that it is the latest successfully written value.

Tuning Quorums for Different Needs

You can adjust W and R to optimize for read performance, write performance, or consistency.

• Fast Writes, Slow Reads (W=1, R=N): A write is acknowledged as soon as one replica receives it. This is very fast. However, a read must wait for a response from all replicas to be sure it's getting the latest data. This is good for write-heavy, read-light workloads.
• Fast Reads, Slow Writes (W=N, R=1): A write must be confirmed by all replicas before it's considered successful. This is slow. But a read can be served from any single replica, as it's guaranteed to be consistent. This is good for read-heavy, write-light workloads.
• Balanced (W=2, R=2 for N=3): This offers a good balance between read and write performance while still guaranteeing strong consistency.

Consensus Algorithms: Paxos and Raft

Quorum is a mechanism, but it's part of a broader class of consensus algorithms. These are formal protocols for achieving agreement in a distributed system, even in the presence of failures.

You are not expected to implement these algorithms in an interview, but knowing what they are and what problem they solve is important.

Paxos

Paxos is one of the first and most famous consensus algorithms. It's known for being mathematically correct but also notoriously difficult to understand and implement in practice.

Raft

Raft is a more modern consensus algorithm that was designed to be easier to understand and implement than Paxos. It's functionally equivalent to Paxos but has a simpler state machine.

How Raft Works (High-Level):

1. Leader Election: The nodes in the cluster elect a single leader.
2. Log Replication: The leader is responsible for all writes. It appends each new command to its log and then replicates that log entry to the follower nodes.
3. Commit: Once a majority of followers have acknowledged that they have received the log entry, the leader "commits" the entry and applies it to its state machine. It then notifies the followers that the entry is committed.

Where are they used? Consensus algorithms like Raft are used in many modern distributed systems to manage critical state, such as:

• ZooKeeper and etcd: Distributed coordination services that are used to manage configuration, leader election, and service discovery in other systems (like Kubernetes and Kafka).
• CockroachDB and TiDB: Distributed SQL databases that use consensus to ensure transactional consistency.

In a system design interview, when you talk about needing to manage state reliably across multiple nodes (e.g., for leader election or managing shard metadata), mentioning that you would use a proven consensus algorithm via a tool like ZooKeeper or etcd is a very strong signal. It shows you understand the problem of consensus and know that you shouldn't try to solve it yourself.