Quorum

Quorum general definition:

The smallest number of people needed to be present at a meeting before it can officially begin.

Replication

In distributed computing, the same data is copied to multiple machines connected via a network.

In a leaderless configuration, which means all requests are sent to all nodes, how can we be sure that the values we read is always up-to-date?

up-to-date read will return the value of lastest write

Keeping in mind that all nodes are operating independently with their own database. They could also gone offline or become unreachable due to network issues. There are plenty possibilities that things can go wrong.

A diagram illustrating a write operation, but only 2 out of the 3 nodes acknowledged.

write

A diagram illustrating a read operation, similarly only 2 out of the 3 nodes responded.

read

Quorum in Distributed Computing

Extend the concept to distributed computing, it refers to the smallest number of acknowledgement/response required in a cluster for an operation to be successful, or service to be availabe.

  • Let N be the number of nodes in a cluster
  • Let W be the minimum number of nodes acknowledged WRITE success
  • Let R be the minimum number of nodes responded to READ

Then, when R + W > N, we are sure that at least 1 node will return up-to-date reads.

R and W are essentially the Quorum for Read and Write

Eg: Let’s say N = 3, we have 3 nodes (A, B, C), and we configure W = R = 2:

  • during a write request, if we receive acknowledgment from A and B, then a read operation from any of the 2 nodes (A & B, A & C, B & C) will have at least one response that’s up-to-date.

How to choose W and R

It depends on your application. A better question to ask would be, is the system read intensive or write intensive?

In a cluster of 3 nodes, if our system is read intensive, we can configure R=1, and W=3. So that, even 2 out of 3 nodes are down, read operations can still function as normal. It also speed up the read. However, W=3 requires all the nodes to acknowledge writes, that means if one node is down, no more writes will be available.

In comparison, if our system is write intensive, one might consider a configuration with W=1, and R=3.

Why N is usually odd number?

Usually a cluster consist of odd number of nodes, 3 and 5 are most commonly seen. But why is that so?

If N=4 and we want to have least one node return up-to-date result, we must have R + W > 4

  • if we configure R=3 and W=2, we can only loose one and still have quorum for both Read and Write. If we loose 2 nodes, then write operations will not be available.
  • if we configure R=W=3, and we lose 2 nodes, the system will come to a complete halt. Client can neither read nor write.

In comparison, if N=3, R=W=2, the maximum number of node we can loose is also 1. Similarly, a cluster of 5 nodes and 6 nodes can tolerate maximum 2 faulty nodes.

Generally, if N is odd number, then a cluster of N nodes and N+1 nodes gives the same level of tolerance for faulty node. And thus, a cluster has usually N nodes where N is an odd number. Fewer nodes are easier to maintain and less costly.