Two-Phase Locking (2PL), Timestamp Ordering & Write-Ahead Logging

Testing precedence graphs after the fact is impossible in real database servers: an engine cannot wait for a day of transactions to run and then check if a cycle occurred. Instead, database engines use concurrency protocols (like 2PL) that guarantee serializability proactively.

Concurrency control protocols ensure that interleaved executions are guaranteed to produce conflict serializable schedules on the fly. Meanwhile, the Crash Recovery Subsystem guarantees that if the server loses power during a write operation, the database can reconstruct committed states and roll back half-finished transactions.

The 2PL Rule: A transaction must acquire all its locks before releasing any lock. It consists of two phases:

1. Growing Phase: Locks may be acquired, but NO locks can be released.

2. Lock Point: The exact moment when the transaction acquires its final lock.

3. Shrinking Phase: Locks may be released, but NO new locks can be acquired.

The 4 Major Variants of 2PL:

• Basic 2PL: Follows the 2 phases. Guarantees conflict serializability, but can suffer from deadlocks and cascading aborts.

• Conservative 2PL (Static 2PL): Transaction locks ALL needed items before execution begins. If any item is unavailable, it waits without locking anything. Guarantees Deadlock-Free execution, but reduces concurrency.

• Strict 2PL: Transaction holds all its Exclusive (X) write locks until after it commits or aborts. Guarantees Cascadelessness and Strict Recoverability! (Does NOT prevent deadlock).

• Rigorous 2PL: Transaction holds ALL locks (Shared and Exclusive) until after commit. Guarantees that the serialization order matches the exact commit order.

Assign each transaction T_i a unique timestamp TS(T_i) based on start time. Older transactions have smaller timestamps (TS(T_old) < TS(T_young)).

1. Wait-Die Scheme (Non-preemptive):

When T_i requests a lock held by T_j:

• If T_i is older (TS(T_i) < TS(T_j)): T_i is allowed to WAIT.

• If T_i is younger (TS(T_i) > TS(T_j)): T_i is killed (DIES) and restarts with its original timestamp.

Mnemonic: The old wait; the young die.

2. Wound-Wait Scheme (Preemptive):

When T_i requests a lock held by T_j:

• If T_i is older (TS(T_i) < TS(T_j)): T_i preempts (WOUNDS) T_j, forcing T_j to abort and release its lock.

• If T_i is younger (TS(T_i) > TS(T_j)): T_i is allowed to WAIT.

Mnemonic: The old wound the young; the young wait.

Result: Both schemes guarantee Deadlock Freedom because wait edges can only flow in one direction in the timestamp timeline!

The Write-Ahead Logging (WAL) Protocol:

1. Before any data page is written to disk, its corresponding log record (containing old value and new value) must be flushed to persistent disk log storage.

2. A transaction cannot be acknowledged as committed until its log record has been safely flushed to disk.

Checkpointing & The Undo/Redo Algorithm:

To avoid scanning the log back to the beginning of time upon reboot, the DBMS periodically writes a Checkpoint:

1. Flushes all dirty buffer pool pages to disk.

2. Writes a log entry and flushes the log.

Recovery on Restart:

• REDO List: Transactions that wrote into the log before crash. Their updates are reapplied to disk to guarantee Durability.

• UNDO List: Transactions that started () but never committed before the crash. Their partial writes are rolled back using the log's before-image to guarantee Atomicity.