在 JavaScript 中生成 UUID 时发生冲突

IT技术 javascript random uuid collision
2021-02-28 12:30:56

这与这个问题有关我正在使用此答案中的以下代码在 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 中运行的 Web 应用程序。
  • 16 个用户。
  • 这些用户在过去两个月中生成了大约 4000 个 UUID。
  • 我遇到了大约 20 次冲突 - 例如,今天生成的新 UUID 与大约两个月前相同(不同的用户)。

是什么导致了这个问题,我该如何避免?

6个回答

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

node-uuid有一个测试工具,您可以使用它来测试该代码中十六进制数字的分布。 如果这看起来没问题,那么它就不是Math.random(),那么尝试将您正在使用的 UUID 实现替换到uuid()那里方法中,看看您是否仍然获得良好的结果。

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

到目前为止没有发生碰撞:)
2021-04-22 12:30:56
谢谢,我现在要使用 uuid.js,因为它使用浏览器的强大加密(如果可用)。将查看是否有任何冲突。
2021-04-24 12:30:56
无论如何,如果它是 Chrome 并且仅在启动时,您的应用程序可以使用上述函数生成和丢弃一行,比如说,十个 guid :)
2021-05-19 12:30:56
问题在于您从 Math.random() 获得的熵有限。对于某些浏览器,熵低至只有 41 位。多次调用 Math.random() 不会提高熵。如果您真的想要唯一的 v4 UUID,您需要使用加密强的 RNG,每个 UUID 生成的熵至少为 122 位。
2021-05-19 12:30:56
你能提供一个你所指的 uuid.js 代码的链接吗?(抱歉,不确定您指的是哪个库。)
2021-05-20 12:30:56

确实存在冲突,但仅限于在 Google Chrome 下。Google Chrome 随机数生成器问题中查看我在该主题上的经验

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

所以做一个完整的测试需要重启谷歌浏览器,生成32字节,重启Chrome,生成,重启,生成等。

这非常令人担忧 - 有没有人提出错误报告?
2021-04-21 12:30:56
尤其喜欢 javascript 中更好的随机数生成器的链接:baagoe.com/en/RandomMusings/javascript
2021-04-21 12:30:56
可悲的是,所述链接现在已损坏:(
2021-04-29 12:30:56
任何人都可以确认此错误是否已得到解决?
2021-05-12 12:30:56

只是为了让其他人能够意识到这一点 - 我使用这里提到的 UUID 生成技术遇到了数量惊人的明显冲突。即使在我为随机数生成器切换到seedrandom之后,这些冲突仍在继续你可以想象,这让我把头发扯掉了。

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

仅供参考。

我们的指标系统遇到了同样的问题。使用“node-uuid”module在浏览器中生成会话 ID 时看到了数千个 UUID 冲突。原来它一直是谷歌机器人。谢谢!
2021-05-11 12:30:56

我刚刚使用您发布的 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);
在 Windows 7 和 Windows XP 的组合上运行。
2021-04-28 12:30:56
另外,我注意到碰撞发生在相隔 3-4 周生成的 UUID 之间。
2021-04-30 12:30:56
很奇怪。你在什么平台上运行?
2021-04-30 12:30:56
V8 的 Math.random() 中似乎不太可能存在如此基本的缺陷,但如果您想尝试,Chromium 11 添加了对使用 window.crypto.getRandomValues API 生成强随机数的支持。blog.chromium.org/2011/06/...
2021-05-11 12:30:56
是的,我也进行了一些本地测试,但没有发生冲突。在不同用户机器上生成的 UUID 之间会发生冲突。我可能需要在不同的机器上生成一些数据并检查冲突。
2021-05-17 12:30:56

最初发布此 UUID 解决方案的答案已于 2017-06-28 更新:

一个来自Chrome的开发者很好的文章讨论的在Chrome,Firefox和Safari的Math.random PRNG质量状态。tl;dr - 截至 2015 年底,它“非常好”,但不是加密质量。为了解决这个问题,这里是上述解决方案的更新版本,它使用了 ES6、cryptoAPI 和一些我无法相信的 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());