No video of the event yet, sorry!

Introduction

Till 2011, Serializable isolation level in PostgreSQL was in fact Snapshot Isolation(SI). SI can allow some types of write skew anomalies with workloads which read and write data related by constraints concurrently. Traditional methods to implement Serializable isolation level use strict 2-phase locking (S2PL), which is a pessimistic algorithm and involves taking locks on reads as well as writes. Postgres Serializable Snapshot Isolation (SSI) first proposed my Michael Cahill is an optimistic algorithm that just imposes a small penalty as compared to SI and gives rise to schedules that are serializable. This algorithm has been proposed as late as 2008 and and is relatively young as compared to other database algorithms in use. This talk is a deep dive into SSI and an overview of its implementation in Postgres. It also covers challenges in testing and a well known testing framework.

SSI Background

We discuss modelling transactions in a system with a multi-version serialization graphs (MVSGs). To understand the intuition behind SSI, it is useful to draw out an MVSG graphs for various concurrent executions of different types of transactions in a system. A cycle means the history is non-serializable. We discuss various examples of concurrent transactions, also looking at cases where a read-only transaction can read a state of a database which could not have existed with any serializable history.

SSI Deep Dive

We discuss the SSI algorithm and how it yields only serializable histories. To detect a non-serializable history it is not necessary to detect the entire cycle, but just enough to detect two adjacent rw-edges. With this simplification, the SSI algorithm can be designed to be:

• Not be overly pessimistic and cause too many aborts
• Not allow any non-serializable history at all
• Keep overheads for detection of cycles to a minimum

Overview of SSI implementation in PostgreSQL

SSI implementation requires detection of adjacent "rw-conflict edges". The talk discusses the implementation for SIREAD locks that do not block writes, but are only used for tracking these edges. Unlike normal locks these are held till all transactions concurrent with the transaction that read the tuple have completed.

To cover records which may not exist when the transaction reads the data, but appear concurrently (phantoms), we need predicate locking, which was so far not required for Snapshot Isolation. This talk discusses its implementation for SSI.

Testing of SSI

Isolation tester in PostgreSQL source code is used for testing various scenarios with concurrent transactions. However, it is also important to see how SSI behaves under extreme load and various failure cases. We discuss Jepsen’s Elle Checker, the lesser known black-box Serializability tester for transactional databases.

References

1. Serializable Snapshot Isolation in PostgreSQL (Dan Ports, Kevin Grittner)
2. Serializable Snapshot Isolation for Snapshot Databases (Michael J Cahill et all)
3. A read-only Snapshot Anomaly under Snapshot Isolation (Alan Fekete et all)