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:

Non-Serializable Transactions
Figure 1. 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store