Concurrency Control

A transaction is a sequence of database operations (reads and writes) that the database treats as a single logical unit. The ACID properties define what the database promises:

• Atomicity: Either all operations in the transaction commit or none do. If the server crashes mid-transaction, the partial work is rolled back.
• Consistency: A transaction takes the database from one valid state to another. Constraints (foreign keys, CHECK constraints) are checked at commit.
• Isolation: Concurrent transactions appear to execute serially — each transaction is isolated from the intermediate states of others.
• Durability: Once committed, the results survive crashes (via write-ahead logging).

This module is almost entirely about Isolation. The others (especially Atomicity and Durability) are handled by the recovery subsystem, which is a separate story.

The key abstraction is a schedule: an interleaving of the operations of multiple transactions. If T1 has operations R(A), W(A) and T2 has R(A), W(A), one possible schedule is: T1:R(A), T2:R(A), T1:W(A), T2:W(A). Whether this schedule is safe depends on what the operations do and in what order — this is exactly what serializability theory analyzes.

-- Classic bank transfer: must be atomic and isolated
BEGIN;
  SELECT balance FROM accounts WHERE id = 'alice';  -- R(alice)
  SELECT balance FROM accounts WHERE id = 'bob';    -- R(bob)
  UPDATE accounts SET balance = balance - 100 WHERE id = 'alice';  -- W(alice)
  UPDATE accounts SET balance = balance + 100 WHERE id = 'bob';    -- W(bob)
COMMIT;

Without isolation, concurrent transactions can interfere in well-defined ways. Each anomaly has a name and a precise definition:

Dirty Read: T1 reads a value written by T2 that T2 has not yet committed. If T2 aborts, T1 has read data that never existed.

Lost Update: T1 and T2 both read the same value, both modify it, and both write back. T1's write is overwritten by T2's write — T1's update is lost. Classic example: two threads both doing balance += 100 where the DB value was 500. Both read 500, both write 600. The balance should be 700.

Non-repeatable Read: T1 reads a value, T2 updates it and commits, T1 reads it again — and sees a different value within the same transaction.

Phantom Read: T1 executes a range query (e.g., SELECT * WHERE salary > 100K). T2 inserts a new row that matches that predicate and commits. T1 re-executes the same query and sees a new row that wasn't there before — a 'phantom'.

Write Skew: A subtle anomaly only visible at higher isolation levels. T1 reads set A, T2 reads set B. Both make a decision based on what they read, and write to disjoint items. Neither overwrites the other, but the combination of their writes violates a constraint. Example: two doctors both check on_call_count >= 2 is true before taking themselves off call. Both see count=2, both write count=1, and now no doctor is on call.

Each isolation level is defined by which of these anomalies it permits. Understanding the anomalies is more fundamental than memorizing isolation level names.

-- Lost Update scenario (pseudocode)
-- T1 and T2 both execute concurrently:

-- T1:                        -- T2:
R(X)  -- reads X=500          R(X)  -- reads X=500
                               W(X=600)  -- writes 600
                               COMMIT
W(X=600)  -- still writes 600 (not 700!)
COMMIT
-- Final X=600, should be 700. T1's +100 is lost.

A schedule is serializable if its outcome (the final database state and the values returned by reads) is equivalent to the outcome of some serial execution of those transactions. There are two flavors:

Conflict Serializability (the practical one): Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write. A schedule is conflict-serializable if its conflict order (the order of conflicting pairs) is consistent with some serial order.

To check conflict serializability, draw the serialization graph (also called the precedence graph):

• One node per transaction.
• Draw an edge Ti → Tj if Ti has an operation that conflicts with a later operation of Tj.
• The schedule is conflict-serializable if and only if this graph is acyclic.

View Serializability is strictly weaker — it requires only that each read sees the same value as in some serial schedule, even if the conflict order differs. View serializability is NP-hard to check and is rarely used in practice.

Why does an acyclic precedence graph mean serializable? Because any topological sort of the graph gives you a valid serial order. If there is a cycle, no serial order exists that respects all the conflict orderings — the schedule is not serializable.

Example: T1: R(A), W(B) and T2: R(B), W(A). Schedule: T1:R(A), T2:R(B), T2:W(A), T1:W(B). Conflicts: T1:R(A) before T2:W(A) → edge T1→T2. T2:R(B) before T1:W(B) → edge T2→T1. The graph has a cycle T1→T2→T1. Not serializable.

# Precedence graph cycle detection
def is_conflict_serializable(schedule, transactions):
    """
    schedule: list of (txn_id, op_type, item)
    Returns True if the schedule is conflict-serializable.
    """
    graph = {t: set() for t in transactions}
    
    for i, (ti, op_i, item_i) in enumerate(schedule):
        for j, (tj, op_j, item_j) in enumerate(schedule):
            if j <= i: continue
            if ti == tj: continue
            if item_i != item_j: continue
            # conflict if at least one is a write
            if op_i == 'W' or op_j == 'W':
                graph[ti].add(tj)  # Ti comes before Tj
    
    # DFS cycle detection
    visited, rec_stack = set(), set()
    def has_cycle(node):
        visited.add(node); rec_stack.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if has_cycle(neighbor): return True
            elif neighbor in rec_stack:
                return True
        rec_stack.discard(node)
        return False
    
    return not any(has_cycle(t) for t in transactions if t not in visited)

Two-phase locking is the classic pessimistic protocol that guarantees conflict serializability. The rule is beautifully simple:

A transaction may not acquire any new lock after it has released a lock.

This creates two phases:

1. Growing phase: the transaction acquires locks, never releases any.
2. Shrinking phase: the transaction releases locks, never acquires any.

Why does 2PL guarantee serializability? Because the point at which a transaction releases its first lock — the lock point — creates a total order on transactions. The serialization order is the order of lock points, and 2PL ensures the conflict order respects this.

Lock types:

• Shared (S) lock: Multiple transactions can hold an S lock on the same item simultaneously. Required for reads.
• Exclusive (X) lock: Only one transaction can hold an X lock. Required for writes.
• Compatibility: S/S is compatible; S/X and X/X are not.

Variants:

• Strict 2PL: Hold all exclusive locks until commit. This prevents cascading aborts (where T1 reads T2's dirty data and must abort if T2 aborts). Most real systems use this.
• Strong Strict 2PL (SS2PL) / Rigorous 2PL: Hold ALL locks (shared and exclusive) until commit. Simpler to implement, slightly less concurrency.

The cost of 2PL is blocking: if T1 holds a lock that T2 needs, T2 waits. This is the tradeoff — pessimistic concurrency uses waiting to ensure safety.

Predicate locks (or gap locks) extend 2PL to ranges to prevent phantoms: instead of locking a single row, you lock the predicate salary > 100K. Any insert that would match the predicate blocks. This is how SQL databases prevent phantom reads under Serializable isolation.

# Simplified lock manager
from collections import defaultdict
import threading

class LockManager:
    def __init__(self):
        self.locks = defaultdict(dict)   # item -> {txn_id: mode}
        self.wait_queue = defaultdict(list)  # item -> [(txn_id, mode, event)]
        self.mutex = threading.Lock()
        self.txn_locks = defaultdict(set)  # txn_id -> {items held}

    def acquire(self, txn_id, item, mode):
        """mode: 'S' or 'X'. Blocks until lock is granted."""
        event = threading.Event()
        with self.mutex:
            if self._compatible(item, txn_id, mode):
                self.locks[item][txn_id] = mode
                self.txn_locks[txn_id].add(item)
                return  # granted immediately
            self.wait_queue[item].append((txn_id, mode, event))
        event.wait()  # block

    def release(self, txn_id, item):
        with self.mutex:
            del self.locks[item][txn_id]
            self.txn_locks[txn_id].discard(item)
            self._grant_waiting(item)

    def release_all(self, txn_id):
        """Called at commit/abort (Strict 2PL)."""
        items = list(self.txn_locks[txn_id])
        for item in items:
            self.release(txn_id, item)

    def _compatible(self, item, txn_id, mode):
        for holder, held_mode in self.locks[item].items():
            if holder == txn_id: continue
            if mode == 'X' or held_mode == 'X':
                return False
        return True

    def _grant_waiting(self, item):
        granted = []
        for waiter in self.wait_queue[item]:
            txn_id, mode, event = waiter
            if self._compatible(item, txn_id, mode):
                self.locks[item][txn_id] = mode
                self.txn_locks[txn_id].add(item)
                event.set()
                granted.append(waiter)
        for w in granted:
            self.wait_queue[item].remove(w)

2PL introduces deadlocks: T1 holds a lock on A and waits for B; T2 holds a lock on B and waits for A. Neither can proceed. The database must break the deadlock by aborting one transaction (the victim).

Detection via Wait-For Graph (WFG): The database maintains a graph where there is an edge Ti → Tj if Ti is waiting for a lock held by Tj. A cycle in this graph means deadlock. Detection runs periodically (or on every lock request). The victim is chosen by heuristics: youngest transaction, fewest locks held, cheapest to re-execute. The victim is aborted and rolled back, releasing its locks.

Prevention — Timestamp-based schemes (avoid cycles entirely):

• Wait-Die: If Ti is older than Tj (smaller timestamp), Ti waits. If Ti is younger, Ti dies (aborts). Older transactions always wait; younger ones abort and retry. The key property: the wait graph is always acyclic because edges only go from old to new.
• Wound-Wait: If Ti is older than Tj, Ti wounds (preemptively aborts) Tj. If Ti is younger, Ti waits. Older transactions preempt younger ones. Also prevents cycles.
• Both schemes guarantee that aborted transactions restart with their original timestamp, preventing starvation.

Timeout: The simplest scheme — if a transaction waits too long, abort it. Simple but can thrash under load or abort unnecessarily under a slow system.

Lock ordering: Require all transactions to acquire locks in a globally consistent order (e.g., ascending by row ID). If every transaction requests lock A before lock B, the T1-holds-A-waits-B / T2-holds-B-waits-A scenario cannot arise. This is the approach used in application-level code (e.g., always lock the lower-numbered account first in a transfer).

Deadlock vs. livelock vs. starvation: Deadlock is a mutual wait with no progress. Livelock is when transactions keep aborting and retrying without making progress (often caused by retrying immediately after abort under high contention). Starvation is when one transaction is always the victim. Timestamp-based prevention avoids starvation because a restarted transaction keeps its old timestamp and eventually becomes the oldest.

-- Prevent deadlock in application code by always locking accounts in ID order
-- Transfer from account A to account B:

CREATE OR REPLACE FUNCTION transfer(from_id INT, to_id INT, amount NUMERIC)
RETURNS VOID AS $$
DECLARE
  first_id INT := LEAST(from_id, to_id);
  second_id INT := GREATEST(from_id, to_id);
BEGIN
  -- Always lock in ascending ID order to prevent deadlock
  PERFORM pg_advisory_xact_lock(first_id);
  PERFORM pg_advisory_xact_lock(second_id);
  
  UPDATE accounts SET balance = balance - amount WHERE id = from_id;
  UPDATE accounts SET balance = balance + amount WHERE id = to_id;
END;
$$ LANGUAGE plpgsql;

The pessimistic assumption of 2PL — that conflicts are common, so acquire locks before you even try — is often wrong in practice. Many workloads are read-heavy, or transactions access disjoint data. Locking everything pessimistically serializes work that could safely run in parallel.

Optimistic Concurrency Control (Kung & Robinson 1981) takes the opposite philosophy: run freely without locks, check for conflicts at commit time, and abort and retry if there was a conflict. The three phases are:

1. Read phase: Execute the transaction, reading from the database and accumulating writes in a private workspace (not yet visible to others). Record the read set (items read) and write set (items written).

2. Validation phase: Check whether the transaction's reads are still valid. The standard check: for every transaction Tj that committed while Ti was in its read phase, ensure that Tj's write set does not intersect Ti's read set. (If it does, Ti read a stale value and must abort.)

3. Write phase: If validation passes, atomically apply the writes from the private workspace to the database and assign a commit timestamp.

Why OCC is good: No lock overhead, no blocking, no deadlocks. Reads never block writes or vice versa. Works extremely well when conflict rate is low.

Why OCC is bad: Under high contention, transactions frequently fail validation and must restart from scratch — all the work done in the read phase is wasted. If many transactions contend on the same hot item, OCC can thrash. The classic analysis: if conflict probability is p per transaction pair, and you have n transactions, expected restarts grow as O(n²p). Above a conflict rate of ~20-30%, pessimistic locking typically wins.

OCC is used in CockroachDB (optimistic reads + serial writes), in many in-memory databases (VoltDB, H-Store), and in transactional memory systems.

# Optimistic concurrency control sketch
import threading
from copy import deepcopy

class OCC_Database:
    def __init__(self, data):
        self.data = data          # committed state
        self.version = {}         # item -> commit_timestamp
        self.global_ts = 0
        self.lock = threading.Lock()

    def begin_transaction(self):
        with self.lock:
            start_ts = self.global_ts
        return {'start_ts': start_ts, 'read_set': {}, 'write_set': {}}

    def read(self, txn, key):
        # Read from committed state, record in read set
        val = self.data.get(key)
        txn['read_set'][key] = self.version.get(key, 0)
        return val

    def write(self, txn, key, value):
        txn['write_set'][key] = value  # to private workspace

    def commit(self, txn):
        with self.lock:  # serialized validation+write
            # Validation: check that read set items haven't changed
            for key, read_version in txn['read_set'].items():
                if self.version.get(key, 0) != read_version:
                    raise Exception(f"Conflict on {key}: abort and retry")
            
            # Write phase: apply writes
            self.global_ts += 1
            commit_ts = self.global_ts
            for key, value in txn['write_set'].items():
                self.data[key] = value
                self.version[key] = commit_ts
            return commit_ts

MVCC is the dominant approach in modern relational databases (PostgreSQL, MySQL InnoDB, Oracle, SQL Server, CockroachDB). Its key insight: instead of overwriting data, keep multiple versions of each tuple, each tagged with the transaction timestamp that created it. Readers get a consistent snapshot of the database at a point in time and never block.

Core mechanics:

• Every row has a xmin (transaction ID that created this version) and xmax (transaction ID that deleted/updated it, or infinity if still current).
• When T1 begins, it records the current transaction counter as its snapshot timestamp.
• Reads: T1 sees the version of each row where xmin <= T1.snapshot < xmax. This is the most recent committed version as of T1's start.
• Writes: T1 creates a new version of the row with xmin = T1.id and marks the old version with xmax = T1.id.
• Readers never block writers; writers never block readers. Writers may still block other writers on the same rows (via row-level locks in PostgreSQL).

Snapshot Isolation (SI): The isolation level that MVCC naturally provides. Each transaction sees a consistent snapshot of the database at its start time. It prevents dirty reads, lost updates (in most implementations), and non-repeatable reads. However, it does not prevent write skew — the subtle anomaly where two transactions both read overlapping data and write disjoint items in a way that violates a constraint.

Serializable Snapshot Isolation (SSI): PostgreSQL 9.1+ implements SSI (Cahill et al. 2008), which detects dangerous write skew patterns at commit time using a technique based on anti-dependency tracking. SSI gives full serializability with MVCC's read performance, at the cost of some additional bookkeeping and occasional false-positive aborts.

Garbage collection: Old versions must eventually be purged. In PostgreSQL this is the job of VACUUM. Long-running transactions that hold an old snapshot prevent GC and can cause table bloat — a common production operational issue.

Practical tip: In PostgreSQL, REPEATABLE READ uses SI; SERIALIZABLE uses SSI. MySQL InnoDB uses a similar MVCC model but implements REPEATABLE READ differently (with gap locks to prevent some phantoms). Oracle and SQL Server's SNAPSHOT isolation mode also use MVCC.

-- PostgreSQL: observe MVCC snapshot isolation in action
-- Session 1:
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM orders;  -- sees 100 rows

-- Session 2 (concurrent):
BEGIN;
INSERT INTO orders VALUES (101, 'new order');
COMMIT;

-- Back in Session 1:
SELECT count(*) FROM orders;  -- still sees 100! (snapshot from BEGIN)
COMMIT;

-- Under READ COMMITTED, Session 1 would see 101 on the second SELECT.
-- Under REPEATABLE READ / SNAPSHOT, it sees its start-of-transaction snapshot.

-- Inspect row versions in PostgreSQL:
SELECT xmin, xmax, ctid, * FROM orders WHERE id = 42;

The SQL standard (SQL-92 and later) defines four isolation levels in terms of which anomalies they permit. From weakest to strongest:

The catch: The SQL-92 specification defines these levels in terms of anomaly prevention, but real databases implement them differently. The same level name can mean something slightly different across databases:

• PostgreSQL READ COMMITTED: Each statement sees a fresh snapshot. Most common default. Fast, but each statement in a transaction may see different data.
• PostgreSQL REPEATABLE READ: Snapshot Isolation. The whole transaction sees a consistent snapshot. Prevents phantoms (unlike the standard's definition) but allows write skew.
• PostgreSQL SERIALIZABLE: SSI. Full serializability. May abort with ERROR: could not serialize access due to read/write dependencies among transactions.
• MySQL InnoDB REPEATABLE READ (default): Uses MVCC for reads + gap locks for writes. Prevents most phantoms. Not full SI.
• Oracle: Only offers READ COMMITTED and SERIALIZABLE (which is actually Snapshot Isolation, not serializable — a famous gap between standard and implementation).

Practical guidance:

• Use READ COMMITTED for most OLTP work where transactions are short and the application handles re-reads.
• Use REPEATABLE READ or SERIALIZABLE for transactions that make decisions based on what they read (e.g., the on-call doctor write skew scenario).
• For financial transactions involving constraints across rows (like the double-spend problem), SERIALIZABLE (or explicit SELECT FOR UPDATE) is necessary.
• Never assume the SQL standard definition maps exactly to the database's behavior — always check the docs for your specific system.

-- Demonstrate write skew (requires SERIALIZABLE to prevent)
-- Two doctors checking on-call coverage

-- T1 (doctor Alice):
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM on_call WHERE shift = 'tonight';  -- sees 2
-- Since count >= 2, safe to go off-call
UPDATE on_call SET doctor = NULL WHERE doctor = 'alice' AND shift = 'tonight';
COMMIT;

-- T2 (doctor Bob, running concurrently with T1):
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM on_call WHERE shift = 'tonight';  -- also sees 2!
-- Also thinks it's safe
UPDATE on_call SET doctor = NULL WHERE doctor = 'bob' AND shift = 'tonight';
COMMIT;
-- Now nobody is on call! Write skew.

-- Fix: use SERIALIZABLE, or use SELECT FOR UPDATE to lock the rows read:
BEGIN;
SELECT count(*) FROM on_call WHERE shift = 'tonight' FOR UPDATE;
-- ...now T2 must wait until T1 commits

So far we have talked about locking individual items (rows, pages, or values). But what is the right granularity? Locking a whole table is coarse (safe but kills concurrency). Locking individual rows is fine-grained (maximum concurrency but enormous lock table overhead for scans). Real databases use a lock hierarchy: database → table → page → row.

Intention locks solve the problem of efficiently checking whether a coarser-level lock is compatible with a request. Before acquiring a fine-grained lock, a transaction acquires an intention lock on each ancestor in the hierarchy:

• IS (Intention Shared): Intent to place S locks on descendants.
• IX (Intention Exclusive): Intent to place X locks on descendants.
• SIX (Shared + Intention Exclusive): Hold an S lock on this node and intent to place X locks on some descendants. Used for operations that read all rows but update some.

The compatibility matrix for intention locks is: IS/IS, IS/S, IS/IX, IX/IX are compatible; S/IX, SIX/SIX, SIX/IX, X/anything are not (except X/nothing).

How it works: To lock row R in table T with an X lock, a transaction first acquires IX on T (and IX on the page). Now if another transaction tries to acquire S on the whole table T, it sees the IX lock on T and knows it conflicts — without having to check every row.

Lock escalation: When a transaction holds too many fine-grained locks (high memory pressure), the lock manager may escalate them to a coarser level (e.g., promote 1000 row locks to a single table lock). This reduces memory but reduces concurrency and can cause unexpected blocking.

Understanding lock granularity is essential for diagnosing production bottlenecks — a full-table lock from an unindexed UPDATE can serialize an entire application.

-- Observe lock types in PostgreSQL
-- In one session:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- PostgreSQL now holds: RowExclusiveLock on the TABLE (intention lock),
-- and a tuple-level lock on row id=1

-- In another session:
SELECT pid, relation::regclass, mode, granted
FROM pg_locks
JOIN pg_stat_activity USING (pid)
WHERE relation = 'accounts'::regclass;

-- You'll see: RowExclusiveLock granted=true for the first session
-- An ALTER TABLE ... would request AccessExclusiveLock and be blocked

Even if a schedule is serializable, it may still be unrecoverable: a transaction Tj reads a value written by Ti, Tj commits, and then Ti aborts. Now Tj has committed based on data that never officially existed. The database cannot undo Tj without violating durability.

A schedule is recoverable if: whenever Tj reads from Ti, Ti commits before Tj commits. This ensures that if Ti aborts, Tj has not yet committed and can also be aborted.

Cascading aborts occur when T1 aborts, and T2 (which read T1's dirty data) must also abort, and T3 (which read T2's dirty data) must also abort. The cascade can propagate through many transactions. This is expensive and complex.

Cascadeless schedules prevent this: a transaction may only read committed data. If you can only read committed values, aborting one transaction never forces another to abort.

Strict schedules go further: a transaction may not read or overwrite a data item written by another transaction until that transaction commits or aborts. This makes recovery trivially simple — you can restore the database to its pre-transaction state by restoring old values from the log.

Strict 2PL (hold X locks until commit) produces strict schedules. This is why virtually all production databases use Strict 2PL rather than plain 2PL — it makes the ARIES recovery protocol practical.

Hierarchy of increasing safety: serializable ⊂ recoverable ⊂ avoids-cascading-aborts (cascadeless) ⊂ strict.

-- Unrecoverable schedule (BAD -- never happens in any real DB with strict 2PL):
-- T1: W(A=5)              
-- T2:         R(A)  -> reads 5 (dirty read from T1)
-- T2:              COMMIT  -> T2 committed!
-- T1:                   ABORT -> T1 aborted, but T2 already read it. UNRECOVERABLE.

-- Strict 2PL prevents this: T1 holds X lock on A until abort.
-- T2 cannot read A until T1 releases its lock (at abort).
-- After T1 aborts and releases, A is restored to its pre-T1 value.
-- T2 reads the correct (pre-T1) value of A.