¿Colisiones al generar UUID en JavaScript?

Esto se relaciona con esta pregunta . Estoy usando el código a continuación de esta respuesta para generar UUID en JavaScript:

'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);
});

Esta solución parece estar funcionando bien, pero tengo colisiones. Esto es lo que tengo:

• Una aplicación web que se ejecuta en Google Chrome.
• 16 usuarios.
• Estos usuarios han generado unos 4000 UUID en los últimos 2 meses.
• Tuve alrededor de 20 colisiones, por ejemplo, el nuevo UUID generado hoy era el mismo que hace aproximadamente 2 meses (usuario diferente).

¿Qué está causando este problema y cómo puedo evitarlo?

Mi mejor suposición es que Math.random()está roto en su sistema por alguna razón (por extraño que parezca). Este es el primer informe que he visto de alguien que sufre colisiones.

node-uuidtiene un arnés de prueba que puede usar para probar la distribución de dígitos hexadecimales en ese código. Si se ve bien, entonces no lo es Math.random(), así que intente sustituir la implementación UUID que está utilizando en el uuid()método allí y vea si aún obtiene buenos resultados.

[Actualización: Acabo de ver el informe de Veselin sobre el error Math.random()al inicio. Dado que el problema es solo al inicio, node-uuides poco probable que la prueba sea útil. Comentaré con más detalle en el enlace devoluk.com.]

De hecho, hay colisiones, pero solo bajo Google Chrome. Mira mi experiencia sobre el tema aquí.

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

(Enlace roto a partir de 2019. Enlace de archivo: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Parece que las colisiones solo ocurren en las primeras llamadas de Math.random. Porque si simplemente ejecuta el método createGUID / testGUIDs anterior (que obviamente fue lo primero que probé), simplemente funciona sin colisiones de ningún tipo.

Entonces, para hacer una prueba completa, es necesario reiniciar Google Chrome, generar 32 bytes, reiniciar Chrome, generar, reiniciar, generar ...

Solo para que otras personas puedan estar al tanto de esto, me encontré con una cantidad sorprendentemente grande de colisiones aparentes utilizando la técnica de generación de UUID mencionada aquí. Estas colisiones continuaron incluso después de que cambié a seedrandom para mi generador de números aleatorios. Eso me hizo arrancarme el pelo, como puedes imaginar.

Eventualmente descubrí que el problema estaba (¿casi?) Asociado exclusivamente con los robots de rastreo web de Google. Tan pronto como comencé a ignorar las solicitudes con "googlebot" en el campo de agente de usuario, las colisiones desaparecieron. Supongo que deben almacenar en caché los resultados de los scripts JS de alguna manera semiinteligente, con el resultado final de que no se puede contar con que su navegador spidering se comporte de la manera que lo hacen los navegadores normales.

Solo un FYI.

Quería publicar esto como un comentario a su pregunta, pero aparentemente StackOverflow no me lo permite.

Acabo de ejecutar una prueba rudimentaria de 100,000 iteraciones en Chrome usando el algoritmo UUID que publicaste y no obtuve colisiones. Aquí hay un fragmento de código:

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

¿Estás seguro de que no pasa nada más aquí?

La respuesta que publicó originalmente esta solución UUID se actualizó el 2017-06-28:

Un buen artículo de los desarrolladores de Chrome que analizan el estado de la calidad PRNG de Math.random en Chrome, Firefox y Safari. tl; dr - A finales de 2015 es "bastante bueno", pero no tiene calidad criptográfica. Para abordar ese problema, aquí hay una versión actualizada de la solución anterior que usa ES6, la cryptoAPI y un poco de asistente de JS que no puedo atribuirme :

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

Las respuestas aquí tratan de "¿qué está causando el problema?" (Problema de semilla aleatoria de Chrome Math.) Pero no "¿cómo puedo evitarlo?".

Si todavía está buscando cómo evitar este problema, escribí esta respuesta hace un tiempo como una versión modificada de la función de Broofa para solucionar este problema exacto. Funciona compensando los primeros 13 números hexadecimales por una parte hexadecimal de la marca de tiempo, lo que significa que incluso si Math.random está en la misma semilla, seguirá generando un UUID diferente a menos que se genere exactamente en el mismo milisegundo.