Transactions §
A transaction is a logical unit of work that the database treats as all-or-nothing. Transactions guarantee that concurrent operations on shared data produce correct results, even in the presence of crashes. They are the foundation of data integrity in any multi-user system.
Authoritative sources
ACID properties §
- Atomicity: a transaction’s operations are all-or-nothing. Either all effects are visible, or none are.
- Consistency: the database moves from one valid state to another. This is ultimately an application-level property: the application defines what “consistent” means (business invariants, domain rules), and the database provides enforcement mechanisms (constraints, triggers, foreign keys) to reject transactions that would violate them.
- Isolation: concurrent transactions do not interfere; each sees a consistent snapshot.
- Durability: once committed, a transaction’s effects survive crashes and power failures.
Transaction lifecycle §
A transaction passes through a sequence of states. The lifecycle determines when atomicity and durability kick in:
- Active: the transaction is executing operations (reads, writes).
- Partially Committed: all operations have executed; the commit is in progress (WAL is being flushed to stable storage).
- Committed: the commit record is on stable storage; effects are visible to other transactions.
- Failed: an error was detected (constraint violation, system crash); the transaction cannot complete.
- Aborted: the transaction has been rolled back; all effects undone via the undo log.
- Terminated: the final state, reached after commit or after abort.
Details
Atomicity mechanism: the undo log (or rollback segment) records before-images of modified data. On abort, the undo log is applied in reverse to restore the pre-transaction state.
Durability mechanism: the WAL (Write-Ahead Log) records after-images before the data page is written to disk. On crash recovery, the WAL is replayed (redo) to re-apply committed changes, and the undo log is applied to roll back uncommitted changes.
Consistency: the application defines the invariants (e.g., “account balance ≥ 0”, “exactly one doctor on call”). The database enforces them via schema constraints (foreign keys, CHECK, NOT NULL) and triggers. If a transaction would violate a constraint, the database rejects it — but the definition of consistency belongs to the application, not the database engine.
Isolation: the strongest guarantee. Implemented via locking or MVCC (see below). The SQL standard defines four levels (see next section).
Isolation levels §
The SQL standard defines four isolation levels, weakest to strongest:
- Read Uncommitted: dirty reads possible (reading another transaction’s uncommitted data).
- Read Committed: no dirty reads; non-repeatable reads possible (re-reading a row may yield a different value).
- Repeatable Read: no non-repeatable reads; phantoms possible (a re-query may return new rows).
- Serializable: full isolation; no anomalies. Equivalent to some serial execution order.
Details
Anomalies:
- Dirty read: T1 reads a value that T2 wrote but has not yet committed. If T2 aborts, T1 read a value that never existed.
- Non-repeatable read: T1 reads a row, T2 updates and commits it, T1 re-reads and gets a different value.
- Phantom read: T1 executes a range query, T2 inserts a new row in that range and commits, T1 re-executes and sees the new row.
- Lost update: T1 and T2 both read the same row, both write, and one write is lost.
PostgreSQL: default is Read Committed. Serializable uses SSI (Serializable Snapshot Isolation), which detects conflicts at commit time and aborts the offending transaction.
MySQL InnoDB: default is Repeatable Read (stronger than the SQL standard default). Uses MVCC with next-key locking to prevent phantoms.
Trade-off: stronger isolation → more conflict detection → more aborts → lower throughput. In practice, Read Committed is the sweet spot for most OLTP workloads.
Example problem
T1 executes SELECT balance FROM accounts WHERE id = 1 (reads 500), then T2 executes UPDATE accounts SET balance = 600 WHERE id = 1 and commits. T1 then re-reads the same row.
At which isolation levels does T1 see 500 both times? At which does it see 500 then 600?
Solution
- Read Uncommitted: T1 may see 500 then 600 (or even T2’s uncommitted 600 before T2 commits).
- Read Committed: T1 sees 500 then 600 (non-repeatable read). Each read takes a fresh snapshot.
- Repeatable Read: T1 sees 500 both times. The snapshot is fixed at the first read.
- Serializable: T1 sees 500 both times (same as Repeatable Read, plus no phantoms).
The key distinction: Read Committed takes a new snapshot per statement; Repeatable Read and Serializable take a single snapshot for the whole transaction.
Concurrency control: the design space §
Concurrency control sits on a spectrum between pessimistic (locking: assume conflicts are likely, block early) and optimistic (MVCC / SSI: assume conflicts are rare, detect them late). The choice depends on the workload’s conflict rate: high-conflict workloads favour locking; low-conflict workloads favour MVCC.
MVCC §
Multi-Version Concurrency Control (MVCC): each write creates a new version of a row with a transaction ID (or timestamp). Readers see a consistent snapshot (all versions with ID ≤ their start time). Writers do not block readers.
- Read path: a reader sees the latest version with
txid ≤ reader_start_txid. - Write path: a writer creates a new version; the old version is marked dead (but not deleted until no active transaction can see it).
- Cleanup: VACUUM (PostgreSQL) or purge threads (InnoDB) remove dead versions.
Details
Why MVCC over locking? Locking (two-phase locking) blocks readers when a writer holds an exclusive lock. MVCC eliminates read-write blocking: readers always see a consistent snapshot, writers always proceed. The cost is extra storage (multiple versions) and periodic cleanup.
Snapshot isolation vs. serializability: MVCC provides snapshot isolation (each transaction sees a consistent snapshot), but snapshot isolation is not equivalent to serializability. A write skew anomaly can occur: two transactions read different rows, both pass their checks, both write, and the combined result violates a constraint. SSI (PostgreSQL) or serializable isolation (Oracle) closes this gap.
Write skew example (two doctors on call):
- Constraint: exactly one doctor must be on call at any time.
- T1 reads doctor A’s status: “not on call”. T1 writes: “A is on call”.
- T2 reads doctor B’s status: “not on call”. T2 writes: “B is on call”.
- Both transactions commit. Now two doctors are on call — the constraint is violated.
- Under serializable isolation, the database detects that T1 and T2 both read and wrote overlapping data (the “on call” invariant) and aborts one of them.
This anomaly is invisible to snapshot isolation because T1 and T2 read different rows (no read-write or write-write conflict on the same row), yet the combined effect is inconsistent.
WAL integration: in PostgreSQL, each transaction’s changes are first written to the WAL (for durability), then applied to the data pages. The WAL also records the transaction’s start and commit/abort, which MVCC uses to determine visibility.
Distributed generalization: in a distributed database, MVCC extends to multiple nodes. Linearizability (see Consensus and Consistency) replaces the single-node snapshot guarantee.
Locking §
Two-phase locking (2PL): a transaction acquires all locks before releasing any (growing phase → shrinking phase). This guarantees conflict serializability.
- Shared lock (S): for reads. Multiple transactions may hold S on the same row.
- Exclusive lock (X): for writes. Only one transaction may hold X; it conflicts with S.
- Upgrade: S → X requires first releasing S (to avoid deadlock).
- Strict 2PL: hold X locks until commit (prevents cascading aborts).
Deadlock: two or more transactions wait for each other’s locks. Detected via the wait-for graph (a cycle means deadlock). Resolution: abort one transaction (the “victim”) and let the other proceed. Alternatively, timeout-based detection.
Details
Lock granularity: row-level (fine-grained, high concurrency), page-level, table-level (coarse-grained, low overhead). Most databases use row-level locks for DML and table-level locks for DDL.
Intent locks: a table-level intent lock (IS, IX) signals that a transaction holds (or wants) row-level locks within the table. This allows the lock manager to quickly reject conflicting table-level requests without scanning all rows.
Lock coupling vs. lock cranking: in B-tree indexes, lock coupling (hold parent lock while acquiring child lock) is simpler; lock cranking (release parent before acquiring child) allows more concurrency but is more complex.
Deadlock prevention: ordering (always acquire locks in a global order) prevents deadlocks but reduces concurrency. In practice, detection + abort is preferred.
Serializability §
A schedule of concurrent transactions is serializable if it is equivalent to some serial (one-at-a-time) order.
- Conflict serializability: two operations conflict if they access the same data item and at least one is a write. The conflict graph has an edge from T1 to T2 if T1’s operation conflicts with T2’s later operation. The schedule is conflict-serializable iff the conflict graph is acyclic.
- View serializability: a weaker notion; the schedule is view-serializable if for every transaction, the reads and writes are indistinguishable from some serial order. All conflict-serializable schedules are view-serializable, but not vice versa.
Details
Testing serializability: build the conflict graph. If it has a cycle, the schedule is not conflict-serializable. Example: T1 writes A, T2 writes A, T1 reads A → cycle T1→T2→T1 → not serializable.
SSI (PostgreSQL): instead of preventing conflicts during execution, SSI lets transactions run under snapshot isolation and detects conflicts at commit time. If a conflict is detected, the transaction is aborted and retried. This is more efficient than pessimistic locking for workloads with low conflict rates.
Distributed serializability: in a multi-node system, serializability requires a global order of transactions. Achieved via consensus (Paxos, Raft) or timestamp ordering. See Consensus and Consistency.
Example problem
Consider the schedule:
- T1: W(A), R(B)
- T2: R(A), W(B)
- T1: W(B)
- T2: R(B)
Is this schedule conflict-serializable? Draw the conflict graph.
Solution
Conflicts (same data item, at least one write, in order):
- T1 W(A) before T2 R(A): edge T1→T2
- T1 R(B) before T2 W(B): edge T1→T2
- T1 W(B) before T2 R(B): edge T1→T2
All edges go T1→T2. The graph is acyclic. The schedule is conflict-serializable, equivalent to the serial order T1 then T2.
WAL and recovery §
The Write-Ahead Log (WAL) is a sequential log of all changes, written before the corresponding data page is modified on disk.
- Write rule: log record for a change must be on stable storage before the data page is written.
- Recovery: on crash, replay the WAL from the last checkpoint: redo committed transactions, undo uncommitted ones.
Details
Checkpoint: a periodic snapshot of the database state. The WAL before the checkpoint can be truncated. Recovery starts from the last checkpoint, not from the beginning of the WAL.
Group commit: multiple transactions’ log records are batched into a single disk flush, amortizing the I/O cost. This is a major throughput optimization.
WAL vs. binlog: in MySQL, the binlog (binary log) is a logical log of SQL statements or row changes, used for replication. The redo log (InnoDB) is the physical WAL, used for crash recovery. They serve different purposes.
Distributed replication: in a distributed database, the WAL is replicated to other nodes (streaming replication, quorum writes). See Fault Tolerance for the distributed replication of WAL.
VACUUM and space management §
VACUUM (PostgreSQL): removes dead tuples (versions no longer visible to any active transaction) to reclaim space. Runs in the background (autovacuum) or manually.
- InnoDB: purge threads perform the same function. Additionally, InnoDB can defragment pages (merge free space) and shrink files.
- Table bloat: if VACUUM falls behind, dead tuples accumulate and the table grows. This degrades scan performance (more pages to read) and index performance (more entries to traverse).
Details
HOT (Heap-Only Tuple) updates: if an update does not modify any indexed columns, PostgreSQL creates a new tuple in the same page and links it to the old one. The index is not updated, and VACUUM can compact the chain without touching the index.
Fill factor: a table or index can be created with a fill factor < 100%, leaving free space for future updates. This reduces page splits and index bloat at the cost of more pages.
Distributed concerns: in a sharded database, VACUUM runs independently on each shard. A long-running transaction on one shard can prevent VACUUM from cleaning up on that shard (the old version is still visible to that transaction).
Interactive simulation §
The simulation below shows two concurrent transactions interleaving on shared data items. Step through the schedule to see how lock acquisition/release (pessimistic) and MVCC version chains (optimistic) each handle the same workload.
Example problem §
Problem: Two transactions run concurrently on a bank database:
- T1: transfer $100 from account A to account B (read A, write A−100, write B+100, commit)
- T2: transfer $50 from account B to account C (read B, write B−50, write C+50, commit)
Under Read Committed isolation with MVCC, can a lost update occur? What about under Serializable?
Solution
Read Committed + MVCC:
- T1 reads B (sees version at T1’s snapshot time).
- T2 reads B (sees version at T2’s snapshot time).
- If T1 commits first, T2’s write to B is based on a stale read. T2 overwrites T1’s change → lost update.
- The lost update is caused by the lack of serializability: T2 read B before T1 committed, so T2’s write does not account for T1’s change. MVCC is the mechanism that allows this interleaving (by not blocking T2’s read), but the anomaly itself is a consequence of the non-serializable schedule, not of MVCC per se.
Serializable (SSI):
- T1 writes B. T2 also writes B. SSI detects the write-write conflict at commit time.
- T2 is aborted and retried. On retry, T2 reads the new version of B (including T1’s $100 deposit) and writes B−50 correctly.
- No lost update.
Lesson: Read Committed is sufficient for most workloads, but for financial transactions where write-write conflicts on the same row are common, Serializable (or explicit row-level locking with SELECT … FOR UPDATE) is required.