Quorum Consensus

The Problem

According to the CAP theorem, you can not achieve consistency, availability, and partition tolerance all at once. However, achieving strong consistency is desirable in many systems, but this strong consistency has a price that should be paid. One naive implementation of strong consistency asks the master to serialize all of the operations, which makes it a bottleneck of the system. Although there are many other kinds of consistency that might be suitable for your system, many systems still need strong consistency. That's why it's important to optimize it as much as possible.

Pigeonhole Principle

Before digging into the optimization, there is an important mathematical (probabilistic) topic that needs to be understood. As it's the base for the solution. Assume that you have n items, and m containers, where n > m. However, you need to put all of these n items inside these m containers. What can you deduce from this information? Right, that there is at least one container that will have more than 1 item inside it! That's because n - m > 0,


Quorum Consensus

Let's improve our insert, get operations performance.

  • Define a replica set of size N
  • put() only succeed if the master received at least acks from W replicas
  • get() only succeed if the master got acks from R replicas
  • W + R > N

Just think about it, it's a direct application of the pigeonhole principle. When we update, we get W acks, when we retrieve, we get R acks, W + R - N > 0 which means that there should be at least one replica that got the update, and that voted in the retrieve.


Assume we started with N = 3 replicas {N1, N3, N4} , and W = 2 (we require 2 acks for each write operation), and R = 2 (we require 2 acks for each get operation)

image.png When the N3 update operation fails, it doesn't matter because we already have 2 other acks.

image.png When we retrieve, we get 2 acks as required, from N1, N3. Although N3 failed and gave us a null result, N1 had already the update, which means that we achieved our goal with the minimum overhead!

References and further reading: