Concurrency Control and Recovery

The previous lesson defined which schedules are correct. A concurrency control protocol makes sure that only such schedules happen, without checking precedence graphs at run time.

Locks

Before using an item, a transaction must lock it:

• Shared lock (S): needed to read. Many transactions can hold S on the same item.
• Exclusive lock (X): needed to write. Only one transaction can hold it, and no one else can hold S at the same time.

Locking alone does not guarantee serializability: if T1 unlocks A too early, T2 can change A and T1 can see an inconsistent mix.

Two-phase locking (2PL)

A transaction follows 2PL if all its lock requests come before all its unlocks. It has two phases:

• 2PL guarantees conflict serializability. The equivalent serial order is the order of the transactions' lock points.
• 2PL does not prevent deadlocks: T1 holds X(A) and wants B while T2 holds X(B) and wants A.
• Basic 2PL does not prevent cascading rollbacks: T1 can release X(A) in its shrinking phase, T2 reads A, and then T1 aborts.

The variants fix the second problem:

Most real databases use strict 2PL.

Deadlocks

A deadlock is detected with a wait-for graph (an edge Ti → Tj when Ti waits for a lock held by Tj): a cycle means deadlock, and one transaction in the cycle (the victim) is aborted.

Deadlocks can also be prevented using transaction timestamps (an older transaction has a smaller timestamp). When Ti requests a lock held by Tj:

In both schemes the older transaction is never aborted on behalf of a younger one, and a restarted transaction keeps its original timestamp, so it eventually becomes the oldest and cannot starve. Waits only ever go in one direction of age, so no cycle can form.

Timestamp ordering

The timestamp-ordering (TO) protocol uses no locks. Each transaction T gets a timestamp TS(T) when it starts, and the schedule must be equivalent to the serial order of timestamps. For every item X the system keeps:

• RTS(X): the largest timestamp of a transaction that read X,
• WTS(X): the largest timestamp of a transaction that wrote X.

Thomas write rule: in the last case, the write is obsolete (a younger write has already replaced it, and nobody read our value), so instead of aborting T the write is simply ignored. This accepts some schedules that are view serializable but not conflict serializable.

TO guarantees conflict serializability and freedom from deadlock (nobody waits), but can starve long transactions and does not by itself ensure recoverable schedules.

A simulation of the protocol makes the rules concrete. TS(T1) = 10, TS(T2) = 20, TS(T3) = 30:

def timestamp_ordering(schedule, ts, thomas=False):
    rts, wts, aborted = {}, {}, set()
    for op in schedule.split():
        kind, t, x = op[0], int(op[1]), op[3]
        if t in aborted:
            continue
        if kind == "R":
            if ts[t] < wts.get(x, 0):
                aborted.add(t); print(op, "-> abort T%d (younger write exists)" % t)
            else:
                rts[x] = max(rts.get(x, 0), ts[t]); print(op, "-> ok")
        elif ts[t] < rts.get(x, 0):
            aborted.add(t); print(op, "-> abort T%d (younger read exists)" % t)
        elif ts[t] < wts.get(x, 0):
            if thomas:
                print(op, "-> ignored (Thomas write rule)")
            else:
                aborted.add(t); print(op, "-> abort T%d (younger write exists)" % t)
        else:
            wts[x] = ts[t]; print(op, "-> ok")
    return aborted

ts = {1: 10, 2: 20, 3: 30}
print("aborted:", timestamp_ordering("R1(A) R2(A) W2(A) W1(A) R3(B) W1(B)", ts))
print()
print("aborted:", timestamp_ordering("R2(B) W3(B) W2(B)", ts, thomas=True))

R1(A) -> ok
R2(A) -> ok
W2(A) -> ok
W1(A) -> abort T1 (younger read exists)
R3(B) -> ok
aborted: {1}

R2(B) -> ok
W3(B) -> ok
W2(B) -> ignored (Thomas write rule)
aborted: set()

In the first schedule, W1(A) fails because T2 (younger) has already read A, so T1 is aborted and its later W1(B) is skipped. In the second, W2(B) is obsolete because T3 already wrote B, and nobody read T2's value; the Thomas write rule ignores it instead of aborting T2.

Log-based recovery

To provide atomicity and durability, the DBMS writes a log of every change before the change reaches the disk (write-ahead logging, WAL). A log record looks like <T1, A, 500, 400>: T1 changed A from 500 (old value, for undo) to 400 (new value, for redo). <T1 start>, <T1 commit> and <T1 abort> mark the transaction boundaries.

After a crash, with immediate update (changes may reach the disk before commit):

• Redo every transaction whose <commit> is in the log (its changes may not have reached the disk).
• Undo every transaction that has a <start> but no <commit> or <abort> (its partial changes may have reached the disk). Undo goes backwards through the log.

A checkpoint writes all modified pages to disk and records <checkpoint L>, where L lists the active transactions. Recovery then only needs to look back to the last checkpoint: a transaction that committed before the checkpoint needs nothing.

Example log, crash after the last line:

<T1 start>
<T1, A, 100, 150>
<T2 start>
<T1 commit>
<checkpoint {T2}>
<T3 start>
<T2, B, 200, 250>
<T3, C, 300, 350>
<T3 commit>
<T4 start>
<T4, D, 400, 450>

T1 committed before the checkpoint, so it is ignored. T3 committed after it, so redo T3. T2 and T4 never committed, so undo T2 and T4: B goes back to 200 and D to 400.

Practice questions