What is Serializability in Distributed System?
Table of Contents
- Introduction
- What is Serializability?
- How to Achieve Serializability?
- Why or Why Not Serializability?
- How is it Different from Linearizability?
- Conclusion
Introduction
Transactions have been the mechanism for simplifying different issues or faults that could happen in a data system. Serializability is an important concept to understand transactions, which guarantees to prevent different data race conditions.
What is 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. It is okay for that serial order to be different from the order in which transactions were actually run.
Here is an example of non-serializable transactions:
It is not serializable because write from transaction A has been overwritten by transaction B. The transaction did not happen as if they had executed one at a time.
How to Achieve serializability?
Let’s look at two different scenarios: single node vs. multi-nodes
Single Node
Here are the different techniques we can use to achieve serializable isolation in a single node:
- Actual serial execution: one thread in a single machine handling all transaction one at a time (serially).
- Two Phase Locking: pessimistic concurrency control that requires an exclusive access (locking) to an object when anyone wants to write (non-blocking on other cases before write)
- Serializable snapshot isolation: optimistic concurrency control that allows transactions to proceed in parallel and detect stale reads at the commit time.
Multiple Nodes
It is much harder to achieve serializability in a distributed system with multiple nodes. Often the system uses the combination of two-phase locking (2PL) and two-phase commit (2PC) to achieve serializability within the system. Depending on the requirement, Paxos can also be used instead of 2PC to achieve serializability.
Please refer to the Spanner paper of how it achieves serializability in a distributed system with multiple nodes across the globe.
Why or Why Not Serializability?
Like any distributed system concepts, there’s pros and cons:
Advantages
Serializability is used to prevent different data race conditions. It also make sure to prevent the following concurrency problems:
- Lost Updates: update from one transaction is overwritten by another transaction (a.k.a Last Write Win — LWW).
- Write Skew: two concurrent transactions update different records upon reading the same records.
- Phantoms Reads: if you read a set of rows again in the same transaction, you won’t get the same set.
- Dirty Reads: reading uncommitted data
- Non-Repeatable Reads: repeated reads on the same record in one transaction result in different returned values.
Disadvantages:
Compared to other weaker isolation level, it incur performance cost, because it requires checks in place to prevent concurrency problems mentioned above. It does not come for free. If you do not need serializability as part of your requirement, you can choose weaker isolation level (e.g., read committed).
How is it different from Linearizability?
People often get confused with linearizability and serializability. Linearizability is a guarantee about single operations on single objects. It provides a real-time (i.e., wall-clock) guarantees on the behavior of a set of single operations on a single object. Read more about the difference from “Linearizability vs. Serializability” explanation.
Important thing to keep in mind is that serializability does not imply linearizability. Similarly, linearizability does not imply serializability.
Conclusion
Serializability is an important concept to understand how single or multiple nodes interact with data to ensure no data race conditions or concurrency problems. Like any other concepts in distributed system, it comes with pros and cons. We need to make the best judgement when to enforce serializability in your system by thoroughly assessing the requirements.
