使用不同算法的UUID碰撞风险

Question

我有一个数据库,其中2(或3或4)个不同的应用程序正在插入信息.新信息具有GUID/UUID类型的ID,但每个应用程序使用不同的算法来生成ID.例如,一个使用NHibernate的"guid.comb",另一个使用SQLServer的NEWID(),其他人可能想使用.NET的Guid.NewGuid()实现.

是否存在ID碰撞或重复的正常风险？

谢谢!

Answer 1

碰撞的风险略有提高,但仍然很小.考虑一下:

• Comb和NEWID/都NEWSEQUENTIALID包含一个精度低至几毫秒^†的时间戳.因此,除非您在所有这些不同来源的完全相同的时刻生成大量ID,否则ID 几乎不可能发生冲突.

• GUID中不基于时间戳的部分可以被认为是随机的; 大多数GUID算法都将这些数字基于PRNG.因此,这些其他10个字节之间发生冲突的可能性与您使用两个单独的随机数生成器并观察冲突的顺序相同.

  想想这一点 - PRNG可以并且确实重复数字,因此它们中的两个之间发生碰撞的可能性并不比仅使用其中一个的碰撞高得多,即使它们使用稍微不同的算法.这有点像每周播放相同的彩票号码而不是每周选择一个随机集合 - 获胜的几率完全相同.

现在,请记住,当您使用像Guid.Comb这样的算法时,您只有10位唯一符,相当于1024个单独的值.因此,如果您在相同的几毫秒内生成大量GUID,则会发生冲突.但是如果你以相当低的频率生成GUID,那么同时使用多少种不同的算法并不重要,碰撞的可能性实际上是不存在的.

绝对确定的最好方法是进行测试; 让所有2或3(或者你使用多少)同时以固定间隔生成GUID,并将它们写出到日志文件中,看看是否发生了冲突(如果是,有多少).这应该可以让您清楚地了解这在实践中的安全性.

PS如果您正在使用NHibernate的梳状生成器为集群主键生成GUID,请考虑使用NEWSEQUENTIALID()而不是NEWID()- 整个Comb点是为了避免页面拆分,如果您有其他进程使用非顺序,则无法实现算法.您还应该Guid.NewGuid使用相同的Comb生成器来更改任何代码- NHibernate中使用的实际Comb算法并不复杂,并且很容易在您自己的域逻辑中复制.

_{†请注意,似乎存在一些争议NEWID,以及它是否包含时间戳.在任何情况下,由于它基于MAC地址,因此可能值的范围远小于V4 GUID或Comb.我建议坚持使用数据库外部和数据库NEWSEQUENTIALID内部的Comb GUID的另一个原因.}

Answer 2

是的，风险高于正常，因为所有这些都使用不同的“GUID”定义。Guid.NewGuid() 是符合 RFC 的大部分随机 GUID，但 NEWSEQUENTIALID 是基于 MAC 地址和时间戳的重新排序（因此不符合 RFC）GUID，而 NHibernate 的梳状 GUID 则完全不同（基于随机性和时间戳） ）。

您可能只想考虑对一个 GUID 实现进行标准化。我为我的所有应用程序使用我自己类型的梳理 GUID。我的博客简要描述了所有这些类型的 GUID 以及我自己的设计决策。