Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
4  
The question was already answered on Stack Overflow: stackoverflow.com/questions/3038023/…, as shows the basic Google search: google.com/search?q=uuid+collision –  MainMa Jan 15 '12 at 13:20
1  
That question is about the specific algorithms used in SQL*Server, which quite definitely is NOT a version 4 (random). I'm asking about version 4 specifically. –  Paul Tomblin Jan 15 '12 at 14:49
    
Are you saying that SQL Server's implementation of the NEWID() function is not random? If so, do you have any sources to back up such a claim? Its output clearly looks like v4 UUIDs to me. NEWSEQUENTIALID() is decidedly not completely random, but that's its purpose: to generate UUIDs which work well (as well as UUIDs can, at least) as index keys. –  Michael Kjörling Jan 16 '12 at 8:54
    
I'm going by the answer to the linked question, which states that NEWID() contains some bits of the mac address, which makes it a V1 or V2 UUID, not a V4. –  Paul Tomblin Jan 16 '12 at 12:54
2  
This question appears to be off-topic because it is about something already discussed ad-nauseum on the internet, in books and especially on StackOverflow –  Jarrod Roberson Dec 31 '13 at 1:50
show 1 more comment

5 Answers

up vote 11 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Version 4, which is the one I'm asking about, pretty much is a bunch of random numbers, except the 6 bits which will be exactly the same in all of them. –  Paul Tomblin Jan 15 '12 at 14:51
6  
10 million isn't even a drop in the bucket. There's only a 1 in 3E30 chance of a collision. If you found one, I'd have advised you to rush out and buy a ticket in every lottery you can! –  Ross Patterson Jan 15 '12 at 14:59
    
@RossPatterson, what I was specifically wondering about is if you've got several hundred computers using the exact same psuedo-random algorithm on the same hardware dramatically increases the odds of collision. I suspect it would. –  Paul Tomblin Jan 15 '12 at 22:32
1  
@Paul - I'd have thought only if there's insufficient entropy in the initial seeding process - for example if the seed is only generated from the time of day, and all your machines started at very close to the same instant. I very much doubt that the seeding is that weak - it's even possible that hardware serial numbers are used, which of course would be unique for each machine. –  Steve314 Jan 15 '12 at 22:43
1  
Alas, seeding can be very weak. Linux systems are fond of seeding the PRNG from highly random sources (device driver activity, etc.), but in other environments, the standard is to use the current timestamp, which with enough machines in close time-sync, could be a problem. –  Ross Patterson Jan 16 '12 at 5:08
add comment

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.

share|improve this answer
1  
your UUID is only as good as your random generator. With a very (very) poor one collisions not only will occur but are inevitable. That said perhaps checking for duplicates at generation time would indeed be overkill, but expecting that the situation could occur and is, in my opinion, not so much to ask for. In some domain (healthcare for example) I think it is necessary to have code that catch such situations (perhaps as collision detection in the database). you would be surprised how much time I spent debugging situations that never happen. –  Newtopian Jan 16 '12 at 3:21
1  
I think I didn't make myself clear. I have updated the answer to be more explicit. –  Pete Jan 16 '12 at 8:06
add comment

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.

share|improve this answer
1  
"The probability (of collision) is NOT 0" Any finite-length sequence has this property. Even with a perfectly random v4 UUID, once you've generated 2^122 unique UUIDs (128 bits minus 4 bits version minus 2 reserved bits), the next one you generate is guaranteed to be a collision. Most likely you would hit a collision sooner than that. The bigger question is whether a collision after something like 5e36 repetitions is an issue, and that cannot be answered generally (though it's obviously possible to answer in each specific case), like you say in the summary. –  Michael Kjörling Jan 16 '12 at 9:00
    
Of course. This was a statement of the obvious (but still bears repeating). The issue is how much correlation to the random number generators have. This might increase the probability of collision significantly (2^large), but how much is something you won't know unless you do a lot of digging, research, or calculation. Assuming the probability of collision is significantly worse than a the best value is probably prudent. After that... you then need to consider the consequences. –  quickly_now Jan 16 '12 at 11:32
add comment

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.

share|improve this answer
    
However, the maximum number of unique UUIDs from RANDU is 2^29, or something over 500 million. If you're generating UUIDs randomly from that set, you have to consider the Birthday Paradox, which suggests that a collision gets likely with 2^15, or about 32,000, UUIDs. A longer-period PRNG (say 2^64) would have more possible UUIDs and would be much less likely to collide. –  David Thornley Feb 1 '12 at 15:33
    
Not sure how you got that result; it seems the internal state is 31 bits (yes, for a single seed the period is 2^29, but with hundreds of machines you won't be using a single seed). Also, the birthday paradox does assume real random numbers; the math is a lot harder when the numbers aren't (like RANDU). –  MSalters Feb 3 '12 at 13:21
    
Thanks for the bit correction, but it only raises the number until likely duplication by a factor of two. I'm treating the internal state (seed state as modified by calls) as a random number here, since the internal state at start of generation determines the UUID. This isn't quite right, particularly if some UUIDs are spat out in rapid succession on one machine, but it's good enough for paranoid work. If there's any serious consequences for a dupe, I'd worry about it. –  David Thornley Feb 3 '12 at 17:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.