Reliable Storage - Operating Systems: Principles and Practice - page 414

Relaxing Isolation
In this topic we focus on the strong and relatively simple isolation requirement of se-
rializability: no matter how much concurrency there is, the system must ensure that the
results of any execution of the program is equivalent to an execution in which transac-
tions are processed one at a time in some sequence. However, strong isolation require-
ments sometimes force transactions to block (e.g., when waiting to acquire locks) or
roll back (e.g., when fixing a deadlock or encountering a “late write” under multiversion
concurrency control).
Relaxing the isolation requirement can allow effectively higher levels of concurrency
by reducing the number of cases in which transactions must block or roll back. The cost,
of course, is potentially increased complexity in reasoning about concurrent programs,
but several relaxed isolation semantics have proven to be sufficiently strong to be widely
used.
For example, snapshot isolation requires each transaction's reads appear to come
from a snapshot of the system's committed data taken when the transaction starts. Each
transaction is buffered until the transaction commits, at which point the system checks
all of the transaction's updates for write-write conflicts. A write-write conflict occurs if
transaction T reads an object o from a snapshot at time t start and tries to commit at
time t commit but some other transaction T 0 commits an update to o between T's read at
t start and T's attempted commit at t commit . If a write-write conflict is detected for any
object being committed by T, T is rolled back.
Snapshot isolation is weaker than serializability because each transaction's reads
logically happen at one time and its writes logically happen at another time. This split
allows, for example, write skew anomolies where one transaction reads object x and
updates object y and a concurrent transaction reads object y and updates object x. If
there is some constraint between x and y, it may now be violated. For example, if x and
y represent the number of hours two managers have assigned you to work on each of
two tasks with a constraint that x + y 40. Manager 1 could read x = 15 and y = 15,
attempt to assign 10 more hours of work on task x, and verify that x+y = 25 + 15 40.
In the mean time manager 2 could read x = 15 and y = 15, attempt to assign 10 more
hours of work on task y, verify that that x + y = 15 + 25 40, and successfully commit
the update, setting y = 25. Finally, manager 1 could successfully commit its update,
setting x = 25 and ruining your weekend.