UUID() is a non-deterministic function and breaks with replication

Hi, patch looks interesting.

Dumb question: is that version 4 random UUID collision proof?

cafuego's patch fails with the PECL extension installed as there's already a uuid_is_valid() function provided by the extension. I'll reroll a patch with a modified version of the function.

Rerolled patch containing cafuego's code and my modifications to the validation function.

Hi, you didn't reply to my dumb question: is that version 4 random UUID collision proof?

@recidive - sorry, meant to reply to your comment before, but didn't. I'm actually inclined to believe that this UUIDv4 generation function is not collision proof. If I understand the specification properly, Version 4 UUIDs require that the digits be created by a cryptographically secure random number generator. cafuego's patch uses the UUID extension if available; if not, it generates UUIDv4s using code in comment #65879 on uniqid. In the second case, the code uses mt_rand(), an implementation of the Mersenne Twister, which is not cryptographically secure.

I think part of the problem is making a cross-platform UUID generator implementation that is collision-proof. If you look at some of the other comments on uniqid, other people have implemented UUIDv4 generators that read directly from /dev/urandom, which isn't available on Windows.

I guess there are two ways to approach this - put the burden on the web server, or put the burden on the database server. The former is seeming to be more complicated. In the case of the latter, both MySQL and Postgres have UUID generation functions, but they're different. We could create a wrapper function that calls the proper function depending on the database platform being used. Part of the problem with statement-based replication in the case of this module is that functions like uuid_user() and uuid_nodeapi() call MySQL's UUID() function within an INSERT query. If we had another function that ran "SELECT UUID();" on MySQL, and the return value was passed to the INSERT query, I believe we would not have the same problems with statement-based replication.

Here is a patch that take care about UUID() compatibility with PgSQL (need tests from users of PgSQL).

The uuid_uuid() function returns a valid UUID, created with MySQL or PgSQL if version > 8.4 ; or created with the function suggested by anarchivist (http://drupal.org/node/502622#comment-1973150) - I changed spaces into dash to have the same result as with MySQL UUID().

So the replication problem no more exists by the way. The main disadvantage of this uuid_uuid() function is it makes an additional query in database, but it allow support of PgSQL.

@B-Prod, as far as I can tell this patch does necessarily work for Postgres; in my understanding, PgSQL doesn't come with a native UUID generation function which therefore requires an extension of some sort. The uuid-ossp extension is available (as well as a few modules). This seems to be the option suggested by the Postgres community.

In addition, this whole thing is potentially made more complicated by the availability of a UUID datatype in PgSQL 8.3 and higher. We can get around this by just not worrying about how the UUID is actually stored in the DB (i.e. by casting it as a formatted string).

Couldn't we get this applied and then worry about postgres when there are some people who want to use it with postgres ...?

Actually, the uuid-ossp extension is available in PgSQL 8.4 but not enabled by default. So I created a new patch that use the anarchivist function if database type is PgSQL.

@B-Prod, yes, that's true, but uuid-ossp is also available for PgSQL 8.3. However, uuid-ossp does not provide a UUID() function; the comparable query to "SELECT UUID();" on MySQL would be "SELECT UUID_GENERATE_V4();" on Postgres.

Any progress here? I find myself in need of a good non-SQL-derived UUID operation myself and the patch in #12 looks like just what I want. I'm probably going to just steal the code but I hope it gets into a stable release of this module soon so I can just make a dependency. :-)

@Crell, does that means you tested and confirm the patch in #12 works and it's RTBC?

I'm probably taking a shot at cleaning up some things and tagging a stable release soon. Please help whenever you can.

Ok, I tested the patch and found a problem with it in uuid_sync() function. Since it's using INSERT INTO ... SELECT ... syntax, we can't pass a single UUID to it as it'll set the same UUID for all items it's generating.

We need another approach to this. We can SELECT, loop and INSERT, but this won't scale well for tons of records. Maybe we need batch API implemented for this?

This may be too much for this patch. So maybe we can implement this with simple loop and file a separate issue for batch API implementation.

What do you think?

I want this patch commited ASAP so I can tag a beta release.

I have been using this code in production for over a year now, and it's quite stable.

I'm attaching patch against DRUPAL-6--1 branch. HEAD is not in sync, so patches should be taken against DRUPAL-6--1. I also changed the order to mysql function first and added the taxonomy part.

I didn't test the patch directly, but I copied the uuid_uuid() function to my own code and it generated something that looks unique. :-) I have not verified it mathematically or anything like that.

Is performance really a big concern? We're generating UUIDs. That's not a critical path operation 99% of the time, so a few microseconds difference doesn't matter. There's plenty of other places to optimize.

Also note that the copyright portion of the docblock needs to be removed. Hell, I'd almost like to see that function in core, but I suppose that's probably asking too much. :-)

Ok, at this point what we need to decide is how we do to sync up UUIDs. The way it's coded in the patch don't work, and generate duplicates. Should we simple do SELECT -> loop -> INSERT?

What do you mean sync up? If the UUID is not generated by the DB as part of a larger insert/update statement then it is only run once, on the master. Problem solved. IMO we should bypass the DB anyway and just use the PECL module / user-space clone of it and be done with it so that we're using the same algorithm.

Check uuid_sync() it is called in hook_enable() for generating UUID for content you already have.

It currently calls queries like that:

db_query("INSERT INTO {uuid_node} SELECT n.nid, UUID() FROM {node} AS n WHERE n.type = '%s' AND NOT EXISTS (SELECT nid FROM {uuid_node} WHERE nid = n.nid)", $type);

the proposed change for change this for using uuid_uuid() instead of UUID() is:

db_query("INSERT INTO {uuid_node} SELECT n.nid, '%s' FROM {node} AS n WHERE n.type = '%s' AND NOT EXISTS (SELECT nid FROM {uuid_node} WHERE nid = n.nid)", uuid_uuid(), $type);

This will generate a lot of duplicates, since the uuid_uuid() function will be called only once, thus will generate only one UUID that will be used for inserting all missing rows.

That's the part that needs fixing in the patch, we should just change that to a loop, or implement batch API.

Thanks cafuego for moving this along.

I took another crack at this and have replaced your approach for avoiding custom queries when syncing nodes with this (untested):

  $types = variable_get('uuid_automatic_for_nodes', array());

  // Remove disabled node types.
  $types = array_filter($types);
  if (!empty($types)) {
    $placeholders = db_placeholders($types, 'varchar');

    // Nodes.
    $result = db_query("SELECT nid FROM {node} WHERE type IN (" . $placeholders . ") AND nid NOT IN (SELECT nid FROM {uuid_node})", $types);
    while ($item = db_fetch_object($result)) {
      db_query("INSERT INTO {uuid_node} (nid, uuid) VALUES(%d, '%s')", $item->nid, uuid_uuid());
    }

    // Revisions.
    $result = db_query("SELECT nr.vid AS vid FROM {node_revisions} AS nr INNER JOIN {node} n ON nr.nid = n.nid WHERE n.type IN (" . $placeholders . ") AND nr.vid NOT IN (SELECT vid FROM {uuid_node_revisions})", $types);
    while ($item = db_fetch_object($result)) {
      db_query("INSERT INTO {uuid_node_revisions} (vid, uuid) VALUES(%d, '%s')", $item->vid, uuid_uuid());
    }
  }

Do you think this will work? Can you test syncing UUIDs with this new patch, so we can commit it and move on?

Are you sure $types variable has more values than the types which have UUID generation enabled? Can you paste a dump of $types here for us to explain?

Also, have you tested the indexes -> unique keys upgrade path?

Thanks again.

Commited to DRUPAL-6--1 branch.

I've also tagged a beta1 release that should be packed soon.

Thanks!