¿Qué tan bueno es UUID.randomUUID de Java?

311

Sé que los UUID aleatorios tienen una muy, muy, muy baja probabilidad de colisión en teoría, pero me pregunto, en la práctica, ¿qué tan bueno es Java randomUUID()en términos de no tener colisión? ¿Alguien tiene alguna experiencia para compartir?

java uuid Alvin
fuente
10
En mi experiencia, nunca he visto una colisión ;-)
Thilo
44
Los algoritmos se especifican en RFC1422: ietf.org/rfc/rfc4122.txt
skaffman el
8
@skaffman: el RFC no dice absolutamente nada sobre el algoritmo utilizado para generar los dígitos aleatorios.
Michael Borgwardt
44
Como esta es una pregunta más abierta, supongo que no marcaré ninguna respuesta como la respuesta correcta; en cambio, le daré un voto a cada una de las respuestas que creo que es bueno :)
Alvin
55
De Wikipedia: ... En otras palabras, solo después de generar 1 billón de UUID por segundo durante los próximos 100 años, la probabilidad de crear un solo duplicado sería de aproximadamente el 50%.
MaVRoSCy

Respuestas:

168

Usa UUID java.security.SecureRandom, que se supone que es "criptográficamente fuerte". Si bien la implementación real no se especifica y puede variar entre JVM (lo que significa que cualquier declaración concreta hecha es válida solo para una JVM específica), sí exige que la salida pase una prueba estadística de generador de números aleatorios.

Siempre es posible que una implementación contenga errores sutiles que arruinen todo esto (vea el error de generación de claves OpenSSH), pero no creo que haya ninguna razón concreta para preocuparse por la aleatoriedad de los UUID de Java.

Michael Borgwardt
fuente
34
"Siempre es posible que una implementación contenga errores sutiles ..." - O (poniéndose un sombrero de papel de aluminio) ... defectos sutiles deliberados. <:-)
Stephen C
25
La fuerza criptográfica es completamente irrelevante para la cuestión de las colisiones.
osa
14
@osa: No producir colisiones (más de lo que cabría esperar de una aleatoriedad perfecta) es prácticamente el requisito de calidad más bajo para un RNG, mientras que la fuerza criptográfica es la más alta. En otras palabras, un RNG criptográficamente fuerte definitivamente no producirá más colisiones de lo esperado.
Michael Borgwardt
3
Sin embargo, puede ser útil tener en cuenta que si, por ejemplo, ejecuta una JVM produciendo UUID dentro de blogs.vmware.com/cto/… , probablemente obtendrá muchas colisiones. Todos los RNG de software son PRNG y, en última instancia, son tan buenos como su fuente de entropía; dos PRNG que se siembran de manera idéntica también se comportarán de manera idéntica, y eso puede suceder sorprendentemente a menudo con configuraciones de servidor y procedimientos de inicio consistentes y duplicados exactos.
user508633
@ user508633: en realidad esperaría obtener una tasa de colisión del 100% en ese caso específico, pero es un caso muy específico que va mucho más allá de "configuraciones de servidor y procedimientos de inicio consistentes y duplicados exactos". Estoy bastante seguro de que no obtendría mayores tasas de colisión si simplemente clonara una VM y la ejecutara normalmente. La auto-siembra de SecureRandom se esfuerza bastante para obtener una entropía real, hasta el punto de bloquear la ejecución si no puede encontrar ninguna: seancassidy.me/wiggle-the-mouse-to-fix-the-test.html
Michael Borgwardt
114

Wikipedia tiene una muy buena respuesta http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

El número de UUID de versión 4 aleatorios que deben generarse para tener una probabilidad del 50% de al menos una colisión es de 2.71 quintillones, calculado de la siguiente manera:

...

Este número es equivalente a generar mil millones de UUID por segundo durante aproximadamente 85 años, y un archivo que contenga tantos UUID, a 16 bytes por UUID, sería de aproximadamente 45 exabytes, muchas veces más grandes que las bases de datos más grandes que existen actualmente. El orden de cientos de petabytes.

...

Por lo tanto, para que haya una posibilidad de duplicación de uno en mil millones, se deben generar 103 trillones de UUID de versión 4.

sheki
fuente
56
También citaría de esa página: "La probabilidad de un duplicado sería de aproximadamente el 50% si cada persona en la tierra posee 600 millones de UUID".
Jeff Axelrod
24
Esto solo es cierto para la aleatoriedad verdadera, no para los números pseudoaleatorios como los UUID de Java.
Markus
99
@ Markus: completamente equivocado. La probabilidad de colisiones para buenos RNG pseudoaleatorios especialmente criptográficamente fuertes no es diferente de la aleatoriedad "verdadera".
Michael Borgwardt
66
@Eric: creo que es tu responsabilidad respaldar tu afirmación. FWIW, los únicos escenarios en los que puedo pensar donde los UUID de tipo 4 colisionarían con más frecuencia de lo que la teoría de probabilidad dice que deberían ser: 1) una mala fuente de números criptográficos aleatorios, o 2) una biblioteca de UUID que ha sido comprometida.
Stephen C
13
Esto no responde a la pregunta formulada. La pregunta es sobre la calidad de la aleatoriedad en Java UUID.randomUUID(), no sobre las posibilidades teóricas para un generador de números aleatorios perfecto dado.
kratenko
69

¿Alguien tiene alguna experiencia para compartir?

Hay 2^122valores posibles para un UUID de tipo 4. (La especificación dice que pierde 2 bits para el tipo y otros 4 bits para un número de versión).

Suponiendo que generara 1 millón de UUID aleatorios por segundo, las posibilidades de que ocurra un duplicado en su vida serían muy pequeñas. ¡Y para detectar el duplicado, tendría que resolver el problema de comparar 1 millón de nuevos UUID por segundo con todos los UUID que ha generado previamente 1 !

Las posibilidades de que alguien haya experimentado (es decir, que haya notado realmente ) un duplicado en la vida real son aún más pequeñas que la desaparición ... debido a la dificultad práctica de buscar colisiones.

Ahora, por supuesto, normalmente usará un generador de números pseudoaleatorios, no una fuente de números verdaderamente aleatorios. Pero creo que podemos estar seguros de que si está utilizando un proveedor acreditado para sus números aleatorios de fuerza criptográfica, entonces será fuerza criptográfica, y la probabilidad de repeticiones será la misma que para un generador de números aleatorios ideal (no sesgado) .

Sin embargo, si tuviera que usar una JVM con un generador de números criptoaleatorios "rotos", todas las apuestas están desactivadas. (Y eso podría incluir algunas de las soluciones para los problemas de "escasez de entropía" en algunos sistemas. O la posibilidad de que alguien haya jugado con su JRE, ya sea en su sistema o en sentido ascendente).

1 - Suponiendo que utilizó "algún tipo de árbol binario" como lo propuso un comentarista anónimo, cada UUID necesitará O(NlogN)bits de memoria RAM para representar Ndistintos UUID asumiendo una baja densidad y distribución aleatoria de los bits. Ahora multiplique eso por 1,000,000 y la cantidad de segundos por los que va a ejecutar el experimento. No creo que sea práctico por el tiempo necesario para probar las colisiones de un RNG de alta calidad. Ni siquiera con representaciones inteligentes (hipotéticas).

Stephen C
fuente
44
"(¡Y para detectar el duplicado, tendrías que resolver el problema de comparar 1 millón de nuevos UUID por segundo con todos los UUID que has generado previamente!"), Esa parte es relativamente sencilla, suponiendo que hayas almacenado tus uuids en algunos tipo de estructura de árbol binario, solo sería un descenso de árbol por nuevo uuid. No necesitaría compararlo individualmente con todos los uuids generados previamente.
user467257
20

No soy un experto, pero supongo que suficientes personas inteligentes miraron el generador de números aleatorios de Java a lo largo de los años. Por lo tanto, también asumiría que los UUID aleatorios son buenos. Entonces, realmente debería tener la probabilidad teórica de colisión (que es aproximadamente 1: 3 × 10 ^ 38 para todos los UUID posibles. ¿Alguien sabe cómo cambia esto solo para UUID aleatorios? ¿Es 1/(16*4)de lo anterior?)

Desde mi experiencia práctica, nunca he visto colisiones hasta ahora. Probablemente me haya dejado una barba asombrosamente larga el día que tenga mi primera;)

sfussenegger
fuente
10
De Wikipedia: ... En otras palabras, solo después de generar 1 billón de UUID por segundo durante los próximos 100 años, la probabilidad de crear un solo duplicado sería de aproximadamente el 50%.
MaVRoSCy
1
En realidad, Wikipedia dice que es por los próximos 85 años ... Yo digo que no cuentes con eso, alguien en algún lugar ha generado el mismo UUID que tú
smac89
12

En un antiguo empleador teníamos una columna única que contenía un líquido aleatorio. Tuvimos una colisión la primera semana después de que se desplegó. Claro, las probabilidades son bajas pero no son cero. Es por eso que Log4j 2 contiene UuidUtil.getTimeBasedUuid. Generará un UUID que es único durante 8,925 años siempre que no genere más de 10,000 UUID / milisegundos en un solo servidor.

rgoers
fuente
2
Si. Pero la pregunta es acerca de UUID aleatorios (es decir, tipo 4).
Stephen C
1
Se está preguntando sobre la probabilidad de sufrir una colisión. La implicación es que quiere asegurarse de evitarlos.
rgoers
1
(La colisión probablemente se debió a una fuente de aleatoriedad interrumpida para la siembra de los PRNG. Pensé que era posible que fuera por pura casualidad)
Stephen C
9

El esquema de generación original para UUID era concatenar la versión UUID con la dirección MAC de la computadora que genera el UUID, y con el número de intervalos de 100 nanosegundos desde la adopción del calendario gregoriano en Occidente. Al representar un solo punto en el espacio (la computadora) y el tiempo (el número de intervalos), la posibilidad de una colisión de valores es efectivamente nula.

Alex2Ustas
fuente
1
Esta explicación me hace optimista de no ver colisiones en la práctica. ¿Puede señalar alguna referencia para esta declaración (algún código fuente sería aún mejor)?
Dragan Marjanović
Encontré esto en las especificaciones ietf.org/rfc/rfc4122.txt . Sin embargo, sería genial ver la implementación.
Dragan Marjanović
1
Sin embargo, ese esquema no es lo que implementa Java. Java implementa el UUID tipo 4, que es puramente aleatorio y no incluye la dirección MAC ni la hora. Por cierto, dado que ahora hay muchos dispositivos físicos y virtuales donde puede elegir su dirección MAC, el algoritmo original no garantiza la unicidad.
Søren Boisen
8

Muchas de las respuestas discuten cuántos UUID tendrían que generarse para alcanzar un 50% de posibilidades de colisión. Pero una probabilidad de colisión del 50%, 25% o incluso 1% no tiene valor para una aplicación donde la colisión debe ser (virtualmente) imposible.

¿Los programadores descartan habitualmente como "imposibles" otros eventos que pueden ocurrir y ocurren?

Cuando escribimos datos en un disco o memoria y los leemos nuevamente, damos por sentado que los datos son correctos. Confiamos en la corrección de errores del dispositivo para detectar cualquier corrupción. Pero la posibilidad de errores no detectados es en realidad alrededor de 2-50 .

¿No tendría sentido aplicar un estándar similar a los UUID aleatorios? Si lo hace, encontrará que es posible una colisión "imposible" en una colección de alrededor de 100 mil millones de UUID aleatorios (2 36.5 ).

Este es un número astronómico, pero aplicaciones como la facturación detallada en un sistema nacional de salud o el registro de datos de sensores de alta frecuencia en una gran variedad de dispositivos definitivamente podrían toparse con estos límites. Si está escribiendo la próxima Guía del autoestopista galáctico, ¡no intente asignar UUID a cada artículo!

erickson
fuente
Como punto de comparación, la posibilidad de ganar un premio mayor de Powerball es de 1 en 300 millones, pero las ventas de 10 a 20 millones de boletos son típicas. El punto es que muchas personas definen "imposible" como algo menos de una oportunidad en cientos de millones.
erickson
4

Como la mayoría de las respuestas se centraron en la teoría, creo que puedo agregar algo a la discusión dando una prueba práctica que hice. En mi base de datos tengo alrededor de 4.5 millones de UUID generados usando Java 8 UUID.randomUUID (). Los siguientes son solo algunos que descubrí:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb


b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64


4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

Si fuera realmente aleatorio, la probabilidad de tener este tipo de UUID similares sería considerablemente baja (ver edición), ya que estamos considerando solo 4.5 millones de entradas. Entonces, aunque esta función es buena, en términos de no tener colisiones, para mí no parece tan buena como lo sería en teoría.

Editar :

Mucha gente parece no entender esta respuesta, así que aclararé mi punto: sé que las similitudes son "pequeñas" y están lejos de ser una colisión total. Sin embargo, solo quería comparar el UUID.randomUUID () de Java con un verdadero generador de números aleatorios, que es la pregunta real.

En un verdadero generador de números aleatorios, la probabilidad de que ocurra el último caso sería de alrededor de = 0.007%. Por lo tanto, creo que mi conclusión se mantiene.

La fórmula se explica en este artículo wiki en.wikipedia.org/wiki/Birthday_problem

André Pinheiro
fuente
66
Esto no es verdad. Este tipo de similitudes surgiría incluso con un verdadero generador de números aleatorios en 4,5 millones de líquidos. Las similitudes entre los UUID que proporcionó son pequeñas y lejanas, muy lejos de una colisión total.
user3711864
Estoy completamente de acuerdo con usted en que las similitudes son "pequeñas" y están lejos de ser una colisión total. Sin embargo, solo quería comparar el UUID.randomUUID () de Java con un verdadero generador de números aleatorios (esta es la pregunta). Con algunos cálculos podemos ver que, en un verdadero generador de números aleatorios, la probabilidad de que ocurra el último caso sería de alrededor de 1-e ^ (- 4500000 ^ 2 / (2 * 36 ^ 11)) = 0.007% = 1 en un 13k. Tendría que ser muy afortunado :)
André Pinheiro
1
Con 4,5 millones de artículos y un 1 en la oportunidad 13k, no sería sería una colisión parcial de esa manera espera que 346 veces?
Ben Lee
No @BenLee, calculé la probabilidad de que ese evento suceda considerando que tenemos 4.5 millones de artículos. No es una posibilidad de 1 en 13k para cada elemento. La fórmula que utilicé se puede encontrar en este artículo wiki en.wikipedia.org/wiki/Birthday_problem
André Pinheiro
2
¿Cuál era tu expectativa? Similar no es lo mismo, ¿no?
Koray Tugay
3

Juego en la lotería el año pasado, y nunca he ganado ... pero parece que la lotería tiene ganadores ...

doc: http://tools.ietf.org/html/rfc4122

Tipo 1: no implementado. la colisión es posible si el uuid se genera en el mismo momento. impl puede sincronizarse artificialmente para evitar este problema.

Tipo 2: nunca ver una implementación.

Tipo 3: hash md5: posible colisión (128 bits-2 bytes técnicos)

Tipo 4: aleatorio: posible colisión (como lotería). tenga en cuenta que el jdk6 impl no usa un "verdadero" aleatorio seguro porque el desarrollador no elige el algoritmo PRNG y puede forzar al sistema a usar un algoritmo PRNG "pobre". Entonces su UUID es predecible.

Tipo 5: hash sha1: no implementado: posible colisión (160 bytes técnicos de 2 bits)

Giher
fuente
44
La probabilidad de ganar la lotería es quizás uno de cada 10 o 100 millones (10 ^ 7 o 10 ^ 8) o algo así. La probabilidad de una colisión con un número aleatorio de 128 bits es 3.4 * 10 ^ 28. ¡Dame un boleto de lotería en cualquier momento!
Stephen C
0

Hemos estado usando el UUID aleatorio de Java en nuestra aplicación durante más de un año y eso en gran medida. Pero nunca llegamos a tener una colisión.

Afsar
fuente