A critique of ANSI SQL Isolation layers (Transaction Processing Book followup)

This paper is from Sigmod 1995. As the title says, it critiques the ANSI SQL 92 standard (book) with respect to problems in isolation layer definitions. This is also a good follow up to the Transaction Book chapter 7 where we reviewed the isolation layers. In fact, here Gray (with co-authors) gets a chance to amend the content in the Transaction Book with recent developments and better understanding/mapping of isolation layers to the degrees 0-4. Snapshot isolation (SI) finally makes its debut here in Gray's writing. Why so late? As we discussed earlier in the 80s the database keys were hot, and people rightly ignored optimistic concurrency control as it was not suitable for those workloads. Moreover, memory space was very scarce commodity, and multi-version (as in snapshot storage) was also off the table. With its increased adoption (with MySQL's use of SI around the corner) we see coverage of snapshot isolation in Gray's writing. 

The paper is very well written, and is a good read.  The lesson from the paper is clear. Scenario based descriptions lead to poor specifications! It is so easy to make omission errors. The paper tries to mend this as for ANSI SQL 92 as below. But it also uses operational/history based specifications. A much better way of doing this is to renounce operational/scenario based definitions of isolation layers, and provide state-based definitions of isolation. This was done in the "Seeing is Believing: A Client-Centric Specification of Database Isolation" (PODC 2017) paper. There was a follow up to it for providing these specifications in TLA+, which I showcased in checking isolation of a simple snapshot-isolated database model. I highly recommend checking that PODC 2017 paper. 

ANSI SQL isolation levels

ANSI SQL-92 defines four Isolation Levels (Read uncommitted, Read committed, repeatable read)  in terms of three phenomena:

• P1 (Dirty Read): Transaction T1 modifies a data item. Another transaction T2 then reads that data item before T1 performs a COMMIT or ROLLBACK. If T1 then performs a ROLLBACK, T2 has read a data item that was never committed and so never really existed.
• P2 (Non-repeatable or Fuzzy Read): Transaction T1 reads a data item. Another transaction T2 then modifies or deletes that data item and commits. If T1 then attempts to reread the data item, it receives a modified value or discovers that the data item has been deleted.
• P3 (Phantom): Transaction T1 reads a set of data items satisfying some <search condition>. Transaction T2 then creates data items that satisfy T1’s <search condition> and commits. If T1 then repeats its read with the same <search condition>, it gets a set of data items different from the first read.

There is a slight difference between phenomenon and anomaly. A phenomenon is a potential anomaly, and may lead to one. 

Wait, no mention of dirty writes in ANSI SQL 92?? This seems to be an omission failure. None of the four isolation layers ANSI SQL considers allow DirtyWrites, so DirtyWrites doesn't show up in the phenomena considered. But that is problematic as the paper shows in the coming sections. 

Locking-based isolation levels 

Defining isolation levels by phenomena (anomalies) was intended to allow non-lock-based implementations of the SQL standard. The upcoming discussion show that these phenomena and the ANSI SQL definitions fail to characterize several popular isolation levels, including the standard locking implementations of the levels.

Some basics first. A transaction has well-formed writes (reads) if it requests a Write (Read) lock on each data item or predicate before writing (reading) that data item, or set of data items defined by a predicate. A transaction has two-phase writes (reads) if it does not set a new Write (Read) lock on a data item after releasing a Write (Read) lock.

The locks requested by a transaction are of long duration if they are held until after the transaction commits or aborts. Otherwise, they are of short duration. 

The transaction book defined Degree 0 consistency to allow both dirty reads and writes: it only required action atomicity. Degrees 1, 2, and 3 correspond to Locking Read Uncommitted, Read Committed, and Serializable, respectively. No isolation degree matches the Locking REPEATABLE READ isolation level.

In terms of strength, we have: Locking Read Uncommitted < Locking Read Committed < Locking Repeatable Read < Locking Serializable

Locking isolation levels are at least as isolated as the same-named ANSI levels. Are they more isolated? The answer is yes, even at the lowest level. Locking Read Uncommitted provides long duration write locking to avoid a phenomenon called "Dirty Writes," but ANSI SQL does not exclude this anomalous behavior other than ANSI Serializable. 

• P0 (Dirty Write): Transaction T1 modifies a data item. Another transaction T2 then further modifies that data item before T1 performs a COMMIT or ROLLBACK. If T1 or T2 then performs a ROLLBACK, it is unclear what the correct data value should be.

Other Isolation Types

This section shows that a number of commercially available isolation implementations provide isolation levels that fall between Read Committed and Repeatable Read.

• P4 (Lost Update): The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits.

There is no dirty read or dirty write here, but T2's update is "lost", because T1 overlaps/covers T2 completely and overwrites T2's update. Well formed two phase locking prevents this, but of course ANSI SQL 92 standard wanted to be technique (e.g., locking) agnostic, and its anomalies/phenomenas were all defined based on reads, and ignored the even basic dirty write, let alone this lost update scenario. Scenario based descriptions lead to poor specifications! It is so easy to make omission errors. 

The Cursor Stability isolation level extends Read Committed locking behavior for SQL cursors by adding a new read action for FETCH from a cursor and requiring that a lock be held on the current item of the cursor. The lock is held until the cursor moves or is closed, possibly by a commit. Cursors are per transaction. In terms of strength, we have: Read Committed < Cursor Stability < Repeatable Read. Cursor Stability is widely implemented by SQL systems to prevent lost updates for rows read via a cursor.

In Snapshot Isolation, each transaction reads data from a snapshot of the (committed) data as of the time the transaction started, called its Start-Timestamp. This time may be any time before the transaction’s first Read. A transaction running in Snapshot Isolation is never blocked attempting a read as long as the snapshot data from its Start-Timestamp can be maintained. The transaction's writes (updates, inserts, and deletes) will also be reflected in this snapshot, to be read again if the transaction accesses (i.e., reads or updates) the data a second time. Updates by other transactions active after the transaction Start-Timestamp are invisible to the transaction. Snapshot Isolation is a type of multiversion concurrency control, and single-valued histories do not properly reflect the temporal action sequences as snapshot isolation imposes a partial order on states.

The paper then defines two more anomalies to capture these additional isolation types completely.

• A5 (Data Item Constraint Violation). Suppose C() is a database constraint between two data items x and y in the database. Here are two anomalies arising from constraint violation.
• A5A Read Skew Suppose transaction T1 reads x, and then a second transaction T2 updates x and y to new values and commits. If now T1 reads y, it may see an inconsistent state, and therefore produce an inconsistent state as output.
• A5B Write Skew Suppose T1 reads x and y, which are consistent with C(), and then a T2 reads x and y, writes x, and commits. Then T1 writes y. If there were a constraint between x and y, it might be violated.

Snapshot isolation is not vulnerable to A5A, which makes it stronger than Read Committed.

A5B write-skew can occur in Snapshot Isolation, whereas this is ruled out by RepeatableReads. On the other hand, Snapshot Isolation cannot experience the A3 subset of the P3 phantom phenomena. A transaction rereading a predicate after an update by another will always see the same old set of data items. But the Repeatable Read isolation level can experience A3 anomalies due to phantom records inserted in the absence of predicate locking. This means Repeatable Read and Snapshot Isolation are incomparable.