First we’ll discuss 3 more isolation anomalies proposed by Generalized Isolation Level Definitions, Adya et al (2000).
There’s a pre-requisite to understanding new anomalies proposed by this paper: first we’ll have to understand Direct Serialization Graphs (DSG).
We define the direct serialization graph arising from a history H, denoted by DSG(H), as follows:
Each node in the graph corresponds to a committed transaction and directed edges correspond to different types of direct conflicts. There is a read/write/anti-dependency edge from transaction T1 to transaction T2 if T1 directly read/write/anti-depends on T2.
WW - Write-Write conflicts
- two transactions overwrite the same row
- T1 directly write-write conflicts with T2 if T2’s write on some row ‘x’ in overwritten by a write by T1 on the same row.
- here, T2 directly write-write conflicts on T1.
example:
update tbl set value = 1 where id = 1; -- W1(x)
update tbl set value = 2 where id = 1; -- W2(x)WR - Write-Read conflicts
- T2 directly item read depends with T1 if T1’s write on some row ‘x’ is read by T2.
- here, T2 directly write-write conflicts on T1.
example:
update tbl set value = 1 where id = 1; -- W1(x)
select * from tbl where id = 1; -- R2(x)RW - Anti-dependency Conflicts
-
T2 directly item anti-depends on T1 if T1 reads some row ‘x’ & then T2 writes to ‘x’.
select * from tbl where id = 1; — Ri(x) update tbl set value = 1 where id = 1; — Wj(x)
Definitions of direct conflicts between transactions
The paper now defines some isolation levels:
1. Isolation Level PL-1
PL-1 is defined as the level in which G0 is disallowed:
G0: Write Cycles
A history H exhibits phenomenon G0 if DSG(H) contains a directed cycle consisting entirely of write-dependency edges.
2. Isolation Level PL-2
Isolation level PL-2 is defined as one in which phenomenon G1 is disallowed
G1a: Aborted Reads
T2 reads some object (including via predicates reads) modified by T1, and T1 aborts. To prevent aborted reads, if T2 reads from T1 and T1 aborts, T2 must also abort – known as a cascading abort.
G1b: Intermediate Reads
T2 reads a version of some object (including via predicate reads) modified by T1, and it was not T1’s final modification of that object. To prevent intermediate reads, transactions can only be allowed to commit if they have read the final versions of objects from other transactions.
G1c: Circular Information Flow
The Direct Serialization Graph contains a directed cycle consisting entirely of (read and write) dependency edges. If T1 is affected by T2, then there is no path by which T2 can also affect T1.
3. Isolation Level PL-3
PL-3 is defined as an isolation level that disallows G1 and G2.
G2: Anti-dependency Cycles.
A history H exhibits phenomenon G2 if DSG(H) contains a directed cycle with one or more anti-dependency edges.
G2-item: Item Anti-dependency Cycles
A history H exhibits phenomenon G2-item if DSG(H) contains a directed cycle having one or more item-antidependency edges.
The following two anomalies came from Peter Bailis et al: “Highly Available Transactions: Virtues and Limitations (Extended Version),” (2014)
Observed Transaction Vanishes (OTV)
A history H exhibits phenomenon OTV if USG(H) contains a directed cycle consisting of exactly one read-dependency edge by x from Tj to Ti and a set of edges by y containing at least one anti-dependency edge from Ti to Tj and Tj ’s read from y precedes its read from x.
Predicate-Many-Preceders (PMP)
A history H exhibits phenomenon PMP if, for all predicate-based reads ri(Pi ∶ V set(Pi)) and rj (Pj ∶ V set(Pj ) in Tk such that the logical ranges of Pi and Pj overlap (call it Po), the set of transactions that change the matches of Po for ri and rj differ.