Transactions, concurrency and recovery

A database is shared by many users at once and runs on machines that crash. Two clerks register students at the same moment; a payment moves money between two accounts just as the power fails. A DBMS promises that, despite concurrency and failures, each unit of work either happens completely or not at all, and that concurrent work does not corrupt the data. The unit of work is the transaction, and this lesson explains the guarantees transactions provide, the anomalies that arise when they interleave, how locking and multiversion concurrency control prevent those anomalies, the isolation levels that let applications trade safety for speed, and how write-ahead logging makes committed work survive crashes.

Transactions and the ACID properties

A transaction is a sequence of reads and writes that forms one logical unit, such as 'enroll student 104 in section 2', which might check capacity, insert an enrollment and update a seat count. In SQL a transaction starts with BEGIN (or implicitly with the first statement) and ends with COMMIT, which makes its changes permanent, or ROLLBACK, which undoes them. The guarantees are summarized by the acronym ACID.

import sqlite3

con = sqlite3.connect(":memory:", isolation_level=None)       # manage transactions explicitly
con.execute("CREATE TABLE account (id TEXT PRIMARY KEY, balance INTEGER CHECK (balance >= 0))")
con.execute("INSERT INTO account VALUES ('A', 300), ('B', 100)")

def transfer(src, dst, amount):
    try:
        con.execute("BEGIN")
        con.execute("UPDATE account SET balance = balance + ? WHERE id = ?", (amount, dst))
        con.execute("UPDATE account SET balance = balance - ? WHERE id = ?", (amount, src))
        con.execute("COMMIT")
        return "committed"
    except sqlite3.IntegrityError as e:
        con.execute("ROLLBACK")                                 # undo the credit already applied
        return f"rolled back ({e})"

print(transfer("A", "B", 200), dict(con.execute("SELECT id, balance FROM account")))
print(transfer("A", "B", 500), dict(con.execute("SELECT id, balance FROM account")))

committed {'A': 100, 'B': 300}
rolled back (CHECK constraint failed: balance >= 0) {'A': 100, 'B': 300}

In the failed transfer the credit to B succeeded before the debit from A violated the CHECK constraint. Without a transaction, B would keep $500 that never left A. Rolling back restores both balances exactly. The same mechanism handles a crash: on restart, the DBMS rolls back every transaction that had not committed. Consistency is partly the DBMS's job, through constraints, and partly the application's, since no constraint can know that a transfer should debit as much as it credits.

Why concurrency causes problems

Running transactions one after another, serially, would avoid every interference problem, but would waste the machine: while one transaction waits for a page from storage or for the user, others could run. So DBMSs interleave the operations of concurrent transactions. A schedule is the sequence of their reads and writes as actually executed. Some interleavings are harmless; others produce results no serial order could, called anomalies.

Serializability

The standard of correctness for concurrent execution is serializability: a schedule is correct if its effect is the same as that of some serial schedule of the same transactions. Two operations conflict if they belong to different transactions, access the same item, and at least one is a write. A schedule is conflict-serializable if it can be turned into a serial schedule by swapping adjacent non-conflicting operations. There is a simple test: draw a precedence graph with a node per transaction and an edge from Ti to Tj whenever an operation of Ti conflicts with a later operation of Tj. The schedule is conflict-serializable exactly when the graph has no cycle, and a topological order of the graph gives an equivalent serial order.

def precedence_edges(schedule):
    """schedule: list of (txn, op, item), op in {'R', 'W'}."""
    edges = set()
    for i, (ti, opi, xi) in enumerate(schedule):
        for tj, opj, xj in schedule[i + 1:]:
            if ti != tj and xi == xj and "W" in (opi, opj):
                edges.add((ti, tj))
    return edges

def has_cycle(edges):
    graph = {}
    for a, b in edges:
        graph.setdefault(a, set()).add(b)
    state = {}
    def visit(n):
        state[n] = "active"
        for m in graph.get(n, ()):
            if state.get(m) == "active" or (m not in state and visit(m)):
                return True
        state[n] = "done"
        return False
    return any(n not in state and visit(n) for n in list(graph))

lost_update = [("T1", "R", "seats"), ("T2", "R", "seats"), ("T1", "W", "seats"), ("T2", "W", "seats")]
fine        = [("T1", "R", "A"), ("T1", "W", "A"), ("T2", "R", "A"), ("T1", "R", "B"), ("T2", "W", "A")]
for name, s in (("lost update", lost_update), ("fine", fine)):
    e = precedence_edges(s)
    print(f"{name:11s} edges {sorted(e)} -> serializable: {not has_cycle(e)}")

lost update edges [('T1', 'T2'), ('T2', 'T1')] -> serializable: False
fine        edges [('T1', 'T2')] -> serializable: True

In the lost-update schedule, T1's read precedes T2's write (edge T1 to T2) and T2's read precedes T1's write (edge T2 to T1), forming a cycle, so no serial order explains it. The second schedule's only conflicts run from T1 to T2, so it is equivalent to running T1 then T2. A DBMS does not draw graphs at run time; instead it uses protocols that guarantee only serializable schedules can occur.

Locking and two-phase locking

The classic protocol uses locks. Before reading an item a transaction acquires a shared (S) lock, which other readers may also hold; before writing it acquires an exclusive (X) lock, which no one else may hold. A transaction that requests a conflicting lock waits. Locks alone are not enough: a transaction that released a lock and later acquired another could still interleave badly. Two-phase locking (2PL) adds the rule that a transaction has a growing phase in which it acquires locks and a shrinking phase in which it releases them, and never acquires a lock after releasing one. 2PL guarantees conflict-serializable schedules. Strict 2PL, used in practice, holds exclusive locks until commit, which also prevents dirty reads and makes rollback safe.

Locking can deadlock: T1 holds a lock on A and waits for B while T2 holds B and waits for A. Neither can proceed. DBMSs detect deadlocks by looking for cycles in a waits-for graph, or by timeouts, and resolve them by aborting one transaction, the victim, which the application should retry. Locks also have a granularity: locking whole tables is simple but limits concurrency; locking rows allows more concurrency at the cost of managing many locks. Phantoms need more than row locks, because the rows that would cause them do not exist yet; systems use predicate or index-range (next-key) locks for that.

Multiversion concurrency control

Most modern systems, including PostgreSQL, Oracle, MySQL's InnoDB, MariaDB and SQLite in its write-ahead-log mode, use multiversion concurrency control (MVCC). Instead of overwriting a row in place, a write creates a new version, and old versions are kept for a while. Each transaction reads from a consistent snapshot: the versions committed as of the moment it started (or, at some isolation levels, as of each statement). The great benefit is that readers never block writers and writers never block readers. Writers still conflict with each other: when two transactions update the same row, one must wait or be aborted. Old versions are later removed by garbage collection, which PostgreSQL calls vacuuming.

import os, sqlite3, tempfile

path = os.path.join(tempfile.mkdtemp(), "demo.db")
setup = sqlite3.connect(path, isolation_level=None)
setup.execute("PRAGMA journal_mode = WAL")           # enable multiversion reads
setup.execute("CREATE TABLE section (sec_id INTEGER PRIMARY KEY, seats_left INTEGER)")
setup.execute("INSERT INTO section VALUES (2, 5)")

reader = sqlite3.connect(path, isolation_level=None)
writer = sqlite3.connect(path, isolation_level=None, timeout=0)

reader.execute("BEGIN")
print("reader sees:", reader.execute("SELECT seats_left FROM section").fetchone()[0])
writer.execute("UPDATE section SET seats_left = 4 WHERE sec_id = 2")       # autocommits
print("writer committed 4; reader still sees:",
      reader.execute("SELECT seats_left FROM section").fetchone()[0])     # its snapshot
reader.execute("COMMIT")
print("new transaction sees:", reader.execute("SELECT seats_left FROM section").fetchone()[0])

# Two writers: SQLite allows one writer at a time
w1 = sqlite3.connect(path, isolation_level=None, timeout=0)
w1.execute("BEGIN IMMEDIATE")                       # take the write lock now
try:
    writer.execute("BEGIN IMMEDIATE")
except sqlite3.OperationalError as e:
    print("second writer:", e)
w1.execute("ROLLBACK")

reader sees: 5
writer committed 4; reader still sees: 5
new transaction sees: 4
second writer: database is locked

The reader's transaction kept seeing 5 after the writer committed 4, because it reads from the snapshot taken when it first read; a repeatable read with no locks. A new transaction sees 4. SQLite permits only one writer at a time for the whole database, and the second writer, configured not to wait, is refused at once. Server systems lock individual rows and allow many concurrent writers, but the principle is the same: conflicting writes are serialized.

Isolation levels

Full serializability can cost throughput, so SQL defines weaker isolation levels that allow some anomalies. The standard's four levels are defined by which of dirty reads, non-repeatable reads and phantoms they permit. Real systems implement them differently, and their defaults vary, which matters when an application moves between systems.

Snapshot isolation, which many systems use for REPEATABLE READ, prevents the three classic anomalies but still allows write skew, the subtle anomaly in which two transactions each check a condition on data the other then changes. PostgreSQL's SERIALIZABLE level detects such dangerous patterns and aborts one transaction (serializable snapshot isolation). The practical advice: know your system's default, use SERIALIZABLE or explicit locking (SELECT ... FOR UPDATE in most servers) for operations whose correctness depends on what was read, such as allocating the last seat, and write applications to retry transactions that are aborted because of conflicts or deadlocks.

Recovery and write-ahead logging

Durability and atomicity across crashes come from the log. Before a change is written to a data page on storage, a log record describing it, with the old and new values, is written to the log, an append-only file: write-ahead logging (WAL). At commit, the DBMS forces the log records of the transaction to stable storage, typically with an fsync call, and only then reports success. Data pages themselves can be written later, lazily, which is efficient because many changes to a hot page are absorbed in memory.

After a crash the DBMS replays the log. Redo reapplies the changes of committed transactions whose pages may not have reached storage. Undo reverses the changes of transactions that had not committed but whose pages may have been written. The widely used ARIES algorithm, developed at IBM around 1992, does this in three passes: analysis, redo and undo. Checkpoints, which periodically record which pages are dirty and which transactions are active, bound how much of the log must be replayed. SQLite's rollback journal and WAL modes are simpler versions of the same ideas.

# A toy redo/undo recovery over a log of (txn, kind, item, old, new)
log = [
    ("T1", "begin",  None, None, None),
    ("T1", "update", "A", 300, 100),
    ("T2", "begin",  None, None, None),
    ("T2", "update", "B", 100, 900),
    ("T1", "commit", None, None, None),
    # -- crash here: T2 never committed
]
disk = {"A": 300, "B": 900}          # page with B happened to be flushed; page with A did not

committed = {t for t, k, *_ in log if k == "commit"}
for t, k, item, old, new in log:                       # redo pass (forward)
    if k == "update" and t in committed:
        disk[item] = new
for t, k, item, old, new in reversed(log):             # undo pass (backward)
    if k == "update" and t not in committed:
        disk[item] = old
print("committed:", sorted(committed), " recovered state:", disk)

committed: ['T1']  recovered state: {'A': 100, 'B': 100}

Durability also depends on hardware and configuration. A disk that acknowledges writes it has only cached, or a database configured to skip fsync for speed (SQLite's PRAGMA synchronous = OFF, PostgreSQL's fsync = off), can lose committed transactions in a power failure. Backups and replication protect against losing the device entirely; the log, archived continuously, also enables point-in-time recovery to the moment before an accidental DELETE.