Do quorum reads and writes imply linearizability?
The short answer is no, but this may seem counterintuitive to many people. In this short article, I will show you when this might happen.
Linearizability
In this article, I will be thinking of linearizability in the context of data replication. Informally, we can think of linearizability as a consistency model which, from the client’s point of view, looks as if we were performing atomic operations on a single register (i.e., replication is transparent). From the client’s point of view, all modifications are immediate. If operation A completed before operation B starts, operation B should see a state no older than operation A. Linearizability is one of the strongest consistency models, which is often hard to satisfy (what we’re about to see). If you are interested in a more formal definition, you can learn more here.
Unlucky timing
Consider the case where we have three replicas. The x value is set to 0 on each replica. The writer wants to set the value of x to 1. He sends the request to each replica. The first one responds immediately. The other two need more time (e.g., due to the network lag), but they still respond within the timeout limit so the write is successful.
Meanwhile (after the first replica confirmed the write, but not yet the other two), a reader (let’s call him reader A) wants to get the value of x. The reader gets the response from two replicas. One of them says that x = 0, the other one that x = 1. The reader picks a newer value (x = 1). A moment later, another reader (let’s call him reader B) also wants to know what the value of x is. He also gets a reply from two replicas, but from those that have not yet had an updated x value. Reader B thinks that x = 0. Although reader B sent his query after reader A’s query finished, he did receive the older data. In the previous paragraph we saw that if operation A completed before operation B starts, operation B should see a state no older than operation A. This condition is not met, which means that the system is not linearizable.
How to make it linearizable?
In order for the above situation not to take place, we must do the so-called read repair. When reader A sees that one of the replicas has stale data, it sends an update request. This ensures that by the time reader A finishes reading, x value will be updated. This is shown in the picture below.
Summary 🏁
Quorum reads and writes by themselves do not provide linearizability. With unlucky timing, it’s still possible to get stale data. The solution to this problem is read repair.
