Two-Phase Locking

Every database faces the same puzzle: thousands of users read and write simultaneously, yet each one expects to see a consistent view of the data. If you transfer money between two accounts, the amount cannot disappear between the debit and the credit, no matter what anyone else is doing at that instant.

The solution almost every relational database relies on is Two-Phase Locking (2PL), invented by Eswaran, Gray, Lorie, and Traiger at IBM in 1976. The idea is disarmingly simple: a transaction may acquire as many locks as it needs, but the moment it releases one lock, it may never acquire another. This creates two clean phases — a growing phase (lock accumulation) and a shrinking phase (lock release). You collect your tools, do your work, then put them all away.

That single rule is provably sufficient for serializability — the strongest correctness guarantee in databases, meaning the outcome of any concurrent execution is identical to some serial order. But the rule carries a price: two transactions can each hold a lock the other needs, and both will wait forever. Deadlock is not a bug in 2PL; it is a structural consequence of the guarantee it provides.

Related: if you want to understand why serializability matters at all, start with P vs NP — the deeper question of whether efficient algorithms exist for hard verification problems.

The simulator below runs two transactions, T1 and T2, that each need two data items. Step through the schedule with Next Step and watch the lock table and wait-for graph update in real time.

<div class="hint">
  {{hint}}
</div>
<div class="scene">
  <div class="lock-table">
    <div class="section-label">{{label_lock_table}}</div>
    <table id="lockTable">
      <thead><tr><th>{{th_item}}</th><th>{{th_holder}}</th><th>{{th_waiters}}</th></tr></thead>
      <tbody>
        <tr><td>A</td><td id="holderA">—</td><td id="waitA">—</td></tr>
        <tr><td>B</td><td id="holderB">—</td><td id="waitB">—</td></tr>
      </tbody>
    </table>
  </div>
  <div class="wfg-box">
    <div class="section-label">{{label_wfg}}</div>
    <svg id="wfg" viewBox="0 0 220 120" width="220" height="120">
      <defs>
        <marker id="arr" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto">
          <path d="M0,0 L0,6 L8,3 z" fill="#c92f3c"/>
        </marker>
        <marker id="arrGray" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto">
          <path d="M0,0 L0,6 L8,3 z" fill="#aaa"/>
        </marker>
      </defs>
      <!-- {{c_t1_node}} -->
      <circle cx="50" cy="60" r="22" class="node" id="nodeT1"/>
      <text x="50" y="65" text-anchor="middle" class="node-label">T1</text>
      <!-- {{c_t2_node}} -->
      <circle cx="170" cy="60" r="22" class="node" id="nodeT2"/>
      <text x="170" y="65" text-anchor="middle" class="node-label">T2</text>
      <!-- {{c_arrows}} -->
      <line id="edgeT1T2" x1="73" y1="50" x2="147" y2="50" class="edge hidden" marker-end="url(#arr)"/>
      <line id="edgeT2T1" x1="147" y1="70" x2="73" y2="70" class="edge hidden" marker-end="url(#arr)"/>
    </svg>
    <div id="deadlockBadge" class="deadlock-badge hidden">{{deadlock_badge}}</div>
  </div>
</div>
<div class="log-wrap">
  <div class="section-label">{{label_exec_log}}</div>
  <div id="log" class="log"></div>
</div>
<div class="btns">
  <button id="stepBtn" type="button">{{btn_next}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="statusBar" class="status-bar"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin-bottom: .8rem; line-height: 1.5;
        background: #f0f4f8; border-left: 3px solid #1d3557; padding: .5rem .7rem; border-radius: 0 6px 6px 0; }
.scene { display: flex; gap: 1rem; align-items: flex-start; flex-wrap: wrap; margin-bottom: .6rem; }
.section-label { font-size: .75rem; font-weight: 700; letter-spacing: .05em; color: #1d3557;
                 text-transform: uppercase; margin-bottom: .3rem; }
.lock-table table { border-collapse: collapse; font-size: .88rem; }
.lock-table th, .lock-table td { border: 1px solid #cdd9e3; padding: .3rem .6rem; text-align: center; }
.lock-table th { background: #e8eef3; font-weight: 700; }
.lock-table td { background: #fff; min-width: 56px; }
td.held-t1 { background: #d6eaff; color: #1d3557; font-weight: 700; }
td.held-t2 { background: #fff3cd; color: #7a4700; font-weight: 700; }
td.waiting { background: #fde8e8; color: #c92f3c; font-style: italic; }
.wfg-box { display: flex; flex-direction: column; align-items: center; }
svg .node { fill: #e8eef3; stroke: #1d3557; stroke-width: 1.6; }
svg .node-label { font: 700 14px system-ui; fill: #1d3557; }
svg .edge { stroke: #c92f3c; stroke-width: 2; }
svg .edge.hidden { display: none; }
.deadlock-badge { font: 700 13px system-ui; color: #fff; background: #c92f3c;
                  border-radius: 6px; padding: .2rem .6rem; margin-top: .3rem; }
.deadlock-badge.hidden { display: none; }
.log-wrap { margin-bottom: .6rem; }
.log { font: .82rem ui-monospace, monospace; background: #f7f9fb; border: 1px solid #cdd9e3;
       border-radius: 6px; padding: .4rem .6rem; max-height: 130px; overflow-y: auto; }
.log-line { padding: 1px 0; }
.log-line.t1 { color: #1d3557; }
.log-line.t2 { color: #7a4700; }
.log-line.sys { color: #c92f3c; font-weight: 700; }
.btns { display: flex; gap: .5rem; margin-bottom: .4rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status-bar { font-size: .88rem; font-weight: 600; min-height: 1.3em; color: #555; }

// Code not found

Notice the moment the wait-for graph gains a cycle: T1 waits for a lock held by T2, while T2 waits for a lock held by T1. Neither can proceed. The only resolution is to abort one transaction and retry — exactly what real databases do with a deadlock detector or a timeout. This is not a quirk of a bad schedule; under 2PL, any interleaving that causes a cycle will deadlock.

2PL sits at a precise and well-understood point in the complexity landscape of concurrency control.

• Proven correct (1976). Eswaran, Gray, Lorie, and Traiger published the definitive theorem: any execution of transactions that all obey 2PL produces a serializable schedule. The proof constructs a serial order from the lock-acquisition sequence. This is not a heuristic — it is a mathematical guarantee.
• Deadlock is structurally inevitable. Whenever two transactions need overlapping lock sets and hold them in opposite order, a cycle forms in the wait-for graph. The protocol cannot prevent this without giving up serializability in edge cases — the two goals are in tension.
• Detecting deadlock is easy. Finding a cycle in a directed graph takes $O(V + E)$ time — polynomial, fast enough to run continuously. Real systems use a background deadlock detector that periodically scans the wait-for graph and picks a victim to abort.
• Strict 2PL. Most production databases use Strict 2PL, which holds all locks until commit. This eliminates cascading rollback (aborting a transaction also forces aborting every other transaction that already read its uncommitted writes) at the cost of holding locks longer.
• Optimistic and MVCC alternatives. Systems like PostgreSQL's MVCC avoid most read locks by giving each transaction a snapshot, reducing deadlocks in read-heavy workloads — but serializable MVCC still needs predicate locks or conflict detection, bringing its own complexity.

Two-phase locking thus proves that correctness and liveness can conflict: you can guarantee a correct result (serializability), but you cannot guarantee progress (freedom from deadlock) at the same time, under arbitrary concurrent workloads. See also Nash Equilibrium for another domain where rational local choices produce globally stuck outcomes.

Two-phase locking is not an academic abstraction — it runs inside the databases handling most of the world's transactions:

• Relational databases: IBM DB2, Microsoft SQL Server, and MySQL's InnoDB engine implement Strict 2PL for serializable isolation. Every row-level lock you see in EXPLAIN output is 2PL in action.
• Distributed databases: Google Spanner uses a distributed variant of 2PL combined with TrueTime timestamps to achieve external consistency across data centers — global 2PL at planetary scale.
• Deadlock tuning: database administrators routinely tune lock granularity (row vs page vs table) and transaction order to minimize deadlock frequency. Understanding 2PL is the prerequisite for that work.
• Isolation levels: SQL's $READ COMMITTED$, $REPEATABLE READ$, and SERIALIZABLE levels correspond to weakened or strengthened variants of 2PL. Choosing the wrong level is a common source of data corruption bugs.
• Teaching concurrency: 2PL is the canonical example used in every database course to show that correctness guarantees come with algorithmic costs — the same trade-off pattern that appears in scheduling and max-flow problems.

If you have ever seen a "deadlock detected" error in a production log, you have already met 2PL. If you have ever waited for a slow query to release its locks, you have felt its shrinking phase.

Two-phase locking is one of the clearest examples in computer science of a correctness guarantee that costs something real. The two-phase rule is both necessary and sufficient for serializability — a fact established in 1976 and never overturned. But the same rule that makes concurrency safe is precisely the reason two transactions can lock each other out forever.

That tension — between safety and liveness, between correctness and progress — runs through distributed systems, operating system schedulers, and network protocols alike. 2PL does not resolve the tension; it makes it visible and manageable. Detect the deadlock, abort a victim, retry — and the system moves forward.

The next time a production alert fires with "deadlock detected", remember: the database is not broken. It is doing exactly what the 1976 theorem says it must do when two transactions want the same data in the wrong order. See also P vs NP for the broader question of whether hard problems have efficient solutions at all.