在 JavaScript 中生成 UUID 时发生冲突

Question

这与这个问题有关。我正在使用此答案 在 JavaScript 中生成 UUID：

'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
    return v.toString(16);
});

这个解决方案似乎工作正常，但我遇到了冲突。这就是我所拥有的：

• 在 Google Chrome 中运行的网络应用程序。
• 16 个用户。
• 这些用户在过去两个月内生成了约 4000 个 UUID。
• 我遇到了大约 20 次冲突 - 例如，今天生成的新 UUID 与大约两个月前（不同的用户）相同。

是什么导致了这个问题以及如何避免它？

Answer 1

我最好的猜测是，由于某种原因，您的系统上的 Math.random() 被破坏了（听起来很奇怪）。这是我第一次看到有人发生碰撞的报告。

node-uuid 有一个 测试工具，您可以用它来测试该代码中十六进制数字的分布。 如果看起来不错，那么它不是 Math.random()，因此请尝试将您正在使用的 UUID 实现替换为 uuid() 方法，然后查看如果你仍然得到好的结果。

[更新：刚刚看到Veselin 的报告关于启动时 Math.random() 的错误。由于问题仅在启动时出现，因此 node-uuid 测试不太可能有用。我将在 devoluk.com 链接上进行更详细的评论。]

Answer 2

确实存在冲突，但仅限于 Google Chrome 下。在 Google Chrome 随机数生成器问题

似乎冲突只发生在 Math.random 的前几次调用中。因为如果您只是运行上面的 createGUID / testGUIDs 方法（这显然是我尝试的第一件事），它就会正常工作而不会发生任何冲突。

因此，要进行完整的测试，需要重新启动 Google Chrome，生成 32 字节，重新启动 Chrome，生成，重新启动，生成等。

Answer 3

只是为了让其他人能够意识到这一点 - 我使用此处提到的 UUID 生成技术遇到了数量惊人的明显冲突。即使我将随机数生成器改用 seedrandom 后，这些冲突仍在继续。正如你可以想象的那样，这让我抓狂了。

我最终发现这个问题（几乎？）完全与谷歌的网络爬虫机器人有关。一旦我开始忽略用户代理字段中“googlebot”的请求，冲突就消失了。我猜测他们必须以某种半智能的方式缓存 JS 脚本的结果，最终的结果是他们的蜘蛛浏览器不能像普通浏览器那样运行。

仅供参考。

Answer 4

最初发布此 UUID 解决方案的答案已于 2017 年 6 月 28 日更新：

来自 Chrome 开发者的好文章 讨论 Chrome、Firefox 和 Safari 中 Math.random PRNG 质量的状态。 tl;dr - 截至 2015 年末，它“相当不错”，但加密质量不佳。为了解决这个问题，这里是上述解决方案的更新版本，它使用 ES6、crypto API 和 一点我不能相信的 JS 魔法：

function uuidv4() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  )
}

console.log(uuidv4());

Answer 5

我刚刚使用您发布的 UUID 算法在 Chrome 中运行了 100,000 次迭代的基本测试，并且没有遇到任何冲突。这是一个代码片段：

var createGUID = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

var testGUIDs = function(upperlimit) {
    alert('Doing collision test on ' + upperlimit + ' GUID creations.');
    var i=0, guids=[];
    while (i++<upperlimit) {
        var guid=createGUID();
        if (guids.indexOf(guid)!=-1) {
            alert('Collision with ' + guid + ' after ' + i + ' iterations');
        }
        guids.push(guid);
    }
    alert(guids.length + ' iterations completed.');
}

testGUIDs(100000);

Answer 6

这里的答案涉及“是什么导致了这个问题？” （Chrome Math.random 种子问题）但不是“我怎样才能避免它？”。

如果您仍在寻找如何避免此问题，我不久前写了这个答案作为对 Broofa 函数的修改解决这个问题。它的工作原理是将前 13 个十六进制数字偏移时间戳的十六进制部分，这意味着即使 Math.random 位于同一种子上，它仍然会生成不同的 UUID，除非在完全相同的毫秒内生成。