V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
3dwelcome
V2EX  ›  分享发现

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

  •  
  •   3dwelcome · 2021-05-14 17:07:23 +08:00 · 7803 次点击
    这是一个创建于 1289 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原来没看到官方源代码前,我网上先搜了一下,做足了功课。一般都说 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

    58 条回复    2021-05-16 23:42:33 +08:00
    Jirajine
        1
    Jirajine  
       2021-05-14 17:09:44 +08:00 via Android
    泄露的是上古版本,简陋也正常。可能现在已经改了?
    3dwelcome
        2
    3dwelcome  
    OP
       2021-05-14 17:19:11 +08:00
    @Jirajine 没改,微软的 VS 安装后,会自带一个 Create GUID 生成工具。

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

    那我还不如自己程序来生产随机数呢。完全不加时间相关的变量的 GUID,大规模用起来,心里没底。
    0x2CA
        3
    0x2CA  
       2021-05-14 17:22:57 +08:00
    GUID 生成单线程生成用事件戳相同的的时间戳计数+1 就好,这样可以保证自己这个机子生成的唯一性
    xupefei
        4
    xupefei  
       2021-05-14 17:32:22 +08:00 via iPhone   ❤️ 1
    Version 4 UUID 就是全部随机数,你看到的带网卡地址的版本是二十年前的了
    xupefei
        6
    xupefei  
       2021-05-14 17:42:11 +08:00 via iPhone   ❤️ 1
    仔细看了看 lz 的贴,不知从何吐槽。
    你又不知道 GenerateRandomNumber 是通过什么当种子的,怎么能说冲突概率大?
    3dwelcome
        7
    3dwelcome  
    OP
       2021-05-14 17:55:41 +08:00
    @xupefei
    时间戳算法是完全 0 冲突,另一个随机算法冲突概率极小,但小归小,冲突也是客观存在的吧。

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

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

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

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

    我们以前同事写各种 COM 代码,都是直接那 Create GUID 工具来生成的。也是对微软无比信任,生成界面就算加个可选时间戳参数,或者加一段随机算法说明,那也是极好的。
    nannanziyu
        8
    nannanziyu  
       2021-05-14 17:59:56 +08:00
    @3dwelcome
    重新定义普通码农
    你质疑一个 API 之前,至少要看下这个 API 自己的文档吧
    https://docs.microsoft.com/en-us/windows/win32/api/rpcdce/nf-rpcdce-uuidcreate
    UuidCreate 的文档页就说了这个事情
    3dwelcome
        9
    3dwelcome  
    OP
       2021-05-14 18:06:44 +08:00
    @nannanziyu

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

    你去看看 CoCreateGuid 那个微软 API 文档,就没提到任何有关算法的事情。
    kop1989
        10
    kop1989  
       2021-05-14 18:13:53 +08:00
    @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
        11
    3dwelcome  
    OP
       2021-05-14 18:22:23 +08:00
    @kop1989 我的控诉,是要微软给的 GUID 的唯一性得到算法上的保障!而不是返回几个随机数敷衍一下。

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

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

    你加一个 CoCreateGuidEx 函数都好啊,可惜什么都没有。
    kop1989
        12
    kop1989  
       2021-05-14 18:29:22 +08:00
    @3dwelcome #10

    普通码农难道不应该用 new Guid 么……GUID 类并没有承诺 GUID 一定是 100%不重复的。
    Guid 类的说明是这么写的:
    SoloCompany
        13
    SoloCompany  
       2021-05-14 18:32:22 +08:00 via iPhone   ❤️ 7
    rss 跳进来,发现有点不知所云,然后发现原来是 block 了楼主,解开看了下赶紧关掉,民科好可怕
    agagega
        14
    agagega  
       2021-05-14 18:35:29 +08:00 via iPhone
    这个就是 uuid v4
    lovecy
        15
    lovecy  
       2021-05-14 18:38:54 +08:00
    没搞过 C++不知道微软 API 代码怎样
    但是凡事一扯上绝对,那个代价基本就是无法承受的。所以人们都得在合理的范围内去靠近绝对,比如根据预估损失来决定安全程度。
    所以其实就算发生了重复,也没楼主想象的那么糟 - -
    lovecy
        16
    lovecy  
       2021-05-14 18:41:05 +08:00
    @lovecy 其实代码里对这种极小概率重复做一下处理,代价是很低的
    zhujinliang
        17
    zhujinliang  
       2021-05-14 18:41:45 +08:00 via iPhone
    首先,电脑时钟精度、同时产生 GUID 个数、不同电脑时间不同步等,导致时间戳可能相同,甚至不同网卡的 MAC 也可能会相同,不存在你说的 0 冲突

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

    有非纯随机部分构成的 GUID,不过是其中一部分用一些其他算法得出的数值代替了随机数,很难说这些算法随机性上优于密码学随机数生成器
    wevsty
        18
    wevsty  
       2021-05-14 18:48:31 +08:00
    一个定长的字节块事实上没有任何方法能保证 100%不重复,只能去想办法降低不重复的概率而已。

    事实上就算加上时间戳也不能保证 100%不重复,而且要制造一个时间戳成本远低于要随机出相同长度的字节数。
    3dwelcome
        19
    3dwelcome  
    OP
       2021-05-14 18:48:43 +08:00
    @lovecy "其实代码里对这种极小概率重复做一下处理,代价是很低的"

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

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

    但问题是不公开,对普通程序员就区分对待,这点我就觉得很不爽。
    AstroProfundis
        20
    AstroProfundis  
       2021-05-14 18:54:54 +08:00
    谁给你说的时间戳算法是 0 冲突的让他请你吃饭
    3dwelcome
        21
    3dwelcome  
    OP
       2021-05-14 19:00:20 +08:00
    @kop1989

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

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

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

    只要时空都能保证,那么就是 100%无冲突版本的 GUID 。也就是微软一开始用 GUID 算法的版本。
    GuuJiang
        22
    GuuJiang  
       2021-05-14 19:04:27 +08:00 via iPhone
    @3dwelcome 只要一个东西是固定长度的,就不可能存在 100%不重复,鸽笼原理了解一下?
    Mutoo
        23
    Mutoo  
       2021-05-14 19:04:44 +08:00
    GUID 在同一个 business domian 里面重复的概率非常低,基本上可以忽略。不过全世界那么多 business domain,纯在相同的 GUID 是必然的。

    但是我写的 APP 里面有一个跟你写的 APP 里有一个相同的 GUID 又如何?这是两个风马牛不相及的业务,并不会真正「冲突」。所以你要是担心重复,可以给你的业务逻辑再加细分子域就可以了。
    EPr2hh6LADQWqRVH
        24
    EPr2hh6LADQWqRVH  
       2021-05-14 19:06:57 +08:00   ❤️ 2
    只能说你对指数没有敬畏,2^128 什么概念缺少感性认识
    3dwelcome
        25
    3dwelcome  
    OP
       2021-05-14 19:09:40 +08:00
    @GuuJiang 没说永远不重复,WIKI 上写了,GUID v1/v2 算法,到 3400 年之前,都不会重复。时间是不会倒流的。

    @Mutoo 微软这个 GUID 生成的 COM Interface,不同软件安装后,写入的是同一个用户注册表。
    也就是全球开发人员用的 domain, 在同一个地方。
    3dwelcome
        26
    3dwelcome  
    OP
       2021-05-14 19:11:46 +08:00
    @avastms 你买云服务器,可靠性 100%和可靠性 99.9999%,就是本质上的区别。
    数的就是小数点后面,有几个 9 。
    Mutoo
        27
    Mutoo  
       2021-05-14 19:11:48 +08:00
    @3dwelcome 这个只能算是一个微软操作系统上的一个 business domain 。 全球开发者写再多软件,2^128 也够保证微软在有生之年使用了。而你软件业务上的其它 GUID 并不会跟这个 domain 冲突。
    Aoang
        28
    Aoang  
       2021-05-14 19:18:18 +08:00 via Android   ❤️ 1
    用过 UUID 的都知道 v4 冲突的概率比 v1 小的多。

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

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

    另,因为要用时间戳,v1 只会越用越少。
    EPr2hh6LADQWqRVH
        29
    EPr2hh6LADQWqRVH  
       2021-05-14 19:19:04 +08:00
    @3dwelcome 就是说 2^1024 也满足不了你呗。。。

    那建议你注意心理卫生。。。
    hoyixi
        30
    hoyixi  
       2021-05-14 19:22:27 +08:00
    代码烂很正常,winxp 之前蓝屏司空见惯,谁的 win 里面还不养几种病毒当宠物
    skies457
        31
    skies457  
       2021-05-14 19:31:18 +08:00
    @3dwelcome "原理就是写入 100ns 为间隔的时间戳,只要大于这个时间段生成的 GUID,就可以保证时间上无冲突" -> 连续生成几个就懵逼了吧
    3dwelcome
        32
    3dwelcome  
    OP
       2021-05-14 19:43:10 +08:00 via Android
    @skies457 微软没那么傻,我看了代码,针对 100ns 额外处理有很多,也有随机数来保障。
    比如预生成很多 guid 后,系统 cache 起来的。你代码获取到的 guid,时间戳有可能是早期的。
    NXzCH8fP20468ML5
        33
    NXzCH8fP20468ML5  
       2021-05-14 19:43:22 +08:00
    @3dwelcome 时间确实不会倒流,但不代表你电脑上的时间就正确啊。
    3dwelcome
        34
    3dwelcome  
    OP
       2021-05-14 20:17:37 +08:00
    @xxfye “但不代表你电脑上的时间就正确啊。”

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

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

    0bit
        35
    0bit  
       2021-05-14 20:18:43 +08:00   ❤️ 1
    就是 UUID v1 和 v4 之争 呗,实际使用中一直用 v4,没用过 v1 。
    geelaw
        36
    geelaw  
       2021-05-14 20:56:09 +08:00 via iPhone
    谁说时间不会倒流的😅 Windows 有 NTP 时间校准机制,很容易发生时间倒流的情况。当然要确保有生之年生成真·不重复的 GUID 也很容易,人工控制时间戳、使用被毁灭的网卡的 MAC 地址并用 v1 算法即可。

    毁灭网卡的例子:
    https://devblogs.microsoft.com/oldnewthing/20040211-00/?p=40663
    3dwelcome
        37
    3dwelcome  
    OP
       2021-05-14 21:45:38 +08:00
    @geelaw 其实本帖的主旨,就在于一个时间序列人为可控,另一个纯随机数不可控。

    微软如果当年在 CoCreateGuid 里多加几个参数,别全部依赖于随机函数,也就没这个帖子了。
    billlee
        38
    billlee  
       2021-05-14 22:13:16 +08:00
    MAC 地址也才 48 bits, 现在虚拟机这么多,MAC 也无法保证唯一。所以还不如整个 128 bits 的随机数让冲突概率小一点
    billlee
        39
    billlee  
       2021-05-14 22:20:42 +08:00
    至于 TCP 那个问题,我觉得应该理解为是当时的历史问题。那个时代 CPU 性能太差,而链路层一般都有强校验,所以 TCP 不太需要强校验了
    lance6716
        40
    lance6716  
       2021-05-15 00:47:19 +08:00 via Android
    不知道楼主有没有用 git,git 也是会有几率遇到哈希冲突的哦,难不难受
    mxT52CRuqR6o5
        41
    mxT52CRuqR6o5  
       2021-05-15 01:04:31 +08:00 via Android
    工程实践中 rsa 算法使用的素数也未必是真正的素数,难受不难受
    Mutoo
        42
    Mutoo  
       2021-05-15 06:57:25 +08:00 via iPhone
    0.1+0.2=30000000000000004 难不难受😂
    swulling
        43
    swulling  
       2021-05-15 07:28:31 +08:00 via iPhone
    uuid4 碰撞的概率太低了。

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

    工程界不需要百分之百的保障
    swulling
        44
    swulling  
       2021-05-15 07:30:22 +08:00 via iPhone
    这么多 uuid,光 uuid 自己就有几十 EB,现在绝大部分实际的数据库有这么大么?担心什么碰撞?真是杞人忧天!
    sillydaddy
        45
    sillydaddy  
       2021-05-15 10:14:15 +08:00
    是的。
    就是#43 楼的 @swulling 提到的概率。
    如果觉得 50%概率太高,可以换一个说法:每秒产出千万个 uuid,连续产出 85 年,才有百万分之五十的概率存在一次碰撞。如果换成每秒百万个 uuid,那么 85 年产生一次碰撞的概率就是一亿分之五十。

    典型的“生日问题”:( https://zh.wikipedia.org/wiki/生日問題 ),里面有概率的计算公式。
    Te11UA
        46
    Te11UA  
       2021-05-15 11:00:47 +08:00
    这几天 LZ 发的帖子真的令人大开眼界
    g00001
        47
    g00001  
       2021-05-15 11:57:51 +08:00
    几乎每天都能看到这些:Windows 多么差劲,用 Windows 难道不浑身难受,用 Windows 惊掉下巴 …… 一个产品能做到天天被人讨论也真是难得,虽然 Windows 占领了桌面系统最大的市场,但为什么总有人喷 Windows 呢?!因为这些喷 Windows 的人都是精英 —— 精英们总是会有高人一等的看法,瞧不起不上档次的人间凡品
    msg7086
        48
    msg7086  
       2021-05-15 12:08:49 +08:00
    @Te11UA 感谢提醒,去看了一眼,赶紧按了一下白色小按钮……
    hst001
        49
    hst001  
       2021-05-15 12:57:57 +08:00
    @3dwelcome #25
    谁教你的带时间就零冲突?
    只要你的 UUID 长度有限就必然有冲突的可能性,只有无限长的字符串才能做到零冲突,选一个能接受的冲突概率就行。
    3dwelcome
        50
    3dwelcome  
    OP
       2021-05-15 13:34:54 +08:00
    @hst001 “谁教你的带时间就零冲突?”

    GUID 又不需要短时间疯狂生成。以单机 PC 一秒生成一个来看,只要时间戳不重复,是不会冲突啊,wiki 上又没写错。
    newmlp
        51
    newmlp  
       2021-05-15 13:45:18 +08:00
    随机有啥问题吗
    3dwelcome
        52
    3dwelcome  
    OP
       2021-05-15 15:57:07 +08:00
    @newmlp 随机当然没问题,有问题的是微软内部用的不是随机算法( v1 版本),给我们程序员用的是随机算法( v4 版本)。

    明显不公平啊。我就想生成 Office Excel 那种简洁明了的 GUID,而不是随机乱码那种。
    liuhan907
        53
    liuhan907  
       2021-05-15 17:41:44 +08:00 via Android
    @3dwelcome 那又是谁给你的自信时间戳是不会重复的。
    3dwelcome
        54
    3dwelcome  
    OP
       2021-05-15 17:51:40 +08:00
    @liuhan907 "那又是谁给你的自信时间戳是不会重复的。"

    你要换个思维,时间戳不一定是本地电脑,也可以是实时网络 ntp time server 动态返回的,这样误差就在可供的范围内。
    liuhan907
        55
    liuhan907  
       2021-05-15 18:02:33 +08:00 via Android
    @3dwelcome 所以你怎么就一定认为 ntp 返回时间就不会重复了呢。同时发生在两个机器上的请求怎么就不可能了?
    3dwelcome
        56
    3dwelcome  
    OP
       2021-05-15 19:00:25 +08:00
    @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
        57
    swulling  
       2021-05-16 01:11:13 +08:00 via iPhone
    @3dwelcome 如果一秒生成一个的话,直到宇宙末日 uuid v4 重复概率依然极低
    hst001
        58
    hst001  
       2021-05-16 23:42:33 +08:00 via Android
    大家承认楼主是对的然后赶紧散了吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2756 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 12:45 · PVG 20:45 · LAX 04:45 · JFK 07:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.