Two-Phase Locking (2PL) & Deadlock Resolution: Shared vs Exclusive Lock Mechanics

At 02:00 AM on Black Friday, your payments database crashes with error 1213 (40001): Deadlock found when trying to get lock; try restarting transaction.

Application logs reveal two microservices updating balances concurrently:

Service A locks User Account #100 and tries to acquire a lock on User Account #200.
Service B locks User Account #200 and tries to acquire a lock on User Account #100.

Both execution threads freeze. Neither service can proceed. System memory spikes as thread queues fill up, database connection pools exhaust, and transactions fail across the entire system.

How do databases maintain concurrency safety while preventing threads from getting stuck in mutual locking loops?

To answer this, we must explore Two-Phase Locking (2PL) and the Deadlock Engine inside relational storage systems.

Lock Types and Hierarchy

Before an engine can read or update a row in memory, it must acquire permission via a Lock Object.

Database locks operate at two structural granularity levels:

Row-level locks: Protect individual tuple rows inside index pages.
Table-level intent locks: Signal intent to lock rows at a finer level, preventing coarse table DDL operations from altering the table schema while background threads update rows.

Fundamental Lock Modes

Shared Lock (S): Acquired when reading data. Multiple transactions can hold S locks on the exact same row simultaneously.
Exclusive Lock (X): Acquired when modifying data (UPDATE, DELETE, INSERT). Only one transaction can hold an X lock on a row. Blocks all other S and X requests.
Intent Shared (IS): Set at the table level before acquiring S locks on specific internal rows.
Intent Exclusive (IX): Set at the table level before acquiring X locks on specific internal rows.

The Lock Compatibility Matrix

When Transaction 2 requests a lock on an object already held by Transaction 1, the engine checks a lock compatibility matrix:

Held \ Requested	Intent Shared (`IS`)	Intent Exclusive (`IX`)	Shared (`S`)	Exclusive (`X`)
Intent Shared (`IS`)	Compatible	Compatible	Compatible	Blocked
Intent Exclusive (`IX`)	Compatible	Compatible	Blocked	Blocked
Shared (`S`)	Compatible	Blocked	Compatible	Blocked
Exclusive (`X`)	Blocked	Blocked	Blocked	Blocked

Two-Phase Locking (2PL) Protocol

Using locks alone is not enough to guarantee isolation. If a transaction releases a lock mid-execution and acquires another lock later, interleaving operations from other transactions can produce corrupted history schedules.

To prevent schedule corruption, database engines enforce the Two-Phase Locking (2PL) protocol.

The Two Phases

Growing Phase: The transaction may acquire new locks, but is forbidden from releasing any lock.
Shrinking Phase: The transaction may release existing locks, but is forbidden from acquiring any new locks.

Lock Count
  ^
  |          /-------------\
  |         /               \      (Shrinking Phase: Releasing locks)
  |        /                 \
  |       /                   \
  |      / (Growing Phase:     \
  |     /   Acquiring locks)    \
  +----+-------------------------+------------------> Time
     BEGIN                       COMMIT / END

Strict 2PL (S2PL) vs Rigorous 2PL

Basic 2PL: Locks are released gradually during the shrinking phase. Allows cascading rollbacks if an uncommitted modified row read by another transaction is rolled back.
Strict 2PL (S2PL): Exclusive X locks must be held until the transaction explicitly commits or rolls back. Prevents cascading aborts.
Rigorous 2PL: All locks (S and X) are held until the exact COMMIT or ROLLBACK signal. This is what most production engines implement.

The Deadlock Problem

While Strict 2PL guarantees serializable isolation, it introduces Deadlocks.

A deadlock occurs when two or more transactions hold locks on resources the other transactions need to complete, creating a cyclic dependency graph.

Interleaved Deadlock Timeline

Time   Transaction 1                           Transaction 2
--------------------------------------------------------------------------------------
T1     BEGIN;                                  BEGIN;
T2     UPDATE accounts SET balance = 500       
       WHERE id = 1;                           
       -- Holds Exclusive Lock X(Row 1)
T3                                             UPDATE accounts SET balance = 700 
                                               WHERE id = 2;
                                               -- Holds Exclusive Lock X(Row 2)
T4     UPDATE accounts SET balance = 500       
       WHERE id = 2;                           
       -- T1 blocks! Waiting for X(Row 2)...
T5                                             UPDATE accounts SET balance = 700 
                                               WHERE id = 1;
                                               -- T2 blocks! Waiting for X(Row 1)...
T6     *** DEADLOCK DETECTED ***               *** BLOCKED ***

Deadlock Resolution Mechanisms

Modern database engines employ two complementary strategies to handle deadlocks:

1. Lock Wait Timeout (`innodb_lock_wait_timeout`)

The simplest fallback. If a transaction thread remains blocked waiting for a lock longer than a configured threshold (e.g., 50 seconds in MySQL), the engine cancels the blocked SQL statement and throws a timeout error:

ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

Problem: Timeout values are coarse. Setting them too short aborts valid long-running queries; setting them too long freezes application connections for nearly a minute.

2. Wait-For Graph (WFG) Cycle Detection

Instead of waiting for timeouts, engines run a dynamic background thread that constructs a directed graph of transaction lock dependencies.

Nodes: Active database transactions ( $T_1, T_2, T_3 \dots$ ).
Edges: A directed edge $T_1 \to T_2$ exists if $T_1$ is waiting for a lock currently held by $T_2$ .

       +-------+  Waiting for Row 2  +-------+
       |  T1   | ------------------> |  T2   |
       +-------+                     +-------+
           ^                             |
           |     Waiting for Row 1       |
           +-----------------------------+

The engine periodically runs Tarjan’s or DFS cycle-finding algorithms on the Wait-For Graph:

If a cycle $T_1 \to T_2 \to T_1$ is detected, a deadlock exists.
The engine must select one transaction as a Victim and issue an immediate ROLLBACK.
The remaining non-victim transaction acquires the freed lock and completes work.

How Engines Pick the Victim Transaction

InnoDB selects the victim transaction based on Rollback Cost Heuristics:

The engine calculates the total weight of each transaction in the cycle.
Weight calculation: The number of modified rows (Undo Log records written) + locks held.
The transaction with the smallest undo footprint is chosen as the victim and aborted. This minimizes disk I/O cost during the rollback.

Best Practices for Deadlock Prevention

Consistent Locking Order: Ensure all application code accesses multiple rows in identical primary key order (e.g., always sort account IDs WHERE id IN (1, 2) numerically before updating).
Keep Transactions Short: Perform network RPC calls, image processing, or heavy CPU parsing outside active database transaction blocks.
Use Lower Isolation Levels with MVCC: Use snapshot reads (REPEATABLE READ or READ COMMITTED) to eliminate S lock wait overheads for read queries.

Summary & Next Steps

Two-Phase Locking enforces transactional safety by separating lock acquisition from lock release:

Strict 2PL holds exclusive locks until COMMIT to prevent cascading aborts.
Intent Locks (IS, IX) prevent coarse table updates while fine-grained row locks are held.
Deadlocks occur when cyclic dependencies form in lock acquisition.
Wait-For Graph Detection finds cycles automatically and aborts the transaction with the smallest undo weight.

In the next post, we examine Multi-Version Concurrency Control (MVCC)—the technique modern databases use to allow non-blocking reads without acquiring read locks.

References & Further Reading

Gray, J. (1981). The Transaction Concept: Virtues and Limitations. Proceedings of VLDB, 144–154.
Bernstein, P. A., Hadzilacos, V., & Goodman, N. (1987). Concurrency Control and Recovery in Database Systems. Addison-Wesley.
Haerder, T., & Reuter, A. (1983). Principles of Transaction-Oriented Database Recovery. ACM Computing Surveys, 15(4), 287–317.