Transactions: ACID, serialisability and two-phase locking
ACID properties, concurrency anomalies, the conflict graph with proof, two-phase locking proved, deadlock, isolation levels and MVCC, logging and recovery after a failure.
A bank transfer takes money from one account and adds it to another: if the system stops halfway, or if two transfers on the same account interleave, money can vanish or multiply. Transactions are the mechanism by which a DBMS guarantees this does not happen, even with thousands of simultaneous users and with failures. In this lesson we look at the ACID properties, concurrency anomalies, serialisability and the conflict graph with the proof of the fundamental theorem, two-phase locking with the proof that it guarantees serialisability, deadlock, isolation levels and recovery after a failure.
The ACID properties
A transaction is a sequence of operations treated as a unit, ending with a COMMIT or a ROLLBACK. It must guarantee:
- atomicity: either all operations take effect, or none does;
- consistency: starting from a state that satisfies the constraints, it reaches a state that satisfies them;
- isolation: each transaction behaves as if it were alone, without seeing the partial results of others;
- durability: once committed, the transaction survives any later failure.
Concurrency anomalies
Executing transactions one at a time would be correct but too slow. Interleaving them freely gives rise to anomalies:
- lost update: two transactions read the same balance of 100, each adds 10 and writes 110: the result should be 120;
- dirty read: a transaction reads data written by another that is then rolled back, i.e. a value that never existed;
- non-repeatable read: reading the same data twice gives different values, because another transaction modified it in between;
- phantoms: re-running a query, new rows inserted by others appear.
Serialisability
A schedule is an interleaving of the operations of several transactions. It is serial if the transactions are executed one after the other, and serialisable if it produces the same effect as a serial schedule. Two operations of different transactions are in conflict if they concern the same data item and at least one is a write: their order matters. A schedule is conflict-serialisable if it can be turned into a serial one by swapping adjacent non-conflicting operations.
The conflict graph has a node for every transaction and an edge 
if an operation of 
precedes a conflicting operation of 
.
Theorem. A schedule is conflict-serialisable if and only if its conflict graph is acyclic.
Proof. *If there is a cycle* 
, in any equivalent serial schedule (which must preserve the order of every pair of conflicting operations) 
would have to precede 
, precede 
, and so on until precedes itself: impossible. *If the graph is acyclic*, it admits a topological order: an order of the transactions in which every edge goes from a transaction to a later one. The serial schedule in that order preserves the order of all conflicting pairs, because every conflict is an edge and the edges respect the order; non-conflicting operations can be reordered freely. So the schedule is equivalent to the serial one. ∎
Two-phase locking
DBMSs do not build the graph after the fact: they use a protocol that guarantees serialisability by construction. Every transaction must obtain a lock on a data item before using it: shared to read (several transactions can read together), exclusive to write. The two-phase locking protocol (2PL) requires every transaction to acquire all the locks it needs before releasing any: there is a growing phase and a shrinking phase, separated by the lock point.
Theorem. Every schedule produced by transactions that obey two-phase locking is conflict-serialisable.
Proof. If the graph has an edge , there is a data item 
on which an operation of precedes a conflicting operation of . The two operations require incompatible locks on , so obtained the lock after released it. releases only after its own lock point, and acquires only before its own: so the lock point of precedes that of . A cycle in the graph would require the lock point of to precede itself. The graph is acyclic, and by the previous theorem the schedule is serialisable. ∎
In the strict version, used in practice, exclusive locks are held until COMMIT: so nobody reads data of transactions that might be rolled back, and dirty reads are avoided.
Deadlock
With locks it can happen that waits for an item locked by and for an item locked by : a deadlock. The DBMS detects it by looking for cycles in the wait-for graph and resolves it by rolling back one of the transactions, which the application will have to retry. That is why a well-written application retries transactions rolled back because of deadlock, and accesses data always in the same order to make deadlocks rare.
Isolation levels
Serialisability costs waiting. SQL provides four isolation levels, allowing progressively fewer anomalies: *read uncommitted*, *read committed* (the default in many systems, which avoids dirty reads), *repeatable read* and *serializable*. Many modern DBMSs use multiversion concurrency control (MVCC): writes create new versions of the data, and every transaction reads a consistent snapshot taken at its start, so reads never block writes and vice versa.
Recovery
For atomicity and durability the DBMS writes every change to a log on stable storage before applying it to the data (write-ahead logging): with the old value and the new one. After a failure, at restart it reads the log: it redoes the changes of committed transactions that might not have reached the data, and undoes those of uncommitted transactions. Periodically it writes a checkpoint so as not to have to reread the log from the beginning. A transaction’s COMMIT is complete when its record is in the log, even if the actual data is still in memory: this is what makes a fast and safe commit possible.
