DBMS

Transactions And Concurrency

Deadlocks and Practical Concurrency

T1: UPDATE accounts SET ... WHERE id='A' -- X on A

JrCodex·8 min read

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 4: Multi-Version Concurrency Control Time to complete: ~20 minutes

Table of Contents

  1. What a Deadlock Is
  2. Detection
  3. Prevention
  4. Optimistic vs Pessimistic Concurrency
  5. Four Patterns Worth Knowing
  6. A Concurrency Checklist
  7. Summary & Next Steps

1. What a Deadlock Is

The Cycle
─────────────────────────────────────────
  T1: UPDATE accounts SET ... WHERE id='A'   -- X on A
  T2: UPDATE accounts SET ... WHERE id='B'   -- X on B
  T1: UPDATE accounts SET ... WHERE id='B'   -- WAITS for T2
  T2: UPDATE accounts SET ... WHERE id='A'   -- WAITS for T1

         T1 ──waits for──► T2
          ▲                 │
          └───waits for─────┘

  Neither can proceed. Neither will ever release.
─────────────────────────────────────────

The Four Necessary Conditions
─────────────────────────────────────────
  MUTUAL EXCLUSION   a resource is held
                     exclusively
  HOLD AND WAIT      a transaction holds one lock
                     while requesting another
  NO PREEMPTION      locks are not forcibly taken
                     away
  CIRCULAR WAIT      a cycle exists in the
                     wait-for graph

  ALL FOUR must hold. Breaking any ONE prevents
  deadlock — which is what every strategy in
  Section 3 does.
─────────────────────────────────────────

2. Detection

The Wait-For Graph
─────────────────────────────────────────
  Nodes: transactions
  Edge Tᵢ → Tⱼ: Tᵢ is waiting for a lock held by Tⱼ

  A CYCLE in this graph IS a deadlock.

  The database checks periodically (PostgreSQL:
  deadlock_timeout, default 1 second) and, on
  finding a cycle, chooses a VICTIM and aborts it.
─────────────────────────────────────────

def find_deadlock(wait_for):
    """wait_for: {txn: set of txns it waits on}. Returns a cycle, or None."""
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {t: WHITE for t in wait_for}
    stack = []
 
    def visit(t):
        colour[t] = GREY
        stack.append(t)
        for nxt in wait_for.get(t, ()):
            if colour.get(nxt, WHITE) == GREY:            # back edge ──► CYCLE
                return stack[stack.index(nxt):]
            if colour.get(nxt, WHITE) == WHITE:
                if (cycle := visit(nxt)):
                    return cycle
        stack.pop()
        colour[t] = BLACK
        return None
 
    for t in wait_for:
        if colour[t] == WHITE and (cycle := visit(t)):
            return cycle
    return None
 
print(find_deadlock({'T1': {'T2'}, 'T2': {'T1'}}))        # ['T1', 'T2']
Choosing a Victim
─────────────────────────────────────────
  Databases prefer to abort the transaction that
  costs least to redo — typically the one that has
  done the least work, or holds the fewest locks.

  Your application receives a deadlock error.

  DEADLOCKS ARE NORMAL under contention. Code that
  takes multiple locks must be prepared to retry,
  exactly like the serialisation-failure retry from
  Chapter 2.
─────────────────────────────────────────

3. Prevention

Four Strategies
─────────────────────────────────────────
  1. CONSISTENT LOCK ORDERING
     Breaks CIRCULAR WAIT.
     Always acquire locks in the same order — by
     primary key, alphabetically, any total order.
     ── the best fix, and usually easy

  2. TAKE ALL LOCKS AT ONCE
     Breaks HOLD AND WAIT.
     One statement locking every needed row.
     Hard when the set is not known upfront.

  3. TIMEOUTS
     Breaks NO PREEMPTION.
     lock_timeout aborts a transaction waiting too
     long. Crude but effective as a backstop.

  4. AVOID LOCKS
     Breaks MUTUAL EXCLUSION.
     Single-statement updates that need no
     application-side read (Chapter 4, Option A).
─────────────────────────────────────────

# The transfer deadlock, and its one-line fix.
 
# ✗ DEADLOCKS: transfer(A,B) and transfer(B,A) run concurrently.
def transfer_bad(conn, src, dst, amount):
    conn.execute("UPDATE accounts SET balance=balance-? WHERE id=?", (amount, src))
    conn.execute("UPDATE accounts SET balance=balance+? WHERE id=?", (amount, dst))
 
# ✓ SAFE: always lock the lower id first, whichever direction the money moves.
def transfer_good(conn, src, dst, amount):
    first, second = sorted([src, dst])                    # ← the entire fix
    conn.execute("SELECT balance FROM accounts WHERE id=? FOR UPDATE", (first,))
    conn.execute("SELECT balance FROM accounts WHERE id=? FOR UPDATE", (second,))
    conn.execute("UPDATE accounts SET balance=balance-? WHERE id=?", (amount, src))
    conn.execute("UPDATE accounts SET balance=balance+? WHERE id=?", (amount, dst))
Why Ordering Works
─────────────────────────────────────────
  With a total order on resources, a cycle is
  impossible.

  T1 holding A and wanting B, plus T2 holding B and
  wanting A, requires T2 to have taken B before A —
  which the ordering rule forbids.

  No cycle is constructible. The deadlock cannot
  occur, rather than being detected and recovered
  from.
─────────────────────────────────────────

4. Optimistic vs Pessimistic Concurrency

The Two Philosophies
─────────────────────────────────────────
  PESSIMISTIC
    Assume conflict. Lock first, then work.
    SELECT ... FOR UPDATE.
    Cost: waiting.
    Best when conflicts are FREQUENT.

  OPTIMISTIC
    Assume no conflict. Work, then check at commit.
    Version numbers, or SERIALIZABLE.
    Cost: wasted work on the retries.
    Best when conflicts are RARE.
─────────────────────────────────────────

-- Optimistic concurrency with a version column — the standard application pattern.
CREATE TABLE documents (
    id      INTEGER PRIMARY KEY,
    content TEXT    NOT NULL,
    version INTEGER NOT NULL DEFAULT 1
);
 
-- Read, including the version.
SELECT id, content, version FROM documents WHERE id = 42;      -- version = 7
 
-- Write, asserting the version has not moved.
UPDATE documents
SET content = :new_content, version = version + 1
WHERE id = 42 AND version = 7;
-- 1 row affected ──► success.
-- 0 rows affected ──► someone else edited it. Re-read and merge.
Why This Pattern Is Everywhere
─────────────────────────────────────────
  It holds NO locks between the read and the write,
  so a user can have a form open for ten minutes
  without blocking anyone.

  The conflict is detected at write time, and the
  application decides what to do — merge, warn, or
  overwrite.

  This is how document editors, wikis and most web
  forms handle concurrent edits. It is also exactly
  the durable-agent pattern of "check the version
  you based your work on".
─────────────────────────────────────────

5. Four Patterns Worth Knowing

1. THE WORK QUEUE
─────────────────────────────────────────
  SELECT * FROM jobs WHERE status='pending'
  ORDER BY created_at LIMIT 1
  FOR UPDATE SKIP LOCKED;

  Chapter 3's SKIP LOCKED. Many workers, no
  contention, no double-processing.

2. THE COUNTER
─────────────────────────────────────────
  ✗ read count, add 1, write back
       ──► lost updates under concurrency

  ✓ UPDATE stats SET views = views + 1 WHERE id=?
       ──► atomic; the database serialises it

  For very hot counters, shard the row into N
  sub-counters and sum them on read.

3. THE UNIQUE CLAIM
─────────────────────────────────────────
  ✗ SELECT to check if the username is free, then
    INSERT
       ──► two transactions both see it free

  ✓ a UNIQUE constraint, and INSERT
       ──► one succeeds, one gets a constraint
           violation. Catch and report it.

  Let the database arbitrate. It is the only
  component that can.

4. THE IDEMPOTENT WRITE
─────────────────────────────────────────
  INSERT ... ON CONFLICT DO NOTHING / DO UPDATE
  (Module 3, Chapter 6's UPSERT)

  Safe to retry, which matters because every
  pattern above may need retrying.
─────────────────────────────────────────

6. A Concurrency Checklist

Before Shipping Code That Writes
─────────────────────────────────────────
  □ Do I know which isolation level I am running
    at? (Chapter 2 — check, do not assume)

  □ Is there a read-then-write? If so, is it
    protected by FOR UPDATE, a version column, or
    expressed as a single statement?

  □ Do I take more than one lock? If so, are they
    ordered consistently?

  □ Is there a retry loop for serialisation
    failures and deadlocks?

  □ Are my transactions SHORT — no network calls,
    no user input, no file I/O inside them?

  □ Does any decision read rows other than the ones
    it writes? (write skew — needs SERIALIZABLE or
    an explicit lock)

  □ Are the columns I filter on in an UPDATE
    indexed? (Chapter 3 — otherwise it over-locks)
─────────────────────────────────────────

The Two Highest-Value Items
─────────────────────────────────────────
  SHORT TRANSACTIONS. They reduce lock duration,
  reduce deadlock probability, and prevent the
  vacuum problem from Chapter 4 — three separate
  failure modes, one habit.

  RETRY LOOPS. Under any correct isolation level,
  aborts are normal operation. Code without a retry
  loop is code that fails randomly under load.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • Deadlock requires four simultaneous conditions, and breaking any one prevents it — consistent lock ordering breaks circular wait and is usually the easiest fix.
  • Databases detect deadlocks by finding cycles in the wait-for graph and abort a victim, so any code taking multiple locks needs a retry loop.
  • Pessimistic concurrency waits and suits frequent conflicts; optimistic version columns hold no locks between read and write and suit rare ones.
  • Let the database arbitrate uniqueness with a constraint rather than checking first, and express read-modify-write as a single statement wherever possible.

Module 7 Complete — What's Next

You now understand what happens when many transactions run at once and how to write code that stays correct. Module 8 covers the other half of the durability promise: what happens when the machine simply stops.

Concept Check

  1. Why does sorting the two account ids make the transfer function deadlock-free rather than merely less likely?
  2. When is optimistic concurrency the better choice than SELECT ... FOR UPDATE, and why?
  3. Why is checking whether a username is free before inserting it wrong, and what should you do instead?

Next Module

→ Module 8: Recovery and Reliability

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