Quorum — Architecture Pattern
Quorum is the minimum number of servers that must acknowledge a distributed operation to be successful before it’s marked a success.
One of the constants with any Distributed System is Failure. We build systems such that they are resilient to failures. Let’s continue from our previous discussion on WAL, where to ensure durability, our operations were stored on the WAL, from where they could be recovered. Let’s assume we want to replicate our WAL to different nodes in the cluster for High Availability and Fault Tolerance. The next question we need to ask is -
How many nodes in our cluster need to acknowledge that they got the replicated copy from the original server before we can say that the update to the WAL was successful?
Quorum is the answer to the above question. Quorum is the minimum number of servers that must acknowledge a distributed operation to be successful before it's marked a success.
But why do we need a quorum? What if we chose not to use Quorum?
Scenario 1: Replicate Changes To All Nodes In The Cluster
Instead of replicating the changes to a quorum of nodes, we can replicate the changes to all the nodes in the cluster. Then the origin server waits for acknowledgement from all the servers. This could lead to slow acknowledgement from the origin server(performance impact) & also could impact application availability as we always need all servers to acknowledge any operation. If any server is down/network partitioned, the operations would not be successfully acknowledged.
Scenario 2: Don’t Replicate Changes
We can choose not to replicate changes at all. In such cases, we run the risk of losing the updates(in case data wasn’t flushed to WAL in our example). This also impacts consistency since the data changes written to a particular server won’t be available till the server is up.
How much is Enough?
We defined Quorum as the minimum number of servers that need to acknowledge an operation before it can be considered successful. But what’s a good number, such that we get both, good application performance & consistency?
We generally prefer for a majority of nodes in the cluster to acknowledge any operation for it to be considered successful. Thus, for an N-node cluster, the Quorum should be of N/2 + 1 node.
What if I choose Quorum to be > N/2 + 1? Well, you will have more nodes to acknowledge your changes, and so you’ll have a performance hit when compared to choosing N/2 + 1 as your Quorum. Refer to Scenario 1 for understanding the impact.
What if I choose Quorum to be < N/2 + 1? In this case, only a minority of the nodes in the cluster are guaranteed to have the changes. In case those nodes go down/are network partitioned, the changes wouldn’t be visible to the end-users & would have consistency issues. Refer to Scenario 2 for understanding the impact.
Quorum & Tolerable Failures
Quorum also helps us determine the number of node failures that can be tolerated as a function of the cluster size.
Number of Failures Servers tolerated = Number of Servers in Cluster — Number of Servers in Quorum
Given below is a table where we can derive the number of failure nodes tolerated for different cluster sizes -
One thing you should note is the Quorum is the same across an Odd and Even cluster pair(Eg: both a 4 & 5 node cluster need a quorum of 3 nodes). This also implies that an Odd cluster size should be preferred because the Quorum will be the same as the Even node cluster, while the failure node tolerations will be higher for the Odd cluster size.
Real-Life Usage
1) Consensus algorithms like Paxos and Raft are all quorum based.
2) Cassandra uses write quorum to ensure data consistency, where a write is considered successful only after its replicated to at least a quorum of replica nodes.
3) Leader Election happens only if the leader gets a vote from the majority of the servers i.e. Quorum.
In a nutshell, Quorum allows us to achieve consistency in a distributed system, with good throughput/performance.