Concurrency Control Algorithms

What actually happens

Two-phase locking, then deadlock

sequenceDiagram
    autonumber
    participant A as Txn A
    participant L as Lock manager
    participant B as Txn B

    A->>L: X lock row 42 (growing)
    B->>L: X lock row 42
    L-->>B: Wait
    A->>L: COMMIT, release (shrinking)
    L-->>B: Grant X
    B->>L: COMMIT, release

flowchart LR
    A[Txn A holds 42, waits 7]
    B[Txn B holds 7, waits 42]
    A -->|wait-for| B
    B -->|wait-for| A

Strict 2PL holds X locks until commit so aborted writes cannot become other people's reads. Conservative 2PL grabs everything at start (rare in SQL; closer to some stored-procedure designs). The lock manager stores a lock mode per resource and a wait queue. Compatibility: S with S is fine; S with X is not.

Compatibility (same resource):

           requested S    requested X
  held S     yes            no
  held X     no             no

Intention (granularity):
  IS  I will take S on a child (row)
  IX  I will take X on a child
  SIX table is S for me, and I will X some rows

  Table X is incompatible with IS/IX/S/X of others.
  That is how ALTER TABLE waits out row workers.

Granularity, gap locks, and escalation

Fine locks raise concurrency and lock-table RAM. Coarse locks are cheap to track and brutal under mixed workloads. Predicate and gap (next-key) locks close the hole where an insert would create a phantom—the mechanism behind some Repeatable Read engines, discussed as a user-visible anomaly in the isolation note.

Intention locks are the bookkeeping that lets row X and table S coexist safely. Skip them in a homemade lock manager and you will either scan all child locks on every table request or take table locks for everything.

Deadlocks: detect, timeout, or prevent

MVCC as a version scheduler

The isolation note explains what a snapshot means to the user. Mechanism view: each row version carries a creator id and a retire id (or an undo pointer to the previous image). A reader's snapshot is a cut in transaction-id space: versions committed before the cut are visible; in-progress creators are not. Writers typically still take a short exclusive lock or use first-updater-wins so two updaters do not install two “latest” versions.

Visibility sketch (append-only tuples):

  snapshot = {xmin, xmax, active_xids}
  version visible if
    creator committed before snapshot
    and not retired before snapshot
    and creator not in active_xids

  Reader never waits for writer's X — it sees the old version.
  Writer vs writer: still a conflict on the live key.

Costs the isolation note only sketches:
  - old versions live until the oldest snapshot releases them
  - freeze / wraparound / undo exhaustion are scheduler debts
  - indexes may point at many versions of one key

Optimistic validation and timestamp order

flowchart TB
    R[Read phase: copy versions, no row X locks]
    V{Validate write set vs committed writers}
    W[Write phase: install versions]
    AB[Abort and retry]
    R --> V
    V -->|no conflict| W
    V -->|conflict| AB
    AB --> R

Classic OCC (Kung–Robinson): read phase, validate phase, write phase. Validation checks that the read set is unchanged and that write sets of overlapping committed transactions do not intersect in a way that breaks serial order. HTTP If-Match / version columns are the same idea in APIs. SSI is OCC sitting on MVCC snapshots: the dangerous pattern is often a read-write antidependency cycle, aborted at commit instead of locked up front.

timestamp ordering assigns each transaction a time and rejects operations that arrive “too late” for that time. The Thomas write rule lets a late write be ignored if a later timestamp already overwrote the item—another optimistic flavour. These schedulers shine when conflicts are sparse. On a single popular seat they become retry storms, which is why production systems hybridize: MVCC for reads, locks or compare-and-set for hot writes.

UPDATE seats
SET holder = $user, version = version + 1
WHERE id = $seat AND version = $seen AND holder IS NULL;

0 rows → someone else won; reread and decide.
This is OCC without a full validator: the predicate is the validate phase.

Worked example: last seat, three mechanisms

Two checkouts, one seat. Isolation note: this is lost update / write skew depending on the SQL shape. Mechanism note: pick the scheduler and predict waits versus aborts.

2PL:
  A: X lock seat, set holder=A
  B: waits
  A: COMMIT
  B: wakes, sees taken, returns sold-out
  User-visible: latency spike on B, no retry logic required

OCC / version column:
  A and B both read version=1, empty
  A: UPDATE ... version=1 → 1 row, COMMIT
  B: UPDATE ... version=1 → 0 rows → retry or fail
  User-visible: B aborts fast; retry may lose again under load

MVCC snapshot + write conflict:
  Both read old version (available)
  First writer installs new version
  Second writer hits cannot-serialize or lock wait
    depending on isolation and engine
  User-visible: mix of snapshot reads and a write-write rule

Distributed lock without fence:
  A holds Redis key 30s, GC pause 35s
  B takes lock after TTL, writes
  A wakes and also writes  → split brain
  Fix: fencing token checked by the storage that accepts writes

Distributed locks, leases, and fencing

A TTL in a cache is not a lock. Pause, GC, and network delay all let two holders believe they are exclusive. A fencing token (or epoch, or lock generation) must be stored with every write the lock was meant to protect, and the store must reject stale generations. Chubby, ZooKeeper, and etcd-style systems pair leases with session liveness. If you cannot put the token in the write path, you do not have mutual exclusion—you have a best-effort hint.

Trade-offs to weigh

Choosing and explaining concurrency control

Wrap-up