¿Son posibles las colisiones GUID?

128

Estoy trabajando en una base de datos en SQL Server 2000 que usa un GUID para cada usuario que usa la aplicación a la que está vinculada. De alguna manera, dos usuarios terminaron con el mismo GUID. Sé que Microsoft utiliza un algoritmo para generar un GUID aleatorio que tiene una probabilidad extremadamente baja de causar colisiones, pero ¿es posible una colisión?

Jason Baker
fuente
11
Todos dicen que no está mal. Ya he chocado 1 UniqueIdentifier con un conjunto de datos de menos de medio millón de registros, MSSQL 2008 R2
Behrooz
2
@Behrooz Yikes. No es imposible gracias a nuestro amigo, la paradoja del cumpleaños, pero todavía es increíblemente desafortunado con GUID v4 completamente aleatorios. ¿Tal vez estabas usando una estrategia de generación de GUID más débil?
Craig Ringer
66
@Behrooz Wow. Esa es una suerte impactante.
Craig Ringer el
66
@Behrooz este es probablemente un número pseudoaleatorio defectuoso utilizado en MSSQL (no me sorprendería si tienen semilla de 32 bits en su generador o similar dada la calidad de su software). Las matemáticas no mienten. Esta posibilidad es tan pequeña que puede ser 99.9999999999 (y mucho 9 después)% de que el generador de guid MSSQL es defectuoso (o puede ser un generador pseudoaleatorio que se utiliza para generar GUID) o cometió un error.
Alex
2
Me encanta cómo en este momento exacto, tanto la pregunta como la respuesta seleccionada tienen 128 puntos. ¿Coincidencia? 🤔
Caio Cunha

Respuestas:

127

Básicamente no. Creo que alguien se metió con su base de datos. Dependiendo del GUID de la versión que esté utilizando, el valor es único (para elementos como los GUID de la versión 1) o único e impredecible (para elementos como los GUID de la versión 4). La implementación de SQL Server para su función NEWID () parece usar un número aleatorio de 128 bits, por lo que no obtendrá una colisión.

Para una probabilidad de colisión del 1%, necesitaría generar aproximadamente 2,600,000,000,000,000,000 GUID.

Tom Ritter
fuente
3
Eso es lo que pensé, pero solo quería asegurarme de que no podía descartar eso. Nunca se sabe qué tipos de errores extraños pueden aparecer en el software de 8 años. :)
Jason Baker
66
En realidad, eso ya no es cierto. Era cierto para los GUID v1, pero no para los actuales v4. Consulte en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm para obtener más información.
Greg Beech
96
Voto negativo porque, en principio (en su forma más cruda), te equivocas al decir "no" a la pregunta "¿Son posibles las colisiones GUID?". Es muy posible. La probabilidad de que sea pequeña, pero es posible. Odio sonar pedante, pero SO se trata de ser conciso y preciso.
13
ingrese "solve [1-exp [- (n ^ 2 / (2 * 2 ^ 128))]> 0.01, n]" en wolfram alpha para obtener el resultado del 1% ... Tenga en cuenta que aunque este número parece grande en contexto de UNA aplicación, ciertamente no es grande para todo el mundo. Si cada computadora en la Tierra generara GUID verdaderos, causarían una colisión con un 1% de probabilidad en aproximadamente un segundo, suponiendo que puedan generar un GUID cada nanosegundo (que probablemente sea bastante realista en estos días). Entonces, si usa GUID para sus ID de base de datos, entonces son únicos. Los GUID para cada cálculo realizado en la tierra colisionarán de inmediato.
thesaint
11
Decir 'No' no es posible, y luego decir que hay un 1% de posibilidades de sufrir una colisión cuando se genera una cierta cantidad, son conflictos directos. La respuesta correcta debería ser teóricamente: sí, una colisión podría ocurrir al azar. Sin embargo, las posibilidades de una colisión son estadísticamente más pequeñas que un asteroide golpeando la Tierra, rebotando en la Tierra y rebotando en la Luna para golpear la Tierra por segunda vez, en la próxima hora.
Baaleos
112

¡Básicamente no son posibles! , las posibilidades son astronómicamente bajas .

Pero ... soy la única persona que conozco en el mundo, que tuvo una colisión GUID una vez (¡sí!).

Y estoy seguro de eso, y de que no fue un error.

Cómo sucedió, en una pequeña aplicación que se estaba ejecutando en Pocket PC, al final de una operación se debe emitir un comando que tiene un GUID generado. El comando después de que se ejecutó en el servidor se almacenó en una tabla de comandos en el servidor junto con la fecha de ejecución. Un día, cuando estaba depurando, emití el comando del módulo (con el GUID recién generado adjunto) y no pasó nada. Lo hice nuevamente (con el mismo guid, porque el guid se generó solo una vez al comienzo de la operación), y nuevamente, y nada, finalmente tratando de averiguar por qué el comando no se está ejecutando, revisé la tabla de comandos, y el mismo GUID que el actual se insertó hace 3 semanas. No creyendo esto, restauré una base de datos a partir de 2 semanas de respaldo, y el guid estaba allí. Comprobado el código, el nuevo guid se generó recientemente sin ninguna duda.

Editar: hay algunos factores que podrían haber aumentado en gran medida la posibilidad de que esto suceda, la aplicación se estaba ejecutando en el emulador PocketPC y el emulador tiene una función de guardar estado, lo que significa que cada vez que se restaura el estado, también se restaura la hora local. y el guid se basa en el temporizador interno ... también el algoritmo de generación de guid para el marco compacto podría ser menos completo que, por ejemplo, el COM ...

Pop Catalin
fuente
38
Votado Guardar estado y reproducir realmente generaría guías duplicadas.
Joshua
35
Probablemente lo que sucedió fue que se trataba de una implementación GUID "mala". Las probabilidades teóricas eran muy bajas, pero en Pocket PC? ¿Quién puede decir que no tomaron un atajo que aumentó esas probabilidades en la categoría "poco probable, pero posible"?
Dave Dopson
9
El hecho de que algo tenga una probabilidad muy baja de suceder no significa que no sucederá.
Renan
3
Como dije anteriormente, las posibilidades son cada vez más pequeñas, por lo que es seguro asumir que cometió un error o que MSSQL usa un PRNG defectuoso ( en.wikipedia.org/wiki/Pseudorandom_number_generator ). Por ejemplo, es probable que este PRNG se inicialice con una semilla de pequeño tamaño. Los PRNG defectuosos no son raros (consulte schneier.com/paper-prngs.html ); por ejemplo, se descubrió recientemente un defecto en el SDK de Android: android-developers.blogspot.com/2013/08/… + usenix.org/conference/woot14 / taller-programa / presentación / ...
Alex
2
@Alex, el error fue "Guardar estado y restaurar" del emulador, que restaura la imagen completa del emulador, incluido el reloj del emulador. Entonces, después de miles de operaciones de restauración durante un año, se generó una colisión guida. Tienes razón, hubo un error!
Pop Catalin
34

Son teóricamente posibles, pero con 3.4E38 números posibles, si crea decenas de billones de GUID en un año, la posibilidad de tener un duplicado es 0.00000000006 ( Fuente ).

Si dos usuarios terminaron con el mismo GUID, apostaría a que hay un error en el programa que está causando que los datos se copien o compartan.

Ben Hoffstein
fuente
"pero con 3.4E38 números posibles" - no. Dos GUID generados casi simultáneamente en la misma máquina terminarían con GUID extremadamente similares.
Kirk Strauser
44
Eso dependería de cómo se genere el GUID, y algunas implementaciones basadas en el tiempo de la CPU o milisegundos (con suerte) exagerarán cualquier cálculo que se base en ellos, por lo que dos GUID generados a partir de milisegundos de diferencia tendrán una gran diferencia.
Dalin Seivewright
44
Con más de 1 procesador en una máquina, si una guía se basa en el tiempo y la dirección MAC, cada núcleo podría emitir la misma guía en el mismo momento en el tiempo.
AndyM
12
Estoy bastante seguro de que ninguna implementación GUID decente no lo hará
Guillaume86
1
@MatthewLock La paradoja del cumpleaños está cubierta en la fuente. Mira el enlace.
Zero3
21

Primero veamos la posibilidad de colisión de dos GUID. No es, como han dicho otras respuestas, 1 en 2 ^ 128 (10 ^ 38) debido a la paradoja del cumpleaños , lo que significa que para un 50% de posibilidades de que dos GUID colisionen, la probabilidad es en realidad 1 en 2 ^ 64 (10 ^ 19) que es mucho más pequeño. Sin embargo, este sigue siendo un número muy grande y, como tal, la probabilidad de colisión suponiendo que está utilizando un número razonable de GUID es baja.

Tenga en cuenta también que los GUID no contienen una marca de tiempo o la dirección MAC como muchas personas también parecen creer. Esto era cierto para los GUID v1, pero ahora se usan los GUID v4, que son simplemente un número pseudoaleatorio, lo que significa que la posibilidad de colisión es posiblemente mayor porque ya no son exclusivos de un tiempo y una máquina.

Entonces, esencialmente la respuesta es sí, las colisiones son posibles. Pero son altamente improbables.

Editar: arreglado para decir 2 ^ 64

Greg Beech
fuente
2
Si bien estoy de acuerdo con todos sus hechos, tenga cuidado con sus matemáticas. Decir que tiene una probabilidad de 1 en 10 ^ 19 de que colisionen dos GUID depende de cuántos GUID haya en el conjunto. Para esa oportunidad, necesitas ~ 2 ^ 32 GUID, por lo que en casi todos los escenarios del mundo real las probabilidades son mucho más bajas.
DocMax
1
Tienes un error tipográfico 1 in 10^64 (10^19), que creo que debería ser 1 in 2^64 (10^19). También estoy muy confundido sobre cómo crees que la paradoja del cumpleaños se aplica a solo 2 números. Supongo que miraste en.wikipedia.org/wiki/Birthday_paradox . La tabla muestra cuántas guías necesita para una probabilidad dada de un duplicado. De esa tabla, una probabilidad de 1 en 10 ^ 18 requiere 2.6 * 10 ^ 10 guías, no nada cerca de solo dos GUID.
Tony Lee
Un punto: las guías v1 todavía se usan ampliamente y dependen de la dirección MAC, particularmente en las bases de datos, ya que tienen características deseables. Vea UuidCreateSequential y es el contenedor de SQL Server NewSequentialID ( msdn.microsoft.com/en-us/library/windows/desktop/… ).
EBarr
18

Las posibilidades de que dos GUID aleatorios colisionen (~ 1 en 10 ^ 38) son menores que la posibilidad de no detectar un paquete TCP / IP corrupto (~ 1 en 10 ^ 10). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf , página 11. Esto también se aplica a las unidades de disco, unidades de CD, etc.

Los GUID son estadísticamente únicos y los datos que lee de la base de datos solo son estadísticamente correctos.

Tony Lee
fuente
¿Estás seguro de que no podría blindar mi red para que menos de 1 de cada 10 ^ 28 paquetes estén corruptos?
Joshua
13

Consideraría la navaja de Occam como una buena guía en este caso. Es increíblemente improbable que tenga una colisión GUID. Es mucho más probable que tenga un error o que alguien se meta con sus datos.

Jason Jackson
fuente
1
En realidad, en esta situación, la navaja de afeitar de Occam no es una buena guía. La Navaja de Occam dice que el caso con menos suposiciones es más probable que sea correcto. En esta situación, el caso de colisión GUID es en realidad mucho más simple, pero la Navaja de Occam no se aplica a una situación como esta donde ya sabemos que uno de los casos es increíblemente improbable.
Lockstock
11

Ver el identificador único global de Wikipedia artículo Wikipedia. Hay varias formas de generar GUID. Aparentemente, la forma antigua (?) Usaba la dirección Mac, una marca de tiempo hasta una unidad muy corta y un contador único (para administrar generaciones rápidas en la misma computadora), por lo que hacerlos duplicados es casi imposible. Pero estos GUID se eliminaron porque podrían usarse para rastrear usuarios ...

No estoy seguro del nuevo algoritmo utilizado por Microsoft (el artículo dice que se puede predecir una secuencia de GUID, ¿parece que ya no usan la marca de tiempo? El artículo de Microsoft vinculado anteriormente dice algo más ...).

Ahora, los GUID están cuidadosamente diseñados para ser, por su nombre, globalmente únicos, por lo que me arriesgaré a que sea imposible, o de muy, muy baja probabilidad. Yo buscaría en otro lado.

PhiLho
fuente
66
Eric post 1
Nat
44
Eric post 2
Nat
44
Eric post 3
Nat
9

Dos máquinas Win95 que tienen tarjetas de ethernet con direcciones MAC duplicadas emitirán GUID duplicados bajo condiciones estrictamente controladas, especialmente si, por ejemplo, se corta la energía en el edificio y ambos arrancan exactamente al mismo tiempo.

Joshua
fuente
¿Es común que dos máquinas diferentes tengan la misma dirección MAC de Ethernet?
Dave Lucre
@DaveLucre: No, pero se han registrado incidentes.
Joshua
Tengo mucha curiosidad por cómo sucede esto. ¿Es más probable con máquinas virtuales que generan aleatoriamente un MAC para cada NIC? ¡Nunca he oído hablar de NIC físicas fabricadas con MAC duplicados! ¡Una especie de llave masiva en proceso si es posible!
Dave Lucre
¡Guauu! Gracias por el enlace @Joshua! ¡Qué colosal mierda!
Dave Lucre
@DaveLucre He usado algunas NIC USB muy baratas donde TODAS ellas están fabricadas con el mismo MAC. Pero, por supuesto, eso no tiene nada que ver con las matemáticas de la aleatoriedad, y todo con la pereza del fabricante.
rudolfbyker
5

Prefacio esto con "No soy una persona de redes, así que puedo hacer oraciones completamente incoherentes después".

Cuando trabajaba en la Universidad Estatal de Illinois, teníamos dos computadoras de escritorio Dell, ordenadas en diferentes momentos. Pusimos el primero en la red, pero cuando intentamos poner el segundo en la red comenzamos a recibir errores locos. Después de mucha solución de problemas, se determinó que ambas máquinas estaban produciendo el mismo GUID (no estoy seguro exactamente para qué, pero las dejó inutilizables en la red). Dell realmente reemplazó ambas máquinas como defectuosas.

John Kraft
fuente
3
Fue específicamente el GUID. Tenía algo que ver con el GUID generado por las máquinas cuando se unían a la red. Dell tardó varias semanas en reemplazar las máquinas porque dijeron que era imposible que los GUID fueran iguales. Pudimos reproducir el problema, Dell retiró las máquinas y pudimos producir los mismos resultados en sus redes. Terminaron reemplazando ambas máquinas. Como dije, no soy una persona de redes, pero recuerdo específicamente que era un problema con los GUID.
John Kraft el
5

Sé que a la gente le gusta la buena respuesta de que los GUID son mágicos y se garantiza que serán únicos, pero en realidad, la mayoría de los GUID son solo números aleatorios de 121 bits (siete de los bits se desperdician en el formateo). Si no se siente cómodo usando un gran número aleatorio, entonces no debería sentirse cómodo usando un GUID.

Rick Yorgason
fuente
11
También te recomiendo que no uses redes. O computadoras. ¡Los bits de paridad solo pueden hacer mucho!
Rushyo
Usted entendió mal. Hay dos cosas que intentaba decir en esta publicación: 1) Si necesita un gran número aleatorio, use un gran número aleatorio. Usar un GUID como un gran número aleatorio es innecesariamente engañoso. (2)
Rick Yorgason
44
De lo que soy completamente consciente. Decías "si no te sentirías cómodo usando un gran número aleatorio". pero los GUID son tan únicos que encontrará que casi todo lo demás en una computadora es más aleatorio, incluso las operaciones que da por sentado. Hay más posibilidades de que una falla de memoria anormal rompa su columna de identidad que una colisión GUID (verdadera). No deberías sentirte "incómodo" con ellos. Si no son ideales para el escenario, está bien, pero no necesitan precaución especial.
Rushyo
3
Supongo que esto no va a ninguna parte, pero lo que la gente está tratando de explicarte es que los mecanismos de detección de errores en hardware común, como tarjetas de red o discos duros, utilizan algoritmos que tienen mayores posibilidades de no detectar un error que tú de obtener una colisión GUID, así que si usted confía en estos, también podría confiar en los GUID
Guillaume86
1
@ Rick, depende de qué tan grande sea tu número. Definitivamente no con un 4 byte int o 8 byte bigint. GUID = 16 bytes, por lo que necesitaría una implementación personalizada de gran número de 16 bytes para lograr las mismas 2 ^ 128 combinaciones posibles. En términos generales, si se usan números aleatorios int o bigint 'normales', la posibilidad de colisiones con un GUID es menor (dejando de lado las consideraciones de algo aleatorio para cada uno).
Wim Hollebrandse
3

¿Podría el código utilizado para generar un GUID tener un error? Sí, por supuesto que podría. Pero la respuesta es la misma que sería para un error del compilador: su propio código tiene órdenes de magnitud más propensas a tener errores, así que mire allí primero.

Mark Ransom
fuente
2

Por supuesto que es posible ... ¿Probable? No es probable, pero es posible.

Recuerde, la misma máquina genera cada GUID (el servidor), por lo que se pierde mucha "aleatoriedad" que se basa en información específica de la máquina.

FlySwat
fuente
1

Solo por sonrisas, pruebe el siguiente script ... (funciona en SQL 2005, no estoy seguro sobre 2000)

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

Ejecutar esto repetidamente (toma menos de un segundo) produce un rango bastante amplio desde la primera selección, incluso con un espacio de tiempo EXTREMADAMENTE corto. Hasta ahora, la segunda selección no ha producido nada.

Galáctico vaquero
fuente
1
Necesita otros 15 ceros al final del mostrador para tener un 50% de posibilidades de un duplicado. Pero, por el amor de Dios, ¡no lo hagas!
Jim Birchall el
0

Imposible si los usuarios tienen diferentes máquinas con tarjetas de red, e incluso si no, sigue siendo un riesgo extremadamente marginal casi teórico.

Personalmente, buscaría en otro lado, ya que es más probable un error en lugar de un choque GUID ...

Siempre que no corte trozos del GUID para acortarlo.

Richard Harrison
fuente
Los GUID se generarían en el servidor, por lo que las tarjetas de red del usuario no entrarían en juego.
Tom Ritter
0

Claro que es posible, y tal vez incluso probable. No es que cada GUID esté en una porción aleatoria del espacio numérico posible. En el caso de que dos hilos intentaran generar uno simultáneamente, salvo algún tipo de función GUID centralizada con un semáforo alrededor, podrían terminar con el mismo valor.

Kirk Strauser
fuente
0

Es muy poco probable que se encuentre con colisiones de GUID si las está generando a través de algo como la NEWID()función en SQL Server (aunque, por supuesto, es posible, como han enfatizado otras respuestas). Una cosa que no han señalado es que en realidad es bastante probable que te encuentres con colisiones si estás generando GUID en JavaScript en navegadores en la naturaleza. No solo a veces hay problemas en el RNG en diferentes navegadores, sino que también me he encontrado con problemas en los que las arañas de Google parecen almacenar en caché los resultados de funciones como esa, y terminaron pasando repetidamente el mismo GUID a nuestros sistemas.

Vea las diferentes respuestas aquí para más detalles:

¿Colisiones al generar UUID en JavaScript?

Ken Smith
fuente