Deadlock is what occurs when two or more transactions are waiting on each other to release a lock. Neither can move, and so both stall.
To combat this, a system can either prevent deadlock from occurring, or detect when it does happen and act accordingly.
Models for Concurrency Control
To understand how deadlock occurs in database systems it helps to understand the role of various concurrency control techniques. I’m going to discuss two popular approaches.
Two-phase locking (2PL) is commonly used to guarantee serializability in database systems. In this model a transaction can either obtain a shared or exclusive lock for an item, but all locking operations must occur before the first unlock operation. The name refers to the two phases that result from this: the expanding phase where locks are acquired, and the shrinking phase where locks are released.
There are a number of variations on this model. Conservative 2PL requires that all locks are taken out at the beginning of the transaction, whereas Rigorous 2PL requires that all locks are held until after the transaction commits (or aborts). The former collapses the expanding phase, while the latter collapses the shrinking phase.
Timestamp-based concurrency control involves using unique transaction timestamps in place of conventional locks. Concurrency control is based on the ordering of timestamps. So, for example, when a transaction accesses an item, the system checks whether this transaction is older than the last one which accessed the item. If this is the case the transaction proceeds; otherwise ordering is violated and the transaction is aborted. Such strict timestamp-based approaches can lead to the cyclic restart of transactions and starvation.
Multi-version concurrency control (MVCC) also incorporates timestamps by allowing several versions of an item to be stored. This allows the system to present a consistent (but potentially historical) version of the database to queries, meaning fewer reads are rejected than with basic timestamp ordering.
Optimistic concurrency control (OCC) allows multiple transactions to read and update items without blocking. However, before a transaction is committed the database must check for conflicts – if any are found one of the conflicting transactions is rolled back.
For deadlock to occur four conditions need to be true (meaning you need to break one to prevent deadlock):
Mutual Exclusion – a resource cannot be held by more than one transaction at a time. This condition is true of database systems using two 2PL where an exclusive lock is required on updates. Systems using OCC don’t hold locks, and so break this condition.
Hold and Wait – transactions already holding resources can request further resources.Conservative 2PL breaks this condition, since it requires all locks to be acquired from the outset. However this isn’t always desirable as it limits concurrency.
No pre-emption – a resource cannot be forcibly removed from a transaction. Pre-emption is used in timestamp-based approaches. Two of the most commonly used schemes are wait-dieand wound-wait. In wait-die (non-preemptive), if a transaction tries to lock an item which is already locked, it waits if the holder of the lock is a younger transaction (based on timestamp); otherwise it will abort. In wound-wait (pre-emptive), instead of waiting as before, the transaction aborts the other younger transaction. If it is the younger transaction it waits.
Circular wait – a number of transactions form a circular chain where each transaction is waiting for a resource that a later transaction (in the chain) holds. This can be prevented by imposing a total ordering on resources, requiring that each transaction requests locks on resources in an agreed order. This may not be possible in some forms of 2PL where locks are not taken out at a single point in time (e.g. rigorous 2PL).
Many of these approaches aren’t ideal because they result in transactions being aborted at the slightest chance of deadlock. In situations where deadlock will rarely occur (for example, when transactions are mostly short-lived and lightweight) detection is more practical.
Deadlock detection involves periodically checking whether the system is in a state of deadlock. There are two basic methods of detection: timeouts and wait-for graphs.
Timeouts represent the simplest method of detection. If a transaction waits for a period longer than some constant timeout period it will be aborted. This method has a low overhead, but may end up aborting transactions even in the absence of deadlock.
Another approach is for the system to construct a wait-for graph. Each node in the graph represents an active transaction. A directed edge is drawn between two transactions when one transaction is waiting for a lock on an item held by the other transaction. Deadlock exists (and is detected) when there is a cycle in the graph. At this point the system engages in victim selection, where one of the transactions is chosen to be aborted. The challenge in this technique is deciding when and how often to check for deadlock in the graph.
For More Information
Hopefully this post provides enough information to give a good understanding of the subject area. If you want to know more I’d recommend looking at some of the material I used while writing this post:
- Fundamentals of Database Systems (Elmasri & Navathe, Fifth Edition)
- Principles of Distributed Database Systems (Tamer Özsu & Valduriez, Second Edition)
- Architecture of a Database System (Hellerstein et al., 2007)