Robust MySQL db_next_id() without LOCK TABLES

I know this issue has a long and messy history, but I really believe that it can be fixed in a robust and sensible way. Since this involves some nasty concurrency issues I'll add a bit of background here. Many of you will know this background already, but its probably helpful to gather in one place.

1. The problem

Drupal uses sequences to get table id, to be used like this:

  $id = db_next_id('{example}_xid');
  db_query("INSERT INTO {example} (xid, data) VALUES (%d, '%s')", $id, $data);

The id returned by db_next_id() must be unique. But Drupal is a concurrent system, so this must work even if two processes try to run it at the same time.

The current MySQL implementation uses table locks, like this

  db_query('LOCK TABLES {sequences} WRITE');
  $id = db_result(db_query("SELECT id FROM {sequences} WHERE name = '%s'", $name)) + 1;
  db_query("REPLACE INTO {sequences} VALUES ('%s', %d)", $name, $id);
  db_query('UNLOCK TABLES');
  return $id;

The LOCK/UNLOCK prevents a concurrent process slipping in between the SELECT and REPLACE: without this, a concurrent process may end up with the same ID.

But some hosts do not allow LOCK TABLES. People don't like having to change hosts just because Drupal tells them to, and I wonder how many people have used Another CMS because it doesn't work on their hosting company. Or some posters report just taking out troublesome LOCK TABLES command and say they've not seen any problems so far. Hmm.

In passing, there is another potential problem with the current method: it is not robust against intermittent database query errors (these can happen - its usually on another machine after all). Consider this:

1. The SELECT query fails due to an intermittent failure.
2. We don't notice.
3. $id gets set to NULL + 1 = 1. Oops.
4. REPLACE query overwrites sensible sequence number with 1. Oh dear.
5. db_next_id() returns 1
6. Caller attempts to insert record with id 1, either failing or overwriting records starting from 1.
7. Subsequent records overwrite 2, 3, ...

To fix this properly we need to allow db_next_id() to tell the caller when it failed, so we'll do that too.

2. Why bother to fix it?

I believe this should be fixed, because

• LOCK TABLES is a barrier for many potential Drupal users (see end for discussions)
• There are some bad solutions about (e.g. delete the LOCK statements). If they break, Drupal will get the blame.
• There is a clean solution that is concurency-safe without locks (its just a bit conceptually tricky).
• The solution is more efficient, using only one UPDATE (and a mysql_insert_id()) in normal operation in place of LOCK/SELECT/REPLACE/UNLOCK sequence.
• It is a drop-in replacement for db_next_id(), with no need to change any other code or tables
• It does not rely on MySQL 4 features (e.g. SELECT FOR UPDATE).
• We can fix a potential intermittent database query failure bug in the process.

I'm going to spend a little time going over the approach. Sorry for the length, but I hope it will be helpful for some readers who may want to use the patch in the meantime.

3. The approach

The approach is based on that suggested by smoogle in http://drupal.org/node/34455. OK I thought of it too but smoogle got there first :-)

As a starting point, let's take a look at the MySQL manual's suggested way to implement sequences in http://dev.mysql.com/doc/refman/4.1/en/information-functions.html:

If expr is given as an argument to LAST_INSERT_ID(), the value of the argument is returned by the function and is remembered as the next value to be returned by LAST_INSERT_ID(). This can be used to simulate sequences:

1. Create a table to hold the sequence counter and initialize it:

mysql> CREATE TABLE sequence (id INT NOT NULL);
mysql> INSERT INTO sequence VALUES (0);

2. Use the table to generate sequence numbers like this:

mysql> UPDATE sequence SET id=LAST_INSERT_ID(id+1);
mysql> SELECT LAST_INSERT_ID();

The UPDATE statement increments the sequence counter and causes the next call to LAST_INSERT_ID() to return the updated value. The SELECT statement retrieves that value. The mysql_insert_id() C API function can also be used to get the value.

So LAST_INSERT_ID() is magic, and "pretends" to be an AUTO_INCREMENT column even if your table doesn't have one.

Modifying the MySQL method slightly for Drupal sequences, the core we need is

  db_query("UPDATE {sequences} SET id=LAST_INSERT_ID(id+1) WHERE name = '%s'", $name);
  return mysql_insert_id();

The update is an atomic operation, so there is no danger that a concurrent process will interfere with it.

This is not quite all, since Drupal only creates sequences as needed. An easy way to do this is to prepend the update with an INSERT IGNORE:
db_query("INSERT IGNORE INTO {sequences} VALUES ('%s', %d)", $name, 0);
If the sequence doesn't exist, it creates it with value zero. If it exists already, it does nothing, and the IGNORE nicely suppresses the error that we would have got.

We can actually do this a little more efficiently, since we only have to create the sequence the first time a sequence is ever used. We therefore do the following:

1. Attempt the update first. If that works, we're done.
2. If the update failed, use INSERT to create the table and try again.

To allow for a concurrent process doing this at the same time, we retain INSERT IGNORE since the other process may actually create the sequence for us if it gets between steps 1 and 2 above.

So the almost-final solution (similar to http://drupal.org/node/34455) is

 function db_next_id($name) {
  $name = db_prefix_tables($name);
  db_query("UPDATE IGNORE {sequences} SET id=LAST_INSERT_ID(id+1) WHERE name = '%s'", $name);
  if (!db_affected_rows()) {
    db_query("INSERT IGNORE INTO {sequences} VALUES ('%s', %d)", $name, 0);
    db_query("UPDATE {sequences} SET id=LAST_INSERT_ID(id+1) WHERE name = '%s'", $name);
  }
  return mysql_insert_id();
}

Note that intermittent database errors should never cause id to be reset, since it will either be incremented or unchanged (the INSERT can never overwrite an existing row). However, we should check the second UPDATE to make sure it worked, since if not we should return an error code to the user

    $ok = db_query("UPDATE {sequences} SET id=LAST_INSERT_ID(id+1) WHERE name = '%s'", $name);
    if (!$ok) {
      return false;
    }

This adds a new functionality to db_next_id, i.e. that it returns FALSE on failure, so can be used as follows:

    $id = db_next_id('{example}_xid');
    if (!$id) {
       // Failed to get an ID, so take a suitable error action
       return false;
    }
    // Got the id OK, so insert the record
    db_query("INSERT INTO {example} (xid, data) VALUES (%d, '%s')", $id, $data);

This is almost backward compatible with current behaviour: if you don't check for failure and plough on regardless, you just attempt to insert with id=0 (instead of id=1 on failure, and subsequently 2, 3, ...).

4. The patch

I've attached a patch for database.mysql.inc for CVS HEAD that incorporates this solution. I have tested this on a new CVS install as of 5 Aug 2006, creating the first "story" to ensure the branch works. If this is OK to incorporate, a directly similar solution should also work for database.mysqli.inc, and also for Drupal 4.7, as far as I can tell.

5. Related posts & discussions

This has a long history of both interesting and dangerous suggested solutions. In case anyone is interested, here are a few:

• Recent (13 July 2006) issue raised for 4.7.2 http://drupal.org/node/73523
• Changing the sequence table and using AUTO_INCREMENT with single sequence for all objects http://drupal.org/node/55516
• Changing the useage of db_next_id() http://drupal.org/node/49836
• More about Lock Tables http://drupal.org/node/40774
• Possible solutions, including removing the locks and hoping for the best(!) http://drupal.org/node/44023
• 18 Oct 2005: Proposed solution from smoogle that does the job http://drupal.org/node/34455
• Patch and discussion for 4.6 http://drupal.org/node/21439
• Early post about the issue http://drupal.org/node/7315
• Another long discussion http://drupal.org/node/1190
• Possible use of AUTO_INCREMENT instead of sequences at http://drupal.org/node/38585 and on the mailing list at http://lists.drupal.org/archives/development/2005-12/msg00291.html
• MySQL Manual with suggested sequence method http://dev.mysql.com/doc/refman/4.1/en/information-functions.html
• MySQL Manual on mysql_insert_id() http://dev.mysql.com/doc/refman/4.1/en/mysql-insert-id.html (Note that 4th bullet point is a typo, and should read "UPDATE statements that generate an AUTO_INCREMENT value by updating any column to LAST_INSERT_ID(expr)"

I hope this is useful,

Mark.