Prueba simple de que el GUID no es único

Me gustaría probar que un GUID no es único en un progtwig de prueba simple. Esperaba que el siguiente código se ejecutara durante horas, pero no funciona. ¿Cómo puedo hacer que funcione?

BigInteger begin = new BigInteger((long)0); BigInteger end = new BigInteger("340282366920938463463374607431768211456",10); //2^128 for(begin; begin<end; begin++) Console.WriteLine(System.Guid.NewGuid().ToString()); 

Estoy usando C #.

Kai, he proporcionado un progtwig que hará lo que quieras usando hilos. Está licenciado bajo los siguientes términos: debe pagarme $ 0,0001 por hora por núcleo de CPU en que lo ejecute. Los honorarios se pagan al final de cada mes calendario. Por favor, póngase en contacto conmigo para obtener los detalles de mi cuenta de paypal lo antes posible.

 using System; using System.Collections.Generic; using System.Linq; namespace GuidCollisionDetector { class Program { static void Main(string[] args) { //var reserveSomeRam = new byte[1024 * 1024 * 100]; // This indeed has no effect. Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now); // Fill up memory with guids. var bigHeapOGuids = new HashSet(); try { do { bigHeapOGuids.Add(Guid.NewGuid()); } while (true); } catch (OutOfMemoryException) { // Release the ram we allocated up front. // Actually, these are pointless too. //GC.KeepAlive(reserveSomeRam); //GC.Collect(); } Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount()); // Spool up some threads to keep checking if there's a match. // Keep running until the heat death of the universe. for (long k = 0; k < Int64.MaxValue; k++) { for (long j = 0; j < Int64.MaxValue; j++) { Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount); System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) => { if (bigHeapOGuids.Contains(Guid.NewGuid())) throw new ApplicationException("Guids collided! Oh my gosh!"); } ); Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount); } } Console.WriteLine("Umm... why hasn't the universe ended yet?"); } } } 

PD: quería probar la biblioteca de extensiones paralelas. Eso fue fácil.

Y usando OutOfMemoryException ya que el flujo de control se siente mal.

EDITAR

Bueno, parece que esto todavía atrae votos. Así que solucioné el problema GC.KeepAlive (). Y lo cambié para ejecutar con C # 4.

Y para aclarar mis términos de soporte: el soporte solo está disponible el 28 / Feb / 2010. Utilice una máquina del tiempo para hacer solicitudes de soporte solo ese día.

EDITAR 2 Como siempre, el GC hace un mejor trabajo que yo en la administración de la memoria; cualquier bash previo de hacerlo yo mismo estaba condenado al fracaso.

Esto funcionará por mucho más que horas. Suponiendo que bucles a 1 GHz (que no lo hará, será mucho más lento que eso), se ejecutará durante 10790283070806014188970 años. Que es alrededor de 83 mil millones de veces más que la edad del universo.

Asumiendo que la ley de Moores es válida, sería mucho más rápido no ejecutar este progtwig, esperar varios cientos de años y ejecutarlo en una computadora que es miles de millones de veces más rápida. De hecho, cualquier progtwig que tarde más en ejecutarse de lo que duplica la velocidad de la CPU (aproximadamente 18 meses) se completará antes si espera hasta que las velocidades de la CPU hayan aumentado y compre una CPU nueva antes de ejecutarla (a menos que la escriba para que puede suspenderse y reanudarse en hardware nuevo).

Un GUID es teóricamente no único. Aquí está su prueba:

  • GUID es un número de 128 bits
  • No puede generar 2 ^ 128 + 1 o más GUID sin volver a utilizar los GUID antiguos

Sin embargo, si toda la potencia de salida del sol estaba dirigida a realizar esta tarea, se enfriaría mucho antes de que finalizara.

Los GUID se pueden generar utilizando varias tácticas diferentes, algunas de las cuales toman medidas especiales para garantizar que una máquina determinada no genere el mismo GUID dos veces. Encontrar colisiones en un algoritmo particular mostraría que su método particular para generar GUID es malo, pero no probaría nada sobre los GUID en general.

Por supuesto, los GUID pueden colisionar. Como los GUID son de 128 bits, solo genere 2^128 + 1 de ellos y según el principio de encasillado debe haber una colisión.

Pero cuando decimos que un GUID es único, lo que realmente queremos decir es que el espacio clave es tan grande que es prácticamente imposible generar accidentalmente el mismo GUID dos veces (suponiendo que generemos GUID de forma aleatoria).

Si genera una secuencia de n GUID aleatoriamente, entonces la probabilidad de al menos una colisión es aproximadamente p(n) = 1 - exp(-n^2 / 2 * 2^128) (este es el problema del cumpleaños con el número de posibles cumpleaños siendo 2^128 ).

  np(n) 2^30 1.69e-21 2^40 1.77e-15 2^50 1.86e-10 2^60 1.95e-03 

Para hacer estos números concretos, 2^60 = 1.15e+18 . Por lo tanto, si genera mil millones de GUID por segundo, le tomará 36 años generar 2^60 GUID aleatorios e incluso entonces la probabilidad de que tenga una colisión sigue siendo 1.95e-03 . Es más probable que sea asesinado en algún momento de su vida ( 4.76e-03 ) que usted para encontrar una colisión en los próximos 36 años. Buena suerte.

Si le preocupa la exclusividad, siempre puede comprar nuevos GUID para poder descartar los antiguos. Pondré algunos en eBay si quieres.

Personalmente, creo que el “Big Bang” fue causado cuando dos GUID colisionaron.

Puede mostrar que en O (1) tiempo con una variante del algoritmo cuántico bogosort .

 Guid g1 = Guid.NewGuid(); Guid g2 = Guid.NewGuid(); if(g1 != g2) Universe.Current.Destroy(); 

Es muy probable que dos GUID sean únicos (no iguales).

Ver esta entrada SO , y de Wikipedia

Aunque 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 alrededor de 5 × 10 ^ 22 estrellas; cada estrella podría tener 6.8 × 10 ^ 15 GUID universalmente únicos.

Entonces probablemente tengas que esperar muchos miles de millones de años más y esperar que llegues a uno antes de que el universo como lo conocemos llegue a su fin.

[Actualización:] Como señalan los comentarios a continuación, los nuevos GUID de MS son V4 y no usan la dirección MAC como parte de la generación de GUID (aunque no he visto ninguna indicación de implementación de V5 de MS, si alguien tiene una enlace confirmando que me avise). Sin embargo, con el V4, el tiempo sigue siendo un factor, y las probabilidades contra la duplicación de GUIDs siguen siendo tan pequeñas que son irrelevantes para cualquier uso práctico. Ciertamente, no es probable que alguna vez genere un GUID duplicado a partir de una sola prueba del sistema, como el OP intentaba hacer.

A la mayoría de estas respuestas le falta un punto vital sobre la implementación de GUID de Microsoft. La primera parte del GUID se basa en una marca de tiempo y otra parte se basa en la dirección MAC de la tarjeta de red (o un número aleatorio si no está instalada una NIC).

Si entiendo esto correctamente, significa que la única forma confiable de duplicar un GUID sería ejecutar generaciones GUID simultáneas en máquinas múltiples donde las direcciones MAC eran las mismas Y donde los relojes en ambos sistemas estaban en el mismo momento exacto cuando la generación se produjo (la marca de tiempo se basa en milisegundos si lo entiendo correctamente) … incluso entonces hay muchos otros bits en el número que son aleatorios, por lo que las probabilidades siguen siendo infinitamente pequeñas.

Para todos los propósitos prácticos, los GUID son universalmente únicos.

Hay una muy buena descripción de MS GUID en el blog “The Old New Thing”

Aquí hay un pequeño y útil método de extensión que puede usar si desea verificar la singularidad de la guía en muchos lugares de su código.

 internal static class GuidExt { public static bool IsUnique(this Guid guid) { while (guid != Guid.NewGuid()) { } return false; } } 

Para llamarlo, simplemente llame a Guid.IsUnique cada vez que genere un nuevo guid …

 Guid g = Guid.NewGuid(); if (!g.IsUnique()) { throw new GuidIsNotUniqueException(); } 

… diablos, incluso recomendaría llamarlo dos veces para asegurarme de que salió bien en la primera ronda.

Contando a 2 ^ 128 – ambicioso.

Imaginemos que podemos contar 2 ^ 32 ID por segundo por máquina, no tan ambicioso, ya que no es ni siquiera 4,3 mil millones por segundo. Dediquemos 2 ^ 32 máquinas a esa tarea. Además, permitamos que 2 ^ 32 civilizaciones dediquen los mismos recursos a la tarea.

Hasta ahora, podemos contar 2 ^ 96 identificaciones por segundo, lo que significa que contaremos durante 2 ^ 32 segundos (un poco más de 136 años).

Ahora, todo lo que necesitamos es conseguir 4,294,967,296 civilizaciones para cada una dedicar 4,294,967,296 máquinas, cada máquina capaz de contar 4,294,967,296 identificaciones por segundo, exclusivamente para esta tarea durante los próximos 136 años más o menos – sugiero que comencemos en esta tarea esencial en este momento; -)

Bueno, si el tiempo de ejecución de 83 mil millones de años no lo asusta, piense que también necesitará almacenar los GUID generados en algún lugar para verificar si tiene un duplicado; almacenar 2 ^ 128 números de 16 bytes solo requeriría asignar 4951760157141521099596496896 terabytes de RAM por adelantado, por lo que imagina que tiene una computadora que podría adaptarse a todo eso y que de alguna manera encuentra un lugar para comprar módulos DIMM de 10 gramos cada uno, combinados lo harán pesa más de 8 masas de tierra, por lo que puede cambiarlo seriamente de la órbita actual, incluso antes de presionar “Ejecutar”. ¡Pensar dos veces!

 for(begin; begin 

No está begin boost para que la condición que begin < end sea ​​siempre cierta.

Si las colisiones GUID son una preocupación, recomendaría usar el ScottGuID en su lugar.

Es de suponer que tiene motivos para creer que el algoritmo para producir Guids no está produciendo números verdaderamente aleatorios, sino que de hecho está circulando con un período < < 2 ^ 128.

por ejemplo, el método RFC4122 utilizado para derivar GUIDs que corrige los valores de algunos bits.

La prueba del ciclismo dependerá del tamaño posible del período.

Para períodos pequeños, la tabla hash de hash (GUID) -> GUID con reemplazo en caso de colisión si los GUID no coinciden (finaliza si es así) podría ser un enfoque. Considere también solo hacer el reemplazo una fracción aleatoria del tiempo.

En última instancia, si el período máximo entre colisiones es lo suficientemente grande (y no se conoce de antemano), cualquier método solo arrojará una probabilidad de que la colisión se encuentre si existiera.

Tenga en cuenta que si el método de generación de Guids se basa en el reloj (consulte el RFC), es posible que no sea posible determinar si existen colisiones porque (a) no podrá esperar el tiempo suficiente para que el reloj se enrolle, o (b) no puede solicitar suficientes Guids dentro de un tic del reloj para forzar una colisión.

Alternativamente, es posible que pueda mostrar una relación estadística entre los bits en el Guid o una correlación de bits entre Guids. Tal relación podría hacer altamente probable que el algoritmo sea defectuoso sin necesariamente poder encontrar una colisión real.

Por supuesto, si solo quiere probar que los Guids pueden colisionar, entonces una respuesta matemática, no un progtwig, es la respuesta.

Pero debe asegurarse de tener un duplicado, o solo le importa si puede haber un duplicado. Para asegurarse de que tiene dos personas con el mismo cumpleaños, necesita 366 personas (sin contar el año bisiesto). Para que haya más del 50% de posibilidades de tener dos personas con el mismo cumpleaños, solo necesitas 23 personas. Ese es el problema del cumpleaños .

Si tiene 32 bits, solo necesita 77,163 valores para tener una probabilidad mayor al 50% de duplicar. Pruébalo:

 Random baseRandom = new Random(0); int DuplicateIntegerTest(int interations) { Random r = new Random(baseRandom.Next()); int[] ints = new int[interations]; for (int i = 0; i < ints.Length; i++) { ints[i] = r.Next(); } Array.Sort(ints); for (int i = 1; i < ints.Length; i++) { if (ints[i] == ints[i - 1]) return 1; } return 0; } void DoTest() { baseRandom = new Random(0); int count = 0; int duplicates = 0; for (int i = 0; i < 1000; i++) { count++; duplicates += DuplicateIntegerTest(77163); } Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates); } 1000 iterations had 737 with duplicates 

Ahora 128 bits es mucho, por lo que todavía está hablando de una gran cantidad de artículos que todavía le da una baja probabilidad de colisión. Necesitará la siguiente cantidad de registros para las probabilidades dadas usando una aproximación:

  • 0.8 billones de billones para una probabilidad de 1/1000 de que ocurra una colisión
  • 21.7 billones de billones con un 50% de probabilidad de que ocurra una colisión
  • 39.6 billones de billones para 90% de posibilidades de que ocurra una colisión

Hay alrededor de 1E14 correos electrónicos enviados por año, por lo que serían aproximadamente 400,000 años en este nivel antes de tener 90% de posibilidades de tener dos con el mismo GUID, pero eso es muy diferente a decir que necesita ejecutar una computadora 83 billones veces la edad del universo o que el sol se enfriará antes de encontrar un duplicado.

No entiendo por qué nadie ha mencionado la actualización de su tarjeta gráfica … Sin duda, si tiene un NVIDIA Quadro FX 4800 de gama alta o algo así (192 núcleos CUDA), esto iría más rápido …

Por supuesto, si pudiera permitirse unos pocos NVIDIA Qadro Plex 2200 S4 (con 960 núcleos CUDA cada uno), este cálculo realmente chillaría. ¿Tal vez NVIDIA estaría dispuesto a prestarle unos pocos para una “Demostración de tecnología” como un truco de relaciones públicas?

Seguramente querrían ser parte de este cálculo histórico

¿No estás perdiendo un punto importante?

Pensé que los GUIDs se generaron usando dos cosas que hacen que las posibilidades de que sean globalmente únicas sean bastante altas. Una es que están sembradas con la dirección MAC de la máquina en la que se encuentra y dos utilizan el tiempo en que se generaron más un número aleatorio.

Por lo tanto, a menos que lo ejecute en la máquina real y ejecute todas las suposiciones en el menor tiempo que la máquina use para representar una hora en el GUID, nunca generará el mismo número sin importar cuántas conjeturas tome usando la llamada al sistema.

Supongo que si conoces la forma real en que se crea un GUID, en realidad acortará el tiempo para adivinar de manera bastante sustancial.

Tony

Podría hash los GUID. De esa forma, deberías obtener un resultado mucho más rápido.

Ah, por supuesto, ejecutar múltiples hilos al mismo tiempo también es una buena idea, de esa manera boostá las posibilidades de que una condición de carrera genere el mismo GUID dos veces en diferentes hilos.

  1. Ve al laboratorio de criogenia en la ciudad de Nueva York.
  2. Congelarse durante (más o menos) 1990 años.
  3. Consigue un trabajo en Planet Express.
  4. Compre una CPU nueva. Construya una computadora, ejecute el progtwig y colóquelo en un lugar seguro con una máquina de movimiento pseudoperpetual, como la máquina del día del juicio final.
  5. Espere hasta que se invente la máquina del tiempo.
  6. Salta al futuro usando la máquina del tiempo. Si compró CPU a 1YHz de 128 bits, vaya a 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps después de cuando comenzó a ejecutar el progtwig.
  7. …?
  8. ¡¡¡LUCRO!!!

… Tarda al menos 10,783,127 años, incluso si tiene una CPU de 1YHz que es de 1,000,000,000,000,000 (o 1,125,899,906,842,624 si prefiere usar el prefijo binario) veces más rápido que la CPU de 1GHz.

Entonces, en lugar de esperar a que termine el cálculo, sería mejor alimentar a las palomas que perdieron su hogar porque otras n palomas se llevaron a casa. 🙁

O bien, puede esperar hasta que se invente la computadora cuántica de 128 bits. Entonces puede probar que el GUID no es único, utilizando su progtwig en un tiempo razonable (tal vez).

Los GUID son de 124 bits porque 4 bits contienen el número de versión.

¿Has probado begin = begin + new BigInteger((long)1) en lugar de begin ++?

Si la cantidad de UUID que se genera sigue la ley de Moore, la impresión de que nunca se quedará sin GUID en un futuro previsible es falsa.

Con 2 ^ 128 UUID, solo tomará 18 meses * Log2 (2 ^ 128) ~ = 192 años, antes de que nos quedemos sin todos los UUID.

Y creo (sin pruebas estadísticas) que en los últimos años desde la adopción masiva de UUID, la velocidad con la que estamos generando el UUID está aumentando mucho más rápido de lo que dicta la ley de Moore. En otras palabras, probablemente tengamos menos de 192 años hasta que tengamos que lidiar con la crisis UUID, eso es mucho antes que el final del universo.

Pero como definitivamente no los estamos agotando para fines de 2012, dejaremos que otras especies se preocupen por el problema.

Las probabilidades de un error en el código de generación GUID son mucho más altas que las probabilidades del algoritmo que genera una colisión. Las probabilidades de un error en su código para probar los GUID son aún mayores. Rendirse.

No p ** s en la hoguera aquí, pero realmente sucede, y sí, entiendo las bromas que le has estado dando a este tipo, pero el GUID es único solo en principio, me topé con este hilo porque hay un error en el emulador WP7, lo que significa que cada vez que arranca, ¡da la MISMA GUÍA la primera vez que se llama! Entonces, donde en teoría no puede haber un conflicto, si hay un problema al generar dicha GUI, entonces puede obtener duplicados

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310

The program, albeit its errors, shows proof that a GUID is not unique. Those that try to prove the contrary are missing the point. This statement just proves the weak implementation of some of the GUID variations.

A GUID is not necessary unique by definition, it is highly unique by definition. You just refined the meaning of highly. Depending on the version, the implementator (MS or others), use of VM’s, etc your definition of highly changes. (see link in earlier post)

You can shorten your 128 bit table to prove your point. The best solution is to use a hash formula to shorten your table with duplicates, and then use the full value once the hash collides and based on that re-generate a GUID. If running from different locations, you would be storing your hash/full key pairs in a central location.

Ps: If the goal is just to generate x number of different values, create a hash table of this width and just check on the hash value.

Since part of Guid generation is based on the current machine’s time, my theory to get a duplicate Guid is:

  1. Perform a clean installation of Windows
  2. Create a startup script that resets the time to 2010-01-01 12:00:00 just as Windows boots up.
  3. Just after the startup script, it triggers your application to generate a Guid.
  4. Clone this Windows installation, so that you rule out any subtle differences that may occur in subsequent boot-ups.
  5. Re-image the hard drive with this image and boot-up the machine a few times.

For me.. the time it takes for a single core to generate a UUIDv1 guarantees it will be unique. Even in a multi core situation if the UUID generator only allows one UUID to be generated at a time for your specific resource (keep in mind that multiple resources can totally utilize the same UUIDs however unlikely since the resource inherently part of the address) then you will have more than enough UUIDs to last you until the timestamp burns out. At which point I really doubt you would care.

Here’s a solution, too:

 int main() { QUuid uuid; while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { } std::cout < < "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl; } 

Note: requires Qt, but I guarantee that if you let it run long enough, it might find one.

(Note note: actually, now that I'm looking at it, there may be something about the generation algorithm that prevents two subsequently generated uuids that collide--but I kinda doubt it).

The only solution to prove GUIDs are not unique would be by having a World GUID Pool. Each time a GUID is generated somewhere, it should be registered to the organization. Or heck, we might include a standardization that all GUID generators needs to register it automatically and for that it needs an active internet connection!