javascript - generate - uuid typescript

Colisiones al generar UUID en JavaScript?

Question

Esto se relaciona con esta pregunta . Estoy usando 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 parecía estar funcionando bien, sin embargo, tengo colisiones. Esto es lo que tengo:

• Una aplicación web que se ejecuta en Google Chrome.
• 16 usuarios.
• Alrededor de 4000 UUIDs han sido generados en los últimos 2 meses por estos usuarios.
• Recibí alrededor de 20 colisiones, por ejemplo, el nuevo UUID creado hoy era el mismo que hace 2 meses (usuario diferente).

Entonces las preguntas son:

1. ¿Qué está causando el problema?
2. ¿Cómo puedo evitarlo?

Answer 1

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

Parece que las colisiones solo ocurren en las primeras llamadas de Math.random. Porque si acaba de ejecutar el método createGUID / testGUIDs anterior (que obviamente fue lo primero que intenté) simplemente funciona sin colisiones.

Entonces para hacer una prueba completa uno necesita reiniciar Google Chrome, generar 32 bytes, reiniciar Chrome, generar, reiniciar, generar ...

Answer 2

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

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

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

Answer 3

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

Eventualmente me di cuenta de que el problema estaba (¿casi?) Asociado exclusivamente con los robots de rastreo de la red 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 una forma semiinteligente, con el resultado final de que no se puede contar con que su navegador spidering se comporte como lo hacen los navegadores normales.

Solo un FYI.

Answer 4

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

Acabo de realizar una prueba rudimentaria de 100.000 iteraciones en Chrome utilizando el algoritmo UUID que ha publicado y no he tenido ninguna colisión. 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 está ocurriendo algo más aquí?

Answer 5

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

Un buen artículo de los desarrolladores de Chrome sobre el estado de la calidad Math.random PRNG en Chrome, Firefox y Safari. tl; dr: a finales de 2015 es "bastante bueno", pero no de calidad criptográfica. Para abordar ese problema, aquí hay una versión actualizada de la solución anterior que usa ES6, la API crypto y un poco de JS wizardy del que no me puedo atribuir el mérito :

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