GUID冲突可能吗？

Question

GUID冲突可能吗？

我正在使用SQL Server 2000中的一个数据库,该数据库为每个使用它所绑定的应用程序的用户使用GUID.不知何故,两个用户最终得到了相同的GUID.我知道微软使用一种算法来生成一个随机GUID,这个GUID极有可能导致碰撞,但是碰撞仍然可能吗？

Answer 1

Tom*_*ter 127

基本上没有.我觉得有人跟你的数据库混在一起.根据您使用的版本GUID,值是唯一的(对于版本1 GUID之类的东西),或者是唯一的和不可预测的(对于版本4 GUID之类的东西).SQL Server的NEWID()函数实现似乎使用128位随机数,因此您不会发生冲突.

对于1%的碰撞机会,您需要生成大约2,600,000,000,000,000,000个 GUID.

向下投票,因为原则上(在它的最新形式),你错误地对"GUID冲突可能吗？"这个问题说"不".这很有可能.其可能性很小,但有可能.我讨厌听起来很迂腐 - 但所有这些都是为了简洁和准确. (89认同)
输入"解决[1-exp [ - (n ^ 2 /(2*2 ^ 128)]]> 0.01,n]"进入wolfram alpha获得1%的结果...请注意这个数字似乎很大一个应用程序的上下文,它对整个世界来说肯定不大.如果地球上的每台计算机都会生成真正的GUID,那么它们会在大约一秒钟内以1%的概率发生碰撞,假设它们每纳秒可以生成一个GUID(这些天可能非常逼真).因此,如果您对数据库ID使用GUID,那么它们是唯一的.在地球上完成的每次计算的GUID都会立即发生碰撞. (13认同)
说'不'是不可能的,然后说当产生一定数量时有1%的机会发生碰撞是直接冲突.正确的反应应该是理论上的 - 是的,碰撞可能是随机发生的.然而,碰撞的可能性在统计上小于撞击地球的小行星,在地球上反弹并在下一个小时内从月球上反弹并再次撞击地球. (8认同)
实际上这不再是真的.对于v1 GUID来说确实如此,但对于当前的v4 GUID则不然.有关详细信息,请参阅http://en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm. (6认同)
这就是我的想法,但我只是想确保我无法排除这一点.你永远不知道在8岁的软件中会出现什么样的奇怪错误.:) (3认同)
@JᴀʏMᴇᴇ(和其他类似的评论),这个答案不说"不"; 它说"**基本上**,没有".恕我直言,"基本上"这个词清楚地表示:"是的,它在理论上是可行的,但实际上它不是.如果你有一个重复的GUID,那么寻找原因,因为它不是随机发生的." (2认同)
@JᴀʏMᴇᴇ转到english.stackexchange.对我来说很清楚. (2认同)

Answer 2

Pop*_*lin 107

基本上他们是不可能的!,天文数字很低.

但是......我是世界上唯一一个我知道的人,曾经有一次GUID colision(是的!).

我很有信心,这不是一个错误.

如何实现,在Pocket PC上运行的小型应用程序中,在操作结束时必须发出具有生成的GUID的命令.在服务器上执行该命令后,该命令与执行日期一起存储在服务器上的命令表中.有一天,当我调试时,我发出了模块命令(附加了新生成的GUID),没有任何反应.我再次做了(使用相同的guid,因为guid仅在操作开始时生成一次),并且再次没有,最后试图找出命令未执行的原因,我检查了命令表,和3周前插入的当前GUID相同.不相信这一点,我从2周的备份中恢复了数据库,并且guid就在那里.检查代码,新的guid新生成毫无疑问.

编辑:有一些因素可能会大大增加这种情况发生的可能性,应用程序在PocketPC模拟器上运行,并且模拟器具有保存状态功能,这意味着每次恢复状态时本地时间也会恢复并且guid基于内部计时器....紧凑框架的guid生成算法可能不如例如COM ...

Upvoted.保存状态和重播确实会产生重复的guid. (34认同)
可能发生的事情是这是一个"糟糕的"GUID实现._theoretical_赔率非常低,但在Pocket PC上？谁能说他们并没有采取将这些可能性提升到"不太可能但可能"类别的捷径. (30认同)
仅仅因为事物发生的可能性非常低并不意味着它不会发生. (8认同)
正如我上面所说,这种情况的可能性越来越小,可以安全地假设您犯了错误或者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 (3认同)
@Alex，错误是来自仿真器的“保存状态并还原”，它可以还原整个仿真器映像，包括仿真器时钟。因此，在一年内完成数千次还原操作后，发生了一次Guid冲突。您说的没错！ (2认同)

Answer 3

Ben*_*ein 32

它们在理论上是可行的,但是对于3.4E38可能的数字,如果你在一年内创造了数万亿的GUID,那么一个副本的可能性是0.00000000006(来源).

如果两个用户最终使用相同的GUID,我会打赌程序中存在导致数据被复制或共享的错误.

我很确定任何体面的GUID实现都不会 (12认同)
这将取决于如何生成GUID,并且基于CPU时间或毫秒的一些实现将(希望)扩展其基于的任何计算,因此从毫秒间隔产生的两个GUID将具有巨大差异. (4认同)
如果一台机器上有一个以上的处理器,如果一个guid基于时间和mac地址,那么每个核心可以在同一时刻发出相同的guid. (4认同)
@MatthewLock 源代码中涵盖了生日悖论。检查链接。 (2认同)

Answer 4

Gre*_*ech 20

首先让我们看看两个GUID发生冲突的可能性.正如其他答案所说的那样,由于生日悖论,它不是1 ^ 2 128(10 ^ 38),这意味着对于两个GUID碰撞的概率为50%,概率实际上是2 ^ 64(10 ^ 19)这个要小得多.但是,这仍然是一个非常大的数字,因此假设您使用合理数量的GUID的冲突概率很低.

另请注意,GUID不包含时间戳或MAC地址,因为许多人似乎也相信.这对于v1 GUID是正确的,但是现在使用了v4 GUID,它们只是一个伪随机数,这意味着碰撞的可能性可以说更高,因为它们不再是时间和机器所特有的.

所以基本上答案是肯定的,碰撞是可能的.但他们极不可能.

编辑:固定为2 ^ 64

你有一个拼写错误“1 in 10^64 (10^19)”，我认为应该是“1 in 2^64 (10^19)”。我也很困惑你怎么认为生日悖论只适用于两个数字。我假设您查看了http://en.wikipedia.org/wiki/Birthday_paradox。该表显示了给定的重复概率需要多少个指导。从该表中，10^18 中的 1 的概率需要 2.6 * 10^10 guid，而不是接近两个 GUID 的任何值。 (3认同)
虽然我同意你的所有事实,但要小心你的数学.要说任何两个GUID发生冲突的几率为10 ^ 19,取决于集合中有多少个GUID.对于这个机会,你需要~2 ^ 32个GUID,因此在几乎所有真实场景中,几率都要低得多. (2认同)

Answer 5

Ton*_*Lee 17

两个随机GUID冲突的可能性(在10 ^ 38中为~1)低于未检测到损坏的TCP/IP分组的机会(在10 ^ 10中为~1). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf,第11页.磁盘驱动器,CD驱动器等也是如此......

GUID在统计上是唯一的,您从数据库中读取的数据仅在统计上是正确的.

Answer 6

Jas*_*son 13

在这种情况下,我会认为奥卡姆剃刀是一个很好的指南.你发生GUID冲突的可能性极小.您更有可能遇到错误,或者有人弄乱您的数据.

事实上，在这种情况下，奥卡姆剃刀根本不是一个好的指南！奥卡姆剃刀说，假设最少的情况最有可能是正确的。在这种情况下，GUID 冲突的情况实际上要简单得多，但奥卡姆剃刀不适用于我们已经知道其中一种情况极不可能发生的情况。 (3认同)

Answer 7

Phi*_*Lho 11

请参阅Wikipedia的全球唯一标识符文章.有几种方法可以生成GUID.显然旧的(？)方式使用Mac地址,时间戳到一个非常短的单位和一个独特的计数器(在同一台计算机上管理快速生成),所以使它们复制几乎是不可能的.但是这些GUID被删除了,因为它们可以用来追踪用户......

我不确定微软使用的新算法(文章说可以预测一系列GUID,看起来他们不再使用时间戳了？上面链接的微软文章说了别的......).

现在,GUID经过精心设计,按名称,全球独一无二,因此我将冒险这是不可能的,或者非常非常低的概率.我会去别处看看.

[Eric post 1](http://blogs.msdn.com/b/ericlippert/archive/2012/04/24/guid-guide-part-one.aspx) (6认同)
[Eric post 2](http://blogs.msdn.com/b/ericlippert/archive/2012/04/30/guid-guide-part-two.aspx) (4认同)
[Eric post 3](http://blogs.msdn.com/b/ericlippert/archive/2012/05/07/guid-guide-part-three.aspx) (4认同)
还有Eric Lipperts优秀系列博客文章 (3认同)

Answer 8

Jos*_*hua 9

具有重复MAC地址的以太网卡的两台Win95机器将在严格控制的条件下发出重复的GUID,特别是例如,如果建筑物中的电源断电并且它们都在完全相同的时间启动.

Answer 9

Ene*_*th3 6

你是数学家吗？好的。

你是工程师吗？那就不要。

Answer 10

Joh*_*aft 5

我将以“我不是网络人士，因此我可能在后面说完全不连贯的句子”作为开头。

当我在伊利诺伊州立大学工作时，我们有两个在不同时间订购的Dell台式机。我们将第一个放入网络，但是当我们尝试将第二个放入网络时，我们开始收到疯狂的错误。经过大量的故障排除后，确定两台计算机都在生成相同的GUID（我不确定确切用于什么目的，但是这使它们在网络上均无法使用）。戴尔实际上将两台计算机都更换为有缺陷的。

特别是GUID。它们与机器加入网络时生成的GUID有关。戴尔花了几周的时间来更换机器，因为他们说GUID不可能相同。我们能够重现该问题，戴尔收回了这些机器，并在其网络上产生了相同的结果。他们最终更换了两台机器。如我所说，我不是网络专家，但我特别记得这是GUID的问题。 (3认同)

Answer 11

Ric*_*son 5

我知道人们喜欢一个很好的答案，即GUID是神奇的，并且保证是唯一的，但是实际上，大多数GUID只是121位随机数（其中有7位浪费在格式化上）。如果您不喜欢使用大随机数，那么使用GUID也不适合。

还建议您不要使用网络。或电脑。奇偶校验位只能做很多事情！ (11认同)
我完全知道。您说“如果您不愿意使用大随机数”。但是GUID非常独特，以至于您会发现计算机中的几乎所有其他东西都是随机的，甚至是您认为理所当然的操作。与（真实的）GUID冲突相比，异常的内存故障将有可能破坏您的标识列。您不应该对它们感到“不舒服”。如果它们不是该方案的理想选择，那就很好-但不需要特别注意。 (4认同)
我想这是无能为力的，但是人们试图向您解释的是，常见硬件（例如网卡或硬盘驱动器）中的错误检测机制使用的算法比您遇到GUID冲突的机会更大，无法检测到错误，因此如果您依靠这些，也可以依靠GUID (3认同)

Answer 12

guk*_*off 5

广义公式

有一个公式可以估计要生成多少个大小为 S 的值才能以概率 P 获得其中两个值之间的碰撞。

变量：

位 - 数据类型中有多少位。
概率 - 碰撞的目标概率。

为了获得碰撞，你必须围绕以下内容生成：

$2^{\frac{位 + 1}{2}} * \sqrt{-log_2(1 - 概率)}$

或者用Python：

from math import sqrt, log

def how_many(bits, probability):
    return 2 ** ((bits + 1) / 2) * sqrt(-log(1 - probability))

Run Code Online (Sandbox Code Playgroud)

GUID

对于 GUID（128 位），要获得概率为 1% (0.01) 的冲突，您需要：

In [2]: how_many(bits=128, probability=0.01)
Out[2]: 2.6153210405530885e+18

Run Code Online (Sandbox Code Playgroud)

...大约 2.6 * 10^18 GUID（即42 艾字节的 GUID）。

请注意，此概率增长迅速。无论位数是多少，99.99% 的概率只需要比 1% 多 30 倍的 GUID！

In [3]: how_many(bits=128, probability=0.9999)
Out[3]: 7.91721721556706e+19

Run Code Online (Sandbox Code Playgroud)

整型64

相同的数字，但对于 int64 数据类型：

In [4]: how_many(bits=64, probability=0.01)
Out[4]: 608926881

In [5]: how_many(bits=64, probability=0.9999)
Out[5]: 18433707802

Run Code Online (Sandbox Code Playgroud)

对于 1% 的冲突概率，您需要5 GB的 int64-s。虽然仍然很多，但与 GUID 相比，这是一个更容易理解的数字。

这就是所谓的生日问题- 在这篇维基百科文章中，您可以找到比本文更精确的估计公式。

归档时间：	17 年，7 月前
查看次数：	66880 次
最近记录：	10 年，4 月前