看了 Windows 的 GUID 生成算法，惊掉我下巴。

[3dwelcome]

原来没看到官方源代码前，我网上先搜了一下，做足了功课。一般都说 CLSID 的结构定义如下：

typedef struct _GUID {
DWORD Data1; // 随机数
WORD Data2; // 和时间相关
WORD Data3; // 和时间相关
BYTE Data4[8]; // 和网卡 MAC 相关
} GUID;

这看起来很合理，里面除了随机数，即有时间戳保证时间不重复，又有网卡保证物理区域不重复。

微软有专门生成 GUID 的 API, 叫 CoCreateGuid 给程序员调用。我看了代码，底层调用了 UuidCreate()。精彩部分的来了，查了 github 上的微软泄漏 UuidCreate()源代码后，发现整个函数核心就一句：

RpcStatus = GenerateRandomNumber((unsigned char *)Uuid, 16);

是的你没看错，就是生成 16 个随机数给用户。什么时间和网卡，全部都不存在！

是否碰撞？那就听天由命吧。只要冲突概率最小，那就可以忽略。（比如 TCP 包校验也有记录冲突，但同样选择忽略，具体可看这个贴： https://www.v2ex.com/t/767293 ）

[Jirajine]

泄露的是上古版本，简陋也正常。可能现在已经改了？

[3dwelcome]

@Jirajine 没改，微软的 VS 安装后，会自带一个 Create GUID 生成工具。

我一直天真的以为，这工具是 time base，或者和 Windows 系统时钟有点关系，然而今天发现，就是一个随机数生成器。

那我还不如自己程序来生产随机数呢。完全不加时间相关的变量的 GUID，大规模用起来，心里没底。

[0x2CA]

GUID 生成单线程生成用事件戳相同的的时间戳计数+1 就好，这样可以保证自己这个机子生成的唯一性

[xupefei]

Version 4 UUID 就是全部随机数，你看到的带网卡地址的版本是二十年前的了

[nannanziyu]

https://docs.microsoft.com/zh-cn/windows/win32/api/rpcdce/nf-rpcdce-uuidcreatesequential

[xupefei]

仔细看了看 lz 的贴，不知从何吐槽。
你又不知道 GenerateRandomNumber 是通过什么当种子的，怎么能说冲突概率大？

[3dwelcome]

@xupefei
时间戳算法是完全 0 冲突，另一个随机算法冲突概率极小，但小归小，冲突也是客观存在的吧。

只要是个严谨的码农，想都不用想，肯定选完全 0 冲突的算法。

生成慢点无所谓，关键就是在未来某年某月，千万别冲突就好。

@nannanziyu
不去深究，普通码农哪里会知道那么多。

就算安全性 MAC 去掉可以理解，但不能把时间戳也一起去掉吧？

我们以前同事写各种 COM 代码，都是直接那 Create GUID 工具来生成的。也是对微软无比信任，生成界面就算加个可选时间戳参数，或者加一段随机算法说明，那也是极好的。

[nannanziyu]

@3dwelcome
重新定义普通码农
你质疑一个 API 之前，至少要看下这个 API 自己的文档吧
https://docs.microsoft.com/en-us/windows/win32/api/rpcdce/nf-rpcdce-uuidcreate
UuidCreate 的文档页就说了这个事情

[3dwelcome]

@nannanziyu

你错了，普通码农只会调用 CoCreateGuid，这才是最常用的。没人会直接调用底层 RPC 的函数，也就是我提到了，你才会去查一下。

你去看看 CoCreateGuid 那个微软 API 文档，就没提到任何有关算法的事情。

[kop1989]

@3dwelcome #8 没太明白你想表达什么，调用的逻辑不就是 New GUID 》 CoCreateGuid 》 UuidCreate 么……
CoCreateGuid 的文档中也明确写着：

The CoCreateGuid function calls the RPC function UuidCreate, which creates a GUID, a globally unique 128-bit integer. Use CoCreateGuid when you need an absolutely unique number that you will use as a persistent identifier in a distributed environment.To a very high degree of certainty, this function returns a unique value – no other invocation, on the same or any other system (networked or not), should return the same value.

[3dwelcome]

@kop1989 我的控诉，是要微软给的 GUID 的唯一性得到算法上的保障！而不是返回几个随机数敷衍一下。

普通码农获取 GUID 的两个办法：
1. 用 VS 带的图形界面生成工具。
2. 用 CoCreateGuid 。

这两个方法，都不能在算法上得到保证。API 文档写了“Use CoCreateGuid when you need an absolutely unique number”， 所以我应该无脑信任微软，返回的 GUID 不重复吗？

你加一个 CoCreateGuidEx 函数都好啊，可惜什么都没有。

[kop1989]

@3dwelcome #10

普通码农难道不应该用 new Guid 么……GUID 类并没有承诺 GUID 一定是 100%不重复的。
Guid 类的说明是这么写的：

[SoloCompany]

rss 跳进来，发现有点不知所云，然后发现原来是 block 了楼主，解开看了下赶紧关掉，民科好可怕

[agagega]

这个就是 uuid v4

[lovecy]

没搞过 C++不知道微软 API 代码怎样
但是凡事一扯上绝对，那个代价基本就是无法承受的。所以人们都得在合理的范围内去靠近绝对，比如根据预估损失来决定安全程度。
所以其实就算发生了重复，也没楼主想象的那么糟 - -

[lovecy]

@lovecy 其实代码里对这种极小概率重复做一下处理，代价是很低的

[zhujinliang]

首先，电脑时钟精度、同时产生 GUID 个数、不同电脑时间不同步等，导致时间戳可能相同，甚至不同网卡的 MAC 也可能会相同，不存在你说的 0 冲突

随机数算法肯定是密码学的随机数算法，理论上可保证随机性，否则全世界的加密算法的安全性就打折扣了

有非纯随机部分构成的 GUID，不过是其中一部分用一些其他算法得出的数值代替了随机数，很难说这些算法随机性上优于密码学随机数生成器

[wevsty]

一个定长的字节块事实上没有任何方法能保证 100%不重复，只能去想办法降低不重复的概率而已。

事实上就算加上时间戳也不能保证 100%不重复，而且要制造一个时间戳成本远低于要随机出相同长度的字节数。

[3dwelcome]

@lovecy "其实代码里对这种极小概率重复做一下处理，代价是很低的"

微软自己内核用的是完全另外一套算法，用到的是高精度时钟，源代码我都找到了。

算法还读取注册表里防重复的值：HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Rpc\UuidSequenceNumber

但问题是不公开，对普通程序员就区分对待，这点我就觉得很不爽。

[AstroProfundis]

谁给你说的时间戳算法是 0 冲突的让他请你吃饭

[3dwelcome]

@kop1989

"GUID 类并没有承诺 GUID 一定是 100%不重复的。"

你去 wiki 查一下 guid, 有不是随机数，基于时间戳的版本（微软内部用的版本，比如早期 Office 的 COM GUID，都是这个生成的）。

原理就是写入 100ns 为间隔的时间戳，只要大于这个时间段生成的 GUID，就可以保证时间上无冲突，另外机器 ID 或者网卡 MAC，能保证空间上无冲突。

只要时空都能保证，那么就是 100%无冲突版本的 GUID 。也就是微软一开始用 GUID 算法的版本。

[GuuJiang]

@3dwelcome 只要一个东西是固定长度的，就不可能存在 100%不重复，鸽笼原理了解一下？

[Mutoo]

GUID 在同一个 business domian 里面重复的概率非常低，基本上可以忽略。不过全世界那么多 business domain，纯在相同的 GUID 是必然的。

但是我写的 APP 里面有一个跟你写的 APP 里有一个相同的 GUID 又如何？这是两个风马牛不相及的业务，并不会真正「冲突」。所以你要是担心重复，可以给你的业务逻辑再加细分子域就可以了。

[EPr2hh6LADQWqRVH]

只能说你对指数没有敬畏，2^128 什么概念缺少感性认识

[3dwelcome]

@GuuJiang 没说永远不重复，WIKI 上写了，GUID v1/v2 算法，到 3400 年之前，都不会重复。时间是不会倒流的。

@Mutoo 微软这个 GUID 生成的 COM Interface，不同软件安装后，写入的是同一个用户注册表。
也就是全球开发人员用的 domain, 在同一个地方。

[3dwelcome]

@avastms 你买云服务器，可靠性 100%和可靠性 99.9999%，就是本质上的区别。
数的就是小数点后面，有几个 9 。

[Mutoo]

@3dwelcome 这个只能算是一个微软操作系统上的一个 business domain 。 全球开发者写再多软件，2^128 也够保证微软在有生之年使用了。而你软件业务上的其它 GUID 并不会跟这个 domain 冲突。

[Aoang]

用过 UUID 的都知道 v4 冲突的概率比 v1 小的多。

v4 一共有 2^128 个 UUID，而 v1 在同一时间同一机器才留了几位给随机数。

只要时间机器相同，v1 就是渣渣，这也是为什么没人用的原因。同一机器多个进程就傻了。

另，因为要用时间戳，v1 只会越用越少。

[EPr2hh6LADQWqRVH]

@3dwelcome 就是说 2^1024 也满足不了你呗。。。

那建议你注意心理卫生。。。

[hoyixi]

代码烂很正常，winxp 之前蓝屏司空见惯，谁的 win 里面还不养几种病毒当宠物

[skies457]

@3dwelcome "原理就是写入 100ns 为间隔的时间戳，只要大于这个时间段生成的 GUID，就可以保证时间上无冲突" -> 连续生成几个就懵逼了吧

[3dwelcome]

@skies457 微软没那么傻，我看了代码，针对 100ns 额外处理有很多，也有随机数来保障。
比如预生成很多 guid 后，系统 cache 起来的。你代码获取到的 guid，时间戳有可能是早期的。

[NXzCH8fP20468ML5]

@3dwelcome 时间确实不会倒流，但不代表你电脑上的时间就正确啊。

[3dwelcome]

@xxfye “但不代表你电脑上的时间就正确啊。”

不同电脑就代表着空域不同，GUID 最后面 8 个 BYTE，就是用来保证空间不一致的。

有个 SSL 设计我想顺便提一下，人家的 random 就不是单纯的随机数，是包含时间戳的。时间是很重要的变量，在一定程度上，要比随机数可控。

[0bit]

就是 UUID v1 和 v4 之争 呗，实际使用中一直用 v4，没用过 v1 。

[geelaw]

谁说时间不会倒流的😅 Windows 有 NTP 时间校准机制，很容易发生时间倒流的情况。当然要确保有生之年生成真·不重复的 GUID 也很容易，人工控制时间戳、使用被毁灭的网卡的 MAC 地址并用 v1 算法即可。

毁灭网卡的例子：
https://devblogs.microsoft.com/oldnewthing/20040211-00/?p=40663

[3dwelcome]

@geelaw 其实本帖的主旨，就在于一个时间序列人为可控，另一个纯随机数不可控。

微软如果当年在 CoCreateGuid 里多加几个参数，别全部依赖于随机函数，也就没这个帖子了。

[billlee]

MAC 地址也才 48 bits, 现在虚拟机这么多，MAC 也无法保证唯一。所以还不如整个 128 bits 的随机数让冲突概率小一点

[billlee]

至于 TCP 那个问题，我觉得应该理解为是当时的历史问题。那个时代 CPU 性能太差，而链路层一般都有强校验，所以 TCP 不太需要强校验了

[lance6716]

不知道楼主有没有用 git，git 也是会有几率遇到哈希冲突的哦，难不难受

[mxT52CRuqR6o5]

工程实践中 rsa 算法使用的素数也未必是真正的素数，难受不难受

[Mutoo]

0.1+0.2=30000000000000004 难不难受😂

[swulling]

uuid4 碰撞的概率太低了。

这么说吧，每秒产出十亿个 uuid，连续产出 85 年，才有百分之五十的概率存在一次碰撞。

工程界不需要百分之百的保障

[swulling]

这么多 uuid，光 uuid 自己就有几十 EB，现在绝大部分实际的数据库有这么大么？担心什么碰撞？真是杞人忧天！

[sillydaddy]

是的。
就是#43 楼的 @swulling 提到的概率。
如果觉得 50%概率太高，可以换一个说法：每秒产出千万个 uuid，连续产出 85 年，才有百万分之五十的概率存在一次碰撞。如果换成每秒百万个 uuid，那么 85 年产生一次碰撞的概率就是一亿分之五十。

典型的“生日问题”：( https://zh.wikipedia.org/wiki/生日問題 )，里面有概率的计算公式。

[Te11UA]

这几天 LZ 发的帖子真的令人大开眼界

[g00001]

几乎每天都能看到这些：Windows 多么差劲，用 Windows 难道不浑身难受，用 Windows 惊掉下巴 …… 一个产品能做到天天被人讨论也真是难得，虽然 Windows 占领了桌面系统最大的市场，但为什么总有人喷 Windows 呢？！因为这些喷 Windows 的人都是精英 —— 精英们总是会有高人一等的看法，瞧不起不上档次的人间凡品

[msg7086]

@Te11UA 感谢提醒，去看了一眼，赶紧按了一下白色小按钮……

[hst001]

@3dwelcome #25
谁教你的带时间就零冲突？
只要你的 UUID 长度有限就必然有冲突的可能性，只有无限长的字符串才能做到零冲突，选一个能接受的冲突概率就行。

[3dwelcome]

@hst001 “谁教你的带时间就零冲突？”

GUID 又不需要短时间疯狂生成。以单机 PC 一秒生成一个来看，只要时间戳不重复，是不会冲突啊，wiki 上又没写错。

[newmlp]

随机有啥问题吗

[3dwelcome]

@newmlp 随机当然没问题，有问题的是微软内部用的不是随机算法（ v1 版本），给我们程序员用的是随机算法（ v4 版本）。

明显不公平啊。我就想生成 Office Excel 那种简洁明了的 GUID，而不是随机乱码那种。

[liuhan907]

@3dwelcome 那又是谁给你的自信时间戳是不会重复的。

[3dwelcome]

@liuhan907 "那又是谁给你的自信时间戳是不会重复的。"

你要换个思维，时间戳不一定是本地电脑，也可以是实时网络 ntp time server 动态返回的，这样误差就在可供的范围内。

[liuhan907]

@3dwelcome 所以你怎么就一定认为 ntp 返回时间就不会重复了呢。同时发生在两个机器上的请求怎么就不可能了？

[3dwelcome]

@sillydaddy 讨论概率的前提，是随机性足够高。这点对于这个案例不适用。

1. GUID v4 不是每个 128bit 都是变化的，不能满打满算。
2. GUID v4 里，GenerateRandomNumber 用到伪随机数生产算法，是 RC4 。

我不知道这算法每个 BIT 的概率是不是都相同的，不相同就不能用生日问题的概率来套用。（ ps: 最常见的 LCG 随机数生成器，就是 vc 早期附带的 rand，每个 bit 就是不同的）。

在 wiki 上，RC4 也陆续被别的 ChaCha20/AES 安全算法给替代（ https://en.wikipedia.org/wiki/RC4#RC4-based_random_number_generators)。当然不是说微软的 RC4 不好，一切数据都需要实测为准。

[swulling]

@3dwelcome 如果一秒生成一个的话，直到宇宙末日 uuid v4 重复概率依然极低

[hst001]

大家承认楼主是对的然后赶紧散了吧