If you're studying consistency models in distributed systems, you'll eventually come across the terms serializability and linearizability. While they sound similar, they describe different characteristics of distributed systems.
Serializability is a model applied to transactions, ensuring that even though transactions may be executed concurrently, they appear to occur in a seamless, indivisible manner. On the other hand, linearizability is concerned with the consistency of operations in real-time, guaranteeing that any operation is observed to be instantaneous and its effect is immediately visible to all subsequent operations. In short, the former ensures that operations are indivisible, while the latter ensures the operations adhere to some real-time sequence.
In the remainder of this blog post we'll explore each concept individually with the aid of real-life examples.
Serializability
Serializability is a transactional isolation level and is usually regarded as the strongest isolation level. It assures that transactions may run concurrently yet the end result is as if they had executed sequentially, one at a time. The order in which these transactions occur is not guaranteed; it only ensures that they effectively act serially. This means that these transactions are insulated from race conditions, as there is no overlap in their constituent operations.
The safeguard against race conditions is crucial, especially in the context of distributed systems, as it helps avert critical bugs in applications.
Ticketing example
To understand what might go wrong with a lack of serializability, let's examine a situation where two users, Alice and Bob, are each trying to secure the final available ticket to a concert via an online ticketing platform.
The system's process to book a ticket involves an initial check to confirm the availability of at least one ticket for the given concert, and upon confirmation, the system proceeds to reserve said ticket. Behind the scenes, this process translates into a transaction made up of two SQL queries: one reads the current ticket inventory from the database to ensure there's at least one ticket available, and the other updates the database to reflect the reservation of a ticket.
Now, consider what might occur in the absence of serializability, depicted in figure 1-1 below.
Figure 1-1. Without a serializable isolation level, Alice and Bob both reserve the same ticket.
In this scenario without serializability, we encounter an issue where both Alice and Bob manage to claim the same final ticket. This outcome is problematic, as it promises more than the system can actually deliver, leading to potential disappointment for one of the users on the day of the concert.
Better luck next time!
The issue arises when Bob's transaction reads the ticket availability while Alice's transaction is in progress. Bob's subsequent operation to reserve the ticket is based on the initial value he reads, but unbeknownst to him, Alice changes this value, invalidating Bob's initial read. This situation, referred to as a phantom read, exemplifies the inconsistencies that a serializable isolation level seeks to eliminate.
Under serializability, implemented in the upcoming example by two-phase locking (2PL), multiple transactions can read the same data simultaneously, provided there are no pending write operations. If a transaction is going to write, exclusive access is mandated.
In the serializable scenario below, when Alice starts her transaction, which attempts to write to ticket_avail, Bob's transaction is precluded from accessing that object — either for reading or writing — until Alice's transaction has been completed. The result of this strict access control is illustrated in figure 1-2.
Figure 1-2. With serializability, only Alice is able to reserve a ticket.
Consequently, Bob's transaction detects that no tickets remain and, therefore, aborts without reserving a ticket. Hence, the ticketing system has successfully upheld the fundamental rule that each ticket is uniquely sold to a single person.
Linearizability
Linearizability, also known as strong consistency, ensures that any operations on data appear instantaneously to an outside observer. In this model, it seems as though there's only one copy of the data, and all operations on it occur atomically. This facade can be important, particularly in a distributed system where, for scalability, data might be replicated across multiple nodes. The resulting abstraction that there's a single copy of the data is highly beneficial for programmers, as it allows them to think and operate in a much simpler manner.
However, the trade-off for this level of consistency is typically increased latency and decreased availability. Therefore, while linearizability is desirable for some applications, others may decide to sacrifice it and tolerate stale data in order to achieve faster response times and better uptime.
Banking example
Let's consider Bob's banking experience to shed light on the concept of linearizability. Bob is handling his bank transactions using both his smartphone and his laptop. He makes a $50 deposit using his banking application on his smartphone, and shortly after, he attempts to verify his account's total balance on his laptop.
The banking system uses a primary database along with a read replica, and does not guarantee linearizability. Depicted in figure 2-1 is a potential outcome.
Figure 2-1. In the absence of linearizability, Bob does not see a consistent view over his bank account.
In the absence of linearizability, there's a temporary inconsistency in Bob's displayed balance. Right after depositing $50 into his account—bringing his total balance to $150—when he checks his balance on his laptop, it erroneously still only shows $100. The reason for this inconsistency is that the laptop's session is connected to a read replica that hasn't yet synchronized with the leader, which holds the most recent update. The delay in updating the replica leads to stale data being displayed, potentially causing Bob to doubt whether his deposit went through or, worse yet, prompting him to make another deposit.
Ultimately, if Bob persists in refreshing his account, the correct balance of $150 will display, once the read replica catches up with the leader. This situation is in fact illustrating a weaker consistency model referred to as eventual consistency.
Just another day in the life of digital banking
To avoid such inconsistencies altogether, the bank opts for a database that provides linearizability. Although there are various methods that database can use to achieve this, some more complex than others, we'll focus on the simplest approach where data is replicated synchronously to the read replica. Only when the replica is updated does the system acknowledge the transaction's success. This is depicted in figure 2-2.
Figure 2-2. In a linearizable system, what Bobs sees is consistent with his actions.
Now, Bob gets a deposit confirmation only after the read replica has been updated with the new value. Consequently, when Bob checks his balance from his laptop, the displayed amount is up-to-date, accurately showing the current status of his account.
Conclusion
Serializability and linearizability may be confused with one another as their definitions in plain English suggest something that is of a sequential order. Yet, as we've explored, they offer distinct guarantees and understanding the difference is important.
Serializability pertains to the sequential integrity of transactions, ensuring they occur in some serial order. This concept was demonstrated with the online ticketing system example, where serializability prevented double booking of a ticket.
Linearizability is concerned with the ordering of read and write operations on an individual object, maintaining the real-time sequence of these operations to avoid any discrepancies during later processing of this data. This was exemplified in the banking scenario where Bob's displayed balance was consistent with his actions.
These two concepts are for the most part independent of each other. A system may ensure serializability without linearizability, or the other way around, and some systems manage to achieve both. Recognizing their differences allows for informed choices in system design, ensuring the appropriate isolation level and consistency model is applied based on application needs.