Handeling Latency in MySQL Transactions

The Problem

I'm trying to figure out how to correctly set up a transaction in a database, and account for potential latency.

The Setup

In my example I have a table of users, keys, where each user can have multiple keys, and a config table that dictates how many keys each user is allowed to have.

I want to run a stored procedure that:

figures out if the given user is allowed to request a key.
get an available, unclaimed key .
attempts to redeem the key for the given user.

the pseudocode for the procedure would be:

    START TRANSACTION
(1)     CALL check_permission(...,@result);
        IF (@result = 'has_permission') THEN
(2)         SET @unclaimed_key_id = (QUERY FOR RETURNING AVAILABLE KEY ID);
(3)         CALL claim_key(@unclaimed_key_id);
        END IF;
    COMMIT;

The problem that I am running into, is that when I simulate lag after step 1, (by using SELECT SLEEP(<seconds>)), it's possible for a given user to redeem multiple keys when they only have permissions to redeem one, by running the procedure in multiple sessions before the first procedure has finished its sleep (which again, is to simulate lag)

Here is the code for the Tables and the Procedures (note: for the small example I didn't bother with indexes and foreign keys, but obviously I use those on the actual project).

To see my issue just set up the tables and procedures in a database, then open two mysql terminals, and in the first run this:

CALL `P_user_request_key`(10,1,@out);
SELECT @out;

And then quickly (you have 10 seconds) in the second run this:

CALL `P_user_request_key`(0,1,@out);
SELECT @out;

Both queries will successfully return key_claimed and User Bob will end up with 4 keys assigned to him, although the max value in config is set to 3 per user.

The Questions

What is the best way of avoiding issues like this? I'm trying to use a transaction but I feel like It's not going to help specifically with this issue, and may be implementing this wrong.
- I realize that one possible way to fix the problem would be to just encapsulate everything in one large update query, but I would prefer to avoid that, since I like being able to set up individual procedures, where each is only meant to do a single task.
The database behind this example is intended to be used by many (thousands) of concurrent users. As such it would be best if one user attempting to redeem a code doesn't block all other users from redeeming one. I'm fine with changing my code to just attempt to redeem again if another user already claimed a key, but it should absolutely not happen that a user can redeem two codes when they only have permission to get one.

You're off the hook for not wanting to encapsulate everything in one large query, because that won't actually solve anything either, it just makes it less likely.

What you need are locks on the rows, or locks on the index where the new row would be inserted.

InnoDB uses an algorithm called next-key locking that combines index-row locking with gap locking. InnoDB performs row-level locking in such a way that when it searches or scans a table index, it sets shared or exclusive locks on the index records it encounters. Thus, the row-level locks are actually index-record locks. In addition, a next-key lock on an index record also affects the “gap” before that index record. That is, a next-key lock is an index-record lock plus a gap lock on the gap preceding the index record. If one session has a shared or exclusive lock on record R in an index, another session cannot insert a new index record in the gap immediately before R in the index order.

http://dev.mysql.com/doc/refman/5.5/en/innodb-next-key-locking.html

So how do we get exclusive locks?

Two connections, mysql1 and mysql2, each of them requesting an exclusive lock using SELECT ... FOR UPDATE. The table 'history' has a column 'user_id' which is indexed. (It's also a foreign key.) There are no rows found, so they both appear to proceed normally as if nothing unusual is going to happen. The user_id 2808 is valid but has nothing in history.

mysql1> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql2> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql1> select * from history where user_id = 2808 for update;
Empty set (0.00 sec)

mysql2> select * from history where user_id = 2808 for update;
Empty set (0.00 sec)

mysql1> insert into history(user_id) values (2808);

... and I don't get my prompt back ... no response ... because another session has a lock, too ... but then:

mysql2> insert into history(user_id) values (2808);
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

Then mysql1 immediately returns success on the insert.

Query OK, 1 row affected (3.96 sec)

All that is left is for mysql1 to COMMIT and magically, we prevented a user with 0 entries from inserting more than 1 entry. The deadlock occurred because both sessions needed incompatible things to happen: mysql1 needed mysql2 to release its lock before it would be able to commit and mysql2 needed mysql1 to release its lock before it would be able to insert. Somebody has to lose that fight, and generally the thread that has done the least work is the loser.

But what if there had been 1 or more rows already existing when I did the SELECT ... FOR UPDATE? In that case, the lock would have been on the rows, so the second session to try to SELECT would actually block waiting for the SELECT until the first session decided to either COMMIT or ROLLBACK, at which time the second session would have seen an accurate count of the number of rows (including any inserted or deleted by the first session) and could have accurately decided the user already had the maximum allowed.

You can't outrace a race condition, but you can lock them out.