What is Linearizability in Distributed System?
Introduction
In a distributed system, we use replication to keep a copy of the same data in multiple machines for fault-tolerance (e.g., network partition). All of the difficulty in replication lies in handling changes to replicated data. Linearizability provides certain guarantees on a system, which simplifies interaction of dependent applications by relying on these guarantees.
What is Linearizability?
Linearizability is the strongest consistency model in a distributed system. It is a recency guarantee on reads and writes of individual objects.
The idea is to make the system appear as if there were only one copy of the data, and all operations on it are atomic. Maintaining the illusion of a single copy of the data means guaranteeing that the value read is the most recent up-to-date value, and does’t come from a stale cache or replica.
In a linearizable system, if one client reads version 2 of a data (e.g., x=2) , all subsequent reads must also return either version 2 (x=2) or updates happened afterward. For instance, the following diagram is not linearizable because user receives v1 (x=2) after seeing v2 (x=1) data.
Causality
Linearizability implies causality (i.e. causes comes before effect) because there’s a total order of operations. An example of a causality order is: a user seeing the question before the answer; it should not be the other way around.
How to Achieve Linearizability?
Let’s explore different ways to achieve linearizability in a distributed system:
Single Copy
The idea of linearizability is to make the system appears as if there were only one copy of the data. Hence, the simplest approach is literally using a single copy of the data. However, this approach is not fault-tolerant; if a node holding the data crashes, the data would be lost or inaccessible until it comes back up.
Complication w/ Data Replication
In order to make a system fault-tolerant, you would have to replicate the data. In order to preserve the linearizability in a replicated system, you would have to make sure as soon as one of the replica returns a new version of the data, all subsequent requests should serve the new version or higher, if there’s additional update made to the data afterward.
This is quite difficult especially in unbounded network delays and numerous failure scenarios in a distributed system. One way to achieve this is to use a single-leader replication strategy, which forces a single leader to handle all writes. All read replicas would check for the latest value from the leader for every read requests, which would incur significant performance cost. Also, we need to prevent the split-brain situation where two nodes acting as leaders, which would break linearizability.
Google Spanner database actually preserve linearizability with minimal penalty cost using their True Time API. Read more about it in the Spanner paper for more information.
Why or Why Not Use Linearizability?
Advantage
Imagine a service you are dependent on guarantees linearizability. Then it’s really easy to think about the interaction with this system because you won’t have to worry about any consistency problems and treat as if there’s a single copy of the data.
Disadvantage
Linearizability is the strongest consistency model in a distributed system, which comes with cost. Depending on the system, it might require additional communication with peers to preserve this property, which can harm system’s availability and performance.
If your system only requires casual consistency (i.e. ensures causes come after effect), you can achieve causal consistency without incurring the performance hit of making it linearizable (e.g., using Lamport logical timestamp)
Q. How is it different from Serializability?
Do not get confused linearizability with serializability. Serializability is an isolation property of transactions, which guarantees that even though transactions may execute in parallel, the end result is the same as if they had executed one at a time, serially, without any concurrency.
Serializability is a global property ensuring the entire history of operations/transactions are executed serially. On the other hand, linearizability is a local property that provides recency guarantee on reads and writes on individual objects. It does not provide any guarantees about transactions.
You can learn more about serializability in the “What is Serializability in Distributed System” blog.
Conclusion
Linearizability is a strong guarantee that not many databases or distributed systems provides due to certain trade-offs. However, such guarantees makes the dependent applications/services much easier to think about the interaction.
By understanding the concept of linearizability, make sure to take advantage of dependent services that are linearizable. Also, thoroughly understand the requirements of your service and assess whether it makes sense to provide linearizability to dependent services of yours!
