Menu
Can anyone out there help me understand what Linearizability is? I need an explanation that is simple and easy to understand. I'm reading The Art of Multiprocessor Programming by Maruice Herilihy and Nir Shavit and am trying to understand Chapter 3 about Concurrent Objects.
I understand that a method is Linearizable if it has a point where it seems to "take effect" instantaneously from the point of view of the other threads. That makes sense, but it is also said that Linearizability is actually a property of the execution history. What does it mean for an execution history to be Linearizable, why do I care, and how does it relate to a method or object being Linearizable?
Thank you!
445
Linearizability is the strongest form of consistency. This means that all operations are executed in a way as if executed on a single machine, despite the data being distributed across multiple replicas. As a result, every operation returns an up-to-date value.
Linearizability is a strong correctness condition, which constrains what outputs are possible when an object is accessed by multiple processes concurrently. It is a safety property which ensures that operations do not complete in an unexpected or unpredictable manner.
The way to achieve linearizability, is to generate a unique sequence number for every request such that the order of the sequence numbers reflect the order in which the client requests are executed.
Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A.
A picture is worth 1000 words.
The first SELECT statement reads the value of 50, while the second SELECT reads the value of 10 since in between the two read operations a write operation was executed.
Linearizability means that modifications happen instantaneously, and once a registry value is written, any subsequent read operation will find the very same value as long as the registry will not undergo any modification.
This time, we don’t have a single registry or a single source of truth. Our system uses asynchronous database replication, and we have a Primary node that takes both reads and writes and a Follower node used for read operations only.
Because replication happens asynchronously, there’s a lag between the Primary node row modification and the time when the Follower applies the same change.
One database connection changes the account balance from 50 to 10 and commits the transaction. Right after, a second transaction reads from the Follower node, but since replication did not apply the balance modification, the value of 50 is read.
Therefore, this system is not linearizable since changes don’t appear to happen instantaneously. In order to make this system linearizable, we need to use synchronous replication, and the Primary node UPDATE operation will not complete until the Follower node also applies the same modification.
167
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
