util - ¿Qué tan bueno es el UUID.randomUUID de java?
uuid java util (10)
¿Alguien tiene alguna experiencia para compartir?
Hay 2^122 valores posibles para un UUID de tipo 4. (La especificación dice que se pierden 2 bits por el tipo y otros 4 bits por 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ías que resolver el problema de comparar 1 millón de UUID por segundo con todos los UUID que generaste anteriormente )
Las posibilidades de que alguien haya experimentado (es decir, que se haya dado cuenta ) de un duplicado en la vida real son incluso más pequeñas que las que desaparecen ... debido a la dificultad práctica de buscar colisiones.
Ahora, por supuesto, normalmente utilizarás 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á una fuerza criptográfica, y la probabilidad de repeticiones será la misma que para un generador de números aleatorios ideal (sin sesgos) .
Sin embargo, si tuviera que utilizar una JVM con un generador de números criptoaleables "rotos", todas las apuestas están desactivadas. (Y eso podría incluir algunas de las soluciones para problemas de "escasez de entropía" en algunos sistemas. O la posibilidad de que alguien haya manipulado su JRE, ya sea en su sistema o en sentido ascendente).
Sé que los UUID aleatorizados tienen una probabilidad muy, muy, muy baja de colisión en teoría, pero me pregunto, en la práctica, ¿qué tan bueno es el randomUUID() Java 5 en términos de no tener colisión? ¿Alguien tiene alguna experiencia para compartir?
El esquema de generación original para los UUID fue concatenar la versión de UUID con la dirección MAC de la computadora que está generando el UUID, y con el número de intervalos de 100 nanosegundos desde la adopción del calendario gregoriano en el Oeste. Al representar un único punto en el espacio (la computadora) y el tiempo (el número de intervalos), la probabilidad de una colisión en los valores es efectivamente nula.
En un antiguo empleador teníamos una columna única que contenía un uuid aleatorio. Conseguimos una colisión la primera semana después de su despliegue. Claro, las probabilidades son bajas pero no son cero. Es por eso que Log4j 2 contiene UuidUtil.getTimeBasedUuid. Generará un UUID que es único por 8,925 años, siempre y cuando no genere más de 10,000 UUID / milisegundos en un solo servidor.
Hemos estado utilizando el UUID aleatorio de Java en nuestra aplicación durante más de un año y eso muy ampliamente. Pero nunca nos encontramos con tener colisión.
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. las colisiones son posibles si el uuid se genera en el mismo momento. impl puede ser artificialmente una sincronización 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 la implementación jdk6 no utiliza un "verdadero" seguro aleatorio porque el desarrollador no puede elegir el algoritmo PRNG y puede forzar al sistema a usar un PRNG "pobre". Entonces tu UUID es predecible.
Tipo 5: hash sha1: no implementado: posible colisión (160 bit-2 bytes técnicos)
Muchas de las respuestas discuten cuántos UUID deberían generarse para alcanzar un 50% de probabilidad de una colisión. Pero un 50%, 25%, o incluso un 1% de probabilidad de colisión no vale para una aplicación donde la colisión debe ser (virtualmente) imposible.
¿Los programadores habitualmente descartan como "imposibles" otros eventos que pueden ocurrir?
Cuando escribimos datos en un disco o memoria y los volvemos a leer, damos por sentado que los datos son correctos. Confiamos en la corrección de errores del dispositivo para detectar cualquier daño. 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 las 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 Hitchhiker para la Galaxia, ¡no intente asignar UUID a cada artículo!
No soy un experto, pero como todos hablaron de teoría, creo que puedo agregar algo a la discusión dando un ejemplo práctico. En mi base de datos tengo alrededor de 4.5 millones de UUID generados utilizando 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-0ba00060fe64"
"be87a209-2114-45b3-9d5a-86d00060fe64"
"4a8a74a6-e972-4069-b480-bdea1177b21f"
"12fb4958-bee2-4c89-8cf8-edea1177b21f"
Si fuera realmente aleatorio, la probabilidad de tener este tipo de UUID similares sería considerablemente baja, 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.
No soy un experto, pero supongo que suficientes personas inteligentes observaron el generador de números aleatorios de Java a lo largo de los años. Por lo tanto, también asumo que los UUID aleatorios son buenos. Entonces, realmente debería tener la probabilidad de colisión teórica (que es aproximadamente 1: 3 × 10 ^ 38 para todos los UUID posibles. ¿Alguien sabe cómo cambia esto solo para los UUID aleatorios? ¿Es 1/(16*4) de los anteriores?)
Desde mi experiencia práctica, nunca he visto colisiones hasta ahora. Probablemente me habré crecido una barba asombrosamente larga el día que reciba la primera;)
UUID usa java.security.SecureRandom , que se supone que es "criptográficamente fuerte". Si bien la implementación real no está especificada y puede variar entre las JVM (lo que significa que cualquier declaración concreta realizada solo es válida para una JVM específica), exige que la salida debe pasar una prueba estadística de generador de números aleatorios.
Siempre es posible que una implementación contenga errores sutiles que arruinen todo esto (consulte el error de generación de claves de OpenSSH) pero no creo que haya ninguna razón concreta para preocuparse por la aleatoriedad de los UUID de Java.
Wikipedia tiene una muy buena respuesta http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions
el número de UUID de la 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 unos 45 exabytes, muchas veces más grande que las bases de datos más grandes que existen actualmente, que están en El orden de los centenares de petabytes.
...
Por lo tanto, para que haya una posibilidad de duplicación de una en mil millones, se deben generar UUID de la versión 4 de 103 billones.