Hack 66. Use Optimistic Locking

You have a complicated transaction that needs multiple SQL statements, and you want to be concurrency safe with good performance, but you also want to use program-level locking.

Consider, again, a booking system for a small theatre. This theatre has six seats, all in a single row. People phone one of two possible operators (called X and Y) to check seat availability and make bookings:

CREATE TABLE seat (
 chairid INT,
 updateid INT,
 booked varchar(20) )
ENGINE=InnoDB;

INSERT INTO seat (chairid,updateid,booked) VALUES (1,1,NULL);
INSERT INTO seat (chairid,updateid,booked) VALUES (2,1,NULL);
INSERT INTO seat (chairid,updateid,booked) VALUES (3,1,NULL);
INSERT INTO seat (chairid,updateid,booked) VALUES (4,1,NULL);
INSERT INTO seat (chairid,updateid,booked) VALUES (5,1,NULL);
INSERT INTO seat (chairid,updateid,booked) VALUES (6,1,NULL);

You need to specify ENGINE=InnoDB only if you are using MySQL and InnoDB is not the default; delete this phrase (but keep the semicolon) on all other platforms.

Be sure to run SHOW WARNINGS after you issue the CREATE TABLE statement. If MySQL insists on using the MyISAM table type, your version of MySQL was not compiled with InnoDB support.

Customers call either operator X or operator Y to ask to book a number of seats. For instance, a customer could ask for three seats together. With a SERIALIZABLE isolation level, conflicting bookings generated simultaneously from A and B would produce a transaction rollback, but for performance reasons, the default isolation level is usually less than SERIALIZABLE (for instance, READ COMMITTED). Thus, you must be careful to ensure that bookings are not lost (see "Determine Your Isolation Level" [Hack #64]).

You could rely on pessimistic locking [Hack #65], but optimistic locking may result in more successful transactions per second.

With optimistic locking, you introduce a new column (updateid in this example) to keep track of rows that have changed. You need to note the values of the updateid column when you check availability with SELECT, and then make sure that they are unchanged when you update.

In another example, say operator X requires a reservation for two seats together, while simultaneously operator Y requires three seats.

To determine the availability of three seats together you can use:

mysql> SELECT s1.chairid AS firstId,s1.updateid
 -> FROM seat s1 CROSS JOIN seat s2,integers
 -> WHERE s2.chairid = s1.chairid+i-1
 -> AND s2.booked IS NULL
 -> AND i<=3
 -> GROUP BY s1.chairid
 -> HAVING count(*) = 3;
+---------+----------+
| firstId | updateid |
+---------+----------+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
+---------+----------+
4 rows in set (0.00 sec)

This result shows that three seats together are available, starting at seat 1, or 2, or 3, or 4. So, if the customer wanted to book starting at seat 1, you would have to book seats 1, 2, and 3.

Running the same query for two seats produces the following:

+---------+----------+
| chairid | updateid |
+---------+----------+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
+---------+----------+

If you simply started making changes in parallel, you could easily run into lost updates, which in turn would mean double bookings. If there were a large number of seats and you used an algorithm to choose a random starting seat, clashes would be rare. However, this hack assumes that both X and Y are going to try to book their seats starting at chairid 1.

With optimistic locking, you use the updateid column. In both queries, the updateid is returned and must be used in any subsequent UPDATE statement (in this example, the updateid starts at 1). If the updateid value is unchanged between the SELECT and the subsequent UPDATE, the UPDATEs have been applied successfully. When a row is changed, the updateid for that row is incremented. So, if operator X, booking two seats, does the following:

mysql> UPDATE seat SET booked='X',updateid=updateid+1
 -> WHERE chairid >= 1 AND chairid <=2
 -> AND updateid = 1;
Query OK, 2 rows affected (0.00 sec)
Rows matched: 2 Changed: 2 Warnings: 0

the response is Changed: 2, which is the right number of seats, so this transaction can be completed by COMMIT. If operator Y now books the three seats starting at chairid 1:

mysql> UPDATE seat SET booked='Y',updateid=updateid+1
 -> WHERE chairid >= 1 AND chairid <=3
 -> AND updateid = 1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1 Changed: 1 Warnings: 0

the response is Changed: 1. It should have updated 3, but two of the rows to be updated had an unexpected updateid. A collision must have happened, and the transaction can be rolled back and the whole process started again:

mysql> ROLLBACK; 
mysql> SELECT s1.chairid,s1.updateid 
 -> FROM seat s1 CROSS JOIN seat s2,integers 
 -> WHERE s2.chairid = s1.chairid+i-1 
 -> AND s2.booked IS NULL 
 -> AND i<=2 
 -> GROUP BY s1.chairid 
 -> HAVING COUNT(*) = 2; 

+---------+----------+
| chairid | updateid |
+---------+----------+
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
+---------+----------+
3 rows in set (0.00 sec)
 Note that chairid=1 is now not a possible starting point, only 3, 4 or 5 
 are available 
mysql> UPDATE seat SET booked='Y',updateid=updateid+1 
 -> WHERE chairid >= 3 AND chairid <=6 
 -> AND updateid = 1; 
Query OK, 4 rows affected (0.02 sec)
Rows matched: 4 Changed: 4 Warnings: 0 (successful booking) 
mysql> COMMIT; 

You need to execute a ROLLBACK only if there was a conflict in concurrent transactions. But with a good approach to selecting the starting seat, conflicts will be rare. In turn, performance will be higher than an approach that uses SERIALIZABLE mode.