Make sure new UUIDs are unique

I think it's important to mention one thing: The bug described (#895622: user warning: Duplicate entry in uuid_node_revisions) is about two uuids being inserted into a column of a db table whose column has been defined as unique. The error is happening upon updates to published revisions, which means that this is not an issue of a new uuid being generated that happens somehow by chance to conflict with one already generated. Published edits on a revision maintain the same revision_uuid.

The source of the problem has to do with the logic of the updates. I address that in the above mentioned thread with a suggestion that previous entries for that vid be deleted before inserting any rows.

That said, I do see a utility for a "uniqueness check." The sad fact is that even with the theoretical possibility of a uuid conflict happening is extremely minimal, perhaps it *could* happen. The problem is that the uuid is intended to be a "universal" unique identifier, so the uniqueness check should not just be checking node revisions for uniqueness, or node uuids, but also every comment uuid, taxonomy uuid etc etc. Only if none of those items have the same uuid, should the generated one be considered unique. in other words, the point is to label every object in your system uniquely, not just within types.

Thus this function would have to be expanded almost to the point of non-usability in order for it to be "usable."

@arski, @klktrk UUIDs are also intended to be "unique" across domains, i.e. it needs to identify a single object created by a single computer around the globe. Like I said previously, it should describe a single CPU cycle made by a single machine in the world.

We can't ensure that a random UUID is unique in the world, but we can do this locally. Checking for this in all tables, a query per table, looks infeasible to me. Adding another table may be an alternative, but not a good one as this tends to be huge and slow. If we had this in a single table we should be storing uuids for objects in that table anyway.

I think it's possible tough to do a check for duplicates on a single query across all uuids tables, but that may be costly, thus may be optional.

That said, we should enforce check for duplicates uuids for the same objects and make the cross check optional. What do you think?

This is a good discussion.

Theoretically, it's possible that someone will experience a uuid conflict.

Theoretically, it should also be "impossible."

The real world "bug" that led to this discussion is that an update of a published revision tries to insert the same uuid into the revision table. That's because revisions remain the same through many edits, as long as the status of the revision is "published." Therefore, it maintains (correctly) the same uuid, and it can't be reinserted.

The real world, practical, solution, is to either delete any preexisting rows for that revision before insertion, or try do to an update, and if it fails, do an insertion. The patch I'm working on addresses this.

I think a huge lookup table is, from a CS point of view, the "right" solution, but from a scalability point of view, it could quickly turn into a nightmare. Aggregate a couple hundred thousand node rows, a few more hundred thousand comments rows and tens of thousands of users, and even an indexed lookup will slow down the load op for every node/user/comment loaded.

AFAIK the people behind the idea of the UUID never created a universal repository against which to check for uniqueness of every single entity ever created. They seem to have been satisfied with the theoretical impossibilities, and felt like there was no need to authoritatively be able to demonstrate that no two items share the same uuid. Therefore, I think we would be over-engineering things to try to do that here. Let's just fix the actual experienced problem, published node updates where the uuid and/or revision ids clash because the row already exists.

so, I don't really get why you are trying to relate this so hard to that other bug alone (which is not the topic of this issue anyway)

I'm not relating it to that bug randomly. If you remember, you started this thread in response to that bug :-)

The point I was making simply was, the only reason the issue of uniqueness came up was due to a design flaw whereby which revisions keep trying to be inserted with the same uuid. That's a bug, plain and simple, and while there is a committed patch for it, it's still not really conceptually resolved.

So, given that the user-experienced uuid clash should go away with a fix to that bug, and since we have no simple way of checking every uuid against all the uuid tables to guarantee uniqueness (unless we change the uuid schema to one table, which, unfortunately, I don't think the maintainers will ever go for), then we *don't* have any means of truly guaranteeing uniqueness.

Thus, this patch, in my opinion, since it doesn't really solve the problem of guaranteeing uniqueness (it simply guarantees hiding a possible duplicate key on insert from the user by generating a new uuid), is, *in actuality* an attempt at a bug fix rather than a uuid-uniqueness solution* [http://drupal.org/node/895622#comment-3484960]. The bug fix is better addressed simply by not updating revision uuids once generated. A patch that would really address the subject line of this thread would move all uuids into one table, or check uuids across tables. otherwise, what you're offering is a bug fix for the very issue you keep wishing I would stop mentioning ;-)

* For reference, please see your own comment above:

If there is a warning, the query generates a new UUID and tries again.

You'll also notice that no one has ever reported a uuid clash against any other table than uuid_node_revision, which indicates that this is not truly a uuid-clash issue; it's a bug in the node revision update logic.

The problem of uniqueness is about generating different uuids, and that part is working perfectly afaik.
The problem of duplicate entries in the database is not that uuid is not unique, it is that a new uuid is not being generated for a different node revision id, and that should not go in.

UUID is by definition, 'collision-less', that is the purpose of the generation algorithm.

Actually: http://en.wikipedia.org/wiki/Universally_unique_identifier

The intent of UUIDs is to enable distributed systems to uniquely identify information without significant central coordination. Thus, anyone can create a UUID and use it to identify something with reasonable confidence that the identifier will never be unintentionally used by anyone for anything else. Information labeled with UUIDs can therefore be later combined into a single database without needing to resolve name conflicts.

So.. http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_p...

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion,[25] that means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

What willl be exactly the fix provided by this issue?

Now lets move into the patch..

 $result = db_query("SELECT uid FROM {users} WHERE uid NOT IN (SELECT uid FROM {uuid_users})");

I wonder what will happen to system's memory when runing this query in a site with 200k entries in the uuid_users table or even more? Nobody tested? This "and not in" is used very often in this module, not only for users, also for nodes, comments, and taxonomy.

If this 'additional validate check' to make sure uuid is not in database should go in even considering the odds, then arski's comment and #935998: Normalize the UUIDs into one table should be considered. Having a single uuid database and associated bundles (right now, 'node' table does this for the content 'type' attribute and nobody complains :) ) is the way to go to perform this database search before accepting the uuid.

so, I have to ask again because I still don't understand the point of the issue: What willl be exactly the fix provided by this issue? a patch for hook_uuid? a database validation of uuid uniqueness? both?

(Note that hook_uuid() was just a random selection from my mind)

mm Arski, I didn't mean they were introduced by the patch, I'm just providing arguments for both sides of the discussion. In fact, I was about to also to state that currently, uuid_is_valid() might take care of this 'uniqueness' verification (depending what do you think _is_valid_ means), but I felt that doing so I would deviate the conversation, so I just skipped that. Actually, current module design is more prone to return NULL as uuid than to generate a collision, as the module has no logic involved in generating a new uuid if the new one is not valid.

Sorry if you thought I was just feeding the trolls, I never tried to do that. The critic is not about the patch, it should go to the issue in any case. What is being discussed diferent in this issue not being discussed in others already?

I totally agree and will support the #902176: Allow admins to select the desired UUID generation method, and also the single big table idea. But probably to achieve that, IMO, uuid module should only focus on 'uuid providing' and forget about attaching it (delegating this to another module) to site 'entities'.

I don't get the point about verifying the uuid uniqueness only for the site, as long as export/import operations still can be crashed by uuids generated in other sites by other methods in other time. I understand we need some kind of safety in this uniqueness, but not sure how much overload in checks should we put in the module for something that by design should not happen, or may happen by other parties that we can't control.

Here the function I modified to check if the uuid is unique:

/**
* Determines if a UUID is valid and unique
*/
function uuid_is_valid($uuid) {

    $tables = array('node',
                    'node_revisions',
                    'comments',
                    'term_data',
                    'users',
                    'vocabulary'
    );

    foreach ($tables as $table) {
        $table = "uuid_" . $table;
        $exists |= db_result(db_queryd('SELECT 1 FROM {%s} WHERE uuid = "%s"', $table, $uuid));
        }

    $exists |= !preg_match('/^[A-Fa-f0-9]{8}-[A-Fa-f0-9]{4}-[A-Fa-f0-9]{4}-[A-Fa-f0-9]{4}-[A-Fa-f0-9]{12}$/', $uuid);

    return (bool) $exists;
}

What do you think ?

But I would preffer to go the Drupal way, with patches. Having the fork in github Pol might help, but is very dificult to track and manage changes. I don't know what is the code difference now between github and Drupal's cvs versions: don't know the changes, and don't know the underneath rationale.. using issue queue and patches can be slower, but things can have some kind of consensus.

I'm unsure that uuid_is_valid should check the existence in the db, I'd wrap, we do need a function to verify that uuid format is valid, regardless being saved, used or not.

Actually, $exists is uninitialized, doing OR operations can't be safe. Does this work really? I mean, if uuid exists it is returned as valid regardless the format validation, even if this MUST BE A NEW UUID for a new entry (e.g. node).. Am I missing something?

Anyway, a patch is prefered, this way we can apply and test the changes. I agree with the rest of comments from Arski.

By the way, Arski, any clue about how can we work together to get this issue fixed? right now the selection methods is a great idea IMO, but we don't even have a list of available methods (out of the module) to create a good sorting criteria.

Given the probability of a conflict, I think the performance impact on the lookup is too great. For the D7 port there is an API which allow contrib modules to easily support UUID, so the number of tables required to check for the a UUID conflict (which is likely to never exist) is very high.

I'll see if I can find the time to create a test to see how long it takes before I can trigger a conflict using just a simple table and PHP code.

Drupal 6 core is no longer supported. We are no longer supporting 6.x-1.x versions of this module. I am closing this issue as won't fix.