DBMS

Transactions And Concurrency

Locking and Two-Phase Locking

Several transactions may hold S on the same

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 2: Anomalies and Isolation Levels Time to complete: ~20 minutes

Table of Contents

  1. Shared and Exclusive Locks
  2. Two-Phase Locking
  3. Strict 2PL
  4. Lock Granularity
  5. Predicate and Gap Locks
  6. Explicit Locking in SQL
  7. Summary & Next Steps

1. Shared and Exclusive Locks

The Two Modes
─────────────────────────────────────────
  SHARED (S) — a read lock
    Several transactions may hold S on the same
    item simultaneously.

  EXCLUSIVE (X) — a write lock
    Only one transaction may hold X, and no S may
    coexist with it.
─────────────────────────────────────────

The Compatibility Matrix
─────────────────────────────────────────
           requested
  held      S      X
  ────────────────────
   S       ✓      ✗
   X       ✗      ✗

  Read the whole thing as: readers do not block
  readers; everything else blocks.
─────────────────────────────────────────

The Consequence
─────────────────────────────────────────
  Under pure locking, a WRITER BLOCKS ALL READERS
  of the same row.

  On a read-heavy workload this is severe: one slow
  update to a popular row stalls every query
  touching it.

  Chapter 4's MVCC exists to remove exactly this
  problem, and is why most modern databases do not
  lock for ordinary reads at all.
─────────────────────────────────────────

2. Two-Phase Locking

The Protocol
─────────────────────────────────────────
  Every transaction has two phases:

  GROWING    may ACQUIRE locks, may not release any
  SHRINKING  may RELEASE locks, may not acquire any

  The moment of the first release is the LOCK
  POINT. After it, no new lock may be taken.

  locks
  held │      ╭────────╮
       │     ╱          ╲
       │    ╱            ╲
       │   ╱              ╲
       └──┴────────────────┴──── time
          growing  ↑  shrinking
                lock point
─────────────────────────────────────────

Why Two Phases Guarantee Serialisability
─────────────────────────────────────────
  The lock points impose a total order on
  transactions.

  If T1 reaches its lock point before T2, then T1
  precedes T2 in the equivalent serial order — for
  every conflict between them, because T1 held all
  its locks at once.

  So the precedence graph (Chapter 1) cannot
  contain a cycle. 2PL produces conflict-
  serialisable schedules, always.
─────────────────────────────────────────

What It Does NOT Prevent
─────────────────────────────────────────
  DEADLOCK. Two transactions in their growing
  phase, each waiting for a lock the other holds,
  wait forever. Chapter 5.

  CASCADING ABORTS. Basic 2PL may release locks
  before commit, so another transaction can read
  uncommitted data. Section 3 fixes this.
─────────────────────────────────────────

3. Strict 2PL

The Rule
─────────────────────────────────────────
  STRICT 2PL: hold ALL EXCLUSIVE locks until
  commit or abort.

  RIGOROUS 2PL: hold ALL locks — shared and
  exclusive — until commit or abort.

  locks
  held │      ╭─────────────┐
       │     ╱              │
       │    ╱               │  ← all released at
       │   ╱                │    once, at COMMIT
       └──┴─────────────────┴──
                          commit
─────────────────────────────────────────

Why Every Real System Uses It
─────────────────────────────────────────
  Nobody can read an uncommitted write, because the
  X lock is held until commit.

  So schedules are STRICT (Chapter 1, Section 5):
  no dirty reads, no cascading aborts, and undo is
  trivial — just restore the before image.

  The cost is that locks are held longer, which
  increases contention. That trade is why keeping
  transactions SHORT matters so much (Module 3,
  Chapter 6): the duration of your transaction is
  the duration other transactions wait.
─────────────────────────────────────────

4. Lock Granularity

The Hierarchy
─────────────────────────────────────────
  DATABASE
     └── TABLE
          └── PAGE
               └── ROW

  COARSE (table)   few locks, low overhead,
                   terrible concurrency
  FINE (row)       excellent concurrency, many
                   locks, high memory and CPU
                   overhead
─────────────────────────────────────────

INTENTION LOCKS
─────────────────────────────────────────
  Problem: to lock a whole table, must the database
  check all million row locks first?

  Solution: before locking a row, take an INTENTION
  lock on the table above it.

    IS   intention shared — I will take S locks
         below
    IX   intention exclusive — I will take X locks
         below
    SIX  S on this level plus IX below

  Now a transaction wanting a table-level X lock
  checks ONE table-level entry, sees an IX, and
  knows to wait — without examining any rows.
─────────────────────────────────────────

LOCK ESCALATION
─────────────────────────────────────────
  When a transaction holds too many row locks, some
  databases ESCALATE to a single table lock.

  Saves memory. Destroys concurrency — suddenly one
  transaction blocks the entire table.

  SQL Server does this. PostgreSQL does NOT (it
  stores row locks in the rows themselves, so they
  cost no separate memory), which is one reason
  large updates behave differently across
  databases.

  Practical mitigation: update in BATCHES rather
  than one enormous statement.
─────────────────────────────────────────

5. Predicate and Gap Locks

Row locks cannot prevent phantoms (Chapter 2) — you cannot lock a row that does not exist yet.

The Problem
─────────────────────────────────────────
  T1: SELECT * FROM students WHERE city='Pune'
      Locks the 3 matching rows.
  T2: INSERT a new Pune student.
      No conflict — that row was not locked,
      because it did not exist.
  T1: re-runs the query ──► 4 rows. PHANTOM.
─────────────────────────────────────────

Two Solutions
─────────────────────────────────────────
  PREDICATE LOCKS
    Lock the CONDITION: "all rows where
    city='Pune'", including future ones.
    Theoretically clean; expensive to check, since
    every insert must be tested against every held
    predicate.

  NEXT-KEY LOCKING (what InnoDB does)
    Lock the index RANGE — the matching entries
    plus the GAPS between and around them.
    An insert into a locked gap blocks.
    Cheap, because it reuses the index structure.
─────────────────────────────────────────

Why This Explains an InnoDB Surprise
─────────────────────────────────────────
  UPDATE orders SET status='x' WHERE amount > 100;

  With no index on `amount`, InnoDB cannot lock a
  range — so it locks essentially EVERY row it
  scans, including non-matching ones.

  With an index on `amount`, it locks only the
  relevant key range.

  So a missing index does not merely make the
  statement slow; it makes it lock far more than it
  should, and blocks unrelated transactions.
  Indexing is a CONCURRENCY concern, not only a
  performance one.
─────────────────────────────────────────

6. Explicit Locking in SQL

-- Take an X lock on the rows you read, so a check-then-act is safe.
BEGIN;
    SELECT balance FROM accounts WHERE id = 'A' FOR UPDATE;
    -- no other transaction can read-for-update or modify this row now
    UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
COMMIT;
 
-- FOR SHARE: prevent modification, allow other readers.
SELECT * FROM courses WHERE id = 10 FOR SHARE;
 
-- Do not wait — fail immediately if locked.
SELECT * FROM accounts WHERE id = 'A' FOR UPDATE NOWAIT;
 
-- Skip rows that are locked — the queue-worker pattern.
SELECT * FROM jobs WHERE status = 'pending'
ORDER BY created_at LIMIT 1
FOR UPDATE SKIP LOCKED;
SKIP LOCKED Deserves Its Own Note
─────────────────────────────────────────
  It is the clean way to build a work queue on a
  relational database.

  Ten workers all run the same statement. Each
  takes a DIFFERENT pending job, because each skips
  rows already locked by the others. No contention,
  no double-processing, no external queue needed.

  Before this existed, people built elaborate
  claim-with-update schemes. This replaces all of
  them with one clause.
─────────────────────────────────────────

Lock Ordering
─────────────────────────────────────────
  When a transaction locks several rows, always
  lock them in a CONSISTENT ORDER — by primary
  key, for instance.

  T1 locking A then B, while T2 locks B then A, is
  the textbook deadlock (Chapter 5). Consistent
  ordering makes it impossible.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • Shared locks are compatible with each other and nothing else, so under pure locking a single writer blocks every reader of that row.
  • Two-phase locking guarantees serialisability because lock points impose a total order on transactions; strict 2PL additionally holds exclusive locks to commit, eliminating dirty reads and cascading aborts.
  • Intention locks let a table-level lock request be evaluated without examining a million row locks.
  • Row locks cannot prevent phantoms, so databases lock index ranges instead — which means a missing index causes over-locking, making indexing a concurrency concern.

Concept Check

  1. Why does strict 2PL make transaction duration a shared cost rather than a private one?
  2. What problem do intention locks solve, and what would happen without them?
  3. Why does an unindexed UPDATE ... WHERE amount > 100 lock more rows in InnoDB than an indexed one?

Next Chapter

→ Chapter 4: Multi-Version Concurrency Control

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index