Consistency models in distributed systems
With distributed systems, consistency is not a monolithic construct and an ubiquitous phenomenon; instead it is a spectrum of stronger to weaker guarantees on ordering of events. Another common misconception is that the C for consistency in ACID and C in CAP are same. They are not! The C in ACID is meant for preserving the guarantees pertaining to wholeness and integrity of data. For example, money cannot be created or destroyed when a transfer happens between two accounts. The C in CAP pertains to establishing an order on the read and write operations across the multiple nodes of a distributed system in light of the challenges of replication lag and the loss of the single memory abstraction. For example, if two writes for the same key land on two different nodes which one takes precedence over the other? Or if a read has seen a recent write should it be prevented from seeing an older one on subsequent attempts?
Linearizability, sequential consistency, causal consistency and eventual consistency-depending on the ordering guarantees we can define numerous consistency models. Lets try and understand these with the help of some intuitive examples.
Pre Conditions
- Imagine Alex and Bob are two unrelated users browsing an e-commerce website with the intention of making a purchase.
- There is a single Google Pixel 2 phone and a single case left in the inventory
- The Google Pixel 2 product page lists both the phone and case together
- The case can be purchased either with the mobile or individually
Sequence of actions leading to to linearizable consistency
(Read)R1 Alex arrives on Google Pixel 2 product page. He sees “Hurry up. Only 1 left!”[R2]. Bob arrives on mobile case product page. He sees “Hurry up. Only 1 left!”(Write)[W1] & [W2] Alex selects both the phone and the case and clicks on pay button. An update request is fired to first “block” the the mobile phone and then conditionally block the mobile case[W3] Bob selects the case and clicks on pay button[R3] Bob’s blocking of mobile case is unsuccessful and he sees “Sorry the item is unavailable”.[R4] Alex’s blocking of mobile phone and the mobile case are successful. Alex sees "Proceed to pay"
The total order of operations i.e. [R1, R2, W1, W2, W3, R3, R4] is preserved for both Alex and Bob
Sequence of actions leading to sequential consistency
(Read)R1. Alex arrives on Google Pixel 2 product page. He sees “Hurry up. Only 1 left!”[R2] Bob arrives on mobile case product page. He sees “Hurry up. Only 1 left!”[W1] & [W2] Alex selects both the phone and the case and clicks on pay button. An update request is fired to first “block” the the mobile phone and then conditionally block the mobile case[W3] Bob selects the case and clicks on pay button. An update request is fired to “block” the the mobile case[R3] Bob’s blocking of mobile case is successful and he sees "Proceed to pay"[R4] Alex’s blocking of mobile phone is successful but not the of mobile case. Alex sees “Sorry the combination is unavailable”.
While the order of operations is preserved individually for both Alex [R1, W1, W2] and Bob [R2, W3, R4], the global order is not preserved i.e. W3 happens before W2 [R1, R2, W1, W3, W2, R3, R4]. Thus a partial order has been established in place of an global order.
Sequence of actions leading to causal consistency
Pre Conditions
- Imagine Alex has updated his FB status and in response his friends are commenting on his update
- Bob and Tom are silent spectators who are reading the updates and enjoying the friendly banter
[Alex] Oh no! My cat just jumped out the window
[Alex (a few minutes later)] Whew, the catnip plant broke her fall.
[reply from Friend 1] I love when that happens to cats! It looks a little weird
[reply from Friend 2] Helen won't mind it :)The causal order of operations is preserved while non causal operations are seen differently by different processes.
As seen by Bob when causal consistency is preserved[Alex] Oh no! My cat just jumped out the window
[Alex (a few minutes later)] Whew, the catnip plant broke her fall
[reply from Friend 2] Helen won't mind it :)
[reply from Friend 1] I love when that happens to cats! It looks a little weird
The replies from Friend 1 and 2 are not causally related to each other; so they appear in any order. But Alex’s response to his own post is causally related to his original post; hence they appear in order
In absence of causal consistency, even causally related operations would find themselves arranged out of order leading to rather unwitty consequences
As seen by Bob in absence of causal consistency [Alex] Oh no! My cat just jumped out the window
[reply from Friend 1] I love when that happens to cats! It looks a little weird
[Alex (a few minutes later)] Whew, the catnip plant broke her fall
[reply from Friend 2] Helen won't mind it :)
Eventual consistency
If a distributed system is able to guarantee Monotonic reads, Monotonic writes and “Read your own Writes” consistency then it is said to be eventually consistent. Lets evaluate all there.
Monotonic reads
Simply put monotonic reads means that if you have read a more recent value for a variable then subsequent reads will always return the same or latter value and never an older value. Of course, its fine if you read the values in the order of their appearance — older first and newer next.
Monotonic writes
It means writes are applied in the order in which they arrived. For example, lets say, x=100 and two write operations arrived in this order -120%X, X+100. Then 120%X will applied before X+100 resulting in 220. If monotonic writes condition is not met then X+100 could be applied before 120%X resulting in 240 which might be incorrect and violate some invariants such as X<225.
Read your own writes
Writes made by a client should be visible to the client immediately for any subsequent reads. For example, lets say you updated your Facebook profile. If you refresh the page then it should reveal all the updates you have applied. In absence of such guarantees its possible that reads that follow updates land on replicas which are stale and hence result in older values being surfaced.
The three models in conjunction are known as Pipelined Random Access Memory (PRAM) which implies that all operations from a single process are seen by other processes in the order they were performed as if they were in a pipeline.
Continuing the C in ACID vs C in CAP debate
In the beginning of the post we talked about how the meaning of consistency from an ACID properties standpoint are different as compared to CAP theorem. As a reminder, the I in ACID stands for Serializability which guarantees that a set of operations will always execute in some serial order without interleaving . If we combine Linearizability and Serializability we get Strict Serializability — a consistency model that ensure that not only transactions execute in isolation, it also ensure they execute in correct temporal order.