Prosty dowód, że GUID nie jest unikalny [zamknięty]

To potrwa dłużej niż godziny. Zakładając, że zapętli się na 1 GHz (czego nie będzie - będzie dużo wolniej), będzie działać przez 10790283070806014188970 lat. Który jest około 83 miliardy razy dłuższy niż wiek Wszechświata.

Zakładając, że prawo Mooresa obowiązuje, dużo szybciej byłoby nie uruchomić tego programu, odczekać kilkaset lat i uruchomić go na komputerze, który jest miliardy razy szybszy. W rzeczywistości każdy program, który trwa dłużej niż procesor prędkość do podwojenia (około 18 miesięcy) zakończy się wcześniej, jeśli poczekasz, aż prędkość procesora wzrośnie i kupisz nowy procesor przed uruchomieniem (chyba że napiszesz go tak, że można go zawiesić i wznowić na nowym sprzęcie).

GUID teoretycznie nie jest unikalny. Oto twój dowód:

• GUID jest 128-bitową liczbą
• nie można wygenerować 2^128 + 1 lub więcej GUID bez ponownego użycia starych GUID

Jednakże, gdyby cała moc słoneczna była skierowana na wykonanie tego zadania, wystygłoby ono na długo przed jego zakończeniem.

Guid mogą być generowane przy użyciu wielu różnych taktyk, z których niektóre podejmują specjalne środki, aby zagwarantować, że dana maszyna nie wygeneruje tego samego GUID dwa razy. Znalezienie kolizji w danym algorytmie pokazałoby, że dana metoda generowania identyfikatorów GUID jest zła, ale nie udowodniłaby niczego o identyfikatorach GUID w ogóle.

Oczywiście Guidy mogą się zderzyć. Ponieważ GUID są 128-bitowe, wystarczy wygenerować 2^128 + 1 z nich i zgodnie z zasadą pigeonhole musi dojść do kolizji.

Ale kiedy mówimy, że GUID jest unikalny, to tak naprawdę mamy na myśli, że przestrzeń kluczy jest tak duża, że praktycznie niemożliwe jest przypadkowe wygenerowanie tego samego GUID dwa razy (zakładając, że generujemy GUID losowo).

Jeśli wygenerujesz sekwencję n GUID losowo, to prawdopodobieństwo co najmniej jednego kolizja wynosi około p(n) = 1 - exp(-n^2 / 2 * 2^128) (jest to problem urodzinowy z liczbą możliwych urodzin to 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

Aby te liczby były konkretne, 2^60 = 1.15e+18. Jeśli wygenerujesz miliard GUID na sekundę, wygenerowanie 2^60 losowych GUID zajmie ci 36 lat, a nawet wtedy prawdopodobieństwo kolizji jest nadal 1.95e-03. Bardziej prawdopodobne, że w którymś momencie swojego życia zostaniesz zamordowana (4.76e-03) / align = "left" / lat. Powodzenia.

Jeśli martwisz się o wyjątkowość, zawsze możesz kupić nowe GUIDs, dzięki czemu możesz wyrzucić swoje stare. Wrzucę trochę na eBay, jeśli chcesz.

Osobiście uważam, że "wielki wybuch" był spowodowany zderzeniem dwóch Guidów.

Możesz pokazać, że w czasie O(1) z wariantem algorytmu quantum bogosort.

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

Dowolne dwa GUID są bardzo prawdopodobne unikalne (Nie równe).

Zobacz ten wpis oraz z Wikipedii

Podczas gdy każdy wygenerowany GUID nie jest gwarantujemy wyjątkowość, całość liczba unikalnych kluczy (2^128 lub 3,4×10^38) jest tak duża, że prawdopodobieństwo tej samej liczby jest wygenerowany dwukrotnie jest bardzo mały. Na przykład, rozważmy obserwowalne uniwersum, który zawiera około 5×10^22 Gwiazdy; każda gwiazda może wtedy mieć 6.8×10^15 unikalne Guidy.

Więc prawdopodobnie musisz poczekać jeszcze wiele miliardów lat i mieć nadzieję, że trafisz w jeden, zanim wszechświat, jaki znamy, dobiegnie końca.

[Aktualizacja:] jak podkreślają poniższe komentarze, nowsze ms GUID są V4 i nie używają adresu MAC jako części generowania GUID (nie widziałem żadnych wskazań implementacji V5 z MS, więc jeśli ktoś ma link potwierdzający, że daj mi znać). Jednak w przypadku V4 czas jest nadal czynnikiem, a szanse na powielanie GUID pozostają tak małe, że nie mają znaczenia dla praktycznego zastosowania. Z pewnością nie będzie prawdopodobne, aby kiedykolwiek wygenerować duplikat GUID z tylko jeden test systemu, taki jak po próbował zrobić.

Większość z tych odpowiedzi brakuje jednego ważnego punktu dotyczącego implementacji GUID Microsoftu. Pierwsza część identyfikatora GUID opiera się na znaczniku czasu, a druga na adresie MAC karty sieciowej (lub na losowej liczbie, jeśli nie jest zainstalowana karta sieciowa).

Jeśli dobrze to Rozumiem, oznacza to, że jedynym niezawodnym sposobem powielenia GUID byłoby uruchamianie symulowanych generacji GUID na wielu maszynach gdzie adresy MAC były takie same i gdzie zegary w obu systemach były dokładnie w tym samym czasie, kiedy nastąpiła generacja (znacznik czasu jest oparty na milisekundach, jeśli dobrze rozumiem).... nawet wtedy jest wiele innych bitów w liczbie, które są losowe, więc szanse są nadal znikają.

Dla wszystkich praktycznych celów GUID są uniwersalnie unikalne.

Jest całkiem dobry opis MS GUID na " Stary Nowy" blog

Oto sprytna metoda rozszerzenia, której możesz użyć, jeśli chcesz sprawdzić unikalność guid w wielu miejscach w kodzie.

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

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

...polecam nawet zadzwonić dwa razy, żeby upewnić się, że w pierwszej rundzie będzie dobrze.

Liczenie do 2^128-ambitne.

Wyobraźmy sobie, że możemy policzyć 2^32 IDs na sekundę na maszynę - nie to ambitne, ponieważ nie jest to nawet 4,3 miliarda na sekundę. Dedykujemy do tego zadania 2^32 maszyny. Ponadto, pozwala uzyskać 2^32 cywilizacje do każdego poświęcić te same zasoby do zadania.

Do tej pory możemy liczyć 2^96 IDs na sekundę, co oznacza, że będziemy liczyć przez 2^32 sekund (trochę ponad 136 lat).

Cóż, jeśli czas pracy 83 miliardów lat nie przeraża, myślę, że trzeba będzie również przechowywać wygenerowane GUID gdzieś, aby sprawdzić, czy masz duplikat; przechowywanie 2^128 16-bajtowych numerów wymagałoby tylko przydzielenia 4951760157141521099596496896 terabajtów pamięci RAM z góry, więc wyobrażając sobie, że masz komputer, który może zmieścić to wszystko i że w jakiś sposób znaleźć miejsce na zakup terabajtów DIMM po 10 gramów każdy., łącznie będą ważyły więcej niż 8 mas Ziemi, więc można poważnie przesuń go z bieżącej orbity, zanim wciśniesz "Uruchom". Pomyśl dwa razy!

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

Nie zwiększasz begin więc warunek begin < end jest zawsze prawdziwy.

Jeśli kolizje GUID są problemem, zalecałbym użycie ScottGuID zamiast tego.

Prawdopodobnie masz powody sądzić, że algorytm wytwarzania GUID nie produkuje naprawdę losowych liczb, ale w rzeczywistości jest cyklem z okresem

Np. metoda RFC4122 używana do wyprowadzania identyfikatorów GUID, które ustalają wartości niektórych bitów.

Dowód jazdy na rowerze będzie zależał od możliwej wielkości okresu.

Dla małych okresów, hash table of hash (GUID) - > GUID z wymianą przy kolizji jeśli GUID nie pasują (Zakończ, jeśli tak) może być podejdźcie. Rozważ również, że wymiana odbywa się tylko w przypadkowym ułamku czasu.

Ostatecznie, jeśli maksymalny okres między kolizjami jest wystarczająco duży (i nie jest znany z góry), każda metoda da tylko prawdopodobieństwo, że kolizja zostanie znaleziona, gdyby istniała.

Zauważ, że jeśli metoda generowania identyfikatorów GUID jest oparta na zegarze (patrz RFC), to może nie być możliwe określenie, czy kolizje istnieją, ponieważ albo (a) nie będziesz w stanie czekać wystarczająco długo na zegar do owinięcia dookoła, lub (b) nie można zażądać wystarczającej ilości GUID w tyknięciu Zegara, aby wymusić kolizję.

Alternatywnie możesz pokazać zależność statystyczną między bitami w Guid lub korelację bitów między GUID. Taka zależność może sprawić, że algorytm będzie wysoce prawdopodobny, bez konieczności znalezienia rzeczywistej kolizji.

Oczywiście, jeśli chcesz tylko udowodnić, że Guidy mogą zderzać się, to dowód matematyczny, a nie program, jest odpowiedzią.

Ale czy musisz być pewnym masz duplikat, czy zależy Ci tylko na tym, czy Może być duplikatem. Aby mieć pewność, że masz dwie osoby o tych samych urodzinach, potrzebujesz 366 osób (nie licząc roku przestępnego). Aby mieć większą niż 50% szansę na posiadanie dwóch osób z tymi samymi urodzinami, potrzebujesz tylko 23 osób. To jest problem urodzinowy .

Jeśli masz 32 bity, potrzebujesz tylko 77 163 wartości, aby mieć większą niż 50% szansę na duplikat. Spróbuj

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

Teraz 128 bitów to dużo, więc nadal mówisz o dużej liczbie elementów, które nadal dają ci małą szansę na kolizję. Potrzebna jest następująca liczba rekordów dla podanych kursów przy użyciu przybliżenia:

• 0,8 miliarda miliardów dla 1/1000 szansy na zderzenie
• 21,7 miliarda miliardów dla 50% szans na zderzenie
• 39,6 miliarda miliardów na 90% szans na zderzenie

Istnieje około 1e14 e-maile wysyłane rocznie, więc byłoby to około 400,000 lat na tym poziomie, zanim miałbyś 90% szans na posiadanie dwóch z tym samym GUID, ale to znacznie różni się od powiedzenia, że trzeba uruchomić komputer 83 miliardy razy wiek wszechświata lub że słońce schłodzi przed znalezieniem duplikatu.

Nie rozumiem dlaczego nikt nie wspomniał o aktualizacji karty graficznej... Na pewno jeśli masz wysokiej klasy NVIDIA Quadro FX 4800 lub coś (rdzenie CUDA 192) to pójdzie szybciej...

Oczywiście, jeśli stać Cię na kilka NVIDIA Qadro Plex 2200 S4 (po 960 rdzeni CUDA każdy), obliczenia te naprawdę. krzycz. Może NVIDIA pożyczy ci kilka na "pokaz technologii" jako wyczyn PR-owy?

Na pewno chcieliby być częścią tego historyczne obliczenia...

Czy wy wszyscy nie pominęliście ważnego punktu?

Myślałem, że Guidy zostały wygenerowane za pomocą dwóch rzeczy, które sprawiają, że szanse na ich globalną unikalność są dość wysokie. Po pierwsze, Są one osadzone z adresem MAC maszyny, na której się znajdujesz, a po drugie, używają czasu, który zostały wygenerowane oraz losowej liczby.

Więc jeśli nie uruchomisz go na rzeczywistej maszynie i uruchom wszystkie odgadnięcia w najmniejszym czasie, który maszyna używa do reprezentowania czasu w GUID you nigdy nie wygeneruje tego samego numeru bez względu na to, ile zgadnięć podejmiesz za pomocą wywołania systemowego.

Myślę, że jeśli znasz rzeczywisty sposób tworzenia GUID, skróci to znacznie czas na odgadnięcie.

Tony

Możesz zahaczać o Guidy. W ten sposób powinieneś uzyskać wynik znacznie szybciej.

Oh, oczywiście, uruchamianie wielu wątków w tym samym czasie jest również dobrym pomysłem, w ten sposób zwiększysz szansę na warunek wyścigu generowanie tego samego GUID dwa razy na różnych wątkach.

Idź do laboratorium kriogeniki w Nowym Jorku. Zamrozić się na (mniej więcej) 1990 lat. Znajdź pracę w Planet Express. Kup nowy procesor. Zbuduj komputer, uruchom program i umieść go w bezpiecznym miejscu za pomocą pseudo-perpetuum mobile jak maszyna doomsday. Poczekaj, aż wehikuł czasu zostanie wynaleziony.
1. Skocz do przyszłości za pomocą wehikułu czasu. Jeśli kupiłeś procesor 1YHZ 128bit, przejdź do 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps po uruchomieniu program.
2. ...?
Zysk!!!

... Zajmuje to co najmniej 10,783,127 lat, nawet jeśli masz procesor 1YHZ, który jest 1,000,000,000,000,000 (lub 1,125,899,906,842,624, jeśli wolisz używać prefiksu binarnego) razy szybszy niż procesor 1GHz.

Więc zamiast czekać na skończone obliczenia, lepiej byłoby nakarmić gołębie, które straciły swój dom, ponieważ inne gołębie zabrały swój dom. :(

Lub, można poczekać, aż 128-bitowy komputer kwantowy zostanie wynaleziony. Wtedy możesz udowodnić, że GUID nie jest unikalny, przez korzystanie z programu w rozsądnym czasie (być może).

Guid to 124 bity, ponieważ 4 bity zawierają Numer wersji.

Próbowałeś begin = begin + new BigInteger((long)1) zamiast begin++?

Jeśli liczba generowanych UUID jest zgodna z prawem Moore ' a, wrażenie, że GUID nigdy nie kończy się w dającej się przewidzieć przyszłości jest fałszywe.

Z 2 ^ 128 uuid, zajmie to tylko 18 miesięcy * Log2(2^128) ~ = 192 lata, zanim zabraknie nam wszystkich uuid.

I wierzę (bez statystycznego dowodu Co-so-ever) w ciągu ostatnich kilku lat od masowego przyjęcia UUID, prędkość generowania uuid rośnie znacznie szybciej niż nakazuje prawo Moore ' a. Innymi słowy, prawdopodobnie mamy mniej niż 192 lata, zanim uporamy się z kryzysem UUID, to dużo wcześniej niż koniec wszechświata.

Ale ponieważ na pewno nie będziemy ich uruchamiać do końca 2012 roku, zostawimy to innym gatunkom, aby martwili się o problem.

Szanse na błąd w kodzie generującym GUID są znacznie wyższe niż szanse algorytmu generującego kolizję. Szanse na błąd w kodzie do testowania GUID jest jeszcze większa. Poddaj się.

Nie p * * s na ognisko tutaj, ale to się rzeczywiście dzieje, i tak, Rozumiem żart, które zostały dając temu facetowi, ale GUID jest unikalny tylko w zasadzie, wpadłem na ten wątek, ponieważ jest błąd w emulatorze WP7, co oznacza, że za każdym razem, gdy buty daje ten sam GUID za pierwszym razem jest nazywany! Więc, gdzie teoretycznie nie można mieć konfliktu, jeśli istnieje problem generowania powiedział GUI, to można uzyskać duplikaty

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

Program, mimo swoich błędów, pokazuje dowód, że GUID nie jest unikalny. Ci, którzy próbują udowodnić coś przeciwnego, nie rozumieją tego. To stwierdzenie dowodzi tylko słabej implementacji niektórych wariantów GUID.

GUID nie jest potrzebny z definicji unikalny, jest bardzo unikalny z definicji. Właśnie udoskonaliłeś znaczenie highly. W zależności od wersji, implementator (MS lub inne), użycie maszyn wirtualnych, itp twoja definicja bardzo zmienia. (patrz link we wcześniejszym post)

Możesz skrócić tabelę 128 bitów, aby udowodnić swoją rację. Najlepszym rozwiązaniem jest użycie formuły skrótu, aby skrócić tabelę z duplikatami, a następnie użyć pełnej wartości, gdy hash zderzy się i na podstawie tego ponownie wygenerować GUID. Jeśli uruchamiasz się z różnych lokalizacji, będziesz przechowywać pary hash/full key W centralnej lokalizacji.

Ps: Jeśli celem jest tylko wygenerowanie X liczby różnych wartości, Utwórz tabelę hash o tej szerokości i po prostu sprawdź hash wartość.

Ponieważ część generowania Guid opiera się na czasie obecnej maszyny, moja teoria, aby uzyskać duplikat Guid jest:

1. Wykonaj czystą instalację systemu Windows
2. Utwórz skrypt startowy, który resetuje czas do 2010-01-01 12: 00: 00 po uruchomieniu systemu Windows.
3. tuż po skrypcie startowym uruchamia aplikację w celu wygenerowania identyfikatora Guid.
4. Sklonuj tę instalację Windows, aby wykluczyć wszelkie subtelne różnice, które mogą wystąpić w kolejnych rozruszniki.
5. Ponownie obraz dysku twardego z tym obrazem i uruchomić maszynę kilka razy.

Dla mnie.. czas potrzebny na wygenerowanie uuidv1 przez pojedynczy rdzeń gwarantuje, że będzie on unikalny. Nawet w sytuacji wielordzeniowej, jeśli generator UUID pozwala na generowanie tylko jednego UUID na raz dla określonego zasobu (należy pamiętać, że wiele zasobów może całkowicie wykorzystać te same uuid, jednak mało prawdopodobne, ponieważ zasób jest częścią adresu), wtedy będziesz mieć więcej niż wystarczająco dużo uuid, aby przetrwać aż do wypalenia znacznika czasu. W którym momencie naprawdę wątpię, byś care.

Tutaj też jest rozwiązanie:

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

Uwaga: Wymaga Qt, ale gwarantuję, że jeśli pozwolisz mu działać wystarczająco długo, może go znaleźć.

(Uwaga Uwaga: właściwie, teraz, gdy na to patrzę, może być coś w algorytmie generowania, który zapobiega kolizji dwóch wygenerowanych później uuid-ale trochę w to wątpię).

Jedynym rozwiązaniem, aby udowodnić, że GUID nie są unikalne, byłoby posiadanie światowej puli GUID. Za każdym razem, gdy GUID jest generowany gdzieś, powinien być zarejestrowany w organizacji. Albo heck, możemy włączyć standaryzację, że wszystkie generatory GUID muszą zarejestrować go automatycznie i do tego potrzebuje aktywnego połączenia z Internetem!