Locked In: The Hidden World of Database Locks

"When debugging concurrency issues, remember: Schrödinger's bug may or may not exist until observed."

In large applications which are accessed daily by thousands or millions of users, concurrency is inevitable. (especially in high transactional systems.)

Let’s say that we have a database which handles “Tickets booking” for football matches, the rule is :

• Tickets are in finite amount. (let’s say 30,000 ticket)

• First come, first serve.

• Once the tickets are fully booked, the booking is closed.

• Users can select their seat number to book.

Thousands of users rush in trying to book tickets for the match. When something weird happens:

• User x checks seat number 100 is free and not booked.

• User y checks seat number 100 is free and not booked.

Both users attempt to book the same seat, at the same time and both user succeeded in booking the same seat, leading to a race condition!

This can lead to data integrity issues in booking systems if this really happened as flight bookings, coupons and discounts on any booking platform would collapse.

Luckily locks mechanisms come into the rescue. Locking protocols are used in DBMS as a means of concurrency control.

I’ll use MySQL as an example in this article.

Table-level locks: Because sometimes you need to keep the whole house locked while you fix one room.

MySQL enables client sessions to acquire table locks explicitly for the purpose of cooperating with other sessions for access to tables, or to prevent other sessions from modifying tables during periods when a session requires exclusive access to them. A session can acquire or release locks only for itself. One session cannot acquire locks for another session or release locks held by another session.

MySQL supports “table-level locking” which by its name means locking applied to the entire table. Which also means that it can block any other sessions from READ or WRITE operations to the table, depending on the exact type of the lock.

READ Lock vs WRITE Lock:

The advantages of table locks that it is very simple and can avoid concurrency issues, but the issue is it literally blocks the entire table even if a small portion of data is being read or modified. So won’t be suitable in all situations especially in high-concurrency environments.

Micro Locks, Macro Efficiency: The Art of Row-Level Locking

MySQL’s engine InnoDB implements standard row-level locking where there are two types of locks, shared (S) locks and exclusive (X) locks.”

Row-level locks allow multiple transactions to access different rows in the same table simultaneously, improving concurrency.

If transaction T1 holds a shared (S) lock on row r, then requests from some distinct transaction T2 for a lock on row r are handled as follows:

• A request by T2 for an S lock can be granted immediately. As a result, both T1 and T2 hold an S lock on r.

• A request by T2 for an X lock cannot be granted immediately.

Also, If a transaction T1 holds an exclusive (X) lock on row r, a request from some distinct transaction T2 for a lock of either type on r cannot be granted immediately. Instead, transaction T2 has to wait for transaction T1 to release its lock on row r.

Phantom rows (Phantom pain)

The so-called phantom problem occurs within a transaction when the same query produces different sets of rows at different times. For example, if a SELECT is executed twice, but returns a row the second time that was not returned the first time, the row is a “phantom” row.

In other words, Phantom reads occur when a transaction reads a set of rows that match a certain condition, but another transaction inserts new rows that also match the condition before the first transaction completes.

Example Scenario

1. Suppose we have a table called items with the following records:

   | id | name | | --- | --- | | 90 | Item A | | 102 | Item B |

   • Transaction A starts: Transaction A executes the following query:

       SELECT * FROM items WHERE id > 100;
     

     The result set for Transaction A at this point would be:

       | id  | name   |
       |-----|--------|
       | 102 | Item B|
     

   • Transaction B starts: While Transaction A is still running, another session (Transaction B) can insert a new record:

       INSERT INTO items (id, name) VALUES (101, 'Item C');
     

     Transaction B successfully inserts this row because there is no lock on the gap between id 90 and id 102 that would prevent this action. Now, the items table looks like this:

     | id | name | | --- | --- | | 90 | Item A | | 101 | Item C | | 102 | Item B |

   • Transaction A continues: If Transaction A re-executes the same query:

       SELECT * FROM items WHERE id > 100;
     

     The result set will now include the newly inserted phantom row:

       | id  | name   |
       |-----|--------|
       | 101 | Item C|
       | 102 | Item B|
     

     This shows that the data has changed during the transaction, violating the isolation property.

   • To prevent such situations, InnoDB employs next-key locking.

Phantom No More: The Mechanism of Next-Key Locking

A next-key lock is a combination of a record lock on the index record and a gap lock on the gap before the index record.

Record locks

A record lock is a lock on an index record. For example, SELECT c1 FROM t WHERE c1 = 10 FOR UPDATE; prevents any other transaction from inserting, updating, or deleting rows where the value of t.c1 is 10.

Record locks always lock index records, even if a table is defined with no indexes. For such cases, InnoDB creates a hidden clustered index and uses this index for record locking.

Gap locks

A gap lock is a lock on a gap between index records, or a lock on the gap before the first or after the last index record.

For example, SELECT c1 FROM table WHERE c1 BETWEEN 10 and 20 FOR UPDATE;

prevents other transactions from inserting a value of 15 into column t.c1, whether or not there was already any such value in the column, because the gaps between all existing values in the range are locked.

A gap might span a single index value, multiple index values, or even be empty.

So InnoDB employs next-key locking. This technique involves both locking the actual index rows and the gaps between them. Here's how it works in this scenario:

1. When Transaction A runs: InnoDB locks the index records it scans and the gaps immediately before them. So, when it checks for ids greater than 100, it locks:

   • The row with id 102 (exclusive or shared lock).

   • The gap before id 102 (to prevent inserts of values like 101).

   • The gap after the last record if it’s scanning beyond the highest id.

2. Locks applied:

   • Lock on record with id 102: This prevents other transactions from modifying or deleting this record.

   • Lock on the gap before 102: This prevents Transaction B from inserting id 101 while Transaction A is active.

So If Transaction B tries to insert the id 101 while Transaction A is still executing, it will be blocked because the gap lock prevents this insertion. As a result, Transaction A will see only the original rows (90 and 102) when it re-executes the query, thus preventing phantom reads.

Conclusion

Concurrency issues, like race conditions and phantom reads, can wreak havoc in high-transaction environments, leading to data inconsistencies and unexpected behavior. By implementing appropriate locking mechanisms, such as row-level and next-key locking in MySQL's InnoDB engine, we can significantly enhance the consistency and integrity of our data.

In summary, Table-level locks provide simplicity and control but at the cost of reduced concurrency. On the other hand, row-level and next-key locking offer a more granular approach, making them better suited for high-concurrency scenarios. Choosing the right locking strategy requires a deep understanding of the application's requirements and the trade-offs involved.