Locking, 2PL, Isolation & Deadlock

01 · Mechanism

Locks and the conflict table

The most common method in commercial systems, and the pessimistic one: assume collisions will happen, and control access to resources so they cannot.

A transaction is well-formed with respect to locking when every read is preceded by an r_lock (a shared lock) and every write by a w_lock (an exclusive lock), each eventually followed by an unlock. Unlocking may be delayed well past the end of the operation itself — and the whole of this chapter turns on how long it is delayed.

A transaction that reads an object and later writes it has two options: acquire the exclusive lock straight away at read time, or take a shared lock and later upgrade it — lock escalation.

An object is therefore in one of three states — free, r-locked (by one or more readers), or w-locked (by exactly one writer) — and the lock manager grants requests from this table:

where $n$ counts concurrent readers, incremented on each r_lock and decremented on each unlock; the object becomes free only when it reaches zero. Implementations use a hash-indexed lock table: each locked item has a linked list of nodes recording the requesting transaction, the lock mode, and whether it is granted or waiting.

Now the crucial negative result. Consider the arrival sequence r1(x) r2(x) w2(x) r1(x), executed by a scheduler that obeys the table above:

r1(x)  → r_lock granted, n=1;   T1 unlock(x) → free
r2(x)  → r_lock granted, n=1
w2(x)  → upgrade to w_lock granted
         T2 unlock(x) → free
r1(x)  → r_lock granted again

Every request was legal. Yet T1 read x twice and got two different values — a nonrepeatable read. Respecting the lock-granting table is not sufficient for serializability.

02 · Protocol

Two-phase locking

One rule, and the class of schedules it generates is serializable.

Every transaction therefore has a growing phase in which it only acquires, a plateau at its maximum lock set, and a shrinking phase in which it only releases. Consider a scheduler that processes only well-formed transactions, grants locks by the conflict table, and checks the two-phase rule: the class of schedules it produces is called 2PL, and

The proof is short and worth reproducing, because papers ask you to justify membership rather than assert it.

The lectures also give a visual test that is faster than reasoning in prose: draw resources on the vertical axis and operation times on the horizontal, mark each transaction’s first acquisition and last release per resource, and look for any transaction whose acquisitions are not all before its releases.

Which anomalies does plain 2PL stop? All of them except one:

03 · Protocol

Strict 2PL, and why write locks are held to commit

Everything so far assumed commit projection — that no transaction aborts. Drop that assumption and 2PL is not enough.

If a transaction releases its locks before it commits, another transaction can read what it wrote; should the first then roll back, the second has performed a dirty read. The fix adds one clause:

Strict-2PL locks are called long-duration locks; plain 2PL locks are short-duration. Most commercial DBMSs use strict 2PL when a high isolation level is requested. Real systems typically apply it asymmetrically — long-duration strict locks for writes, more varied policies for reads, because long-duration read locks are expensive and are often replaced by the multiversion mechanisms of chapter 7.

Why writes in particular can never be short-duration is worth deriving, since a paper asks it outright:

w1[x] … w2[x] … then (c1 or a1) and (c2 or a2) in any order

04 · SQL

Predicate locks and the SQL isolation levels

Phantom inserts need locks on rows that do not exist yet; and SQL exposes the whole spectrum of lock-duration choices as four named levels.

A phantom insert happens when a transaction adds items to a set another transaction has already read. No data lock can prevent it, because the row is not there to lock. A predicate lock extends locking to future data: for update Tab set B=1 where A>1, the lock is on the predicate A > 1, and no other transaction may insert, delete or update any tuple satisfying it. Implementations use index structures (gap locks); where predicate locks are unsupported, the lock degenerates to the whole table.

SQL:1999 defines four isolation levels, specifying which anomalies must be prevented. Note what they do not touch: a transaction always takes an exclusive lock on anything it modifies and holds it to completion — strict 2PL on writes — regardless of level. The levels only vary the protection of reads.

And the same table read as lock durations — the version worth memorising, because it explains why:

Read down the read-lock column and the anomaly table falls out: no read locks admits dirty reads; short read locks mean a value can change between two reads; long data locks fix that but leave predicates unguarded, so inserts still slip in; long predicate locks close the last gap.

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SET TRANSACTION READ ONLY;

05 · Deadlock

Deadlock: timeout, prevention, detection

Waiting is the price of locking, and waiting can become circular.

Transactions requesting a held lock are suspended and queued. Two pathologies follow:

• Deadlock — two or more transactions in endless mutual wait, each holding what another needs.
• Starvation — a single transaction waiting forever, typically a writer behind an endless stream of readers on a hot object such as an index root.

The canonical deadlock takes four operations:

T1: r1(x) w1(y)          S: r_lock1(x), r_lock2(y), r1(x), r2(y),
T2: r2(y) w2(x)              w_lock1(y) → wait,  w_lock2(x) → wait

Two representations: the lock graph is bipartite, with resources and transactions as nodes and arcs for requests and assignments; the wait-for graph keeps only transactions, with an arc $T_i \to T_j$ when $T_i$ waits for something $T_j$ holds. A deadlock is a cycle in the wait-for graph.

Three families of resolution:

The two transaction-based prevention schemes are exam vocabulary. Both compare the age of the requesting transaction (RT) with that of the conflicting holder (CT), where a lower timestamp means older, and in both the oldest transaction always survives:

A killed transaction restarts with its original timestamp, so it becomes progressively older and cannot starve.

How likely is any of this? With $n$ records and transactions making two accesses each under a uniform distribution, conflict probability is $O(1/n)$ and deadlock probability $O(1/n^2)$ — much rarer, but real: the lectures quote once a minute in a mid-sized bank. The probability is linear in the number of transactions and quadratic in their length, which is the practical argument for keeping transactions short.

06 · Deadlock

Obermarck’s distributed detection

When a transaction spans nodes, no single node can see the whole wait-for graph. Obermarck’s algorithm detects the cycle anyway, by having each node forward summaries of what it knows.

The setting: transactions run on one main node but may spawn sub-transactions elsewhere, suspending until the sub-transaction returns. So there are two kinds of waiting — $T_i$ waits for $T_j$ on the same node because of a data lock, and a sub-transaction of $T_i$ waits for another sub-transaction of $T_i$ on a different node, via an external call.

Each node records its local situation as strings of the form

E_B → T2 → T1 → E_C

read as: a remote transaction at node B is waited for by $T_2$, which waits for $T_1$ (a local data lock), which in turn waits for something at node C. The $E_X$ markers are external-call nodes.

The forwarding rule decides who tells whom, and it exists to stop every node from independently detecting the same deadlock:

The algorithm runs periodically at each node, in four steps: receive graph information from the preceding nodes; merge it into the local graph; check for cycles among transactions and, if one is found, select a transaction in it and kill it; send updated information onward, propagating news of any kill.

07 · Refinements

The update lock

One deadlock pattern is far more common than all others, and one extra lock mode removes it.

The pattern is two transactions that both read an object and then both decide to write it:

r1(x) r2(x) w1(x) w2(x)

with SL/XL only:  SL1 granted, SL2 granted, XL1 → T1 waits, XL2 → T2 waits.   Deadlock.

Each holds a shared lock the other’s upgrade is waiting on. The update lock (UL) is requested by a transaction that intends to read and later write. Its compatibility is asymmetric — it tolerates existing readers, but no second UL:

Replay the pattern with it: UL1 granted, UL2 waits immediately, XL1 granted — T1 finishes and T2 proceeds. No deadlock, and the cost is only that T2 waited a little earlier than it strictly had to. Update locks are requested through SELECT … FOR UPDATE:

START TRANSACTION;
SELECT * FROM t WHERE i = 2 FOR UPDATE;             -- rows write-locked until commit
SELECT * FROM t WHERE i = 2 FOR UPDATE NOWAIT;      -- error instead of waiting
SELECT * FROM t FOR UPDATE SKIP LOCKED;             -- skip rows locked by others

NOWAIT executes a command only if it does not run into a conflict; SKIP LOCKED returns only the unclaimed rows — the standard trick for queue tables, where avoiding conflict matters more than seeing every row.

08 · Refinements

Hierarchical (intention) locking

Update locks prudently extend the interval a resource is locked. Hierarchical locking answers the other question: locking what?

Locking a whole table destroys concurrency; locking single tuples means an enormous number of locks and slow conflict detection. So resources form a hierarchy — schema, table, fragment, page, tuple, field — and the objectives are to lock the minimum amount of data while recognising conflicts as early as possible.

The protocol has two halves:

• Requests go top-down, from the root toward the granule you actually want.
• Releases go bottom-up.

Beyond SL and XL, three modes declare intent at the coarser levels:

• ISL — intention to lock a sub-element in shared mode.
• IXL — intention to lock a sub-element in exclusive mode.
• SIXL — lock this element in shared mode and intend to lock a sub-element exclusively (SL + IXL).

The rules for descending: to request SL or ISL on a non-root element you must already hold ISL or IXL on its parent; to request IXL, XL or SIXL you must already hold SIXL or IXL on the parent. And the granting table:

Reading it pays off: ISL conflicts only with XL, so many readers can descend in parallel; XL conflicts with everything, so an exclusive lock high in the tree blocks all traffic beneath it.