Deadlock Detection with Wait-For Graphs

Understanding Deadlocks and the Waits-For Graph

Before we can build a detector, we need a formal way to represent "who is waiting for whom." This is done using a waits-for graph. The concept is simple:

• Nodes: Each active transaction is a node in the graph.
• Edges: A directed edge from transaction $T_i$ to transaction $T_j$ (i.e., $T_i\to T_j$) means that $T_i$ is waiting for $T_j$ to release a lock.
• Deadlock: A cycle in the waits-for graph indicates a deadlock.

For example, if $T_1\to T_2$ and $T_2\to T_1$, we have a deadlock. Neither transaction can make progress because each is waiting for the other.

To see how this graph is constructed from a sequence of lock requests, the following video provides a clear, step-by-step example.

Implementing a Deadlock Detector

Now that we understand the model, let's design the implementation. In most database systems, deadlock detection is not performed on every lock request because that would be too slow. Instead, a dedicated background thread wakes up periodically, checks for deadlocks, and resolves them.

Your implementation will follow this model, which consists of three main steps:

1. Build the waits-for graph based on the current state of the lock manager.
2. Detect cycles in the graph.
3. Break any detected cycles by aborting a "victim" transaction.

The project specification for CMU's database course provides an excellent, practical guide for this task. It outlines a clear API and provides crucial implementation hints that we will follow.

Let's break down the implementation details based on that reading.

Step 1: Building the Waits-For Graph

Your background thread will start by constructing the graph from scratch. The necessary information resides within the LockManager, which you built in a previous lesson. The LockManager contains lock request queues for each data item.

The algorithm to build the graph is as follows:

1. Create an empty graph data structure. You can use an adjacency list, like std::unordered_map<txn_id_t, std::vector<txn_id_t>>.
2. Iterate through the LockManager's internal state (e.g., its map of locked items).
3. For each data item, identify the set of transactions waiting for a lock on it (T_waiters) and the set of transactions currently holding a lock on it (T_holders).
4. For every transaction $T_w\in T_{waiters}$ and every transaction $T_h\in T_{holders}$, add a directed edge from $T_w$ to $T_h$. This is because $T_w$ cannot acquire its lock until all incompatible holders in $T_{holders}$ release theirs.
   • Important: Remember that multiple transactions can hold a shared lock. If a transaction is waiting to acquire an exclusive lock, it is waiting on all current shared lock holders.

As the project spec notes, you should not include already aborted transactions in your graph.

Step 2: Detecting Cycles with Depth-First Search (DFS)

With the graph built, you need to find cycles. Since you have a background in algorithms, you know that DFS is the standard way to detect cycles in a directed graph.

The algorithm works by maintaining the status of each node:

• UNVISITED: Not yet explored.
• VISITING: Currently in the recursion stack for the current DFS traversal.
• VISITED: Fully explored (all its descendants have been visited).

When performing DFS from a node u:

1. Move u from UNVISITED to VISITING.
2. For each neighbor v of u:
   • If v is in the VISITING state, you have found a back edge, which means a cycle exists.
   • If v is UNVISITED, recursively call DFS on v.
3. Once all neighbors of u are explored, move u from VISITING to VISITED.

To ensure your implementation is deterministic (as required by the CMU project), you should always start your DFS traversals from the active transaction with the lowest ID. When exploring neighbors, also process them in sorted order of their transaction IDs.

Step 3: Breaking the Cycle (Victim Selection)

When your DFS finds a cycle, you must break it by aborting one of the transactions. This is called victim selection. There are many possible heuristics, such as aborting the transaction that has done the least work or holds the fewest locks.

However, a simple and common strategy is to abort the youngest transaction in the cycle (the one with the highest transaction ID). This approach helps prevent starvation, where the same transaction is repeatedly chosen as the victim and never gets to finish.

Once the victim is chosen:

1. The transaction's state is set to ABORTED.
2. The TransactionManager must be notified to roll back its changes and release all locks it holds.
3. Your detection thread should not stop after finding one cycle. It should continue checking until all cycles in the graph are broken before going back to sleep.

Deadlock Detection in Practice

Seeing how real database systems handle deadlocks can provide valuable context. The following video demonstrates deadlock scenarios in MySQL and PostgreSQL, showing how the systems automatically detect the cycle and abort one of the transactions.

A key takeaway from the demo is the trade-off in detection frequency. This is controlled by a configuration parameter (like deadlock_timeout in Postgres or the sleep interval of your background thread).

• Frequent checking: Detects deadlocks quickly, reducing transaction latency. However, it consumes more CPU resources.
• Infrequent checking: Lower overhead, but transactions may be stuck waiting for a long time before a deadlock is resolved, hurting system throughput.

Conclusion

In this lesson, we designed a complete system for handling the deadlocks that can arise from lock-based concurrency control. You now have a practical, implementation-focused understanding of this critical database component.

Key Takeaways:

• A deadlock is a circular wait among transactions, which can be modeled with a waits-for graph. A cycle in this graph signifies a deadlock.
• The common implementation strategy is a background thread that periodically builds the graph from the lock manager's state, detects cycles using DFS, and breaks them by aborting a victim transaction.
• A robust heuristic for victim selection is to abort the youngest transaction in the cycle to prevent starvation.
• Real-world systems provide knobs to control deadlock detection behavior, reflecting the trade-off between detection overhead and resolution latency.

Preview of the Next Lesson

While Strict 2PL with deadlock detection is a robust and widely used approach, it's not the only one. For workloads with many read operations, the cost of acquiring locks and the potential for blocking can be a bottleneck. In our next lesson, we will explore a fundamentally different approach: Multi-Version Concurrency Control (MVCC). We'll see how MVCC allows readers to proceed without acquiring locks, dramatically improving concurrency in many common scenarios.