language agnostic - ¿Es un GUID único el 100% del tiempo?

language-agnostic (19)

¿Es un GUID único el 100% del tiempo?

¿Se mantendrá único en múltiples hilos?

¿Es un GUID único el 100% del tiempo?

No garantizado, ya que hay varias formas de generar uno. Sin embargo, puede intentar calcular la posibilidad de crear dos GUID que sean idénticos y se le ocurre la idea: un GUID tiene 128 bits, por lo tanto, hay 2 ¹²⁸ GUID distintos, mucho más que estrellas en el universo conocido. Lea el artículo de wikipedia para más detalles.

Si bien no se garantiza que cada GUID generado sea único, el número total de claves únicas (2 ^ 128 o 3.4 × 10 ^ 38) es tan grande que la probabilidad de que se genere el mismo número dos veces es muy pequeña. Por ejemplo, considere el universo observable, que contiene aproximadamente 5 × 10 ^ 22 estrellas; cada estrella podría tener 6,8 × 10 ^ 15 GUID universalmente únicos.

De wikipedia

Estos son algunos buenos artículos sobre cómo se hace un GUID (para .NET) y cómo podría obtener el mismo Guid en la situación correcta.

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-three/

Al aire libre

Como nota al margen, estaba jugando con GUID de volumen en Windows XP. Este es un diseño de partición muy oscuro con tres discos y catorce volúmenes.

//?/Volume{23005604-eb1b-11de-85ba-806d6172696f}/ (F:) //?/Volume{23005605-eb1b-11de-85ba-806d6172696f}/ (G:) //?/Volume{23005606-eb1b-11de-85ba-806d6172696f}/ (H:) //?/Volume{23005607-eb1b-11de-85ba-806d6172696f}/ (J:) //?/Volume{23005608-eb1b-11de-85ba-806d6172696f}/ (D:) //?/Volume{23005609-eb1b-11de-85ba-806d6172696f}/ (P:) //?/Volume{2300560b-eb1b-11de-85ba-806d6172696f}/ (K:) //?/Volume{2300560c-eb1b-11de-85ba-806d6172696f}/ (L:) //?/Volume{2300560d-eb1b-11de-85ba-806d6172696f}/ (M:) //?/Volume{2300560e-eb1b-11de-85ba-806d6172696f}/ (N:) //?/Volume{2300560f-eb1b-11de-85ba-806d6172696f}/ (O:) //?/Volume{23005610-eb1b-11de-85ba-806d6172696f}/ (E:) //?/Volume{23005611-eb1b-11de-85ba-806d6172696f}/ (R:) | | | | | | | | | +-- 6f = o | | | +---- 69 = i | | +------ 72 = r | +-------- 61 = a +---------- 6d = m

No es que los GUID sean muy similares, sino el hecho de que todos los GUID tienen la cadena "mario" en ellos. ¿Es eso una coincidencia o hay una explicación detrás de esto?

Ahora, cuando busqué en Google para la parte 4 en el GUID, encontré aproximadamente 125.000 resultados con los GUID de volumen.

Conclusión: cuando se trata de GUID de volumen, no son tan únicos como otros GUID.

Desde http://www.guidgenerator.com/online-guid-generator.aspx

¿Qué es un GUID?
GUID (o UUID) es un acrónimo de ''Identificador global único'' (o ''Identificador universal único''). Es un número entero de 128 bits que se utiliza para identificar recursos. El término GUID es generalmente usado por los desarrolladores que trabajan con tecnologías de Microsoft, mientras que UUID se usa en cualquier otro lugar.
¿Qué tan único es un GUID?
128 bits es lo suficientemente grande y el algoritmo de generación es lo suficientemente único como para que si se generaran 1,000,000 GUID por segundo durante 1 año, la probabilidad de un duplicado sería solo del 50%. O si cada humano en la Tierra generara 600,000,000 GUIDs, solo habría un 50% de probabilidad de un duplicado.

En un sentido más general, esto se conoce como el "problema del cumpleaños" o "paradoja del cumpleaños". Wikipedia tiene una visión general bastante buena en: Wikipedia - Problema de cumpleaños

En términos muy aproximados, la raíz cuadrada del tamaño de la agrupación es una aproximación aproximada de cuándo se puede esperar un 50% de probabilidad de un duplicado. El artículo incluye una tabla de probabilidad de tamaño de grupo y varias probabilidades, incluida una fila para 2 ^ 128. Por lo tanto, para una probabilidad de colisión del 1%, esperaría elegir de forma aleatoria 2.6 * 10 ^ 18 números de 128 bits. Un 50% de probabilidad requiere 2.2 * 10 ^ 19 selecciones, mientras que SQRT (2 ^ 128) es 1.8 * 10 ^ 19.

Por supuesto, ese es el caso ideal de un proceso verdaderamente aleatorio. Como han dicho otros, mucho se basa en ese aspecto aleatorio : ¿qué tan bueno es el generador y la semilla? Sería bueno si hubiera algún soporte de hardware para ayudar con este proceso, que sería más seguro, excepto que cualquier cosa puede ser falsificada o virtualizada. Sospecho que podría ser la razón por la cual las direcciones MAC / sellos de tiempo ya no están incorporados.

Eric Lippert ha escrito una serie muy interesante de artículos sobre GUIDs.

Hay en el orden 2 ³⁰ computadoras personales en el mundo (y, por supuesto, muchos dispositivos portátiles o dispositivos informáticos que no son PC y que tienen más o menos los mismos niveles de potencia informática, pero ignoremos esos). Supongamos que ponemos todas esas PC en el mundo para la tarea de generar GUID; si cada uno puede generar, digamos, 2 ²⁰ GUID por segundo, luego de solo 2 ⁷² segundos, ciento cincuenta billones de años , tendrá una probabilidad muy alta de generar una colisión con su GUID específico. Y las probabilidades de colisión se vuelven bastante buenas después de solo treinta trillones de años.

Experimenté un GUID duplicado.

Utilizo el escáner de escritorio Neat Receipts y viene con un software de base de datos propietario. El software tiene una función de sincronización con la nube, y recibí un error al sincronizar. Un vistazo a los registros reveló la línea impresionante:

"errores": [{"código": 1, "mensaje": "creator_guid: ya está tomado", "guid": "C83E5734-D77A-4B09-B8C1-9623CAC7B167"}]}

Me sorprendió un poco, pero seguramente lo suficiente, cuando encontré una forma de ingresar a mi base de datos local de neatworks y eliminé el registro que contenía ese GUID, el error dejó de ocurrir.

Entonces, para responder a tu pregunta con evidencia anecdótica, no. Un duplicado es posible. Pero es probable que la razón por la que sucedió no se debió al azar, sino a que la práctica estándar no se cumplió de alguna manera. (No tengo tanta suerte) Sin embargo, no puedo decirlo con seguridad. No es mi software.

Su atención al cliente fue EXTREMADAMENTE cortés y servicial, pero nunca antes se habían encontrado con este problema porque, después de más de 3 horas en el teléfono con ellos, no encontraron la solución. (FWIW, estoy muy impresionado con Neat, y esta falla, aunque frustrante, no cambió mi opinión sobre su producto).

He experimentado que los GUID no son únicos durante las pruebas unitarias de procesos múltiples o múltiples procesos (¿también?). Supongo que eso tiene que ver con que todas las otras cosas sean iguales, la siembra idéntica (o la falta de siembra) de los generadores seudoaleatorios. Lo estaba usando para generar nombres de archivos únicos. Encontré que el sistema operativo es mucho mejor haciendo eso :)

Alerta de arrastre

Preguntas si los GUID son 100% únicos. Eso depende del número de GUIDs entre los que debe ser único. A medida que el número de GUID se acerca al infinito, la probabilidad de duplicar los GUID se acerca al 100%.

La respuesta de "¿Es un GUID es 100% único?" es simplemente "no" .

Si desea un 100% de singularidad de GUID, entonces haga lo siguiente.
1. generar GUID
2. compruebe si ese GUID es Exist en su columna de la tabla donde está buscando unicensess
3. si existe entonces ve al paso 1 o al paso 4
4. Utilice este GUID como único.

La respuesta simple es sí.

Raymond Chen escribió un excelente artículo sobre los GUID y por qué no se garantiza que las subcadenas de los GUID sean únicas. El artículo profundiza en la forma en que se generan los GUID y los datos que utilizan para garantizar la singularidad, lo que debería ser un tanto extenso para explicar por qué son :-)

Las guías son estadísticamente únicas. Las probabilidades de que dos clientes diferentes generen el mismo Guid son infinitamente pequeñas (suponiendo que no haya errores en el código generador de Guid). También puede preocuparse por la falla de su procesador debido a un rayo cósmico y decidir que 2 + 2 = 5 hoy.

Varios subprocesos que asignan nuevas guías obtendrán valores únicos, pero debe obtener que la función que está llamando es segura para subprocesos. ¿En qué entorno se encuentra?

Los algoritmos GUID generalmente se implementan de acuerdo con la especificación GUID v4, que es esencialmente una cadena pseudoaleatoria. Lamentablemente, estos pertenecen a la categoría de "probablemente no único" , de Wikipedia (no sé por qué tanta gente ignora este bit): "... otras versiones de GUID tienen diferentes propiedades y probabilidades de singularidad, que van desde la singularidad garantizada. a la no-singularidad probable ".

Las propiedades pseudoaleatorias de JavaScript Math.random() de V8 son TERRIBLES en su singularidad, con colisiones a menudo después de unas pocas miles de iteraciones, pero V8 no es el único culpable. He visto colisiones de GUID en el mundo real utilizando implementaciones tanto de PHP como de Ruby de los GUID v4.

Debido a que es cada vez más común escalar la generación de ID en múltiples clientes y grupos de servidores, la entropía tiene un gran éxito: las posibilidades de que la misma semilla aleatoria se use para generar una ID de escalada (el tiempo a menudo se usa como una semilla aleatoria) en los generadores seudoaleatorios), y las colisiones de GUID aumentan de "probablemente no únicas" a "muy probablemente causen muchos problemas".

Para resolver este problema, me propuse crear un algoritmo de identificación que pudiera escalar de forma segura y ofrecer mejores garantías contra la colisión. Lo hace mediante el uso de la marca de tiempo, el contador de un cliente en memoria, la huella digital del cliente y los caracteres aleatorios. La combinación de factores crea una complejidad aditiva que es particularmente resistente a la colisión, incluso si la escala en varios hosts:

http://usecuid.org/

Ninguno parece mencionar las matemáticas reales de la probabilidad de que ocurra.

Primero, asumamos que podemos usar todo el espacio de 128 bits (Guid v4 solo usa 122 bits).

Sabemos que la probabilidad general de NO obtener un duplicado en n picks es:

(1-1 / 2 ¹²⁸ ) (1-2 / 2 ¹²⁸ ) ... (1- (n-1) / 2 ¹²⁸ )

Debido a que 2 ¹²⁸ es mucho más grande que n , podemos aproximar esto a:

(1-1 / 2 ¹²⁸ ) ^{n (n-1) / 2}

Y como podemos suponer que n es mucho más grande que 0, podemos aproximar eso a:

(1-1 / 2 ¹²⁸ ) ^{n ^ 2/2}

Ahora podemos igualar esto con la probabilidad "aceptable", digamos 1%:

(1-1 / 2 ¹²⁸ ) ^{n ^} 2/2 = 0.01

Que resolvemos para n y obtenemos:

n = sqrt (2 * log 0.01 / log (1-1 / 2 ¹²⁸ ))

Que Wolfram Alpha llega a ser 5.598318 × 10 ¹⁹

Para poner ese número en perspectiva, tomemos 10000 máquinas, cada una con una CPU de 4 núcleos, haciendo 4GHz y gastando 10000 ciclos para generar un Guid y no hacer nada más. Luego tomarían ~ 111 años antes de que generen un duplicado.

No debería suceder. Sin embargo, cuando .NET está bajo una carga pesada, es posible obtener guías duplicadas. Tengo dos servidores web diferentes utilizando dos servidores SQL diferentes. Fui a combinar los datos y descubrí que tenía 15 millones de guías y 7 duplicados.

Sí, un GUID siempre debe ser único. Se basa tanto en el hardware como en el tiempo, más algunos bits adicionales para asegurarse de que sea único. Estoy seguro de que es teóricamente posible terminar con dos idénticas, pero extremadamente improbable en un escenario del mundo real.

Aquí hay un gran artículo de Raymond Chen en Guids:

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Si el reloj de su sistema está configurado correctamente y no se ha ajustado, y si su NIC tiene su propio MAC (es decir, no ha configurado un MAC personalizado) y su proveedor de NIC no ha estado reciclando los MAC (lo que no deben hacer) pero se sabe que ocurre), y si la función de generación de GUID de su sistema se implementa correctamente, su sistema nunca generará GUID duplicados.

Si todos los que están generando GUID en la tierra siguen esas reglas, entonces sus GUID serán únicos a nivel mundial.

En la práctica, la cantidad de personas que infringen las reglas es baja, y es poco probable que sus GUID se "escapen". Los conflictos son estadísticamente improbables.

Si le temen los mismos valores de GUID, coloque dos de ellos uno al lado del otro.

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

Si eres demasiado paranoico entonces pon tres.

Teóricamente, no, no son únicos. Es posible generar un guid idéntico una y otra vez. Sin embargo, las posibilidades de que esto ocurra son tan bajas que se puede asumir que son únicas.

He leído antes que las posibilidades son tan bajas que realmente debería estresarse por otra cosa, como la combustión espontánea de su servidor u otros errores en su código. Es decir, asuma que es único y no genere ningún código para "atrapar" duplicados: dedique su tiempo a algo más probable que suceda (es decir, cualquier otra cosa ).

Intenté describir la utilidad de los GUID para la audiencia de mi blog (miembros de familia no técnicos). Desde allí (a través de Wikipedia), las probabilidades de generar un GUID duplicado:

1 en 2 ^ 128
1 en 340 undecillion (no te preocupes, undecillion no está en el cuestionario)
1 en 3.4 × 10 ^ 38
1 en 340,000,000,000,000,000,000,000,000,000,000,000,000,000

MSDN :

Hay una probabilidad muy baja de que el valor del nuevo Guid sea todos ceros o igual a cualquier otro Guid.