logo标签列表

Java的UUID.randomUUID有多好？

javauuid
359

我知道理论上随机生成的UUID具有非常非常低的碰撞概率，但我想知道，在实践中，Java的randomUUID()在避免碰撞方面有多好？有人有任何经验分享吗？

14
根据我的经验，我从未见过碰撞；-) - Thilo
4
算法规定在RFC1422中：http://www.ietf.org/rfc/rfc4122.txt。 - skaffman
8
RFC并没有提及生成随机数字所使用的算法。 - Michael Borgwardt
5
因为这是一个更加开放的问题，我想我不会标记任何答案为正确答案；相反，我将给我认为好的每个答案投一票 :) - Alvin
9
换句话说，仅在未来的100年里每秒生成10亿个UUID，才有大约50%的概率只创建一个重复。 - MaVRoSCy
显示剩余4条评论
9个回答
191

UUID使用java.security.SecureRandom，这是一个“密码学强”的算法。虽然实际的实现方式没有明确规定，并且可能因为不同JVM而有所差异（这意味着任何具体的描述仅适用于特定的JVM），但它必须通过统计随机数生成器测试。

虽然实现过程中可能存在微妙的错误（参见OpenSSH密钥生成漏洞），但我认为没有具体的理由担心Java UUID的随机性。

37
实现中可能存在微妙的错误...或者（戴上锡纸帽）...故意设置微妙的缺陷。（<：-） - Stephen C
29
密码学强度与碰撞问题毫无关联。 - Sergey Orshanskiy
17
产生的碰撞数量不超出理论随机模型预期是随机数生成器 (RNG) 最基本的质量要求，而加密强度则是最高的。换言之，加密强度高的 RNG 肯定不会产生比预期更多的碰撞。 - Michael Borgwardt
4
值得注意的是，如果您在 https://blogs.vmware.com/cto/the-amazing-vm-recordreplay-feature-in-vmware-workstation-6/ 中运行生成UUID的JVM，可能会出现许多碰撞。所有软件随机数生成器都是伪随机数生成器，其质量取决于熵源；两个种子相同的伪随机数生成器也将表现相同，在具有一致和完全重复的服务器设置和启动程序的情况下，这种情况可能会惊人地发生。 - user508633
@user508633：在那种特定情况下，我实际上预计会得到100％的碰撞率，但这确实是一个非常特殊的情况，远远超出了“一致的完全重复的服务器设置和启动程序”。我相信，如果你只是克隆了一个虚拟机并正常运行它，你不会得到任何增加的碰撞率。SecureRandom的自我播种会尽力获取一些真正的熵，甚至在找不到任何熵的情况下阻止执行：https://www.seancassidy.me/wiggle-the-mouse-to-fix-the-test.html - Michael Borgwardt
虽然这只是把一个问题从JVM转移到了Linux内核中，但这是真实的。只要您相信Linux内核中的熵池估计是准确的（自然碰撞仍然很少见，但在那里出现错误可能会削弱安全性而面对专门的对手）。 - user508633
128

维基百科给出了一个很好的答案 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

生成随机版本4 UUID的数量，以至少有50％的概率发生至少一次冲突，需要生成2.71万亿个，计算如下：

...

这个数字相当于每秒生成10亿个UUID约85年，一个包含这么多UUID的文件，每个UUID是16字节，将达到45艾字节，比目前已经存在的最大数据库大得多，后者大约是数百拍字节的规模。

...

因此，要使重复的概率达到十亿分之一，必须生成103万亿个版本4 UUID。

67
如果地球上的每个人都拥有六亿个UUID，则一个重复的概率约为50％。我还要引用该页面上的话。 - Jeff Axelrod
29
这只适用于真正的随机数，而不适用于伪随机数，比如Java UUID。 - Markus
9
@Markus：完全错了。对于好的伪随机数生成器（特别是密码学上强的那些），碰撞的概率与“真正”的随机性没有区别。 - Michael Borgwardt
7
@Eric - 我认为你有责任支持你的说法。就我所知，唯一可能导致类型4 UUID发生碰撞频率高于概率理论预测的情况是：1）加密随机数源不好或2）UUID库已被攻击。 - Stephen C
16
这并不回答所提出的问题。该问题是关于Java中UUID.randomUUID()生成的随机性质量，而不是关于给定完美随机数生成器的理论概率。 - kratenko
显示剩余5条评论
74
有人有经验可以分享吗？
对于类型为4的UUID，有2^122种可能的值。（规范说明您会失去2个位用于类型和进一步的4个位用于版本号。）
假设您每秒生成100万个随机UUID，则在您的生命周期内发生重复的概率非常小。而要检测到重复，您必须解决每秒将1百万个新UUID与先前生成的所有UUID进行比较的问题！
任何人实际上注意到重复的概率甚至比微不足道的小...因为寻找碰撞的实际难度。
现在当然，您通常将使用伪随机数生成器，而不是真正的随机数源。但我认为，如果您使用信誉提供商提供的加密强度随机数，那么它将是加密强度，重复的概率将与理想（无偏）随机数生成器相同。
但是，如果您使用具有“损坏”加密随机数生成器的JVM，则所有赌注都将消失。（这可能包括某些系统上“熵短缺”问题的解决方法。或者某人在您的系统上游或上游修改了您的JRE。）
对于低密度和位的随机分布，假设您使用了像匿名评论者建议的“某种二进制B树”，则每个UUID都将需要O（NlogN）位的RAM内存来表示N个不同的UUID。现在将其乘以100万和您要运行实验的秒数。我认为这对于测试高质量RNG的冲突所需的时间长度来说是不切实际的。即使使用（假设的）巧妙表示方式。
5
“（而要检测重复，您需要解决每秒比较1百万个新UUID与先前生成的所有UUID的问题！）” - 假设您已将uuid存储在某种二叉树结构中，那么这部分相对简单，只需要对于每个新的uuid进行一次树下降即可。您不需要实际逐个与之前生成的所有uuid进行比较。 - user467257
"在你的一生中出现重复的可能性微乎其微。" "未来的后代会因为什么谴责我们呢..." - The Student
也许他们会谴责我们认为每秒生成10^6个唯一标识是不现实的假设，或者10^12个。或者我们可能没有意识到不存在所谓的随机数。或者其他一些难以想象的事情。但是...嘿...人类自古以来就一直在对自己的祖先进行评判，而这并没有改变什么。 - Stephen C
21

虽然我不是专家，但我认为足够聪明的人们多年来一直在研究Java的随机数生成器。因此，我也认为随机UUID很好。因此，您应该真正具有理论上的冲突概率（对于所有可能的UUID来说，这大约是1：3×10^38）。有人知道仅针对随机UUID，这会如何改变吗？是上面的1/（16×4）吗？

从我的实际经验来看，我到目前为止从未见过任何碰撞。当我第一次遇到碰撞时，我可能会长出惊人的长胡须;)

11
换句话说，只有在接下来的100年里每秒生成10亿个UUID时，才有大约50%的概率仅创建一个重复项。 - MaVRoSCy
1
实际上，维基百科说它可以用于未来85年...但我认为不要指望它，因为某个地方可能已经生成了与你相同的UUID。 - smac89
13

在以前的雇主那里，我们有一个包含随机 uuid 的独特列。它刚上线一周后就出现了重复。当然，概率很低，但并非为零。这就是为什么 Log4j 2 包含 UuidUtil.getTimeBasedUuid。只要您不在单个服务器上每毫秒生成超过10,000个 UUID，它就会生成一个可持续8,925年的唯一UUID。

2
是的。但问题是在询问随机（即类型4）UUID。 - Stephen C
1
它询问的是发生碰撞的可能性。暗示着他希望确保避免碰撞。 - rgoers
2
碰撞很可能是由于用于PRNG种子的随机源损坏造成的。虽然我猜这也有可能是纯粹的巧合。 - Stephen C
https://logging.apache.org/log4j/log4j-2.2/log4j-core/apidocs/org/apache/logging/log4j/core/util/UuidUtil.html -> 这个想法是在UUID中使用时间的100纳秒分辨率以及MAC地址。因此，如果在同一100纳秒间隔内生成两个UUID，它们不保证是随机的，实际上它们比具有更多随机位的UUID更有可能相等。我不知道碰撞的可能性有多大，但如果我的理解是正确的，那么只要遵守每毫秒10,000个UUID的限制，就不可能发生任何碰撞的暗示是错误的。 - undefined
@rgoers 你是对的，每次生成uuid时都会增加一个计数器，还有一个计数器用于记录经过的时间片数，所以我的担忧是没有根据的。https://logging.apache.org/log4j/log4j-2.4/log4j-core/apidocs/src-html/org/apache/logging/log4j/core/util/UuidUtil.html - undefined
显示剩余2条评论
12
许多答案都讨论了要生成多少个UUID才能达到50％的碰撞概率。但是，在必须（实际上）避免碰撞的应用程序中，50％、25％或甚至1％的碰撞概率都是无意义的。
程序员是否会惯常地将其他可能发生的事件也视为“不可能”呢？
当我们向磁盘或内存写入数据并再次读取时，我们认为数据是正确的。我们依靠设备的纠错功能来检测任何损坏。但未被检测到的错误的机率实际上大约是2-50。
在随机UUID中应用类似的标准会有意义吗？如果这样做，你会发现，在大约1000亿个随机UUID的集合中（236.5），“不可能”的碰撞是可能的。
这是一个天文数字，但像国家医疗保健系统的明细化账单或在大量设备上记录高频传感器数据等应用程序确实可能达到这些限制。如果你正在编写下一部《银河系漫游指南》之类的书籍，请勿尝试为每篇文章分配UUID！
作为比较的一点，赢得Powerball大奖的机会是3亿分之1，但售出1000万到2000万张彩票是很常见的。重点是许多人将“不可能”定义为少于数亿分之一的机会。 - erickson
11

UUID的原始生成方案是将UUID版本与生成UUID的计算机的MAC地址以及自公历在西方的采用以来的100纳秒间隔数连接起来。通过表示空间（计算机）和时间（间隔数）中的单个点，值冲突的可能性有效地为零。

1
这个解释让我对实践中不会发生碰撞感到乐观。你能指出任何支持这个说法的参考资料吗（最好是一些源代码）？ - Dragan Marjanović
在规格说明书http://www.ietf.org/rfc/rfc4122.txt中找到了这个。不过看到实现会很棒。 - Dragan Marjanović
1
然而，这个方案并不是Java所实现的。Java实现了类型4 UUID，它是纯随机的，不包括MAC地址或时间。顺便说一句，由于现在有许多物理和虚拟设备可以选择您的MAC地址，原始算法不能保证唯一性。 - Søren Boisen
这个模式不是Java标准库中实现的，但是在Java中通过log4j2实现了：https://logging.apache.org/log4j/log4j-2.2/log4j-core/apidocs/org/apache/logging/log4j/core/util/UuidUtil.html - undefined
4

去年我参加了彩票，但我从未赢过......但似乎这里有中奖者......

文档：https://www.rfc-editor.org/rfc/rfc4122

类型1：未实现。如果在同一时刻生成UUID，则可能发生冲突。可以通过人为异步实现来规避此问题。

类型2：从未见过实现。

类型3：MD5哈希：可能会发生冲突（128位-2个技术字节）

类型4：随机数：可能会发生冲突（就像彩票一样）。请注意，jdk6实现不使用“真正的”安全随机数，因为PRNG算法不是由开发人员选择的，您可以强制系统使用“差劲”的PRNG算法。因此，您的UUID是可预测的。

类型5：SHA1哈希：未实现：可能会发生冲突（160位-2个技术字节）

5
中奖彩票的概率可能是十分之一或一亿（10^7或10^8）左右。与128位随机数发生碰撞的概率为3.4 * 10^28。给我一张彩票吧，随时都可以！ - Stephen C
1

我们在应用程序中已经使用Java的随机UUID超过一年，而且使用非常广泛。但是我们从未遇到过碰撞的情况。

你能具体说明已经生成了多少个UUID吗？ - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接