logo标签列表

GUID冲突可能吗？

sql-serverguid
156
我正在处理一个在SQL Server 2000中使用GUID的数据库，每个使用此应用程序的用户都有一个GUID。不知怎么的，两个用户的GUID相同了。我知道Microsoft使用算法生成随机GUID，几乎不可能发生冲突，但是仍然有可能发生冲突吗？
14
每个说“不”的人都是错的。我已经将一个唯一标识符与少于50万条记录的数据集发生了冲突，使用的是MSSQL 2008 R2。 - Behrooz
4
哎呀。由于生日悖论，这并不是不可能的，但对于完全随机的v4 GUID来说仍然是极为不幸的。也许你正在使用更弱的GUID生成策略？ - Craig Ringer
7
哇，这运气真是太出乎意料了。 - Craig Ringer
9
这可能是在 MSSQL 中使用的有缺陷的伪随机数（鉴于其软件质量，我不会惊讶他们的生成器中有 32 位种子或类似的内容）。数学是不会撒谎的。这种可能性非常小，以至于您可以确信 99.9999999999% （后面跟着很多个9），MSSQL 的 GUID 生成器有缺陷（或者可能是用来生成 GUID 的伪随机数生成器），或者您犯了一个错误。 - Alex
5
此时此刻，问题和被选答案的分数都是128分，真巧合吗？ - Caio Cunha
显示剩余9条评论
20个回答
156
基本上不会。我认为有人在你的数据库中进行了修改。根据你使用的版本GUID，该值可能是唯一的（例如版本1 GUID）或既唯一又不可预测（例如版本4 GUID）。SQL Server的NEWID()函数实现似乎使用了一个128位的随机数，因此你不会遇到碰撞问题。
要使碰撞的概率为1％，你需要生成约2,600,000,000,000,000,000个GUID。
7
实际上这不再是正确的了。这对于版本1的GUID是正确的，但对于当前的版本4不再适用。请参考http://en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm获取更多信息。 - Greg Beech
139
因为原则上来讲，你否定了“GUID是否可能发生冲突”的问题，所以我会对你进行负面评价。实际上这是非常有可能的，虽然概率很小。我不想显得卖弄学识，但是SO的宗旨就是准确简洁。 - user1017882
17
将“solve[1-exp[-(n^2/(2*2^128))] > 0.01, n]”输入到沃尔夫拉姆阿尔法中，以获取1%的结果。请注意，尽管在一个应用程序的情况下这个数字似乎很大，但对于整个世界来说并不算大。假设地球上每台计算机都可以每纳秒生成一个GUID（这在今天可能是相当现实的），它们将在约一秒钟内产生1％的碰撞。因此，如果您将GUID用作数据库ID，则它们是唯一的。用于地球上进行的每个计算的GUID将立即发生碰撞。 - thesaint
17
说“不可能”，然后又说在生成一定数量时有1％的概率发生冲突，这是直接矛盾的。 正确的回答应该是：理论上-是的，冲突可能会随机发生。 然而，与小行星撞击地球、反弹至月球并在下一个小时再次撞击地球相比，冲突的概率在统计学上要小得多。 - Baaleos
5
@JᴀʏMᴇᴇ（和其他类似的评论），这个回答并没有说“不行”，它说的是“基本上不行”。在我看来，“基本上”这个词明显意味着：“是的，从理论上讲可能行得通，但实际上不行。如果你有一个重复的 GUID，则需要在其他地方寻找原因，因为这不是随机发生的。” - TTT
显示剩余31条评论
123

基本上这是不可能的！机会极其微小。

但是...我是世界上唯一一个我知道曾经发生过GUID冲突的人（是的！）。

我很确定这一点，而且这不是一个错误。

它是如何发生的呢？在运行于Pocket PC上的一个小应用程序中，在操作结束时必须发出一个生成的GUID命令。该命令在服务器上执行后，将与执行日期一起存储在服务器上的命令表中。有一天当我在调试时，我发出了模块命令（附带新生成的GUID），但没有任何反应。我再次尝试（使用相同的GUID，因为GUID只在操作开始时生成一次），但还是没有反应。最终，为了找出命令为什么没有执行，我检查了命令表，发现与当前GUID相同的GUID已经在3周前插入了。我不相信这个结果，于是我从2周前的备份中恢复了数据库，发现GUID还在那里。检查代码，新的GUID肯定是新生成的。Pow，GUID冲突，只发生了一次，但我真希望我能赢得彩票，机会更大：）。

编辑：有一些因素可能会大大增加这种情况发生的机会，应用程序运行在PocketPC模拟器上，并且模拟器具有保存状态功能，这意味着每次恢复状态时本地时间也会恢复，并且GUID是基于内部计时器的...此外，紧凑框架的GUID生成算法可能比COM更不完整...

43
点赞了。保存状态和重播确实会生成重复的GUID。 - Joshua
42
可能发生的情况是这个GUID实现存在问题。从理论上讲，概率非常低，但在Pocket PC上？谁又能说他们没有采取捷径，将这些概率提高到“不太可能，但可能”的范畴。 - Dave Dopson
11
某事发生的概率很低，并不意味着它不会发生。 - Geeky Guy
3
如我之前所说，发生这种情况的概率已经变得极小，因此可以安全地假设您要么犯了错误，要么MSSQL使用了有缺陷的伪随机数生成器（PRNG）（http://en.wikipedia.org/wiki/Pseudorandom_number_generator）。例如，很可能该PRNG被初始化为一个较小的种子。有缺陷的PRNG并不罕见（请参见https://www.schneier.com/paper-prngs.html），例如最近在Android SDK中发现了一个缺陷 - http://android-developers.blogspot.com/2013/08/some-securerandom-thoughts.html + https://www.usenix.org/conference/woot14/workshop-program/presentation/kaplan。 - Alex
3
@Alex，错误出在模拟器的“保存状态和恢复”功能上，它会还原整个模拟器图像，包括模拟器时钟。因此，在一年内进行了数千次还原操作后，生成了一个GUID冲突。你是对的，这是一个错误！ - Pop Catalin
显示剩余6条评论
53

你是数学家吗？那么是的。

你是工程师吗？那么不是。

1
最好的答案！ - nyan-cat
这个答案非常优雅。 - undefined
40

理论上讲，它们是可能存在的，但由于UUID有3.4E38个可能的编号，每年创建数万亿个GUID时出现重复的概率仅为0.00000000006 (参考资料)。

如果两个用户最终拥有了相同的GUID，我敢打赌这是程序中导致数据被复制或共享的一个漏洞。

4
这取决于GUID的生成方式，有一些实现是基于CPU时间或毫秒级别的，这将（希望）夸大它所依据的任何计算，因此生成的两个GUID在毫秒级别上会有很大的差异。 - user29053
4
如果一台机器上有多个处理器，如果一个GUID基于时间和MAC地址，则每个核心可以在同一时刻发出相同的GUID。 - AndyM
13
我相信任何一个良好的GUID实现都不会 - Guillaume86
我想知道生日悖论能将任意两个GUID发生冲突的概率降低多少？ - Matthew Lock
2
@MatthewLock 生日悖论在源代码中有涉及。请查看链接。 - Zero3
显示剩余2条评论
25
首先让我们看一下两个GUID发生碰撞的概率。与其他答案所述的不同，它不是2^128 (10^38)中的1，因为存在生日悖论，这意味着对于50%的GUID碰撞机会，实际概率为1 in 2^64（10^19），这要小得多。然而，这仍然是一个非常大的数字，因此假设您使用合理数量的GUID，则碰撞的可能性很低。
另请注意，许多人似乎认为GUID包含时间戳或MAC地址，但事实并非如此。这对于v1 GUID是正确的，但现在使用的是v4 GUIDs，它们只是伪随机数，这意味着碰撞的可能性更高，因为它们不再唯一地对应于时间和机器。
因此，基本上答案是“是的，碰撞是可能的。但它们高度不太可能发生。”
编辑：更正为2^64
2
虽然我同意你的所有事实，但在数学上要小心一点。说你有 10^19 中的 1 的机会让任意两个 GUID 相撞是取决于集合中有多少个 GUID。为了有那样的机会，你需要大约 2^32 个 GUID，所以在几乎所有的真实场景中，这个概率要低得多。 - DocMax
3
你在“10^64（10^19）”中打错了一个字，我认为应该是“2^64（10^19）”。我也很困惑你如何认为生日悖论只适用于两个数字。我猜你看过http://en.wikipedia.org/wiki/Birthday_paradox。表格显示了你需要多少个GUID才能获得重复的给定概率。从那个表格可以看出，1/10^18的概率需要2.6 * 10^10个GUID，而不仅仅是两个GUID。 - Tony Lee
一个要点——v1 guids仍然广泛使用，并依赖于MAC地址，在数据库中具有理想的特性。请参见UuidCreateSequential和它的SQL Server包装器NewSequentialID（http://msdn.microsoft.com/en-us/library/windows/desktop/aa379322(v=vs.85).aspx）。 - EBarr
18

两个随机GUID重复的概率（约为10的38次方分之1）比未检测到损坏的TCP/IP数据包的概率（约为10的10次方分之1）更低。详情请查看http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf第11页。磁盘驱动器、光驱等也是如此…

GUID通常是唯一的，从数据库中读取的数据仅在统计学上正确。

你确定我不可能加固我的网络，以至于少于10^28个数据包中只有不到1个是损坏的吗？ - Joshua
13

在这种情况下，我认为奥卡姆剃刀原理是一个很好的指导。你遇到GUID碰撞的概率极小，更有可能是出了Bug或者是有人篡改了你的数据。

1
实际上，在这种情况下，奥卡姆剃刀根本不是一个好的指南！奥卡姆剃刀原则认为，假设最少的情况最有可能是正确的。在这种情况下，GUID碰撞的情况实际上要简单得多，但是在我们已经知道其中一种情况极不可能发生的情况下，奥卡姆剃刀原则并不适用。 - lockstock
11
请参阅维基百科的全局唯一标识符文章。有几种生成GUID的方法。显然，旧的方式使用了Mac地址、时间戳到非常短的单位和一个唯一计数器（用于在同一台计算机上快速生成），所以使它们重复几乎是不可能的。但是这些GUID被放弃了，因为它们可以用来跟踪用户...
我不确定Microsoft使用的新算法（文章说一系列GUID可以被预测，看起来他们不再使用时间戳？上面链接的Microsoft文章说了其他事情...）。
现在，GUID被精心设计成全球唯一的，所以我认为这是不可能的，或者极其低的概率。我会去别处看看。
6
Eric Lippert发表了一系列关于 GUID 的文章，本文是其中的第一篇。GUID 是一个全球唯一标识符，它通常用于在分布式系统中唯一地标识某些东西。GUID 是根据特定算法生成的 128 位数字，可以保证其几乎不可能重复。GUID 可以表示为字符串，格式为 xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx，其中 x 是十六进制数字。GUID 还有许多其他有趣的属性和特点，包括可排序性和版本号。 - Nat
5
Eric post 2 埃里克文章2 - Nat
5
Eric post 3 - Nat
9

如果两台安装有以太网卡且MAC地址重复的Win95机器在严格控制条件下运行，尤其是例如建筑停电后它们恰好同时启动，那么它们将发出重复的GUIDS。

两台不同的机器拥有相同的以太网MAC地址是常见的吗？ - Dave Lucre
@DaveLucre：没有，但是已经记录了一些事件。 - Joshua
我真的很好奇这个问题是怎么发生的。随机生成每个NIC的MAC地址的虚拟机比较容易出现这种情况吗？我从未听说过物理网卡会制造具有重复MAC地址的情况！如果可能的话，这会给系统造成极大的麻烦！ - Dave Lucre
哇！感谢@Joshua提供的链接！这是一个巨大的失误！ - Dave Lucre
@DaveLucre 我曾经使用过一些非常便宜的USB网卡，其中所有网卡都使用相同的MAC地址制造。但是，这当然与随机性的数学无关，而与制造商的懒惰有关。 - rudolfbyker
哇，为所有设备使用相同的MAC地址不仅是懒惰，@rudolfbyker，这是疏忽大意。 - Dave Lucre
6

我知道人们喜欢听到GUID是神奇的，能够保证唯一性的回答，但实际上，大多数GUID只是121位随机数（其中七位用于格式化而被浪费）。如果您不舒服使用一个大随机数，那么您也不应该使用GUID。

13
建议您不要使用网络或计算机，因为奇偶校验位只能做到这么多！ - Rushyo
(2) GUID并不是神奇的唯一标识符，除非你已经考虑过它们是否真正适合使用，否则不应该使用它们。通常，一个字符串、一个递增的数字或一对ID可能更合适且更易读。有人声称GUID非常适合分布式数据库，但是一个标识创建行的服务器的smallint列和一个递增的ID同样有效，更易于阅读，并且占用更少的空间。 - Rick Yorgason
7
我完全明白你的意思。你说：“如果你不愿意使用一个大随机数，那么你可能会感到不舒服。” 但是GUID非常独特，以至于你会发现计算机中几乎所有其他东西都更加随机，甚至是一些你认为理所当然的操作。与（真正的）GUID碰撞相比，有更多的机会是由于异常内存故障而破坏你的身份列。你不应该对它们感到“不安”。如果它们不适合当前场景，那就没问题 - 但它们不需要特别的谨慎。 - Rushyo
5
我猜这件事情没办法再讲下去了，但人们试图向您解释的是，常见硬件（例如网络卡或硬盘驱动器）中的错误检测机制使用的算法具有更大的不检测到错误的概率，而不是您遇到GUID冲突的概率，因此如果您依赖这些机制，与依赖GUID一样可靠。 - Guillaume86
1
@Rick，这取决于你的数字有多大。绝对不能使用4字节int或8字节bigint。GUID=16字节，因此您需要自定义16字节的大数实现才能实现相同的2^128个可能组合。因此，一般来说，如果使用“普通”的int或bigint随机数，则与GUID发生冲突的机会确实较低（每个随机算法的考虑除外）。 - Wim
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接