Year: 2000

Author: A Adya, B Liskov, and P O’Neil

Summary

The ANSI standard has either ambiguous definitions or too strict definitions based solely on locking. The authors propose a more flexible definition that applies to OCC and MVCC. They also handle predicates.

Note that the new levels generated are closely related to the previous lock based levels but have nuanced differences. It’s defined around the serialization graphs.

Serialization Graphs

In oder to construct the graph from a history of the execution (note that isolation level is a standard, not a constructive algorithm), we first define edges, which are the same as traditional dependency graphs for analyzing serializability (undergrad material) except that every edge is typed:

LSM tree

The intuition for anti-dependency: a transaction overwrites a version observed by some other transaction.

Because the isolation levels are a lot more nuanced the graph does not replace the history, which is also used when evaluating isolation level.

Isolation Levels

How do people create standards?

  • Aligned with the motivation of ANSI standard.
  • Like the previous approaches, defined in terms of phenomena that must be avoided at each level.

Note that the phenomenas are labeled G and isolation level PL.

Since the paper makes extensive reference to the previously defined isolation level from A Critique of ANSI SQL Isolation Levels, I include the descriptions here:

old isolation

And now for the new isolation levels!

PL-1: updates of conflicting transactions are not interleaved. No G0: Write Cycles. No constraints on reads. It is more permissive than D1 (read uncommitted) because G0 allows concurrent transactions to modify the same object, as explained below:

non-serializable interleaving of write operations is possible among uncommitted transactions as long as such interleavings are disallowed among committed transactions

PL-2: dissected the original motivation: “T1 updates could not be read by T2 while T1 was still uncommitted” to the following cases:

  • G1a: Aborted Reads: aborted transaction T1 and a committed transaction T2 such that T2 has read some object (maybe via a predicate) modified by T1.
  • G1b: Intermediate Reads: committed transaction T2 that has read a version of object x (maybe via a predicate) written by transaction T1 that was not T1’s final modification of x.
  • G1c: Circular Information Flow: if the graph contains directed cycle consisting entirely of dependency edges.

PL-3: neither G1 or G2 allowed. G2: Anti-dependency Cycles. Contains a directed cycle with one or more anti-dependency edges. The authors prove that this is conflict serializability whereas P3 is view serializability.

PL-2.99: one or more item-anti-dependency edges. Related to REPEATABLE READ.

Notes

  • The morning paper has a summary as well.
  • It’s interesting how this paper was not written earlier since the last one was over twenty years ago by Jim Gray.
  • Surprisingly easy read!