在JavaScript中生成UUID时发生冲突？

Question

这与this question有关。我正在使用this answer在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位用户
• 这些用户在过去2个月内已生成约4000个UUID。
• 我有大约20次碰撞 - 例如今天生成的新UUID与大约2个月前相同（不同的用户）。

所以问题是：

1. 是什么导致了这个问题？
2. 我怎么能避免呢？

Answer 1

我最好的猜测是，Math.random()由于某种原因在你的系统上被破坏了（听起来很奇怪）。这是我见过的第一个发生冲突的报告。

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

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

Answer 2

确实存在冲突，但仅限谷歌Chrome。在这里查看我对该主题的体验

http://devoluk.com/google-chrome-math-random-issue.html

似乎碰撞只发生在Math.random的前几次调用中。因为如果你只是运行上面的createGUID / testGUIDs方法（这显然是我尝试过的第一件事）它只是没有任何碰撞。

因此，要进行全面测试，需要重新启动Google Chrome，生成32字节，重启Chrome，生成，重启，生成...

Answer 3

正如其他人可以意识到这一点 - 我使用这里提到的UUID生成技术遇到了大量明显的冲突。即使在我为随机数发生器切换到seedrandom后，这些碰撞仍在继续。就像你想象的那样，让我把头发撕掉了。

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

只是一个FYI。

Answer 4

我想发布这个作为你的问题的评论，但显然StackOverflow不会让我。

我刚刚使用您发布的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 5

最初发布此UUID解决方案的The answer已于2017-06-28更新：

good article from Chrome developers讨论Chrome，Firefox和Safari中Math.random PRNG质量的状态。 tl; dr - 截至2015年底它“非常好”，但不是加密质量。为了解决这个问题，这里是使用ES6，crypto API和a bit of JS wizardy I can't take credit for的上述解决方案的更新版本：

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());