Hack 86. Set Up Queuing in the Database

You want to implement strict FIFO queuing using a table to store the queue state. You also want the queue to be fail-safe and reliable.

If you were to implement a queue in a programming language, with the possibility of multiple programs trying to manipulate the queue simultaneously, you might choose to use a file to hold the queue data and use file locking to serialize queue access. You can achieve the same effect in a pure database implementation.

You can implement a queue while still relying on the simplicity of autocommit, as long as all critical actions are started and completed in a single query. This is the approach we discuss here.

The linuxzoo site (http://linuxzoo.net) provides virtual Linux machines to Internet users. When a user visits, he must enter a queue for a machine. If we attempt to run too many virtual servers at the same time, the performance for all users suffers disproportionately, so we have to ration time on the machines. If, for instance, there were two possible virtual machines, the first two visitors would enter the queue and receive a machine immediately. Even when they receive a virtual machine, they remain in the queue until their session ends. The third user would enter the queue but would be told to wait until one of the two virtual machines became available.

To implement this queue in a database we need this queuing mechanism to be atomic, safe, and error resistant. The site is designed so that all users have to refresh their details once per minute to remain in the queue. A client-side script performs the refresh in the background, unless the user leaves the page.

The queue looks like Table 10-14.

Table 10-14. The queue table

Username	Position	LastChecked
Jennifer	1	2006-05-05 09:15
Allan	2	2006-05-05 09:17
David	4	2006-05-05 09:16
Laura	6	2006-05-05 09:15

Users Jennifer and Allan are at the head of the queue, so they have the two available virtual machines. All users must keep refreshing their LastChecked information or they will be kicked out of the queue. When someone leaves, the user with the lowest Position is considered to be at the head of the queue. New users are given a Position higher than all positions currently in the queue.

To join the queue:

INSERT INTO QUEUE SELECT 'Gordon',COALESCE(MAX(position)+1,0),
 CURRENT_TIMESTAMP
 FROM QUEUE;

This update is completely atomic and thus transaction safe.

The browser used by user Gordon visits linuxzoo every minute or so. This refreshes Gordon's queue entry and keeps him informed of his queue position. This updates the LastChecked value. The refreshing process must continue until Gordon is finished with the booking. These queries remove anyone who has not refreshed for 2 minutes:

DELETE FROM queue 
 WHERE CURRENT_TIMESTAMP > LastChecked + INTERVAL '2' MINUTE;

UPDATE queue 
 SET lastchecked = CURRENT_TIMESTAMP WHERE username = 'Gordon';

SELECT username FROM queue
ORDER BY position;

If the entry for Gordon is first or second, he gets to use one of the virtual machines. If he is third or more, he has to wait.

To manually leave the queue at any time all you need to do is:

DELETE FROM queue WHERE username = 'Gordon';

As long as each user joins, tests, and leaves in the method described, and uses the SQL statements shown in this hack in the order shown, this technique is safe and reliable.