Consistency & Consensus for System Design Interview (1): introduction to linearizability
PREV | HOME | NEXT | System Design Resource List
Don’t forget to get your copy of Designing Data Intensive Applications, the single most important book to read for system design interview prep!
Check out ByteByteGo’s popular System Design Interview Course
Introduction
A database with multiple replicas, experiences some lag copying a new write processed by one of the replicas to the rest of the replicas. During this time, a read request routed to one of the replicas which hasn’t replicated the new write yet, returns the old value. If multiple read requests are issued, then some of these requests may reach replicas who have replicated the new write and some requests to replicas that are yet to replicate the new write. The result is that some read requests return the new value and some the old value. All the database replicas are expected to eventually record the new write, however, there’s no bound on how long it takes for all the replicas to replicate the write.
Eventual consistency is a weak guarantee as it doesn’t say when the replicas will converge to the same value. Also, from a developer’s perspective it’s unnatural to write a key but see an old value returned when reading the key immediately after the write, in case the read is routed to a lagging replica. We can design systems with stronger consistency models in lieu of the eventual consistency model, but doing so will cost us fault tolerance ability or performance of the system.
Linearizability
Wikipedia defines consistency model as “a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of reading, writing, or updating memory will be predictable.” Consistency models detail how the state of replicas is handled in a distributed system which can experience network delays and node failures.
Linearizability is one of the strongest consistency models also known by the following names:
- Atomic consistency
- Strong consistency
- Immediate consistency
- External consistency
Land a higher salary with Grokking Comp Negotiation in Tech.
Side-stepping the formal definition of Linearizability, the concept behind Linearizability is for a system to emulate the behavior and present a view of a single copy of data with all operations on the data being atomic. A linearizable system will hide away the internal details of having multiple replicas and appear to end-users/clients as if they are interacting with a single copy of data.
In a linearizable system, after a successful write is complete, all subsequent reads are returned the last value written, i.e. an old value from a lagging replica is never returned. The system maintains an illusion of a single copy of data that reads the most recent value that was written. This is why linearizability is also known as the recency guarantee.
Let’s consider an example that demonstrates a system which is not linearizable. A website for US presidential elections has a database or datastore comprising three nodes, A, B and C. On election day, the website displays real-time results. A candidate is required to win 270 or more electoral votes out of a total of 538 to win the election. A process updates the electoral votes won so far for both Biden and Trump. As the election unfolds consider the following sequence of events:
- For simplicity consider the database holds a row with column names Biden and Trump and the columns hold the electoral vote count won by each candidate so far. Biden has 264 votes so far and Trump has 223.
- State of Pennsylvania is called in favor of Biden, giving him 20 electoral votes and putting his total count at 284. This information is updated in the database via a write request that updates the Biden column to 284. The write request is routed to node C which updates the row.
- At this point nodes A and B are yet to replicate the changes that node C recorded.
- Jill loads the website in her browser to see the latest results and her read request is routed to node C, which informs her that Biden has secured 284 votes and won the presidential election.
- Jill texts Jack about the election result, and Jack loads the website on his mobile phone to see the results for himself. Jack’s read request is routed to node B, which hasn’t yet replicated changes from node C, and returns the stale results, where there’s no presidential winner so far.
Check out the course Coderust: Hacking the Coding Interview for Facebook and Google coding interviews.
In the above scenario, once Jill’s read request had seen the updated results, every read request thereafter should have observed the same results as Jill’s to conform as a linearizable system. Since Jack’s read request which occurs after Jill’s read request on the timeline, observes stale results, we can declare the system isn’t linearizable.
Explaining Linearizability
Consider three clients A, B and C that interact with a database system. Client C writes a key K and the other two clients consistently poll the value of key K. From the client’s perspective, a read or write request involves sending a request to the database and then receiving a response. A request is considered complete when a response is received by the client. Each request thus takes some time to complete and isn’t instantaneous. There are three ways read and write requests can be sequenced with each other and we discuss each one below. The database is considered to be a blackbox with replicas hidden from the clients. Say the initial value of the key is set to K=10, and a write request attempts to change the value to K = 7.
- Read request starts and completes before the write request initiates. In this case, the read request should return K=10
2. Read request starts and completes, after the write request completes. In this case, the read request occurs after the write request has completed, the response for the read request should return K=7.
3. Read request is initiated while the write request is in progress or the write request is initiated while the read request is in progress, i.e. the read and write requests overlap in time and are concurrent. There can also be multiple read requests that are concurrent with a write request. To claim linearizability, the database must NOT flip back and forth between returning 10 and 7 for the concurrent read requests, while the write is in progress.
4. The above responses switch between the old and the new value, because the read request is being served by different replicas some of which haven’t caught up to the latest value. The above behavior violates linearizability. Once a database serves the new value of the key as the response to a read request, it must serve the latest value to all subsequent read requests to satisfy the linearizability requirement.
5. Another way to think about the above scenario is to consider the write request as an atomic operation that changes the key K’s value from 10 to 7 atomically at some point in time and all read requests that follow observe the latest value.
Get a leg up on your competition with the Grokking the Advanced System Design Interview course and land that dream job!
Before we delve into more examples of linearizability, we’ll describe how a read or a write operation is represented as a bar on a timeline in the upcoming illustrations. Each bar depicted on a timeline represents the start and end of a write, read or compare-and-set operation, from the point the operation is initiated by the client to the point a response is received back at the client. The vertical line within the bar denotes the instant at which the operation executes on the database, i.e. a value is overwritten or read.
The above rectangular bar depicts a write operation that starts at time=5, ends at time=20 and the write of key K=7 executes on the database at time=13.
Given this context we can now look at some more examples of linearizability.
Consider the following two reads and writes.
The read A initiates first, then a write, followed by read B. However, read B executes before read A and also completes earlier. Both reads return the newer value since the write operation executes before both the reads. Read A starts the earliest but completes last.
If you are interviewing, consider buying our number#1 course for Python Multithreading Interviews.
This is plausible since the request from the client may be delayed getting to the database, be queued at the database, or take a long time to be processed etc. Similarly the response from the database may get queued at the system before being sent out or experience network delay reaching back to the client. In short, there could be numerous reasons along the path of a request followed by a response that cause delays. Consequently, the overall time that a read request takes to complete increases. It is also plausible that the database processes the requests in the order write, read B and read A, which is a legal ordering since the requests are concurrent.
Another variation of the three operations is shown below. Here read A returns the old value and read B returns the new value. The write operation executes in between when the two read operations execute.
The above sequence of reads and writes is also linearizable. In contrast, consider the same scenario but this time there’s a third read request, read C that executes after read B executes. Read C returns the key value as 10, AFTER read B has already read the key value as 7. This is an example of a non-linearizable read.
In the above sequence, observe that read C initiates before read B and completes after it. This is plausible as the request or response may experience delay due to a variety of reasons.
Difference between Serializability and Linearizability
One must not confuse serializability with linearizability. Recall that we previously discussed serializability as a property of transactions that says the effect of running concurrent transactions is the same as if each transaction ran in isolation in some serial order, i.e. no transaction steps on another transaction even though the transactions may be executed in parallel. On the contrary linearizability is a recency guarantee for write and read operations on individual entities within a database. Linearizability doesn’t apply to a group of operations as serializability does. This implies that a system that is only linerizable but not serializable can suffer from issues such as write-skew, phantom reads etc.
Systems that implement serializability using two-phase locking are also linearizable. Actual serial execution of transactions also implies linearizability. Finally, systems that are both serializable and linearizable are said to abide by strict serializability or strong one-copy serializability.
Get insights on designing machine learning systems with Grokking Machine Learning Design.
Try to answer the following question from what you have learnt so far:
Question: Is serializable snapshot isolation linearizable?
If you jog your memory you’ll recall that a consistent snapshot may be used by long-running queries to avoid blocking writers, while making reads from the snapshot. There may be newer writes to fields/objects but those newer writes are never reflected by the snapshot. The reads fetch stale values for fields/objects and not the most recent thus violating linearizability.
Applications of Linearizability
Apart from the election website example we discussed, some serious applications of linearizability include:
- leader election and distributed locks. One way of electing a leader is to have a distributed lock that every node in a system attempts to acquire. The node which holds the lock is considered as the leader, however, for this scheme to work the lock must be linearizable and all nodes should agree on which node holds the lock.
Get ready for your next interview by mastering Object Orientated Design and Principles.
- enforcing uniqueness guarantees, such as an email id gets registered by a single user, a meeting room is never double booked for a given time slot, a hotel room or a plane seat is allocated to a single customer.
In all these examples, the idea is for the participants to place a hold on a conceptual lock. The lock may be on a username, a hotel room, a plane seat or just the plain lock itself. Linearizability ensures that all participants agree on the single up to date value. Finally, lack of linearizability can also cause race conditions in distributed systems.
Your Comprehensive Interview Kit for Big Tech Jobs
0. Grokking the Machine Learning Interview
This course helps you build that skill, and goes over some of the most popularly asked interview problems at big tech companies.
1. Grokking the System Design Interview
Learn how to prepare for system design interviews and practice common system design interview questions.
2. Grokking Dynamic Programming Patterns for Coding Interviews
Faster preparation for coding interviews.
3. Grokking the Advanced System Design Interview
Learn system design through architectural review of real systems.
4. Grokking the Coding Interview: Patterns for Coding Questions
Faster preparation for coding interviews.
5. Grokking the Object Oriented Design Interview
Learn how to prepare for object oriented design interviews and practice common object oriented design interview questions
6. Machine Learning System Design
