Two-Phase Locking (2PL): Pessimistic Concurrency and Conflict Serializability

In relational database transactions, executing concurrent operations without isolation leads to classical concurrency anomalies: dirty reads, non-repeatable reads, and lost updates. While Multi-Version Concurrency Control (MVCC) offers optimistic or snapshot-based isolation, pessimistic concurrency engines enforce strict mathematical **Conflict Serializability** by acquiring shared and exclusive locks on data resources.

Simply acquiring and releasing locks arbitrarily during transaction execution does not guarantee serializability. Formulated by Kenneth P. Eswaran, Jim Gray, Raymond Lorie, and Irving Traiger in 1976, the **Two-Phase Locking (2PL)** protocol defines strict phase-ordering constraints on lock acquisitions and releases to guarantee that all concurrent transaction schedules are equivalent to a serial execution schedule.

The 2PL Invariant & Architectural Variants

Under basic 2PL, every transaction executes in two distinct, non-overlapping phases:

1. Growing (Expanding) Phase: The transaction may acquire new locks (Shared or Exclusive) and upgrade Shared locks to Exclusive. It is strictly forbidden from releasing any locks during this phase.
2. Lock Point: The exact instant when the transaction acquires its final lock, representing the transaction's logical serialization order.
3. Shrinking (Contracting) Phase: The transaction may release acquired locks or downgrade Exclusive locks to Shared. It is strictly forbidden from acquiring any new locks once the first lock is released.

Variants: Strict 2PL (S2PL) vs. Rigorous 2PL (SS2PL)

• Basic 2PL: Releases locks during the shrinking phase before commit. While serializable, it is vulnerable to **Cascading Aborts**: if Transaction A modifies an item, releases its lock, and then aborts, any Transaction B that read the uncommitted modification must also be forcibly aborted.
• Strict 2PL (S2PL): Enforces that all **Exclusive (X)** write locks must be held until the transaction finishes (Commit or Abort). Eliminates cascading aborts and guarantees Recoverable schedules.
• Rigorous / Strong Strict 2PL (SS2PL): Enforces that **all locks (both Shared S and Exclusive X)** must be held until the transaction terminates. Execution schedule order precisely matches the commit order.

Multiple Granularity Locking & Intent Locks

Databases organize data hierarchically: Database $\rightarrow$ Table $\rightarrow$ Page $\rightarrow$ Row (Tuple). Locking an entire table with an Exclusive lock to modify one row destroys concurrency; conversely, checking every row lock before granting a table lock is $O(N)$.

Engines resolve this using **Intent Locks** on ancestor nodes before locking child nodes:

• Intent Shared (IS): Indicates an intention to acquire Shared (S) locks on descendants.
• Intent Exclusive (IX): Indicates an intention to acquire Exclusive (X) locks on descendants.
• Shared with Intent Exclusive (SIX): Holds a Shared lock on the current node (e.g., reading an entire table) while concurrently modifying individual child rows with IX/X locks.

Lock Compatibility Matrix

IS and IX locks are mutually compatible with other intention locks, allowing concurrent transactions to lock different rows inside the same table simultaneously without conflict.

Deadlock Resolution: Detection vs. Prevention

Because 2PL transactions hold locks while waiting for other locks, cyclic wait dependencies create **Deadlocks** (where Transaction A waits for Transaction B while Transaction B waits for Transaction A).

1. Deadlock Detection: Wait-For Graphs (WFG)

A background lock manager thread maintains a directed graph where nodes are active transactions and directed edges $T_1 \rightarrow T_2$ indicate $T_1$ is waiting for a lock held by $T_2$. The engine periodically runs cycle-detection algorithms (Tarjan's strongly connected components or DFS) to detect cycles and aborts the lowest-cost 'victim' transaction.

2. Deadlock Prevention: Timestamp-Based Priority Rules

Assigns unique physical or logical timestamps $TS(T)$ when transactions start (older transactions have smaller timestamps and higher priority):

• Wait-Die (Non-preemptive): If an older transaction $T_{old}$ requests a lock held by a younger $T_{young}$, $T_{old}$ is allowed to wait. If $T_{young}$ requests a lock held by $T_{old}$, $T_{young}$ is immediately aborted ('dies') and restarted.
• Wound-Wait (Preemptive): If an older transaction $T_{old}$ requests a lock held by $T_{young}$, $T_{old}$ preempts ('wounds') $T_{young}$, forcing $T_{young}$ to abort and surrender the lock. If $T_{young}$ requests a lock held by $T_{old}$, $T_{young}$ is allowed to wait.

C++ Conceptual Simulation Blueprint (Lock Manager & Wait-For Graph)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

class LockManager {
private:
    // Transaction Wait-For Graph: TxnId -> Set of TxnIds it is waiting for
    std::unordered_map<uint32_t, std::unordered_set<uint32_t>> waitForGraph;

    bool hasCycleDFS(uint32_t node, std::unordered_set<uint32_t>& visited,
                     std::unordered_set<uint32_t>& inStack) {
        visited.insert(node);
        inStack.insert(node);

        if (waitForGraph.count(node)) {
            for (uint32_t neighbor : waitForGraph[node]) {
                if (!visited.count(neighbor)) {
                    if (hasCycleDFS(neighbor, visited, inStack)) return true;
                } else if (inStack.count(neighbor)) {
                    return true; // Cycle detected
                }
            }
        }
        inStack.erase(node);
        return false;
    }

public:
    void addDependency(uint32_t waitingTxn, uint32_t holdingTxn) {
        waitForGraph[waitingTxn].insert(holdingTxn);
    }

    void removeTransaction(uint32_t txnId) {
        waitForGraph.erase(txnId);
        for (auto& [k, v] : waitForGraph) {
            v.erase(txnId);
        }
    }

    bool detectDeadlock() {
        std::unordered_set<uint32_t> visited;
        std::unordered_set<uint32_t> inStack;

        for (const auto& [node, _] : waitForGraph) {
            if (!visited.count(node)) {
                if (hasCycleDFS(node, visited, inStack)) {
                    return true;
                }
            }
        }
        return false;
    }
};

Real-World Database Systems & Concurrency Engines

1. MySQL InnoDB Engine: Implements Strict 2PL for explicit locking queries (`SELECT ... FOR UPDATE` and `LOCK IN SHARE MODE`) and runs background deadlock detection workers to roll back the transaction modifying the fewest rows.
2. PostgreSQL Lock Manager: Manages coarse and fine-grained table and row lock queues, falling back to a `deadlock_timeout` timer (default 1s) to trigger Wait-For Graph cycle detection only when contention occurs.
3. Google Spanner: Combines Wound-Wait deadlock prevention with Paxos replicated state machines and TrueTime to coordinate cross-node distributed 2PL locks without deadlock detection stalls.
4. Microsoft SQL Server: Implements dynamic lock escalation (automatically converting thousands of individual row locks into a single table lock when memory thresholds are exceeded).