Hermitage: Testing transaction isolation levels

“Aristotle maintained that women have fewer teeth than men; although he was twice married, it never occurred to him to verify this statement by examining his wives' mouths.”

― Bertrand Russell, The Impact of Science on Society (1952)

Hermitage is an attempt to nail down precisely what different database systems actually mean with their isolation levels. It's a suite of tests that simulates various concurrency issues — some common, some more obscure — and documents how different databases handle those situations.

This project was started by Martin Kleppmann as background research for his book, Designing Data-Intensive Applications. In this repository you'll find a lot of nitty-gritty detail. For a gentle, friendly introduction to the topic, please read the book. There is also a blog post with some background story.

Summary of test results

The cryptic abbreviations (G1c, PMP etc) are different kinds of concurrency anomalies — issues which can occur when multiple clients are executing transactions at the same time, and which can cause application bugs. The precise definitions of these anomalies are given in the literature (see below for details).

Legend:

• ★ = default configuration
• ✓ = isolation level prevents this anomaly from occurring
• — = isolation level does not prevent this anomaly, so it can occur
• R/O = isolation level prevents this anomaly in a read-only context, but when you perform writes, the anomaly can occur (see test cases for details)
• some = isolation level prevents this anomaly in some cases, but not in others (see test cases for details)
• anomalies
  • G0: Write Cycles (dirty writes)
  • G1a: Aborted Reads (dirty reads, cascaded aborts)
  • G1b: Intermediate Reads (dirty reads)
  • G1c: Circular Information Flow (dirty reads)
  • OTV: Observed Transaction Vanishes
  • PMP: Predicate-Many-Preceders
  • P4: Lost Update
  • G-single: Single Anti-dependency Cycles (read skew)
  • G2-item: Item Anti-dependency Cycles (write skew on disjoint read)
  • G2: Anti-Dependency Cycles (write skew on predicate read)

Background

Isolation is the I in ACID, and it describes how a database protects an application from concurrency problems (race conditions). If you read a traditional database theory textbook, it will tell you that isolation is supposed to mean serializability, i.e. you can pretend that transactions are executed one after another, and concurrency problems do not happen. However, if you look at the implementations of isolation in practice, you see that serializability is rarely used, and some popular databases (such as Oracle) don't even implement it.

So what does isolation actually mean? Well, in practice, many database systems allow you to choose your isolation level, as a trade-off between performance and safety (weaker isolation is faster but exposes you to more potential race conditions). Unfortunately, those weaker isolation levels are quite poorly understood. Even though our industry has been working with this stuff for 20 years or more, there are not many people who can explain off-the-cuff the difference between, say, read committed and repeatable read. This is a problem, because if you don't know what guarantees you can expect from your database, you cannot know whether your code has concurrency bugs and race conditions.

The SQL standard tried to define four isolation levels (read uncommitted, read committed, repeatable read and serializable), but its definition is flawed. Several researchers have tried to nail down more precise definitions of weak (i.e. non-serializable) isolation levels. In particular:

• Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica: "Scalable Atomic Visibility with RAMP Transactions" at ACM Transactions on Database Systems, Vol. 41, No. 3, Article 15, Publication date: July 2016.
• Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M Hellerstein and Ion Stoica: “Highly Available Transactions: Virtues and Limitations (Extended Version),” at 40th International Conference on Very Large Data Bases (VLDB), September 2014.
• Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil, and Dennis Shasha: “Making Snapshot Isolation Serializable,” ACM Transactions on Database Systems (TODS), volume 30, number 2, pages 492–528, June 2005. doi:10.1145/1071610.1071615
• Readings in Database Systems, edited by Joseph M. Hellerstein and Michael Stonebraker, 4th edition, MIT Press, 2005. ISBN: 978-0-262-69314-1
• Atul Adya, Barbara Liskov, Patrick O’Neil: "Generalized Isolation Level Definitions" Appears in the Proceedings of the IEEE International Conference on Data Engineering, San Diego, CA, March 2000
• Atul Adya: “Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions,” PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, March 1999.
• Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil and Patrick O'Neil: “A Critique of ANSI SQL Isolation Levels,” at ACM International Conference on Management of Data (SIGMOD), volume 24, number 2, May 1995. doi:10.1145/568271.223785
• Jim N Gray, Raymond A Lorie, Gianfranco R Putzolu, and Irving L Traiger: “Granularity of Locks and Degrees of Consistency in a Shared Data Base,” in Modelling in Data Base Management Systems: Proceedings of the IFIP Working Conference on Modelling in Data Base Management Systems, edited by G.M. Nijssen, Elsevier/North Holland Publishing, pages 364–394, 1976.

This project is based on the formal definition of weak isolation introduced by Adya, as extended by Bailis et al. They mathematically define certain anomalies (or phenomena) which can occur in an unrestricted concurrency model, and define isolation levels as prohibiting or preventing certain anomalies from occurring.

The formal definitions are not easy to understand, but at least they are precise. By comparison, the database vendors' documentation of isolation levels is also hard to understand, but on top of that it's also frustratingly vague:

• PostgreSQL
• MySQL/InnoDB
• Oracle
• SQL Server
• FoundationDB

Goals of this project

This repository contains a series of tests which probe for a range of concurrency anomalies. They are based on the definitions in the literature above. This is useful for several reasons:

• It allows us to compare isolation levels easily: the more check marks in the table above, the stronger its guarantees.
• For anyone who needs help choosing the right isolation level for their application, the test suites provide concrete examples of the differences between isolation levels.
• Various new databases have claimed to support ACID transactions, but their marketing materials often don't make clear what guarantees are actually provided. This test suite can allow a fair comparison of different databases, at least on the isolation aspect of ACID.
• Hopefully, this effort can be part of a journey towards a better understanding of weak isolation. It looks like weak isolation isn't going away, so we need to learn to be more precise about what it means, and build tools to help us deal with it, otherwise we'll just continue creating buggy applications.

Caveats

• This is a test suite. It obviously cannot prove that a database always behaves in a certain way, it can only probe certain examples and observe what happens.
• Tests are currently executed by hand. This means that any concurrency issues that depend on fast timings will not be found. However, it's remarkable that even at the slow speed of a human, you can still easily demonstrate concurrency issues. It's not the speed that matters, it's the ordering of events.
• The summary table above only describes safety properties, i.e. whether the database allows a certain race condition to occur. It doesn't describe how the anomaly is prevented (usually by blocking or aborting some of the transactions). In practice, how much transactions need to be blocked or aborted makes a big performance difference. For example, although PostgreSQL's serializable and MySQL's serializable have the same isolation guarantees, they have totally different implementations and very different performance characteristics.
• We're not trying to compare performance here. Performance depends on the workload, so please do your own benchmarking.
• More check marks doesn't necessarily mean better. This is not Top Trumps, it's a game of trade-offs. All we're trying to do here is to understand what we gain and what we lose at different isolation levels.

Using this project

The tests are currently executed by hand: you simply open two or three connections to the same database in different terminal windows, and run the queries in the order they appear in the test script. A comment indicates which transaction executes a particular query, and what the expected result is.

This could probably be automated, but it's actually quite interesting to go through the exercise of stepping through transactions one line at a time, and watching how the database responds. If you want to build an intuition for database concurrency, running through the test suite is a good exercise. For some databases, setup instructions are included at the bottom of the file.

At the moment, this project only compares five databases, but many more databases offer transactions. It would be especially interesting to add the new generation of distributed transactional databases ("NewSQL" if you like marketing-speak) to this comparison: Aerospike, NuoDB, MemSQL, etc. FoundationDB is currently included.

If you would like to port the test suite to another database, or add new tests, your contribution would be most welcome!

Thank you to contributors:

• Jennifer Rullmann for porting the test suite to FoundationDB.
• @dddinary for porting the test suite to CockroachDB.
• Franck Pachot for porting the test suite to YugabyteDB.

License

Copyright Martin Kleppmann, 2014. This work is licensed under a Creative Commons Attribution 4.0 International License.