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

323

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
fuente
107
Como desarrollador de software, ¿qué diría si un usuario se acercara a usted y le dijera "no está funcionando"?
JoshJordan el
152
Espera varios billones de años.
hobbs
67
Mejorado porque esto es lo más divertido que he visto en línea hoy.
jrockway
32
@jrockway - jajaja. Tengo problemas para encontrar algo sobre esta pregunta que no sea fundamentalmente incorrecto. Cuanto más lo miro, más divertido se vuelve.
tylerl
243
Es globalmente único, por lo que es único en nuestro planeta. Si desea una identificación verdaderamente única, debe usar una identificación universalmente única (UUID). Supongo que solo te interesa la unicidad dentro de nuestro universo. :-)
tvanfosson

Respuestas:

407

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.

revs ligos
fuente
120
Esa última consola. WriteLine me hizo reír mucho. Creo que deberías lanzar un CommonlyAcceptedCosmologicTheoriesWrongExceptionen su lugar.
R. Martinho Fernandes
17
¿marcar esto como Aceptado también significa que @Kai acepta los términos estipulados por @ligos?
kb.
3
La configuración en reserveSomeRam = null;realidad no logra nada.
DevinB
44
@devinb por favor explique? parece que está liberando los bytes que se asignaron previamente para que el GC pueda Collect()hacerlo. ¿Por qué no logra nada?
mythz
3
GuidCollisionDetector. El nombre tiene potencial
Ufuk Hacıoğulları
226

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

rjmunro
fuente
27
maldición, ¿entonces quizás varios hilos que generan guías es una mejor idea?
Kai
107
4 hilos en un procesador de cuatro núcleos lo harían funcionar en 20 mil millones de veces la edad del universo, así que sí, eso ayudaría mucho.
rjmunro
34
Sospecho que se trata de un troll, pero si no lo es, los hilos no son mágicos. Si puede hacer mil millones de operaciones por segundo en un subproceso, ir a diez subprocesos significa que cada uno ejecuta 1/10 de la frecuencia. Cada hilo realiza 100 M de operaciones por segundo; el número total de operaciones por segundo no aumenta. La forma de aumentar el número de operaciones por segundo es comprar más computadoras. Supongamos que compraste mil millones de computadoras más. Eso reduciría el problema a solo tomar 10790283070806 años, que aún son más de cuatro horas.
Eric Lippert
10
Creo que rjmunro está asumiendo que cada hilo se ejecutará en un núcleo separado; 83 mil millones de universos / 4 núcleos equivalen aproximadamente a 20 mil millones de universos. ¡Es hora de comprar acciones de Intel!
Dour High Arch
44
@Erik 83 mil millones de procesadores significa que podrá hacerlo en aproximadamente la cantidad de tiempo que el universo ha existido hasta ahora. Así que incluso eso no es suficiente.
rjmunro
170

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.

tylerl
fuente
44
¡Principio de casillero al rescate!
yfeldblum
22
+1 para el sol que se enfría comentario. Hubo un comentario interesante en alguna parte sobre la inutilidad de las claves de cifrado> 256 bits. Repetir todos los valores clave posibles requeriría más energía de la que posee todo el universo. Alternar un poco en la CPU requiere una pequeña cantidad de energía (es lo que genera el calor) que, cuando se multiplica 2 ^ 256 veces es un número realmente masivo que excede la energía almacenada en el universo, usando E = mc2 el universo necesitaría una masa de 2 ^ 227 kg, nuestro sol es 2 ^ 101 kg, ¡eso es 2 ^ 126 soles!
Skizz
31
@Skizz: Esto es cierto solo para ataques de fuerza bruta. Cuando un esquema de cifrado está "roto", significa que se puede resolver en menos tiempo que la fuerza bruta, pero el tiempo de resolución sigue siendo proporcional al tamaño de la clave.
Steven Sudit
1
@StevenSudit: proporcional al exponente del tamaño de la clave (a menos que P == NP)
Ihar Bury
1
@Orlangur Proporcional al tamaño de clave medido en bits.
Steven Sudit
137

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.

Jason
fuente
239
Si eres asesinado en algún momento de tu vida, es probable que sea al final.
Michael Myers
25
@mmyers: Excelente punto. Eso significa que mis posibilidades de ser asesinado en este momento son absurdamente bajas, ya que este no es el final de mi vida. Oh, espera ...
Steven Sudit
Además, si se crean dos GUID en un período corto, las posibilidades de que se usen dentro del mismo sistema son escasas. Por lo tanto, esto aumenta la unicidad.
AMissico
Estos números y referencias al problema del cumpleaños no tienen sentido. Los algoritmos de generación de GUID no generan valores en todo el rango con la misma probabilidad. De hecho, el algoritmo original IIRC utilizó la dirección MAC de la PC generadora + la hora actual como parte del resultado, lo que reduce el riesgo de colisión con las guías generadas en otras PC, pero por supuesto reduce el espacio clave.
Joe
17
Estás asumiendo que la probabilidad de ser asesinado es una constante para todos los seres humanos. Pero claramente las personas que escriben comentarios sarcásticos en las publicaciones del foro son el tipo de personas que tienen más probabilidades de ser asesinadas que la persona promedio.
Jay
61

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.

ctacke
fuente
13
Genial: ¿cuánto cuesta el conjunto completo, de 0 a (2 ^ 128) -1?
Steve314
23
A la venta, $ 0.01 por 1k GUID. Voy a poner algunas campanas de viento de bambú si pides en los próximos 60 minutos.
ctacke
77
Mi set es más exclusivo y de mayor calidad. Se verifican y verifican dos veces, lo que hace que valgan $ 1 por GUID. Incluso puede comprarlos en lotes si no desea hacer la inversión completa de una sola vez. Sin embargo, tendré que cobrar $ 10 adicionales por lote.
Thomas
3
Te estableceré un plan mensual y te daré guías ilimitadas por el precio correcto. ^ Esos tipos están tratando de estafarte y venderte guías caros. ¡Te venderé guías de calidad hechas en China!
ErocM
47

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

Amissico
fuente
44
Solo recuerde Se necesita un tipo de programador "especial" para hacer eso ...
AnthonyLambert
Me gustaría escuchar tu razonamiento a tu teoría. ¡Creo que podríamos comenzar una nueva religión basada en esto y reclutar a T.Cruise!
ErocM
@ErocM; Consulte "Cosmología de Brane" ( en.wikipedia.org/wiki/Brane_cosmology ) y "Membrana (M-Theory)" ( en.wikipedia.org/wiki/Membrane_(M-Theory) ). La idea es que si dos branas tocan se crea un nuevo universo. Por lo tanto, puede inferir que si dos GUID se tocan, se crea un nuevo universo.
AMissico
2
Si Timecop nos enseñó algo es que la misma materia no puede ocupar el mismo espacio en un momento dado. Entonces, si dos GUIDs donde chocan, se consumirían entre sí y la implosión resultante generaría un agujero negro, engullendo todo el universo. Entonces, en realidad, no crearía un Universo, lo destruiría.
AJC
42

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();
R. Martinho Fernandes
fuente
21
Recibo una excepción al llamar a Destroy (). Según el texto, creo que mi computadora carece del hardware necesario para destruir el universo actual. ¿Sabes dónde podría obtenerlo?
Steven Sudit
11
@ Steven: No, algunos gerentes se preocuparon demasiado por lo mal que se vería esa API para el público y dictaminaron que siempre fallaba por "razones de seguridad". Si nos fijamos en la fuente del método sólo hay una línea que: throw new MundaneHardwareException();. De todos modos, escuché que los muchachos del CERN tienen algún tipo de Big Hadron Thingy que podría hacer el truco ...
R. Martinho Fernandes
77
@ Martininho: Ah, está bien. Buscaré reemplazar Universe.Current.Destroy()con Cern.Lhc.DestroyThisUniverse().
Steven Sudit
61
Sabía que había una razón por la que programé en Haskell. Estos efectos secundarios son cada vez más aterradores.
Edward KMETT
66
"Hay una teoría que establece que si alguna vez alguien descubre exactamente para qué es el Universo y por qué está aquí, desaparecerá instantáneamente y será reemplazado por algo aún más extrañamente inexplicable. Hay otra teoría que afirma que esto ya sucedió ". - Douglas Adams, La guía del autoestopista galáctico
Mike Pirnat
28

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.

Graviton
fuente
Entonces, ¿2 ^ 128 no es el número correcto de guías posibles?
Kai
21
Es. ¿Por qué crees que 2 ^ 128 es un número pequeño?
jrockway
Sí, 2 ^ 128 es el número correcto de guías posibles.
Graviton el
3
Ese es un gran número. $ irb >> 2**128 => 340282366920938463463374607431768211456
adamJLev
45
@Infinity - ¿Incluso para ti?
Austin Richardson
27

[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"

Stephen M. Redd
fuente
3
Eso es realmente factible cuando se usa la virtualización. Puedes y obtienes guías duplicadas.
Goran
8
Sin embargo, Raymond está desactualizado en la parte de la dirección MAC, Microsoft ya no los usa. Consulte en.wikipedia.org/wiki/GUID#Algorithm para ver la diferencia entre las guías V1 y V4.
Michael Stum
1
Este ya no es el caso. El esquema V5 actual tiene solo 128 bits de bondad pseudoaleatoria pura.
Edward KMETT
¿Es curioso cómo declaras todo lo que hice un mes después que yo y obtienes 16 puntos y todavía tengo 0?
AnthonyLambert
1
Ya Tony, hay algo extraño con eso. Cuando respondí la publicación, solo había 3 o 4 respuestas, y no recordaba haber visto la suya ... si lo hubiera hecho, simplemente la habría votado. Por lo general, no respondo preguntas cuando ya hay otras respuestas que lo cubren lo suficientemente bien (por eso es probable que tenga un representante general bastante bajo).
Stephen M. Redd
23

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.

KristoferA
fuente
2
¿Cómo garantiza esto que this guidnunca se haya generado en ningún otro lugar del mundo? : p Diablos, necesitamos un grupo mundial de guid. :)
nawfal 01 de
19

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; -)

Steve314
fuente
17

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!

kibitzer
fuente
12
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.

Nathan Taylor
fuente
1
no - porque no puedo iterar bigint
Kai
3
¿Realmente importa si realiza un bucle para siempre frente a un bucle 340282366920938463463374607431768211456 veces?
Jay
3
entonces ... ¿preferirías ser golpeado 340282366920938463463374607431768211456 veces o para siempre!?!?!?
ErocM
En realidad, esto es lo que realmente responde a la pregunta. y sin votos: p
nawfal
11

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

Matt Peterson
fuente
9

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.

revs MZB
fuente
8

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

papá
fuente
hmmmm ..... podría ejecutarlo en nuestra cuadrícula de 10,000 nodos en el trabajo.
AnthonyLambert
8

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.

Jason Goemaat
fuente
7

¿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

AnthonyLambert
fuente
3
No todos los GUID se crean de esta manera. Incluso si lo fueran, Kai solo necesita esperar hasta que la marca de tiempo utilizada para crear el GUID se ajuste lo suficiente como para que se vuelva a usar uno que utilizó para crear un GUID.
Dour High Arch
3
Las guías no se han basado en la dirección mac desde 2000 o 2001. A partir de uno de los paquetes de servicio para NT4 y / o Win2k, cambiaron el algoritmo por completo. Ahora son generados por un generador de números aleatorios, menos unos pocos bits que identifican qué tipo de guía es.
KristoferA
44
No todos los GUID provienen de las plataformas de Windows ...
AnthonyLambert
OP menciona C #, entonces es Windows. Además, ¿los V4 GUID son solo para Windows?
Steven Sudit
55
@Martinho: Ah, pero la prueba de unidad de Mono para Guid, en GuidTest.cs, contiene un método que crea dos nuevos GUID y los verifica para determinar la igualdad, fallando si son iguales. Como Mono se construye con éxito, ¡podemos estar absolutamente seguros de que sus GUID son únicos! :-)
Steven Sudit
6

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.

Michael Stum
fuente
6

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

Behrooz
fuente
la razón para no añadir esto como un comentario: nadie lo mencionó, y no sé que yo debería decir esto a :).
Behrooz
Hooooraaaay, lo hice. En alguna aplicación "real" que escribí, tuve una colisión Guid en una mesa con ~ 260k filas. (MSSQL 2008 R2 Express).
Behrooz
6
  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).

revs JiminP
fuente
Estaba esperando una referencia de superhéroe en esta respuesta - falla por póster: p - impresionante, no obstante.
IbrarMumtaz
4

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

RCIX
fuente
2
nadie ha votado por la respuesta que realmente responde a la pregunta: P
nawfal
4

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.

Bill Yang
fuente
3

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.

Mark Ransom
fuente
2

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.

ydebilloez
fuente
2

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

Ben
fuente
1

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.
codificador de mundo real
fuente
0

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.

más duro
fuente
0

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

Scott
fuente
0

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.

nawfal
fuente