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?
311
Respuestas:
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.
fuente
Wikipedia tiene una muy buena respuesta http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions
fuente
UUID.randomUUID()
, no sobre las posibilidades teóricas para un generador de números aleatorios perfecto dado.Hay
2^122
valores 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 representarN
distintos 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).fuente
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;)
fuente
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.
fuente
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.
fuente
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!
fuente
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
fuente
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)
fuente
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.
fuente