Database interviews:What are the necessary conditions for a deadlock to occur? How do I resolve deadlocks?

Have you ever been asked a similar question in an interview? Or you will meet in the future, let’s explore and master it together

Thank you for reading this article. More Interview Questions here:
https://programmerscareer.com/software-interview-set/

Topic: 1.1 Introduction to Deadlocks

Deadlocks are a condition in a multithreading environment when two or more threads are unable to proceed because each is waiting for the others to release resources. In the context of a MySQL database, a deadlock occurs when two or more transactions mutually hold and request for locks, creating a cycle of dependencies.

In a transaction, a thread might need to lock multiple tables or rows, which can sometimes lead to a situation where the thread needs a resource that’s locked by another thread. Meanwhile, that thread might be waiting for a resource locked by the first thread. This is known as a deadlock.

Let me illustrate this with a simple story:

Imagine two comic book fans, Alice and Bob. Alice has the latest ‘Superbot’ comic which Bob wants. At the same time, Bob has the newest ‘Megagirl’ comic, which Alice wants. Now, Alice is not willing to give up her ‘Superbot’ comic until she has the ‘Megagirl’ comic in her hands, and Bob too, won’t give up his ‘Megagirl’ comic until he has the ‘Superbot’ comic. So, both are waiting for each other to let go of their comics, which results in a deadlock.

In terms of database transactions, Alice and Bob could be transactions, and the comic books could be the locked resources.

Topic: 1.2 Understanding Necessary Conditions for a Deadlock

To understand how deadlocks occur, we need to be familiar with Coffman’s Conditions, which are a set of four conditions that must all hold for a deadlock to occur. These are named after Edward G. Coffman, Jr., who first articulated them. The conditions are:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode. This means only one process (or thread) can use the resource at any given time. If another process requests the resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait (Resource Holding): A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be forcibly removed from the processes holding them until the resources are used to completion. The resources can only be released voluntarily by the process holding them.
4. Circular Wait: A circular chain of processes exists where each process holds one resource while requesting another resource held by another process in the chain. Essentially, there’s a process P1 that is waiting for a resource that is held by process P2, and P2 is waiting for a resource held by P1. This makes a circular chain of waiting processes.

These 4 conditions inherently provide a logical structure to understand and structure the prevention policies. By ensuring that at least one of the above conditions never occurs, we can prevent the formation of deadlocks.

Topic 1.3: Detecting Deadlocks in MySQL

In MySQL, the InnoDB storage engine automatically detects deadlocks and resolves them by rolling back one of the transactions involved. Therefore, your application should always be ready to re-issue a transaction if it gets rolled back due to a deadlock.

When a deadlock occurs in MySQL, it’s immediately detected and resolved by the system. This is achieved by the wait-for graph deadlock detection mechanism, where MySQL maintains information about which transactions are waiting for locks held by which other transactions. With this approach, MySQL can check for cycles in the wait-for graph. If it detects a cycle, this indicates a deadlock, and it’ll roll back one of the transactions to break the deadlock.

To give you more insight into the situation, MySQL also provides diagnostic information when it detects and resolves a deadlock. This information can be obtained from the SHOW ENGINE INNODB STATUS command, which will showcase the latest deadlock error.

However, it’s important to note that deadlocks are not necessarily a sign of a design flaw or error. In some high concurrency systems, deadlocks may happen from time to time and can be considered a cost of doing business. But of course, if you are experiencing them frequently, it may be worth investigating further to see if there can be improvements in the transaction processing.

Topic 1.4: Preventing Deadlocks

Here are several strategies for preventing deadlocks:

1. Order Your Locks: Always lock tables in the same order. For example, if all your transactions lock the ‘orders’ table before the ‘products’ table, you won’t have one transaction locking ‘orders’ and a second transaction locking ‘product’ and waiting for ‘orders’.
2. Keep Transactions Short and Fast: The shorter a transaction, the less likely it is to lock a row that’s needed by another transaction.
3. Error Handling: Since InnoDB automatically detects deadlocks and rolls back a transaction, you need to be ready to catch that error in your code and retry the transaction.
4. Use Lower Isolation Levels: If possible, use the Read Committed isolation level rather than Repeatable Read to lessen the chance of deadlocks.
5. Avoid Hotspots: If you can avoid frequently updated rows, you can reduce the likelihood of deadlocks. For instance, instead of having a counter table that gets updated each time an operation is performed, consider using a different strategy to count operations.

Topic 1.5: Resolving Deadlocks

When it comes to resolving deadlocks, the ideal circumstance is that deadlocks are detected and handled automatically by MySQL’s InnoDB storage engine. InnoDB uses a mechanism known as wait-for graph to detect deadlocks. When a deadlock happens, InnoDB chooses one of the transactions and kills it, thereby resolving the deadlock.

While this takes care of resolving the deadlock, it is important for application developers to handle these scenarios within the application. When InnoDB kills a transaction due to a deadlock, it raises an error that needs to be caught in your application, and, typically, the transaction that was terminated should be retried.

The automatic deadlock detection in InnoDB resolves deadlocks as they happen, but in certain cases, the detection and killing of a transaction can take substantial time, impacting your application’s performance. That is why it is also important to design your application to avoid deadlocks as much as possible.

Although it’s hard to prevent deadlocks entirely in high concurrency systems, trying to minimize them as much as possible will lead to a smoother and more efficient operation of your database system. Good coding practices, efficient design of your tables, and correctly applying transactions and lock controls, can help you avert most deadlocks.

Topic 1.6: Troubleshooting Deadlocks

Investigating and troubleshooting deadlocks can provide valuable insights to prevent them or improve the response time. MySQL includes several tools that can assist in this process.

1. SHOW ENGINE INNODB STATUS: This command outputs a text-based report that includes information about the most recent deadlock if one has occurred. It’s essential to run this command as soon as possible after the deadlock because its information is lost with the next one.
2. InnoDB Monitors: These are more detailed and extensive reports about InnoDB’s internal workings, including deadlocks. There are standard, lock, and mutex monitors.
3. Performance Schema: MySQL’s Performance Schema can be configured to capture detailed data about events, including transaction events. This data is stored in tables and can be queried like other MySQL data.
4. Binary Logs: MySQL’s binary logs can help determine the sequence of queries that led to the deadlock. These logs require that you have the binary log enabled and that you’re logging in ROW format.
5. Error Log: Deadlocks are logged here if you have innodb_print_all_deadlocks configuration enabled.

By analyzing these sources, you can determine which transactions were involved in a deadlock and what resources they were trying to access. In many cases, careful analysis may point to a better way to order locks or a better transaction size to prevent foreseeable deadlocks.

Topic: 1.7 Review and Assessments

Example Problem:
Assume that you encounter a deadlock in your MySQL database. You decide to run the command SHOW ENGINE INNODB STATUS for more information.

The LATEST DETECTED DEADLOCK section gives you the following output:

LATEST DETECTED DEADLOCK  
------------------------  
2022-08-24 23:08:02 7f3e6e2fd700  
*** (1) TRANSACTION:  
TRANSACTION 118945420, ACTIVE 22 sec inserting  
mysql tables in use 1, locked 1  
1700 lock struct(s), heap size 187648, 1249789 row lock(s), undo log entries 1  
MySQL thread id 155, OS thread handle 0x7f3e6e3e7700, query id 25749768 localhost user  
INSERT INTO customer (id, name, address) VALUES (3, 'John Doe', '123 Main St')  
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:  
RECORD LOCKS space id 66873 page no 70541 n bits 600 index `id` of table `test`.`customer` trx id 118945420 lock mode S waiting up to 3 years total: 47.56T, and currently at 47.68T to rise above: 47.68T  
*** (2) TRANSACTION:  
TRANSACTION 118945416, ACTIVE (PREPARED) 13 sec committing, thread declared inside InnoDB 476  
mysql tables in use 1, locked 1  
1 lock struct(s), heap size 368, 0 row lock(s)  
MySQL thread id 117, OS thread handle 0x7f3e6e2fd700, query id 25749765 localhost user  
COMMIT  
*** (2) HOLDS THE LOCK(S):  
RECORD LOCKS space id 66873 page no 70541 n bits 600 index `id` of table `test`.`customer` trx id 118945416 lock mode S  
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:  
RECORD LOCKS space id 66873 page no 70541 n bits 600 index `id` of table `test`.`customer` trx id 118945416 lock_mode X waiting up to 3 years total: 47.68T to rise above: 47.56T  
*** WE ROLL BACK TRANSACTION (1)

Based on this information, what is causing the deadlock and how could you potentially resolve it?

Now let’s test your knowledge.

Question 1 — Simple Familiar Problem (Difficulty 3/10):

What are the four conditions that must be present for a deadlock as per Coffman’s conditions? Provide a brief explanation of each condition.

Question 2 — Complex Familiar Problem (Difficulty 6/10):

What steps would you take to proactively prevent or minimize deadlock occurrences?

Question 3 — Complex Unfamiliar Problem (Difficulty 9/10):

Why does MySQL InnoDB engine automatically resolve deadlocks by rolling back a transaction? What are the advantages and potential disadvantages of this approach?

Please always try to get to the answer by yourself first before asking for help.

---

Solution for Example Problem:

The deadlock occurred because two transactions were each waiting for resource more than the individual ones. The transaction (1) was waiting for an S-mode (read) lock on the id index of the customer table, that was being held by transaction (2). At the same time, transaction (2) was waiting for an X-mode (write) lock on the very same resource while transaction (2) held an S-mode (read) lock.

This scenario means that neither transaction could proceed, resulting in a deadlock. The resolution could be to ensure the transactions request locks in the same order, as it is one of the well-known techniques to avoid deadlock.

Solution to Question 1:

Coffman’s deadlock conditions are as follows:

1. Mutual Exclusion: A resource can only be held by one process at a time.
2. Hold and Wait: Processes already holding resources can request new resources.
3. No Preemption: Only the process holding the resource can release it.
4. Circular Wait: A circular chain of processes exists where each process holds a resource needed by the next process in the chain.

Solution to Question 2:

Multiple approaches can be deployed to prevent or minimize deadlocks:

1. Setting Lock Timeout: By limiting how long a transaction waits to acquire a lock, you can minimize wait time and potentially resolve deadlocks.
2. Ordering Locks: Having transactions request locks in a specific order can prevent deadlocks by eliminating the circular wait condition.
3. Frequent Committing: Smaller transactions that commit frequently are less likely to clash with other transactions.
4. Deadlock Detection Tools: Utilize built-in or third-party tools to determine when and why deadlocks occur so programmatic resolutions can be applied.

Solution to Question 3:

When a deadlock occurs in MySQL, the InnoDB engine automatically chooses the smallest transaction (the one with fewest row locks) and rolls it back to break the deadlock

Advantages:

1. This automatic resolution helps to keep the database running smoothly without manual intervention.

Potential Disadvantages:

1. If the transaction that is rolled back is large or critical, rolling it back might lead to data not being updated or saved correctly.
2. Continuous rollbacks due to deadlocks can negatively affect performance.
3. Not all business logic scenarios may suit automatic rollback.

中文文章: https://programmerscareer.com/zh-cn/mysql-interview6/
Author: Wesley Wei – Twitter Wesley Wei – Medium
Note: If you choose to repost or use this article, please cite the original source.