Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Deadlocks and MVCC
DBMS

Deadlocks and MVCC

Master deadlock detection, prevention (Wait-Die, Wound-Wait), and Multi-Version Concurrency Control (MVCC) — the two key mechanisms for handling concurrent transactions.

Deadlocks and MVCC

Two transactions waiting for each other’s locks is a deadlock — neither can proceed. Multi-Version Concurrency Control (MVCC) is an alternative approach that avoids locking entirely for reads.

This chapter covers deadlock handling and MVCC, the two most important concurrency mechanisms in modern databases.

Learning Objectives

After completing this chapter, you will be able to:

  • Describe what a deadlock is and how it occurs.
  • Draw and interpret a wait-for graph.
  • Compare deadlock prevention (Wait-Die, Wound-Wait) and deadlock detection.
  • Explain MVCC and how it avoids read locks.
  • Understand snapshot isolation.
  • Differentiate between locking-based and MVCC-based concurrency.
  • Answer deadlock and MVCC interview questions.

What is a Deadlock?

A deadlock occurs when two or more transactions are waiting for locks held by each other, creating a cycle. None can proceed.

Example

Transaction T1:                 Transaction T2:
Lock-X(A)                       Lock-X(B)
Lock-X(B)  ← BLOCKED           Lock-X(A)  ← BLOCKED

T1 holds X-lock on A and wants X-lock on B. T2 holds X-lock on B and wants X-lock on A. Neither can proceed.

Wait-For Graph (WFG)

A Wait-For Graph is a directed graph used for deadlock detection.

  • Nodes: Transactions.
  • Edges: T1 → T2 means T1 is waiting for a lock held by T2.
  • Deadlock: If the graph contains a cycle.

Example

T1 → T2 → T3 → T1 (cycle = deadlock)

T1 ──→ T2
 ↑      │
 │      ▼
 └──── T3

Deadlock Detection

How It Works

The DBMS periodically checks the wait-for graph for cycles.

Steps

  1. Build the wait-for graph from the lock manager’s data.
  2. Run cycle detection algorithm (DFS).
  3. If a cycle is found, choose a victim transaction to abort.
  4. Abort the victim, release its locks, and restart it.

Victim Selection

The DBMS chooses which transaction to abort based on:

CriterionVictim
YoungestAbort the transaction that started most recently
Fewest locksAbort the transaction holding the fewest locks
Lowest priorityAbort the transaction with lower priority/importance
Most progressSome systems abort the transaction that has done the least work (cheapest to roll back)

Deadlock Prevention

Prevention protocols ensure deadlocks never occur by imposing ordering rules.

Wait-Die (Non-Preemptive)

Rule: If an older transaction waits for a younger transaction, the older waits. If a younger transaction waits for an older transaction, the younger dies (aborts).

ConditionAction
Older T1 waits for Younger T2T1 waits
Younger T1 waits for Older T2T1 aborts (dies)

Example

  • T1 (started at time 10) wants a lock held by T2 (time 20).

  • T1 is older → T1 waits.

  • T2 (time 20) wants a lock held by T1 (time 10).

  • T2 is younger → T2 aborts.

Wound-Wait (Preemptive)

Rule: If an older transaction waits for a younger transaction, the older wounds the younger (the younger aborts). If a younger transaction waits for an older transaction, the younger waits.

ConditionAction
Older T1 waits for Younger T2T1 wounds T2 (T2 aborts)
Younger T1 waits for Older T2T1 waits

Example

  • T1 (time 10) wants a lock held by T2 (time 20).

  • T1 is older → T1 wounds T2. T2 aborts.

  • T2 (time 20) wants a lock held by T1 (time 10).

  • T2 is younger → T2 waits.

Wait-Die vs Wound-Wait

AspectWait-DieWound-Wait
Older waits for youngerYes (waits)No (wounds)
Younger waits for olderNo (dies)Yes (waits)
Preemptive?NoYes
RestartsYounger transactions restart moreOlder transactions can preempt younger
Starvation riskOlder transactions may wait repeatedlyYounger transactions may be wounded repeatedly

No-Wait Algorithm

Simpler than Wait-Die / Wound-Wait.

Rule: If a transaction cannot acquire a lock immediately, it aborts immediately and retries later.

Pros: Simple, no deadlock detection overhead. Cons: High abort rate under contention.

Timeout-Based Deadlock Handling

Rule: If a transaction waits for a lock longer than a threshold (e.g., 5 seconds), assume deadlock and abort.

Pros: Simple, no graph maintenance. Cons: Mistaken aborts (innocent transactions killed), hard to pick the right timeout value.

Multi-Version Concurrency Control (MVCC)

MVCC is an alternative to pure locking. Instead of blocking readers when a writer is active, MVCC provides each reader with a snapshot of the data as of a specific point in time.

How It Works

  1. When a transaction writes data, the DBMS creates a new version of the data item (does not overwrite the old version).
  2. Transactions see a consistent snapshot of the database taken at the transaction’s start time.
  3. A transaction’s writes are not visible to other transactions until it commits.

Benefits

  • Readers never block writers: A read transaction can read the old version while a write transaction creates a new version.
  • Writers never block readers: A write transaction creates a new version; readers continue reading the old version.
  • Snapshot isolation: Each transaction sees a consistent database state.

Drawbacks

  • Storage overhead: Multiple versions of the same data exist.
  • Old versions need cleanup: The garbage collector (VACUUM in PostgreSQL) must remove versions no longer needed.
  • Write skew: A subtle anomaly possible under snapshot isolation.

MVCC vs Locking

AspectLocking (2PL)MVCC
Reads block writes?Yes (S-lock blocks X-lock)No
Writes block reads?Yes (X-lock blocks S-lock)No
StorageSingle versionMultiple versions
CleanupNot neededNeed version cleanup (VACUUM)
AnomaliesDeadlocksWrite skew, lost updates
Used bySome older databasesPostgreSQL, MySQL (InnoDB), Oracle

MVCC in Practice

PostgreSQL

  • Every transaction gets a Transaction ID (XID).
  • Each row has xmin (the transaction that created it) and xmax (the transaction that deleted/updated it).
  • A transaction sees rows where xmin ≤ its own XID and xmax is either NULL or > its own XID.
  • Dead tuples are cleaned by VACUUM.

MySQL (InnoDB)

  • Stores multiple versions in the undo log.
  • Each transaction sees a consistent snapshot based on its read view.
  • Old versions are purged by the purge system.

Oracle

  • Uses undo segments to store rollback data.
  • A query sees data as of the point in time when the query started (statement-level snapshot by default).

Snapshot Isolation

Snapshot Isolation is the isolation level provided by MVCC.

Rules

  • Each transaction reads from a snapshot of the database taken at transaction start.
  • A transaction commits only if its writes do not conflict with concurrent committed writes.

Anomaly: Write Skew

Write skew is possible under snapshot isolation.

Example

  • Two doctors are on call. At least one must be on call at all times.
  • T1: Doctor A checks if B is on call (A sees B is on call). T1 takes A off call.
  • T2: Doctor B checks if A is on call (B sees A is on call). T2 takes B off call.
  • Both commit. Now neither is on call.

This cannot happen under serializable isolation.

Interview Deep Dive

Q: What is the difference between deadlock and starvation?

A: In a deadlock, two or more transactions are stuck waiting for each other’s locks — they can never proceed without external intervention. In starvation, a transaction keeps getting postponed because higher-priority transactions keep taking the resource first. Starvation is not a cycle — the transaction could eventually get the lock, but it keeps getting preempted.

Q: Why do most modern databases use MVCC instead of pure locking?

A: MVCC provides significantly better concurrency for read-heavy workloads because readers never block writers and writers never block readers. In a pure locking system, any write blocks all reads on that row. With MVCC, reads see a consistent snapshot without waiting for write locks. This is critical for modern web applications where reads dominate the workload.

Q: When would you use Wound-Wait over Wait-Die?

A: Wound-Wait is generally preferred because it reduces the number of transaction restarts. In Wait-Die, younger transactions frequently die and restart. In Wound-Wait, older transactions preempt younger ones, and the restarted transaction is always the younger one — which has likely done less work and costs less to roll back.

Q: What anomalies can occur under snapshot isolation that cannot occur under serializable isolation?

A: The main anomaly is write skew — when two transactions read overlapping data sets, make disjoint updates based on those reads, and the combined result violates a constraint. Example: two doctors both going off call because each sees the other as on call. Serializable isolation prevents this by detecting such conflicts.

Key Takeaways

  • A deadlock is a cycle of transactions waiting for each other’s locks.
  • Wait-for graphs detect deadlocks; cycles = deadlock.
  • Deadlock detection picks a victim to abort.
  • Wait-Die: older waits for younger; younger dies for older.
  • Wound-Wait: older wounds younger; younger waits for older.
  • Timeout-based handling aborts transactions waiting too long.
  • MVCC provides snapshot isolation by maintaining multiple versions of data.
  • MVCC eliminates read-write conflicts — readers never block writers and vice versa.
  • MVCC is used by PostgreSQL, MySQL (InnoDB), and Oracle.
  • Snapshot isolation may allow write skew.

My Private Notes

Notes are auto-saved locally to this device.