¿Son posibles las colisiones GUID?

Question

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?

Answer 1

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 del 1% de colisión, necesitaría generar unos 2,600,000,000,000,000,000 GUID.

Answer 2

¡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 ejecutaba 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 de 2 semanas de respaldo, y el guid estaba allí. Comprobado el código, el nuevo guid se generó recientemente sin ninguna duda. La colisión de Pow Guid, ocurrió solo una vez, pero realmente desearía haber ganado en la lotería, la posibilidad es mayor :).

Editar: hay algunos factores que podrían haber aumentado considerablemente 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 el estado se restaura la hora local también se restaura 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 ...

Answer 3

Son teóricamente posibles, pero con 3.4E38 números posibles, si crea decenas de billones de GUID en un año, la probabilidad 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 hace que los datos se copien o compartan.

Answer 4

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 una probabilidad del 50% de que dos GUID colisionen, la probabilidad es en realidad 1 en 2 ^ 64 (10 ^ 19), que es mucho menor. 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 exclusivas 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

Answer 5

Las posibilidades de que dos GUID aleatorios colisionen (~ 1 en 10 ^ 38) son menores que las posibilidades de no detectar un paquete TCP / IP corrupto (~ 1 en 10 ^ 10). http: //wwwse.inf.tu-dresden .de / data / cursos / 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.

Answer 6

Consideraría Navaja de afeitar 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.

Answer 7

Consulte el artículo de Wikipedia Globally Unique Identifier . Hay varias formas de generar GUID. Aparentemente, la forma antigua (?) Usaba la dirección Mac, una marca de tiempo en 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 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 nombre, globalmente únicos, por lo que me arriesgaré a que sea imposible, o de muy, muy baja probabilidad. Yo buscaría en otro lado.

Answer 8

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

Answer 9

Sé que a la gente le gusta la respuesta positiva de que los GUID son mágicos y se garantiza que sean ú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.

Answer 10

¿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.

Answer 11

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

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

Answer 12

Solo por sonrisas, prueba 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.

Answer 13

Imposible si los usuarios tienen máquinas diferentes 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 que sea un error en lugar de un choque GUID ...

Siempre que no corte trozos del GUID para acortarlo.

Answer 14

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.

Answer 15

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

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.

Answer 16

Es muy poco probable que se encuentre con colisiones de GUID si las está generando a través de algo como la función NEWID () en SQL Server (aunque, por supuesto, es posible, como lo han enfatizado otras respuestas) . Una cosa que no han señalado es que en realidad es bastante probable que se encuentre con colisiones si está 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?