- Berkeley DB Reference Guide:
- Locking Subsystem
|
|
Practically any application that uses locking may deadlock. In nearly all cases, in order to recover from a deadlock, transactions must be used, so that an operation that deadlocks mid-way through can be undone, leaving the database in a consistent state. As the access methods may perform updates on multiple pages during a single API call, transactions are necessary even when the application makes only single update calls into the database. The only exception to this rule is when all the threads accessing the database are doing so read-only or when the Concurrent Data Store product is used; this product guarantees deadlock-free operation at the expense of reduced concurrency. Since deadlocks cannot be prevented, Berkeley DB provides the ability to detect deadlocks and recover from them gracefully.
Deadlocks occur when two or more threads of control are blocked waiting on each other's forward progress. Consider two transactions, each of which wants to modify items A and B. Assume that transaction 1 modifies first A and then B, but transaction 2 modifies B then A. Now, assume that transaction 1 obtains its writelock on A, but before it obtains its writelock on B, it is descheduled and transaction 2 runs. Transaction 2 successfully acquires its writelock on B, but then blocks when it tries to obtain its writelock on A, because transaction 1 already holds a writelock on it. This is a deadlock. Transaction 1 cannot make forward progress until Transaction 2 releases its lock on B, but Transaction 2 cannot make forward progress until Transaction 1 releases its lock on A.
The lock_detect function runs an instance of the Berkeley DB deadlock detector. The db_deadlock utility performs deadlock detection by calling lock_detect at regular intervals. When a deadlock exists in the system, all of the threads of control involved in the deadlock are, by definition, waiting on a lock. The deadlock detector examines the state of the lock manager and identifies a deadlock, and selects one of the participants to abort. (See Configuring locking for a discussion of how a participant is selected). The lock on which the selected participant is waiting is identified such that the lock_get (or lock_vec) call in which that lock was requested will receive an error return of DB_LOCK_DEADLOCK. In the access methods, this error return is propagated back through the Berkeley DB interface as DB_LOCK_DEADLOCK.
When an application receives an DB_LOCK_DEADLOCK, the correct action is to abort the current transaction, and optionally retry it. Transaction support is necessary for recovery from deadlocks. When a deadlock occurs, the database may be left in an inconsistent or corrupted state, and any database changes already accomplished must be undone before the application can proceed further.
The deadlock detector identifies deadlocks by looking for a cycle in what is commonly referred to as its "waits-for" graph. More precisely, the deadlock detector reads through the lock table, and finds each object currently locked. Each object has a list of transactions or operations (hereafter called lockers) that currently hold locks on the object and possibly a list of waiting lockers, waiting on the lockers holding it. Each object creates one or more partial orderings of lockers. That is, for a particular object, every waiting locker comes after every holding locker, because that holding locker must release its lock before the waiting locker can make forward progress. Conceptually, after each object has been examined, the partial orderings are topologically sorted (see tsort). If this topological sort reveals any cycles, then the lockers forming the cycle are involved in a deadlock. One of the lockers is selected for abortion.
It is possible that aborting a single transaction involved in a deadlock is not enough to allow other transactions to make forward progress. In this case, the deadlock detector will be called repeatedly. Unfortunately, at the time a transaction is selected for abortion, there is not enough information available to determine if aborting that single transaction will allow forward progress or not. Since most applications have few deadlocks, Berkeley DB takes the conservative approach, aborting as few transactions as may be necessary to resolve the existing deadlocks. In particular, for each unique cycle found in the waits-for graph described in the previous paragraph, only one transaction is selected for abortion. However, if there are multiple cycles, then one transaction from each cycle is selected for abortion. Only after the aborting transactions have received the deadlock return and aborted their transactions, can it be determined if it is necessary to abort other transactions in order to allow forward progress.
|
|