Isolation levels, deadlocks, and recovery
Real databases offer a range of isolation levels, must detect deadlocks, and recover from crashes using logs. Together these make ACID practical.
SQL isolation levels
The SQL standard defines four levels. Read uncommitted allows dirty reads. Read committed prevents dirty reads but allows non-repeatable reads and phantoms. Repeatable read also prevents non-repeatable reads. Serializable prevents all these anomalies. PostgreSQL and Oracle default to read committed; MySQL's InnoDB defaults to repeatable read.
Multiversion concurrency control
Most modern databases use multiversion concurrency control (MVCC): writers create new versions of rows instead of overwriting them, and each transaction reads a consistent snapshot of the data as of its start or statement. Readers never block writers and writers never block readers. Old versions are cleaned up later, as by PostgreSQL's VACUUM.
Snapshot isolation and write skew
Snapshot isolation, provided by MVCC, prevents dirty and non-repeatable reads but allows write skew: two doctors each check that at least one other doctor is on call, both see two on call, and both go off call, leaving none. PostgreSQL's serializable level uses serializable snapshot isolation (SSI), detecting such dangerous patterns and aborting one transaction.
Deadlocks
A deadlock occurs when transactions wait for each other's locks in a cycle: T1 holds A and wants B; T2 holds B and wants A. Databases detect deadlocks by finding cycles in a waits-for graph and abort one victim transaction, which the application should retry. Accessing tables and rows in a consistent order reduces deadlocks.
Write-ahead logging
Durability and atomicity rely on the write-ahead log (WAL): before a change to a data page reaches storage, a log record describing it is written to the log, and a transaction commits only once its commit record is safely on stable storage. Because the log is written sequentially, it is fast, and data pages can be flushed later at convenient times.
Crash recovery
After a crash, the database replays the log. The ARIES algorithm, developed at IBM by C. Mohan and colleagues around 1992, works in three phases: analysis (find which transactions were active and which pages were dirty), redo (repeat history, reapplying logged changes), and undo (roll back transactions that had not committed). Checkpoints limit how much log must be replayed.
Backups and point-in-time recovery
Logs also support backups: a full backup plus archived WAL lets administrators restore the database to any moment, such as just before an accidental DELETE, called point-in-time recovery. Replicas fed by the log can take over if the primary fails. Backups must be tested by actually restoring them; an untested backup is only a hope.
Worked example
Under read committed, a transaction runs SELECT SUM(balance) twice while another transaction commits a transfer between the two reads; the sums may differ, a non-repeatable read at the aggregate level. Under repeatable read in PostgreSQL, both reads use the same snapshot and return the same sum. Under serializable, any interleaving that could not occur serially causes one transaction to fail with a serialisation error to retry.
Key takeaways
SQL defines read uncommitted, read committed, repeatable read, and serializable levels, preventing progressively more anomalies; PostgreSQL defaults to read committed and InnoDB to repeatable read. MVCC keeps row versions so readers and writers do not block each other. Snapshot isolation allows write skew; serializable snapshot isolation detects it. Deadlocks are cycles in the waits-for graph, broken by aborting a victim. Write-ahead logging records changes before pages are written and makes commits durable. ARIES recovery runs analysis, redo, and undo, with checkpoints. Archived logs enable point-in-time recovery and replication; test backups.
Flashcard
Allows dirty reads
Check your understanding
Why does write-ahead logging let a database acknowledge a commit before writing changed data pages?