UUID collisions

Question

Has anybody done any real research on the probability of UUID collisions, especially with version 4 (random) UUIDs, given that the random number generators we use aren't truly random and that we might have dozens or hundreds of identical machines running the same code generating UUIDs?

My co-workers consider testing for UUID collision to be a complete waste of time, but I always put in code to catch a duplicate key exception from the database and try again with a new UUID. But that's not going to solve the problem if the UUID comes from another process and refers to a real object.

Answer 1

Wikipedia has some details:

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

http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

But the probability only holds if the bits are perfectly random. However, the RFC http://tools.ietf.org/html/rfc4122#page-14 linked in the other answer defines this for version 4:

"4.4. [...] The version 4 UUID is meant for generating UUIDs from truly-random or pseudo-random numbers. [...] Set all the other bits to randomly (or pseudo-randomly) chosen values."

This pretty much allows anything from the xkcd random generator http://xkcd.com/221/ to a hardware device using quantum noise. The security considerations in the RFC:

"6. Distributed applications generating UUIDs at a variety of hosts must be willing to rely on the random number source at all hosts. If this is not feasible, the namespace variant should be used."

I read this as: You're on your own. You're responsible for your random generator within your own application, but this and anything else is based on trust. If you don't trust your own ability to correctly understand and use the random generator of your choice, then it is indeed a good idea to check for collisions. If you do not trust the programmer of the other processes, then check for collisions or use a different UUID version.

Answer 2

You should certainly detect if a collision occurs, and your application should throw an exception if it does happen. E.g. if the UUID is used as primary key in the database, then the database should throw an error when inserting a colliding ID.

However, I would believe that writing code for generating a new UUID in the case of a collision and trying again to be a waste of time. The chance of a collision occurring is so small that throwing an exception would be a perfectly reasonable way of dealing with it.

Remember, it is not only a waste of your own time writing the code, but it also makes the code more complex, making it more difficult for the next person to read, for almost no gain at all.

Answer 3

The issue you have is that if you use a "Random number generator" and you don't know how random that generator is, then the probability of collision is actually unknown. If the random number generators are correlated in some way, the probability of collision may dramatically increase - possibly many, many orders or magnitude.

Even if you have a very small probability of collision, you have a fundamental problem: The probability is NOT 0. This means that a collision WILL eventually occur, they just won't occur very often.

The more frequently you generate and use the UUIDs the sooner that collision is likely to be seen. (generating 1 a year means a longer waiting time than generating a million per second, all other things being equal).

If that probability is finite, unknown, and you use a lot of UUIDs then you need to consider the consequences of a collision. If it is not acceptable to throw an exception and shut down a business application, then don't do it! (Examples off the top of my head: "It's OK to shut down the web server in the middle of updating a library checkin... it won't happen often" and "It's ok to shut down the payroll system in the middle of doing the pay run". These decisions may be career limiting moves.)

You may have a worse case though, again depending on your application. If you test for presence of a UUID (ie, do a lookup) and then make a new one if one is not already there - which is a common enough kind of thing to do - then you may find you are linking records or making relationships, when in fact you are hooking up 2 things via a UUID that should not be hooked up. This is something where throwing an exception won't solve anything and you have an undetectable mess created somewhere. This is the kind of thing that leads to information leakage and can be very embarrassing. (ex: Log in to your bank and find you can see the balance of somebody elses account! Bad!)

Summary: you need to consider the way your UUIDs are used, and the consequences of a collision. This determines if you should take care to detect and avoid collisions, take some simple action in the event of a collision, or do nothing. A simple, single, one-fits-all solution is likely to be inappropriate in some circumstances.

Answer 4

I've tested it once using a quite simple (brute force) program that generated 10 million UUID-s and I haven't experienced collision.

The UUID RFC says that the UUID is not just a bunch of (pseudo) random numbers.

Answer 5

You're worried about the imperfection of PRNG's. That's not really necessary in this case.

Even the older, extremely poor Linear Congruential PRNG's such as RANDU still have a period of 2^29, discounting the effect of seeding (which is almost always done with the clock). Since you need 122 bits for a type-4 UUID, that translates into 5 calls of RANDU, or 4 for a decent LCG. For RANDU, this means that you can skip the top bit and lowest 6 bits (which are less random), and use only the 5*25 most random bits of each number.