Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 52

Understanding Deadlocks in Concurrent Transactions

Recommended resources

Hello! Welcome to the final lesson in our module on Transactions and Concurrency.

In our previous lessons, we explored the ACID properties, identified concurrency anomalies like Dirty Reads and Phantom Reads, and saw how transaction isolation levels provide a powerful tool to prevent them. You learned that even with strong isolation, managing concurrent access is complex.

Today, we will address a classic problem that arises from this complexity: the deadlock. Our goal is to define a deadlock and explain how it can occur between concurrent transactions. Understanding this concept is critical for anyone writing applications that interact with a database, as it's a common source of bugs and performance issues in production systems. We'll explore not just what a deadlock is, but also the low-level "why" of how a database system detects and resolves this "deadly embrace."

What is a Deadlock?

At its core, a deadlock is a situation where two or more transactions are stuck in a state of permanent blocking, each waiting for a resource that the other holds. It's a circular dependency that neither transaction can resolve on its own.

It is crucial to distinguish a deadlock from normal blocking. When Transaction A tries to access a resource locked by Transaction B, A is blocked. It simply waits. When B finishes its work and releases the lock, A can proceed. This is a normal and expected part of concurrent database operations.

A deadlock is different. In a deadlock, Transaction A is waiting for B, and simultaneously, Transaction B is waiting for A. Neither can proceed, and they would wait forever if the database didn't intervene.

To get a clear picture of this circular dependency, let's watch a short, effective explanation.

Database Deadlocks Easily Explained

The video 'Database Deadlocks Easily Explained' by Software Developer Diaries provides a great visual and conceptual introduction to deadlocks.

Watch from the beginning until 03:01. Focus on the distinction between simple blocking and the circular dependency that defines a deadlock. The diagram the presenter draws is a perfect illustration of this concept.

This diagram illustrates the static state of a deadlock.

SQL Server Deadlock Illustration
A classic deadlock scenario. Process A has locked Table A and needs Table B. Concurrently, Process B has locked Table B and needs Table A. Neither can proceed.

How Do Deadlocks Occur? The Classic Scenario

The most common cause of deadlocks is inconsistent lock ordering. This happens when different transactions acquire locks on the same set of resources but in a different sequence.

Let's walk through a classic example: transferring money between two bank accounts. Imagine Alice wants to send $50 to Bob, and at the same time, Bob wants to send $100 to Alice.

Consider two transactions running concurrently:

  • Transaction 1 (Alice to Bob):
    1. Lock Alice's account (id=1).
    2. Lock Bob's account (id=2).
  • Transaction 2 (Bob to Alice):
    1. Lock Bob's account (id=2).
    2. Lock Alice's account (id=1).

The following sequence of events will lead to a deadlock:

Database Deadlock Scenario
This sequence diagram shows the step-by-step process leading to a deadlock. Notice how both transactions successfully acquire their first lock but get stuck when requesting their second lock, creating a circular wait.
  1. Transaction 1 begins and acquires an UPDATE lock on the row for accounts where id = 1.
  2. Transaction 2 begins and acquires an UPDATE lock on the row for accounts where id = 2.
  3. Transaction 1 now tries to acquire a lock on the row for accounts where id = 2. It cannot, because Transaction 2 holds that lock. So, Transaction 1 waits.
  4. Transaction 2 now tries to acquire a lock on the row for accounts where id = 1. It cannot, because Transaction 1 holds that lock. So, Transaction 2 waits.

At this point, a deadlock has occurred. Transaction 1 is waiting for Transaction 2, and Transaction 2 is waiting for Transaction 1.

Let's see this exact scenario demonstrated in code.

Database Deadlocks Easily Explained

The video we watched earlier continues with a code demonstration that perfectly matches this scenario. The presenter runs two scripts that attempt to update two accounts in the opposite order.

Watch the segment from 03:01 to 05:08. Observe how the two transactions block each other and, after a few seconds, the database detects the issue and returns a 'deadlock found' error for one of them.

The "Low-Level Why": Deadlock Detection

This brings us to a crucial question that aligns with your interest in systems programming: How does the database know a deadlock has occurred?

Modern database systems don't let deadlocked transactions wait forever. They employ a background process often called a deadlock monitor or detector. This process periodically checks for deadlocks and resolves them.

The primary mechanism for this is the construction of a "waits-for" graph.

  • The nodes in the graph represent the currently running transactions.
  • A directed edge from node T1 to T2 means "Transaction T1 is waiting for a resource currently held by Transaction T2."

If the detector finds a cycle in this graph (e.g., T1 → T2 → T1), it has found a deadlock.

Lecture 19 Part 7 Deadlock Detection and Resolution

For a more formal explanation of this mechanism, we can turn to a lecture from UC Berkeley's database course. It clearly explains how the waits-for graph is built and how a cycle signifies a deadlock.

Watch from the beginning until 02:42. Focus on how the graph is constructed as transactions acquire and wait for locks. The key takeaway is that a cycle in the waits-for graph is the definitive signature of a deadlock.

Once a deadlock is detected, the database must resolve it. It does this by choosing one of the transactions in the cycle as a deadlock victim. The database then aborts the victim's transaction, rolls back all of its changes, and releases its locks. This breaks the cycle and allows the other transaction(s) to proceed.

The database typically chooses the victim based on a cost-based heuristic, such as aborting the transaction that has done the least amount of work or is the least expensive to roll back. The application that initiated the aborted transaction receives an error (like the "deadlock found" message we saw) and is expected to handle it, usually by retrying the transaction.

Test your understanding!

Consider two concurrent transactions, T1 and T2, operating on two resources, Resource A and Resource B. The following sequence of events occurs:

  1. T1 acquires a lock on Resource A.
  2. T2 acquires a lock on Resource B.
  3. T1 attempts to acquire a lock on Resource B.
  4. T2 attempts to acquire a lock on Resource A.

At what step does the system enter a deadlock state? Explain your reasoning using the concept of a waits-for graph.

Show answer

The deadlock occurs at Step 4.

Here's the breakdown using a waits-for graph:

  • After Step 1 and 2, no one is waiting. The graph is empty.
  • At Step 3, T1 tries to lock Resource B, which is held by T2. The database adds an edge to the waits-for graph: T1 → T2 (T1 is waiting for T2). At this point, T1 is simply blocked, which is normal.
  • At Step 4, T2 tries to lock Resource A, which is held by T1. The database adds another edge: T2 → T1 (T2 is waiting for T1).

Now, the waits-for graph contains a cycle: T1 → T2 → T1. This cycle signifies a deadlock. Neither transaction can proceed because each is waiting for a resource held by the other.

Conclusion

In this lesson, we dissected the nature of database deadlocks. You now have a robust mental model for what they are, how they happen, and how the database system works at a low level to resolve them.

Key Takeaways:

  • A deadlock is a circular dependency where two or more transactions are permanently blocked, each waiting for a resource the other holds.
  • The most common cause is inconsistent lock ordering across concurrent transactions.
  • Database systems automatically detect deadlocks by periodically building a waits-for graph and searching for cycles.
  • Resolution involves choosing a deadlock victim, aborting its transaction, and rolling it back. The application is then responsible for retrying the failed transaction.

This lesson concludes our module on Transactions and Concurrency. You have built a solid foundation, from the core ACID principles and isolation levels that ensure correctness, to handling the inevitable issue of deadlocks. This knowledge is fundamental to building reliable, multi-user applications.

Preview of the Next Module:
So far, our focus has been primarily on correctness. Now, we will shift our attention to another critical aspect of database management: performance. In our next module, "Query Performance and Optimization," we will begin by exploring one of the most powerful tools for accelerating data retrieval: indexes. We'll investigate how they function internally to allow the database to find the data you need without having to perform a costly full scan of an entire table.