I'm working on a database in SQL Server 2000 that uses a GUID for each user that uses the app it's tied to. Somehow, two users ended up with the same GUID. I know that microsoft uses an algorithm to generate a random GUID that has an extremely low chance of causing collisons, but is a collision still possible?
-
14Everybody saying no is wrong.I already have collided 1 UniqueIdentifier with a dataset of less than half a million records, MSSQL 2008 R2– BehroozJul 30, 2012 at 12:47
-
4@Behrooz Yikes. It isn't impossible thanks to our friend the birthday paradox, but it's still insanely unlucky with fully random v4 GUIDs. Maybe you were using a weaker GUID generation strategy?– Craig RingerOct 30, 2012 at 7:57
-
7@Behrooz Wow. That's shocking luck.– Craig RingerNov 6, 2012 at 7:42
-
9@Behrooz this is probably a defective pseudo random number used in MSSQL (I wouldn't be surprised if they have 32-bit seed in their generator or the like given the quality of their software). The math doesn't lie. This possibility is so small so that you can be 99.9999999999(and a lot of 9 after)% that either MSSQL guid generator is defective (or may be pseudo random generator which is used to generate GUIDs) or you made a mistake.– AlexDec 12, 2014 at 20:05
-
5Love how at this exact moment, both the question and the selected answer have 128 score. Coincidence? 🤔– Caio CunhaJun 10, 2020 at 21:59
20 Answers
Basically, no. I think someone went mucking with your database. Depending on the version GUID you're using the value is either unique (for things like version 1 GUIDs), or both unique and unpredictable (for things like version 4 GUIDs). SQL Server's implementation for their NEWID() function appears to use a 128-bit random number, so you're not going to get a collision.
For a 1% chance of collision, you'd need to generate about 2,600,000,000,000,000,000 GUIDs.
-
7Actually that isn't true any more. It was true for v1 GUIDs, but not for the current v4 ones. See en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm for more info. Oct 8, 2008 at 23:10
-
138Down vote because, in principle (in it's rawest form), you are wrong saying "no" to the question "Are GUID collisions possible?". It's very possible. The likelihood of which is tiny, but it's possible. I hate to sound pedantic - but SO is all about being concise and accurate.– user1017882Oct 9, 2012 at 16:08
-
17enter "solve[1-exp[-(n^2/(2*2^128))] > 0.01, n]" into wolfram alpha to get the result for 1%... Beaware that while this number seems large in context of ONE application, it certainly isn't large for the entire world. If every computer on the earth would genereate true GUIDs, they would cause a collision with 1% probability within about one second, assuming they can generate a GUID each nanosecond (which is probably quite realistic these days). So if you use GUIDs for your database IDs, then they are unique. GUIDs for every computation done on earth, will collide immediately.– thesaintNov 14, 2014 at 10:03
-
16Saying 'No' its not possible, and then saying that there is a 1% chance of getting a collision when a certain amount is generated, are direct conflicts. The correct response should be Theoretically - yes, a collision could happen randomly. However, the chances of a collision are statistically smaller than an asteroid hitting the Earth, bouncing off the Earth and rebounding off the Moon to hit Earth a second time, in the next hour.– BaaleosJan 20, 2016 at 13:25
-
5@JᴀʏMᴇᴇ (and other similar comments), this answer doesn't say "No"; it says "Basically, no". IMHO, the word "basically" clearly means: "Yes, it's theoretically possible, but practically it isn't. If you have a duplicate GUID, then look elsewhere for a cause as it didn't happen randomly."– TTTFeb 23, 2018 at 20:10
Basically they are not possible !, the chances are astronomically low.
But... I'm the only person I the world that I know of, that had a GUID colision once (yep!).
And I'm sure of it, and that it wasn't a mistake.
How did it happen, in a small application that was running on Pocket PC, at the end of an operation a command that has an generated GUID must be issued. The command after it was executed on the server it was stored in a command table on the server along with the execution date. One day when I was debugging I issued the module command (with the newly generated GUID attached) and nothing happened. I did it again (with the same guid, because the guid was generated only once at the beginning of the operation), and again, and nothing, finally trying to find out why the command isn't executing, I checked the command table, and the same GUID as the current one was inserted 3 weeks ago. Not believing this, I restored a database from 2 weeks backup, and the guid was there. Checked the code, the new guid was freshly generated no doubt about it. Pow guid collision, happened only once, but I really wish I would have won at lotto instead,the chance is greater :).
Edit: there are some factors that could have greatly increased the chance of this happening, the application was running on the PocketPC emulator, and the emulator has a save state feature, which means that every time the state is restored the local time is restored also and the guid is based on on the internal timer....also the guid generating algorithm for compact framework might be less complete than for example the COM one...
-
43
-
42Likely what happened was this was a "bad" GUID implementation. The theoretical odds were very low, but on Pocket PC?? Who is to say that they didn't take a shortcut that bumped those odds up into the "unlikely, but possible" category. Mar 9, 2012 at 1:47
-
11Just because something has a very low probability to happen doesn't mean it won't happen. Sep 17, 2013 at 19:45
-
3As I said above the chances of that are so increasingly small that it is safe to assume that either you made a mistake or MSSQL uses a defective PRNG (en.wikipedia.org/wiki/Pseudorandom_number_generator). E.g. it is likely that this PRNG is initalized with a seed of small size. Defective PRNGs are not rare (see schneier.com/paper-prngs.html) - for example one defect was recently discovered in Android SDK - android-developers.blogspot.com/2013/08/… + usenix.org/conference/woot14/workshop-program/presentation/…– AlexDec 12, 2014 at 20:10
-
3@Alex, the mistake was "Save State and Restore" from the Emulator, which restore the entire emulator image including the emulator clock. So after thousands of Restore operations over one year, one guid collision was generated. You are right there was a mistake! Dec 15, 2014 at 8:55
Are you a mathematician? Then yes.
Are you an engineer? Then no.
-
1
-
They are theoretically possible, but with 3.4E38 possible numbers, if you create tens of trillions of GUIDs in a year the chance of having one duplicate is 0.00000000006 (Source).
If two users ended up with the same GUID, I would wager that there is a bug in the program which is causing the data to be copied or shared.
-
"but with 3.4E38 possible numbers" - no. Two GUIDs generated almost simultaneously on the same machine would end up with extremely similar GUIDs. Oct 8, 2008 at 21:14
-
4That would depend on how the GUID is generated, and some implementations based on the CPU time or milliseconds will (hopefully) exagerate whatever calculation its based off of so two GUID's generated from milliseconds apart will have a vast difference.– user29053Oct 31, 2008 at 15:19
-
4With more than 1 processor on a machine, if a guid is based on time and mac address then each core could issue the same guid at the same moment in time.– AndyMFeb 19, 2010 at 16:53
-
13
-
2@MatthewLock The birthday paradox is covered in the source. Check the link.– Zero3Jan 11, 2016 at 9:02
First lets look at the chance of collision of two GUIDs. It is not, as other answers have stated, 1 in 2^128 (10^38) because of the birthday paradox, which means that for a 50% chance of two GUIDs colliding the probability is actually 1 in 2^64 (10^19) which is a lot smaller. However, this is still a very large number, and as such the probability of collision assuming you are using a reasonable number of GUIDs is low.
Note also that GUIDs do not contain a timestamp or the MAC address as many people also seem to believe. This was true for v1 GUIDs but now v4 GUIDs are used, which are simply a pseudo-random number which means that possibility of collision is arguably higher because they are no longer unique to a time and a machine.
So essentially the answer is yes, collisions are possible. But they are highly unlikely.
Edit: fixed to say 2^64
-
2While I agree with all of your facts, be careful with your math. To say that you have a 1 in 10^19 chance of any two GUIDs colliding depends on how many GUIDs are in the set. For that chance you need ~2^32 GUIDs, so in nearly all real-world scenarios the odds are much lower.– DocMaxOct 9, 2008 at 7:16
-
3You have a typo of
1 in 10^64 (10^19)
, which I think should be1 in 2^64 (10^19)
. I'm also very confused how you think the birthday paradox applies to just 2 numbers. I assume you looked at en.wikipedia.org/wiki/Birthday_paradox. The table shows how many guids you need for a given probability of a duplicate. From that table a probability of 1 in 10^18 requires 2.6 * 10^10 guids, not anything close to just two GUIDs.– Tony LeeDec 29, 2011 at 1:22 -
One point -- v1 guids are still in wide use, and rely upon MAC address, particularly in databases as they have desirable characteristics. See UuidCreateSequential and it's SQL Server wrapper NewSequentialID (msdn.microsoft.com/en-us/library/windows/desktop/…).– EBarrJul 22, 2014 at 22:01
The chances of two random GUIDs colliding (~1 in 10^38) is lower than the chance of not detecting a corrupt TCP/IP packet (~1 in 10^10). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf, page 11. This is also true of disk drives, cd drives, etc...
GUIDs are statistically unique and the data you read from the db is only statistically correct.
-
Are you sure I couldn't possibly armor my network so less than 1 in 10^28 packets are corrupt?– JoshuaJun 10, 2013 at 21:46
I would consider Occam's razor as a good guide in this case. It is incredibly unlikely that you have a GUID collision. It is much more likely you have a bug, or someone messing with your data.
-
1Actually in this situation Occam's razor is not a good guide at all! Occam's Razor says that the case with the least assumptions is most likely to be correct. In this situation the case of GUID collision is actually much simpler, but Occam's Razor does not apply to a situation like this where we already know that one of the cases is incredibly unlikely. Aug 14, 2019 at 1:49
See Wikipedia's Globally Unique Identifier article. There are several ways to generate GUIDs. Apparently the old (?) way used Mac address, a timestamp down to a very short unit and a unique counter (to manage fast generations on the same computer), so making them duplicate is nearly impossible. But these GUIDs were dropped because they could be used to track down users...
I am not sure of the new algorithm used by Microsoft (the article says a sequence of GUIDs can be predicted, looks like they no longer use timestamp? The Microsoft article linked above says something else...).
Now, GUIDs are carefully designed to be, by name, globally unique, so I will risk it is impossible, or of very very very low probability. I would look elsewhere.
-
6
-
5
-
5
Two Win95 machines that have ethernet cards with duplicate MAC addresses will issue duplicate GUIDS under tightly controlled conditions, especially if, for example, the power goes off in the building and they both boot at exactly the same time.
-
Is it common for two different machines to have the same ethernet MAC address? Jun 27, 2018 at 22:19
-
-
I'm really curious how this comes about. Is it more likely with VMs that randomly generate a MAC for each NIC? I've never heard of physical NICs being manufactured with duplicate MACs! Kind of throws a massive spanner in the works if that's possible! Jun 27, 2018 at 23:20
-
-
@DaveLucre I've used some very cheap USB NICs where ALL of them are manufactured with the same MAC. But of course, that has nothing to do with the mathematics of randomness, and everything to do with the laziness of the manufacturer. Dec 3, 2018 at 11:07
I know people like the feel-good answer that GUIDs are magical and guaranteed to be unique, but in reality, most GUIDs are just 121-bit random numbers (seven of the bits are wasted on formatting). If you wouldn't feel comfortable using a big random number, then you shouldn't feel comfortable using a GUID.
-
13Also recommend you don't use networks. Or computers. Parity bits can only do so much!– RushyoFeb 3, 2011 at 15:44
-
You misunderstood. There's two things I was trying to say in this post:1) If you need a big random number, use a big random number. Using a GUID as a big random number is needlessly misleading. (2) Mar 18, 2011 at 21:11
-
7Which I'm fully aware of. You stated "if you wouldn't feel comfortable using a big random number." but GUIDs are so unique that you'd find that pretty much everything else in a computer is more random, even operations you take for granted. There's more chance that a freak memory glitch will break your identity column than a (true) GUID collision will occur. You should not feel 'uncomfortable' about them. If they're not ideal for the scenario then fine - but they don't need special caution.– RushyoMar 22, 2011 at 11:51
-
5I guess this is going nowhere but what people are trying to explain to you is that error detections mecanisms in common hardware like network cards or hard drives use algorithms that have bigger chances of not detecting an error than you of getting a GUID collision, so if you rely on these, you could as well rely on GUIDs Jun 4, 2012 at 15:28
-
1@Rick, depends how big your number is. Definitely not with a 4 byte int or 8 byte bigint. GUID=16 bytes, so you'd need a custom 16 byte big number implementation to achieve the same 2^128 possible combinations. So generally speaking, if using 'normal' int or bigint random numbers, the chance of collisions with a GUID is lower (leaving out random algo considerations for each).– WimOct 4, 2012 at 10:43
I'll preface this with "I'm not a networking person, so I may make completely incoherent sentences following.".
When I worked at Illinois State University, we had two Dell desktops, ordered at different times. We put the first one on the network, but when we tried to put the second one on the network we started receiving crazy errors. After much troubleshooting, it was determined that both machines were producing the same GUID (I'm not sure exactly what for, but it made them both unusable on the network). Dell actually replaced both machines as defective.
-
3It was specifically the GUID. It had something to do with the GUID generated by the machines when they joined the network. It took several weeks for Dell to replace the machines because they said it was impossible for the GUIDs to be the same. We were able to reproduce the problem, Dell took the machines back, and were able to produce the same results on their networks. They ended up replacing both machines. As I said, I'm not a networking person, but I specifically remember it was a problem with GUIDs. Oct 15, 2009 at 1:46
Generalized formula
There's a formula that estimates how many values of size S to generate to get a collision between two of them with probability P.
Variables:
- bits - how many bits in your data type.
- probability - target probability for the collision.
To get a collision, you have to generate around:
Or in Python:
from math import sqrt, log
def how_many(bits, probability):
return 2 ** ((bits + 1) / 2) * sqrt(-log(1 - probability))
GUIDs
For GUIDs (128 bits), to get a collision with probability 1% (0.01), you'll need:
In [2]: how_many(bits=128, probability=0.01)
Out[2]: 2.6153210405530885e+18
...around 2.6 * 10^18 GUIDs (that's 42 exabytes of GUIDs).
Note that this probability grows rapidly. No matter the number of bits, for 99.99% probability you'll need only 30x more GUIDs than for 1%!
In [3]: how_many(bits=128, probability=0.9999)
Out[3]: 7.91721721556706e+19
Int64
Same numbers, but for the int64 datatype:
In [4]: how_many(bits=64, probability=0.01)
Out[4]: 608926881
In [5]: how_many(bits=64, probability=0.9999)
Out[5]: 18433707802
For 1% collision probability you'll need 5 gigabytes of int64-s. Still a lot but compared to the GUIDs that is a much more comprehensible number.
It's the so called birthday problem - and in this Wikipedia article you can find more precise estimation formulas than this one.
Could the code used to generate a GUID have a bug in it? Yes, of course it could. But the answer is the same as it would be for a compiler bug - your own code is orders of magnitude more likely to be buggy, so look there first.
Of course its possible....Probable? Not likely, but it is possible.
Remember, the same machine is generating every GUID (the server), so a lot of the "randomness" that is based on machine specific information is lost.
Just for grins, try the following script... (works on SQL 2005, not sure about 2000)
declare @table table
(
column1 uniqueidentifier default (newid()),
column2 int,
column3 datetime default (getdate())
)
declare @counter int
set @counter = 1
while @counter <= 10000
begin
insert into @table (column2) values (@counter)
set @counter = @counter + 1
end
select * from @table
select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2
Running this repeatedly (takes less than a second) produces a fairly wide range from the first select, even with an EXTREMELY short time gap. So far the second select hasn't produced anything.
-
1You need another 15 zeros at the end of the counter to have a 50% chance of a duplicate. But, for Pete's sake don't do it! Oct 31, 2008 at 16:22
Impossible if the users have different machines with network cards, and even if not it is still an extremely marginal almost theoretical risk.
Personally I'd look elsewhere as it is more likely a bug rather than a GUID clash...
Providing of course that you don't chop bits off the GUID to make it shorter.
-
The GUIDs would be generated on the Server, so the user's network cards would not come into play. Oct 8, 2008 at 21:01
It's highly unlikely that you'll run into GUID collisions if you're generating them through something like the NEWID()
function in SQL Server (though of course possible, as other answers have emphasized). One thing they haven't pointed out is that it's actually quite likely that you'll run into collisions if you're generating GUIDs in JavaScript on browsers in the wild. Not only are there sometimes problems in the RNG in different browsers, but I've also run into problems where the Google spiders seem to cache the results of functions like that, and ended up repeatedly passing the same GUID up to our systems.
See the various answers here for more details:
Don’t worry about what it is. Make it impossible. Mix the improbability of GUID with the impossibility of sequential. Just add a database sequential I’d to the GUID and call it done. You may need to change the data type from GUID to String-ish but they are not that different storage wise.
I discussed it with my colleague and here it was we came across:
A GUID has 1038 unique values, and for a 50% chance of a collision you need 1019 elements to get a probability of a single guid collision (assuming each guid is actually random), it would take:
1 million Threads each producing one thousand random GUIDs per second for 1 million years (approximately).
So, in theory
YES, GUIDs are NOT UNIQUE
.
But in practical
, its PROBABLY REARLY POSSIBLE
to hit duplicate.
Sure it's possible, and maybe even likely. It's not like each GUID is in a random portion of the possible number space. In the event that two threads attempted to generate one simultaneously, barring some kind of centralized GUID function with a semaphore around it, they could end up with the same value.