Prueba simple de que GUID no es único [cerrado]

Me gustaría demostrar que un GUID no es único en un programa 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 programa que hará lo que quieras usando hilos. Tiene licencia bajo los siguientes términos: debe pagarme $ 0.0001 por hora por núcleo de CPU en el que lo ejecuta. Las tarifas se pagan al final de cada mes calendario. Comuníquese 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<Guid>();
            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 usar OutOfMemoryException como flujo de control simplemente se siente mal.

EDITAR

Bueno, parece que esto todavía atrae votos. Así que he solucionado el problema GC.KeepAlive (). Y lo cambió para que se ejecute 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 realizar solicitudes de soporte solo ese día.

EDIT 2 Como siempre, el GC hace un mejor trabajo que yo en la gestión de la memoria; Cualquier intento anterior de hacerlo yo mismo estaba condenado al fracaso.

Esto durará mucho más que horas. Suponiendo que se repita a 1 GHz (lo cual no será, será mucho más lento que eso), funcionará durante 10790283070806014188970 años. Que es aproximadamente 83 mil millones de veces más larga que la edad del universo.

Suponiendo que la ley de Moores sea válida, sería mucho más rápido no ejecutar este programa, 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 programa que demore más en ejecutarse que el que duplica la velocidad de la CPU (aproximadamente 18 meses) se completará antes si espera hasta que la velocidad de la CPU haya aumentado y compre una nueva CPU antes de ejecutarla (a menos que la escriba para que puede suspenderse y reanudarse en un nuevo hardware).

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

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

Sin embargo, si toda la potencia del sol se dirigiera a realizar esta tarea, se enfriaría mucho antes de que terminara.

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. Dado que los GUID son de 128 bits, solo genere 2^128 + 1de ellos y por el principio del casillero 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 estamos generando GUID al azar).

Si genera una secuencia de nGUID al azar, la probabilidad de al menos una colisión es aproximadamente p(n) = 1 - exp(-n^2 / 2 * 2^128)(este es el problema de cumpleaños con la cantidad de cumpleaños posibles 2^128).

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

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

Si le preocupa la singularidad, siempre puede comprar nuevos GUID para que pueda deshacerse de los antiguos. Pondré un poco en eBay si lo desea.

Personalmente, creo que el "Big Bang" fue causado cuando dos GUID chocaron.

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

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

Dos GUID son muy probablemente únicos (no iguales).

Vea esta entrada SO y de Wikipedia

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.

Entonces, probablemente tenga que esperar muchos miles de millones de años más, y esperar que llegue a uno antes del universo, ya que sabemos que llega 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 (no he visto ninguna indicación de una implementación de V5 de MS, así que si alguien tiene un enlace que confirma que hágamelo saber). Sin embargo, con V4, el tiempo sigue siendo un factor, y las probabilidades contra la duplicación de GUID siguen siendo tan pequeñas que no son relevantes para ningún uso práctico. Ciertamente, es probable que nunca genere un GUID duplicado a partir de una sola prueba del sistema, como el OP estaba tratando de hacer.

A la mayoría de estas respuestas les 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 hay una NIC instalada).

Si entiendo esto correctamente, significa que la única forma confiable de duplicar un GUID sería ejecutar generaciones simultáneas de GUID en varias máquinas donde las direcciones MAC eran las mismas Y donde los relojes en ambos sistemas estaban en el mismo momento exacto cuando la generación ocurrió (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 muy pequeñas.

A todos los efectos prácticos, los GUID son universalmente únicos.

Hay una muy buena descripción del MS GUID en el blog "The Old New Thing"

Aquí hay un pequeño método de extensión ingenioso que puede usar si desea verificar la unicidad guid 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 siempre 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 funcionó bien en la primera ronda.

Contando hasta 2 ^ 128 - ambicioso.

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

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

Ahora, todo lo que necesitamos es obtener 4,294,967,296 civilizaciones para dedicar 4,294,967,296 máquinas, cada máquina capaz de contar 4,294,967,296 identificaciones por segundo, puramente para esta tarea durante los próximos 136 años más o menos. Sugiero que comencemos 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 que asigne 4951760157141521099596496896 terabytes de RAM por adelantado, por lo que si imagina que tiene una computadora que podría adaptarse a todo eso y que de alguna manera encuentra un lugar para comprar DIMM de terabytes a 10 gramos cada uno, combinados lo harán pesa más de 8 masas terrestres, por lo que puede cambiarlo seriamente de la órbita actual, incluso antes de presionar "Ejecutar". ¡Pensar dos veces!

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

No estás incrementando, beginpor lo que la condición begin < endsiempre es verdadera.

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

Presumiblemente, tiene razones para creer que el algoritmo para producir Guías no está produciendo números verdaderamente aleatorios, sino que está ciclando con un período << 2 ^ 128.

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

La prueba de ciclismo dependerá del posible tamaño 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 (terminan si lo hacen) podría ser un enfoque. Considere también hacer el reemplazo solo 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 generará una probabilidad de que la colisión se encuentre si existiera.

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

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

Por supuesto, si solo quieres probar que las Guías pueden colisionar, entonces una prueba matemática, no un programa, es la respuesta.

No entiendo por qué nadie ha mencionado la actualización de su tarjeta gráfica ... Seguramente, 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 pagar algunos NVIDIA Qadro Plex 2200 S4 (con 960 núcleos CUDA cada uno), este cálculo realmente gritaría. ¿Quizás NVIDIA estaría dispuesto a prestarle algunos para una "Demostración de Tecnología" como un truco de relaciones públicas?

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

Pero tienes que estar seguro tener un duplicado o solo le importa si hay 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 una probabilidad superior al 50% de tener dos personas con el mismo cumpleaños, solo necesita 23 personas. Ese es el problema del cumpleaños .

Si tiene 32 bits, solo necesita 77.163 valores para tener una probabilidad superior al 50% de un duplicado. 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 elementos que aún le dan una baja posibilidad de colisión. Necesitaría el siguiente número de registros para las cuotas dadas usando una aproximación:

• 0.8 billones de billones para una probabilidad de 1/1000 de que ocurra una colisión
• 21.7 mil millones para una probabilidad del 50% de que ocurra una colisión
• 39,6 mil millones para una probabilidad del 90% de que ocurra una colisión

Se envían alrededor de 1E14 correos electrónicos por año, por lo que pasarían unos 400,000 años en este nivel antes de que tuviera un 90% de posibilidades de tener dos con el mismo GUID, pero eso es muy diferente de decir que necesita ejecutar una computadora 83 mil millones veces la edad del universo o que el sol se enfríe antes de encontrar un duplicado.

¿No se están perdiendo un punto importante?

Pensé que los GUID se generaban usando dos cosas que hacen que las posibilidades de que sean Globalmente únicos 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 usan el tiempo en que se generaron más un número aleatorio.

Entonces, a menos que lo ejecute en la máquina real y ejecute todas sus conjeturas en el menor tiempo posible que la máquina usa para representar un tiempo en el GUID, nunca generará el mismo número, sin importar cuántas conjeturas realice con la llamada al sistema.

Supongo que si conoces la forma real en que se hace un GUID, en realidad acortaría el tiempo para adivinar de manera sustancial.

Tony

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

Ah, por supuesto, ejecutar varios subprocesos al mismo tiempo también es una buena idea, de esa manera aumentará la posibilidad de que una condición de carrera genere el mismo GUID dos veces en diferentes subprocesos.

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

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

... Lleva al menos 10,783,127años, incluso si tuviera una CPU de 1YHz, que es 1,000,000,000,000,000(o 1,125,899,906,842,624si prefiere usar un prefijo binario) veces más rápida 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 otros n palomas se llevaron su hogar. :(

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

¿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 nunca quedarse sin GUID en el futuro previsible es falsa.

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

Y creo (sin pruebas estadísticas de ningún tipo) en los últimos años desde la adopción masiva de UUID, la velocidad que estamos generando 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 de UUID, eso es mucho antes que el final del universo.

Pero dado que definitivamente no los agotaremos 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 de GUID son mucho más altas que las probabilidades de que el algoritmo genere una colisión. Las probabilidades de un error en su código para probar los GUID son aún mayores. Rendirse.

El programa, aunque sus errores, muestra la prueba de que un GUID no es único. Los que intentan demostrar lo contrario están perdiendo el punto. Esta declaración solo prueba la implementación débil de algunas de las variaciones GUID.

Un GUID no es necesariamente único por definición, es altamente único por definición. Acabas de refinar el significado de altamente. Dependiendo de la versión, el implementador (MS u otros), el uso de máquinas virtuales, etc., su definición de cambios importantes. (ver enlace en publicación anterior)

Puede acortar su tabla de 128 bits para demostrar su punto. La mejor solución es usar una fórmula hash para acortar su tabla con duplicados, y luego usar el valor completo una vez que el hash colisiona y, en función de eso, volver a generar un GUID. Si se ejecuta desde diferentes ubicaciones, estaría almacenando sus pares de claves hash / completas en una ubicación central.

Ps: Si el objetivo es solo generar x número de valores diferentes, cree una tabla hash de este ancho y simplemente verifique el valor hash.

No para p ** s en la hoguera aquí, pero en realidad 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, muestra el MISMO GUID la primera vez que se llama. Entonces, cuando en teoría no puedes tener un conflicto, si hay un problema al generar dicha GUI, entonces puedes obtener duplicados

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

Dado que parte de la generación de Guid se basa en el tiempo actual de la máquina, mi teoría para obtener un Guid duplicado es:

1. Realizar una instalación limpia de Windows
2. Cree un script de inicio que restablezca el tiempo a 2010-01-01 12:00:00 justo cuando Windows se inicia.
3. Justo después del script de inicio, activa su aplicación para generar un Guid.
4. Clone esta instalación de Windows, de modo que descarte cualquier diferencia sutil que pueda ocurrir en posteriores arranques.
5. Vuelva a crear una imagen del disco duro con esta imagen y arranque la máquina varias veces.

Para mí ... el tiempo que tarda un solo núcleo en generar un UUIDv1 garantiza que será único. Incluso en una situación de múltiples núcleos, si el generador de UUID solo permite que se genere un UUID a la vez para su recurso específico (tenga en cuenta que múltiples recursos pueden utilizar totalmente los mismos UUID, aunque es poco probable ya que el recurso forma parte inherente de la dirección) tendrá UUID más que suficientes para durar hasta que se agote la marca de tiempo. En ese momento dudo mucho que te importe.

Aquí también hay una solución:

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

Nota: requiere Qt, pero le garantizo que si lo deja correr el tiempo suficiente, podría encontrar uno.

(Nota: en realidad, ahora que lo estoy viendo, puede haber algo en el algoritmo de generación que evita que dos uuidos generados posteriormente colisionen, pero dudo un poco).

La única solución para demostrar que los GUID no son únicos sería tener un grupo GUID mundial. Cada vez que se genera un GUID en algún lugar, debe registrarse en la organización. O diablos, podríamos incluir una estandarización que todos los generadores GUID necesitan para registrarla automáticamente y para eso necesita una conexión a Internet activa.