He estado implementando un protocolo de red y requiero que los paquetes tengan identificadores únicos. Hasta ahora, solo he estado generando enteros aleatorios de 32 bits, y asumiendo que es astronómicamente improbable que haya una colisión durante la vida útil de un programa / conexión. ¿Se considera esto generalmente como una práctica aceptable en el código de producción, o se debe diseñar un sistema más complejo para evitar colisiones?
Cuidado con la paradoja de cumpleaños .
Suponga que está generando una secuencia de valores aleatorios (uniformemente, independientemente) de un conjunto de tamaño N (N = 2 ^ 32 en su caso).
Luego, la regla de oro para la paradoja de cumpleaños indica que una vez que haya generado sobre sqrt (N) valores, hay al menos un 50% de probabilidad de que haya ocurrido una colisión, es decir, que haya al menos dos valores idénticos en la secuencia generada.
Para N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Entonces, después de que haya generado alrededor de 65k identificadores, ¡es más probable que dos de ellos colisionen que no! Si genera un identificador por segundo, esto sucedería en menos de un día; No hace falta decir que muchos protocolos de red funcionan mucho más rápido que eso.
Se considera ampliamente aceptable confiar en que los números aleatorios sean únicos si esos números tienen suficientes bits. Hay protocolos criptográficos donde la repetición de un número aleatorio romperá toda la seguridad. Y mientras no se utilicen vulnerabilidades graves en el generador de números aleatorios, eso no ha sido un problema.
Uno de los algoritmos para generar UUID generará efectivamente una ID que consta de 122 bits aleatorios y asumirá que será único. Y dos de los otros algoritmos se basan en un valor hash truncado a 122 bits que es único, lo que tiene aproximadamente el mismo riesgo de colisiones.
Por lo tanto, existen estándares que se basan en que 122 bits son suficientes para hacer que una ID aleatoria sea única, pero 32 bits definitivamente no es suficiente. Con las ID de 32 bits, solo se necesitan aproximadamente 2¹⁶ ID antes de que el riesgo de una colisión alcance el 50% porque con las 2¹⁶ ID habrá cerca de 2³¹ pares, cada una de las cuales podría ser una colisión.
Incluso 122 bits es menos de lo que recomendaría en cualquier diseño nuevo. Si seguir una cierta estandarización es importante para usted, entonces use los UUID. De lo contrario, utilice algo más grande que 122 bits.
La función de hash SHA1 con una salida de 160 bits ya no se considera segura, en parte porque 160 bits no son suficientes para garantizar la singularidad de las salidas. Las funciones hash modernas tienen salidas de 224 a 512 bits. Las ID generadas aleatoriamente deben apuntar a los mismos tamaños para garantizar la exclusividad con un buen margen de seguridad.
Yo llamaría a esto una mala práctica. Los números aleatorios se generan simplemente no crean números únicos, simplemente crean números aleatorios. Es probable que una distribución aleatoria incluya algunos duplicados. Puedes hacer esta circunstancia aceptablemente improbable agregando un elemento de tiempo. Si obtiene la hora actual del reloj del sistema en milisegundos. Algo como esto:
parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))
recorrerá un largo camino Obviamente, para garantizar realmente la singularidad es necesario utilizar UUID / GUID. Pero pueden ser costosos de generar, lo anterior es probablemente suficiente, ya que la única posibilidad de superposición es si el generador aleatorio tenía un duplicado en el mismo milisegundo.
Depende tanto de la probabilidad de falla como de las consecuencias de la falla.
Recuerdo un debate entre gente de software y hardware donde la gente de hardware consideraba que un algoritmo con una pequeña probabilidad de resultados incorrectos (algo así como una falla en 100 años) era aceptable, y la gente de software pensó que esto era un anatema. Resultó que la gente de hardware calculó rutinariamente las tasas de falla esperadas, y estaban muy acostumbradas a la idea de que todo daría respuestas incorrectas de vez en cuando, por ejemplo. Debido a las perturbaciones causadas por los rayos cósmicos; encontraron extraño que la gente de software esperara un 100% de confiabilidad.
Claro, tienes probabilidades bastante bajas de que dos enteros aleatorios de 32 bits sean secuenciales, pero no es del todo imposible. La decisión de ingeniería apropiada se basa en cuáles serían las consecuencias de las colisiones, una estimación del volumen de números que está generando, la vida útil durante la cual se requiere la singularidad & ¿Qué sucede si un usuario malintencionado comienza a intentar causar colisiones?
Puede ser aceptable asumir que los números aleatorios serán únicos, pero debes tener cuidado.
Suponiendo que sus números aleatorios están distribuidos equitativamente, la probabilidad de una colisión es aproximadamente (n 2 / 2) / k donde n es el número de números aleatorios que genera y k es el número de posibles valores que un número "aleatorio" puede tomar.
No le asignas un número astronómicamente improbable, así que vamos a tomarlo como 1 en 2 30 (aproximadamente en mil millones). Digamos además que genera 2 30 paquetes (si cada paquete representa aproximadamente un kilobyte de datos, esto significa aproximadamente un terabyte de datos totales, grandes pero no inimaginablemente). Descubrimos que necesitamos un número aleatorio con al menos 2 89 valores posibles.
Primero, tus números aleatorios deben ser lo suficientemente grandes. Un número aleatorio de 32 bits puede tener como máximo 2 valores posibles 32 . Para un servidor ocupado que no es lo suficientemente alto.
En segundo lugar, su generador de números aleatorios debe tener un estado interno suficientemente grande. Si su generador de números aleatorios solo tiene un estado interno de 32 bits, no importa qué tan grande sea el valor que genere de él, solo obtendrá un máximo de 2 32 valores posibles.
En tercer lugar, si necesita que los números aleatorios sean únicos en todas las conexiones en lugar de solo dentro de una conexión, su generador de números aleatorios debe estar bien sembrado. Esto es especialmente cierto si su programa se reinicia con frecuencia.
En general, los generadores de números aleatorios "regulares" en lenguajes de programación no son adecuados para tal uso. Los generadores de números aleatorios proporcionados por las bibliotecas de criptografía en general son.
incorporado en algunas de las respuestas anteriores es la suposición de que el generador de números aleatorios es en realidad 'plano'; que la probabilidad de que dos números sean los siguientes es la misma.
Eso probablemente no sea cierto para la mayoría de los generadores de números aleatorios. La mayoría de los cuales usan un polinomio de alto orden aplicado repetidamente a una semilla.
Dicho esto, hay muchos sistemas que dependen de este esquema, generalmente con UUID. Por ejemplo, cada objeto y activo en Second Life tiene un UUID de 128 bits, generado aleatoriamente, y rara vez chocan.
Muchas personas ya han dado respuestas de alta calidad, pero me gustaría agregar algunos puntos menores: primero, el punto de @nomadictype sobre la paradoja del cumpleaños es excelente .
Otro punto: la aleatoriedad no es tan sencilla de generar y definir como la gente podría asumir. (De hecho, en realidad hay pruebas estadísticas de aleatoriedad disponibles).
Dicho esto, es importante conocer la Falacia del jugador , que es una falacia estadística en la que las personas Supongamos que los eventos independientes de alguna manera se influyen mutuamente. Los eventos aleatorios generalmente son estadísticamente independientes entre sí, es decir, si genera un "10" aleatoriamente, no cambia su probabilidad futura de generar más "10" s en lo más mínimo. (Tal vez alguien podría crear una excepción a esa regla, pero yo esperaría que ese fuera el caso de casi todos los generadores de números aleatorios).
Así que mi respuesta es que si pudieras asumir que una secuencia suficientemente larga de números aleatorios era única, realmente no serían números aleatorios porque eso sería un patrón estadístico claro. Además, implicaría que cada nuevo número no es un evento independiente porque si genera, por ejemplo, un 10, eso significaría que la probabilidad de generar cualquier 10 en el futuro sería del 0% (posiblemente no podría ocurrir), más eso significaría que aumentaría las posibilidades de obtener un número distinto de 10 (es decir, cuantos más números genere, mayor será la probabilidad de que cada uno de los números restantes se convierta en uno).
Una cosa más a considerar: la posibilidad de ganar el Powerball de jugar un solo juego es, según tengo entendido, aproximadamente 1 de cada 175 millones. Sin embargo, las probabilidades de que alguien gane son considerablemente más altas que eso. Le interesan más las probabilidades de que alguien "gane" (es decir, que sea un duplicado) de alguien que las probabilidades de que un número en particular "gane" / sea un duplicado.
No importa cuántos bits utilice, NO PUEDE garantizar que dos números "aleatorios" serán diferentes. En cambio, sugiero que use algo como la dirección IP u otra dirección de red de la computadora y un número secuencial, preferiblemente un número secuencial HONKIN 'BIG - 128 bits (obviamente sin signo) suena como un buen comienzo, pero 256 sería mejor.
No, por supuesto que no. A menos que el rng esté utilizando muestras sin reemplazo, existe la posibilidad, por pequeña que sea, de duplicación.
Lea otras preguntas en las etiquetas programming-practices