Cover

CMU Database Group · 1:05:22 · Watch on YouTube

Summary

This lecture (CMU 15-445/645, Fall 2024) moves from the previous class's static schedules — where every read and write is known in advance — to dynamic schedules, where the DBMS must decide on the fly which transaction may touch which object. The solution presented is two-phase locking (2PL): transactions acquire locks in a growing phase and, once the first lock is released, may only release locks in a shrinking phase. The lecture shows that plain locking is not sufficient for serializability, that 2PL fixes it but permits cascading aborts, and that strong strict 2PL (holding all locks until commit) eliminates those. It then covers the two deadlock strategies — detection via a waits-for graph and a background worker, and prevention via the age-priority Wait-Die and Wound-Wait protocols — before closing with hierarchical locking (intention locks IS/IX/SIX, lock escalation) and the SQL hints SELECT ... FOR UPDATE and SKIP LOCKED.

Overview

graph TD
    A[Dynamic schedules:<br/>queries arrive on the fly] --> B[Locks + lock manager]
    B --> C[Locking alone is NOT enough<br/>unrepeatable read]
    C --> D[Two-Phase Locking<br/>= conflict serializable]
    D --> E[Cascading aborts remain]
    E --> F[Strong Strict 2PL<br/>hold all locks until commit]
    D --> G[Deadlocks]
    G --> H[Detection<br/>waits-for graph + victim]
    G --> I[Prevention<br/>Wait-Die / Wound-Wait]
    F --> J[Too many locks?<br/>Hierarchical locking]
    J --> K[Intention locks IS / IX / SIX<br/>+ lock escalation]
    K --> L[SQL hints:<br/>FOR UPDATE, SKIP LOCKED]

Topics

  1. Recap: serializability and the shift to dynamic schedules
  2. Locks vs. latches, and the lock manager
  3. Basic lock types, and why locking alone is not enough
  4. Two-phase locking (2PL)
  5. Cascading aborts and strong strict 2PL
  6. Worked example: bank transfer under each protocol
  7. Deadlock detection
  8. Deadlock prevention
  9. Hierarchical locking, granularity, and intention locks
  10. Locking hints in SQL
  11. Wrap-up and what's next

Full source: transcript.md

Key takeaways

  • Using locks does not by itself guarantee serializability. The lecture's counter-example locks every operation correctly yet still produces an unrepeatable read, because T1 released the lock on A and later re-acquired it after T2 wrote 14:36, 15:16.
  • 2PL alone is sufficient for conflict serializability: once you can never acquire a lock after releasing one, the precedence graph is guaranteed acyclic. It was the first provably correct concurrency control protocol, invented by Jim Gray at IBM on System R in the 1970s (Turing Award, 1990s) 15:59, 18:06, 19:14.
  • Strong strict 2PL is what you actually get in practice. Holding every lock until commit removes cascading aborts and makes rollback a single-transaction operation instead of unwinding a dependency chain; since SQL has no UNLOCK, most systems default to it when you ask for serializable isolation 24:22, 24:50, 25:26.
  • The bank-transfer example quantifies the failure: without 2PL, T2 reports a total of $19,900 — $100 missing — because it read A after the debit and B before the credit. Both basic 2PL and strong strict 2PL produce the correct total 26:49, 28:01, 28:17.
  • Deadlock handling is a tuning problem, not a solved one. Detection trades detector frequency (60 s = cheap but slow recovery; microseconds = burned CPU) and uses a cheap two-transaction cycle heuristic before the expensive full search; victim selection weighs age, queries run, locks held, prior rollbacks, and cascading impact — the thing that separates enterprise systems from open source 32:11, 33:55, 35:40.
  • Prevention needs no background worker at all. Wait-Die (old waits, young dies) and Wound-Wait (young waits, old kills) make all waiting flow in one direction, so cycles are impossible; restarted transactions reuse their original timestamp to avoid starvation 41:01, 43:29, 43:42.
  • Granularity is the real performance lever. DB2 originally shipped a single lock for the entire database — trivially correct, terrible parallelism. Intention locks (IS/IX/SIX) let a table-level hint coexist with fine-grained tuple locks (IS is compatible with IX), and lock escalation collapses many leaf locks back into one to reduce latch contention in the lock manager 46:08, 54:57, 57:57.
  • SKIP LOCKED turns a database into a work queue: workers skip rows locked by other transactions instead of blocking, letting each pull the next available task 1:01:54, 1:02:19.