Paper Review: Generalized Isolation Level Definitions

Title and Author of Paper

Generalized Isolation Level Definitions, Adya et al.

Summary

The ANSI SQL standard defines isolation levels allowing database users to trade off between performance and consistency when running transactions. Unfortunately, the wording in the SQL standard is geared towards locking as the sole supported concurrency method. This paper presents alternative definitions to the isolation levels specified in the ANSI SQL standard that are general enough to allow for any concurrency method (multi-version, optimistic, etc.) to be used.

The paper takes the approach of specifying particular phenomena that are disallowed at commit time while allowing transaction histories to vary by implementation. That is, different concurrency methods may take alternate routes to the same destination; as long as the destination is the same, the route should not matter. This means that some ambiguity is allowed to exist in a transaction’s processing history depending on the concurrency method implementation.

This paper is a dense read; providing a somewhat mathematical approach to defining isolation levels. Rather than rehash the definitions, I will use this space to describe the different phenomena that can exist when running concurrent transactions and what guarantees the isolation levels provide with this paper’s generalized definitions.

Phenomena

This section describes different phenomena that can occur when running transactions concurrently. Each of these phenomena are things that may occur in a database that allows concurrent transactions.

Write Cycles

A write cycle occurs when two transactions write the same set of data. Preventing write cycles is the minimum requirement to having a functional database by ensuring that writes performed by transaction A are not overwritten by transaction B while transaction A is still running.

Dirty Read

A dirty read refers a transaction that is allowed to read modifications made by uncommitted (or even aborted) transactions.

Non-Repeatable Read

A non-repeatable read is a phenomena that occurs when a tuple is read twice during a transaction and that tuple value differs between reads.

Phantom Reads

A phantom read occurs when a transaction makes two identical queries during processing, yet the returned results of the two queries are different.

Generalized Isolation Levels

This section outlines the different isolation levels used to prevent the phenomena in the previous section from occurring. In this paper, the terminology PL is used to denote portable isolation levels that do not depend on a particular concurrency method (locking). I have also added the more commonly referred to name for each isolation level defined by the ANSI SQL standard.

PL-1 (READ UNCOMMITTED)

PL-1 isolation disallows write cycles and guarantees that transaction A’s writes are completely isolated from the writes of other transactions. This isolation level allows dirty reads; one transaction may see uncommitted changes made by some other transaction.

PL-2 (READ COMMITTED)

PL-2 isolation disallows both write cycles and dirty reads. It ensures that transactions are only allowed to read the updates of data that has committed (along with PL-1 guarantees). This isolation level allows non-repeatable reads; one transaction may see different results after reading the same value twice during processing.

PL-2.99 (REPEATABLE READ)

PL-2.99 isolation is a slightly relaxed version of PL-3 that allows for phantom reads. It provides full serializability guarantees for individual data items but not for queries.

PL-3 (SERIALIZABLE)

PL-3 isolation disallows all phenomena by preventing transactions that perform inconsistent reads or writes from committing. It ensures that transaction A is completely isolated from other transactions, meaning that all operations of transaction A appear to occur either before or after all operations of any other transaction.

Isolation Levels

The following tables summarizes the effect of each isolation level in terms of the phenomena that they allow.