¿Un GUID es único el 100% del tiempo?

https://stackoverflow.com/questions/39771

09-06-2019
|

Pregunta

¿Seguirá siendo único en varios subprocesos?

Solución

Si bien no se garantiza que cada GUID generado sea único, el número total de claves únicas (2¹²⁸ o 3.4 × 10³⁸) 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²²estrellas;Cada estrella podría tener 6.8 × 10¹⁵ GUID universalmente únicos.

De Wikipedia.

Estos son algunos buenos artículos sobre cómo se crea un GUID (para .NET) y cómo se puede 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-tres/

Otros consejos

La respuesta sencilla es sí.

Raymond Chen escribió un Excelente artículo sobre los GUID y por qué las subcadenas de los GUID son no Único garantizado.El artículo profundiza en la forma en que se generan los GUID y los datos que utilizan para garantizar la unicidad, lo que debería explicar con cierta extensión. por qué ellos son :-)

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

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

Si eres demasiado paranoico entonces pon tres.

Como nota al margen, estaba jugando con los 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".¿Es una coincidencia o hay una explicación detrás de esto?

Ahora, cuando buscando en google la parte 4 en el GUID encontré aproximadamente 125.000 visitas con GUID de volumen.

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

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

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

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

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

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 de generación del Guid).También puede preocuparse de que su procesador falle debido a un rayo cósmico y decidir que 2+2=5 hoy.

Varios subprocesos que asignan nuevos guids obtendrán valores únicos, pero debes saber que la función que estás llamando es segura para subprocesos.¿En qué entorno se encuentra esto?

Eric Lippert ha escrito una serie de artículos muy interesantes sobre GUID.

Hay en el orden 2³⁰ Computadoras personales en el mundo (y, por supuesto, muchos dispositivos de mano o dispositivos de computación no PC que tienen más o menos los mismos niveles de potencia informática, pero los ignoremos).Supongamos que ponemos todas esas PC en el mundo en la tarea de generar GUID;si cada uno puede generar, digamos, 2²⁰ GUID por segundo después de solo unos 2⁷² segundos -- Ciento cincuenta billones de años - tendrás un muy alto posibilidad 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 billones de años.

En teoría, no, no son únicos.Es posible generar una guía idéntica una y otra vez.Sin embargo, las posibilidades de que esto suceda son tan bajas que se puede asumir que son únicas.

He leído antes que las posibilidades son tan bajas que realmente deberías preocuparte por otra cosa, como que tu servidor se queme espontáneamente u otros errores en tu código.Es decir, asuma que es único y no incluya ningún código para "captar" duplicados; dedique su tiempo a algo que tenga más probabilidades de suceder (es decir, cualquier cosa demás).

I hizo un intento describir la utilidad de los GUID para la audiencia de mi blog (miembros de la familia sin conocimientos técnicos).A partir de ahí (a través de Wikipedia), las probabilidades de generar un GUID duplicado:

1 en 2^128
1 en 340 Undecillion (no te preocupes, el indeciso no está en el cuestionario)
1 en 3,4 × 10^38
1 entre 340.000.000.000.000.000.000.000.000.000.000.000.000

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

Primero, supongamos 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 selecciones es:

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

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

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

Y porque podemos suponer n es mucho mayor que 0, podemos aproximarlo a:

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

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

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

que resolvemos n y obten:

n = raíz cuadrada (2* log 0,01 / log (1-1/2¹²⁸))

¿Qué 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, funcionando a 4 Ghz y gastando 10000 ciclos para generar un Guid y no hacer nada más.Entonces pasarían ~111 años antes de que generaran un duplicado.

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

¿Qué es un GUID?

GUID (o UUID) es un acrónimo de 'Identificador único global' (o 'Identificador único universal').Es un número entero de 128 bits que se utiliza para identificar recursos.El término GUID lo utilizan generalmente los desarrolladores que trabajan con tecnologías de Microsoft, mientras que UUID se utiliza en todos los demás.

¿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.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 GUID, solo habría un 50% de probabilidad de que se duplicara.

MSDN:

Existe una probabilidad muy baja de que el valor del nuevo Guid sea todo ceros o igual al de cualquier otro Guid.

Si el reloj de su sistema está configurado correctamente y no se ha ajustado, y si su NIC tiene su propia MAC (es decir,no ha configurado una MAC personalizada) y su proveedor de NIC no ha estado reciclando las MAC (lo que se supone que no deben hacer, pero se sabe que ocurre), y si la función de generación de GUID de su sistema está implementada correctamente, entonces su sistema nunca genere GUID duplicados.

Si todos los que generan GUID en la tierra siguen esas reglas, sus GUID serán globalmente únicos.

En la práctica, el número de personas que infringen las reglas es bajo y es poco probable que sus GUID "escapan".Los conflictos son estadísticamente improbables.

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 seguía recibiendo un error al sincronizar.Un vistazo a los registros reveló la asombrosa frase:

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

Estaba un poco incrédulo, pero seguramente, cuando encontré una manera de ingresar a mi base de datos local de niceworks y eliminé el registro que contenía ese GUID, el error dejó de ocurrir.

Entonces, para responder a su pregunta con evidencia anecdótica, no.Es posible un duplicado.Pero es probable que la razón por la que sucedió no se debiera al azar, sino a que no se cumplió de alguna manera con la práctica estándar.(Simplemente 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 deben haber encontrado este problema antes porque después de más de 3 horas hablando por teléfono con ellos, no encontraron la solución.(FWIW, estoy muy impresionado con Neat, y este error, por frustrante que sea, no cambió mi opinión sobre su producto).

¿Un GUID es único el 100% del tiempo?

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

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

Las propiedades pseudoaleatorias del JavaScript V8 Math.random() son TERRIBLES en cuanto a singularidad, y las colisiones a menudo se producen después de solo unos pocos miles de iteraciones, pero V8 no es el único culpable.He visto colisiones de GUID en el mundo real utilizando implementaciones PHP y Ruby de GUID v4.

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

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

http://usecuid.org/

He experimentado que los GUID no son únicos durante las pruebas unitarias de subprocesos múltiples/procesos múltiples (¿también?).Supongo que eso tiene que ver con, en igualdad de condiciones, la siembra idéntica (o la falta de siembra) de generadores pseudoaleatorios.Lo estaba usando para generar nombres de archivos únicos.Descubrí que el sistema operativo es mucho mejor para hacer eso :)

Alerta de troleo

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

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

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

Por supuesto, éste es sólo el caso ideal de un proceso verdaderamente aleatorio.Como otros mencionaron, mucho depende de eso. aleatorio aspecto: ¿qué tan buenos son 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 a prueba de balas excepto que cualquier cosa puede ser falsificada o virtualizada.Sospecho que esa podría ser la razón por la cual las direcciones MAC/marcas de tiempo ya no se incorporan.

La respuesta de "¿Un GUID es 100% único?" es simple "No" .

Si desea que el GUID sea 100% único, haga lo siguiente.
1. generar GUID
2. compruebe si ese GUID existe en la columna de su tabla donde busca singularidad
3. Si existe, vaya al paso 1; de lo contrario, vaya al paso 4.
4. utilice este GUID como único.

La parte más difícil no es generar un Guid duplicado.

La parte más difícil es diseñar una base de datos para almacenar todos los generados y comprobar si realmente están duplicados.

De WIKI:

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

ingrese la descripción de la imagen aquí

Este número equivale a generar mil millones de UUID por segundo durante aproximadamente 85 años, y un archivo que contenga esta cantidad de UUID, a 16 bytes por UUID, ocuparía aproximadamente 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 cientos de petabytes

GUID significa Identificador único global

En breve:(la pista está en el nombre)

En detalle:Los GUID están diseñados para ser únicos;se calculan utilizando un método aleatorio basado en el reloj de la computadora y en la computadora misma; si está creando muchos GUID en el mismo milisegundo en la misma máquina, es posible que coincidan, pero para casi todas las operaciones normales deben considerarse únicos.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow