Concurrency Control (2PL and Timestamp Ordering)

Why control concurrency?

A busy database runs many transactions at once. If their reads and writes interleave freely, you get lost updates, dirty reads and other anomalies. The goal is a schedule that is conflict serializable: equivalent to running the transactions one after another. A concurrency-control protocol enforces that automatically. There are two classic families: locking (make transactions wait) and timestamps (let them run, and abort the ones that come too late).

Locks

Requested ↓ / Held →	none	S (shared)	X (exclusive)
S (to read)	✓ granted	✓ granted	✗ wait
X (to write)	✓ granted	✗ wait	✗ wait

Many readers may share an item, but a writer needs it alone. A transaction holding an S lock may upgrade it to X if nobody else holds the item.

Two-phase locking (2PL)

Locks alone are not enough. Unlocking too early still allows non-serializable schedules. 2PL adds one rule: once a transaction releases any lock, it may never acquire another. So each transaction has:

1. a growing phase, where it only acquires locks,
2. a shrinking phase, where it only releases them.

The moment it holds all its locks is its lock point. Every schedule 2PL allows is conflict serializable, and the equivalent serial order is the order of the lock points.

Problem 1: cascading aborts

In the Early unlock example, T1 writes A and then passes its lock point, so basic 2PL lets it unlock A before committing. T2 then reads A. If T1 aborted now, T2 would have read a value that never officially existed, and T2 would have to be rolled back too. That is a cascading abort.

Strict 2PL keeps every exclusive lock until commit or abort, so nobody ever reads uncommitted data. Rigorous 2PL keeps all locks until commit. Real databases use strict or rigorous 2PL.

Problem 2: deadlocks

In Lost update, T1 and T2 both read A (two S locks), then both want to write it. Each upgrade waits for the other’s S lock, which is a deadlock. The system detects the cycle in the wait-for graph and aborts one transaction, usually the youngest. Alternatively, it can prevent deadlocks with timestamp-based rules such as wait-die and wound-wait.

Timestamp ordering (TO)

Give every transaction a timestamp when it starts (here TS(Ti) = i, so T1 is the oldest), and require conflicting operations to happen in timestamp order. Each item X remembers RTS(X), the largest timestamp that has read it, and WTS(X), the largest that has written it.

Operation by T	Rule
read X	if TS(T) < WTS(X): abort T (a younger transaction already overwrote X). Else read, and RTS(X) = max(RTS(X), TS(T)).
write X	if TS(T) < RTS(X) or TS(T) < WTS(X): abort T. Else write, and WTS(X) = TS(T).

Nobody ever waits, so there are no deadlocks. But an old transaction that arrives late is aborted and restarted with a new timestamp. In Lost update, T2 has read A (RTS = 2) when T1 tries to write it, so T1 is aborted, not T2 as under 2PL.

Thomas’s write rule: if TS(T) < WTS(X) but TS(T) ≥ RTS(X), the write is obsolete: a younger transaction has already overwritten X and nobody read the old value in between. So ignore the write instead of aborting. See the Late write example.

Side by side

	2PL / strict 2PL	Timestamp ordering
Conflicts are handled by	waiting	aborting and restarting
Deadlocks	possible, must be detected or prevented	impossible
Equivalent serial order	order of lock points	order of timestamps
Used in	most SQL databases (often together with MVCC)	some distributed and multiversion systems

Code

import re

def is_two_phase(schedule):
    """True if no transaction locks anything after it has unlocked something.
    S1(A) = shared lock, X1(A) = exclusive lock, U1(A) = unlock."""
    released = set()
    for kind, t, x in re.findall(r'([SXU])(\d)\((\w)\)', schedule):
        if kind == 'U':
            released.add(t)
        elif t in released:
            return False
    return True

def timestamp_order(schedule, thomas=False):
    """Basic timestamp ordering. Ti has timestamp i (T1 is the oldest)."""
    rts, wts, aborted, log = {}, {}, set(), []
    for kind, t, x in re.findall(r'([RW])(\d)\((\w)\)', schedule):
        t = int(t)
        if t in aborted:
            continue
        if kind == 'R':
            if t < wts.get(x, 0):                 # a younger txn already wrote x
                aborted.add(t); log.append(f'abort T{t}'); continue
            rts[x] = max(rts.get(x, 0), t)
        else:
            if t < rts.get(x, 0):                 # a younger txn already read x
                aborted.add(t); log.append(f'abort T{t}'); continue
            if t < wts.get(x, 0):                 # a younger txn already wrote x
                if thomas:
                    log.append(f'ignore W{t}({x})'); continue
                aborted.add(t); log.append(f'abort T{t}'); continue
            wts[x] = t
        log.append(f'{kind}{t}({x})')
    return log

print(is_two_phase('S1(A) X1(B) U1(A) U1(B)'))   # True
print(is_two_phase('S1(A) U1(A) X1(B) U1(B)'))   # False
print(timestamp_order('R1(A) R2(A) W1(A) W2(A)'))
# ['R1(A)', 'R2(A)', 'abort T1', 'W2(A)']
print(timestamp_order('R1(A) W2(A) W1(A)', thomas=True))
# ['R1(A)', 'W2(A)', 'ignore W1(A)']

Common mistakes

• Thinking 2PL prevents deadlocks. It doesn’t. Strict 2PL doesn’t either.
• Confusing “two-phase” with “lock everything at the start”. That is conservative 2PL, which does avoid deadlocks but needs to know every item in advance.
• Thinking basic 2PL avoids dirty reads. Only strict (or rigorous) 2PL does.
• Getting the timestamp comparison backwards. An operation is rejected when it comes from an older transaction (smaller timestamp) than one that has already touched the item.
• Applying Thomas’s rule to reads. It only ever skips obsolete writes.