What is a database deadlock? Provide an example and explanation of a deadlock in a database.
In a database, a deadlock is a situation that occurs when two or more different database sessions have some data locked, and each database session requests a lock on the data that another, different, session has already locked. Because the sessions are waiting for each other, nothing can get done, and the sessions just waste time instead. This scenario where nothing happens because of sessions waiting indefinitely for each other is known as deadlock.
If you are confused, some examples of deadlock should definitely help clarify what goes on during deadlock. And, you should probably read our explanation of database locks before proceeding since that will help your understanding as well.
Database deadlock example
Suppose we have two database sessions called A and B. Let’s say that session A requests and has a lock on some data – and let’s call the data Y. And then session B has a lock on some data that we will call Z. But now, lets say that session A needs a lock on data Z in order to run another SQL statement, but that lock is currently held by session B. And, let’s say that session B needs a lock on data Y, but that lock is currently held by session A. This means that session B is waiting on session A’s lock and session B is waiting for session A’s lock. And this is what deadlock is all about!
Let’s go through a more detailed (and less abstract) example of deadlock so that you can get a more specific idea of how deadlock can arise.
Database deadlock example in banking
Let’s use an example of two database users working at a bank – let’s call those database users X and Y. Let’s say that user X works in the customer service department and has to update the database for two of the banks customers, because one customer (call him customer A) incorrectly received $5,000 in his account when it should have gone to another customer (call him customer B) – so user X has to debit customer X’s account by $5,000 and also credit customer Y’s account $5,000.
Note that the crediting of customer B and debiting of customer A will be run as a single transaction – this is important for the discussion that follows.
Now, let’s also say that the other database user – Y – works in the IT department and has to go through the customers table and update the zip code of all customers who currently have a zip code of 94520, because that zip code has now been changed to 94521. So, the SQL for this would simply have a WHERE clause that would limit the update to customers with a zip code of 94520.
Also, both customers A and B currently have zip codes of 94520, which means that their information will be updated by database user Y.
Here is a breakdown of the events in our fictitious example that lead to deadlock:
- 1. Database user X in the customer service department selects customer A’s data and updates A’s bank balance to debit/decrease it by $5,000. However, what’s important here is that there is no COMMIT issued yet because database user X still has to update customer B’s balance to increase/credit by $5,000 – and those 2 separate SQL statements will run as a single SQL transaction. Most importantly, this means that database user X still holds a lock on the row for customer A because his transaction is not fully committed yet (he still has to update customer A). The lock on the row for customer A will stay until the transaction is committed.
- 2. Database user Y then has to run his SQL to update the zip codes for customers with zip codes of 94520. The SQL then updates customer B’s zip code. But, because the SQL statement from user Y must be run as a single transaction, the transaction has not committed yet because all of the customers haven’t had their zip codes changed yet. So, this means that database user Y holds a lock on the row for customer B. .
- 3. Now, Database user X still has to run the SQL statement that will update customer B’s balance to increase it by $5,000. But, now the problem is that database user Y has a lock on the row for customer B. This means that the request to update customer B’s balance must wait for user Y to release the lock on customer B. So, database user X is waiting for user Y to release a lock on customer B.
- 4. Now, the SQL statement being run by user Y tries to update the zip code for customer A. But, this update can not happen because user X holds a lock on customer A’s row. So, user Y is waiting for a lock to be released by user X.
- 5. Now you can see that we have user X waiting for user Y to release a lock and user Y waiting for user X to release a lock. This is the situation of deadlock, since neither user can make any progress, and nothing happens because they are both waiting for each other. So, in theory, these two database sessions will be stalled forever. But, read on to see how some DBMS’s deal with this unique situation.
Database deadlock prevention
So now you have seen an example of deadlock. The question is how do DBMS’s deal with it? Well, very few modern DBMS’s can actually prevent or avoid deadlocks, because there’s a lot of overhead required in order to do so. This is because the DBMS’s that do try to prevent deadlocks have to try to predict what a database user will do next, and the theory behind deadlock prevention is that each lock request is inspected to see if it has the potential to cause contention. If that is the case, then the lock is not allowed to be placed.
Database deadlock detection
Instead of deadlock prevention, the more popular approach to dealing with database deadlocks is deadlock detection. What is deadlock detection? Well, deadlock detection is based on the principle that one of the requests that caused the deadlock should be aborted.
How does deadlock detection work?
There are two common approaches to deadlock detection: 1. Whenever a session is waiting for a lock to be released it is in what’s known as a “lock wait” state. One way deadlock detection is implemented is to simply set the lock wait time period to a certain preset limit (like 5 seconds). So, if a session waits more than 5 seconds for a lock to free up, then that session will will be terminated. 2. The RDBMS can regularly inspect all the locks currently in place to see if there are any two sessions that have locked each other out and are in a state of deadlock.
In either of the deadlock detection methods, one of the requests will have to be terminated to stop the deadlock. This also means that any transaction changes which came before the request will have to be rolled back so that the other request can make progress and finish.