In a previous article we wrote data to the database using atomic update statements, and then using transactions with SELECT ... FOR UPDATE. In this article we will look at what happens when we continue doing this, in a more complicated way. Source code for this article is also available on github.com.
A simple row lock
But first let’s do things manually: We create a table kris with an integer primary key column and a secondary unindexed data column. We are filling it with some records with gaps between the primary keys.
We then START TRANSACTION READ WRITE and SELECT ... FOR UPDATE a record:
The SELECT ... FOR UPDATE created a LOCK_TYPE: TABLE table-level lock with LOCK_MODE: IX. This is an intention-lock set by FOR UPDATE which indicates the desire to set X-locks (exclusive-locks, write-locks) on rows.
The statement then proceeded to actually create a row-lock, at the record level: We see LOCK_TYPE: RECORD with LOCK_DATA: 10, so the record id=10 has been locked. The LOCK_MODE: X, REC_NOT_GAP indicates a lock on the record only, not on the gap before the record.
A lock on a nonexistent row
Adding to the preceding transaction, we now also search for a non-existent row, using FOR UPDATE to signal our intent to later create this row. Since the row does not exist, the result set is empty:
Reusing the table-level IX lock from before, we now see a third entry in PERFORMANCE_SCHEMA.DATA_LOCKS:
This, too, is a record-level lock, but this time it is LOCK_MODE: X,GAP and LOCK_DATA: 40. What we get here is a lock on the space between the rows id=30 (excluding) and id=40 (including), preventing other threads from inserting a row id=35.
Inserting into a locked gap, with timeouts.
We can try do demonstrate that with a second session:
While the SELECT ... FOR UPDATE had a where clause of WHERE id=35, the lock covers the entire interval (30, 40], and our attempt to insert a record with id=33 hangs and has to wait until either the locking transaction is committed or our attempt times out. This can be a long wait: by default, innodb_lock_wait_timeout is set to 50 seconds.
We can change that:
We are rolling back all our transactions, and reset the table kris to the initial 4 tuples ((10,10), (20,20), (30,30), (40,40)).
InnoDB handles Deadlocks
Whenever we collect locks in a non-atomic fashion there is a risk of deadlocking.
A deadlock is any situation where a thread A holds a resource 1 and wants to lock a resource 2, where at the same time a thread B holds the lock on 2 and wants a lock on 1.
A holds lock 1 and needs a lock on 2 to complete and release both locks, while B holds the lock on 2 and needs the lock on 1 to complete and release both locks. There is no way to resolve this situation except with intervention from the outside, forcing one transaction to roll back (and hopefully retry). There is no problem for either A or B to complete the operation, but not while both are trying to finish concurrently.
The deadlock scenario is only possible because A and B do not aquire locks in a canoncial order: Had B also aquired the locks in numerically ascending order (1, 2), the transactions would have had serialized themselves successfully, and no forced conflict resolution would have been necessary. You can think of the rollback with a later retry as a clumsy, forced serialisation of events instead.
More complicated scenarios with 3 or more threads and larger circular dependencies are possible.
So, let’s excercise a deadlock with two sessions:
and in the other session:
Now that both threads hold their first resource, let’s get their respective opposite to complete the deadlock. Session1 hangs, because it waits for Session2 to release the lock on id=10.
And Session2, trying to lock id=30, which is held by Session1, then is being detected and rolled back forcibly:
At the same time Session1 can complete the statement:
The time reported is the time this session hung waiting for the lock to be granted.
After the rollback PERFORMANCE_SCHEMA.DATA_LOCKS looks like this:
These locks are owned by Session1, and after executing ROLLBACK or COMMIT in Session1 they are released and the select-statement on performance_schema comes back empty.
We can try to formalize what we learned in code: A table demo with 10 counters numbered from 1 to 10 is being set up, the counters are starting at 0.
We are running two programs concurrently: One program is counting up the counters i and i+1, and the other program is counting up the counters i and i-1. Whenever the two programs generate overlapping transactions, a deadlock situation should arise.
We want to be able to detect this, and restart the transactions. A quick and dirty attempt at this: A function to lock a record by id.
A function to increment a counter in a record we locked this way:
And a really dirty function with way too many parameters to exercise these two functions for pairs of records:
And two driver functions, one that goes up and another that goes down, wrapped with click so that they can be accessed via the command line:
When running this, we get deadlocks because we built it this way:
As soon as the count-down (6,5) and the count-up (5,6) cross their streams a deadlock happens. The count-up (5,6) is rolled back and needs to retry. After retry the counter values are correctly incremented.
We managed to detect the deadlocks, retry the transactions and set things right. Once more the world is safe.