Czy GUID jest unikalny w 100% przypadków?

Czy GUID jest unikalny w 100% przypadków?

Czy pozostanie wyjątkowy w wielu wątkach?

Chociaż nie ma gwarancji, że każdy wygenerowany identyfikator GUID będzie unikalny, całkowita liczba unikalnych kluczy (2 ¹²⁸ lub 3,4 × 10 ³⁸ ) jest tak duża, że ​​prawdopodobieństwo dwukrotnego wygenerowania tej samej liczby jest bardzo małe. Rozważmy na przykład obserwowalny wszechświat, który zawiera około 5 × 10 ²² gwiazd; każda gwiazda mogłaby wtedy mieć 6,8 × 10 ¹⁵ uniwersalnie unikalnych GUID.

Z Wikipedii .

Oto kilka dobrych artykułów na temat tworzenia GUID (dla .NET) i tego, jak uzyskać ten sam identyfikator w odpowiedniej sytuacji.

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-three/

W pobliżu

Jeśli boisz się tych samych wartości GUID, umieść dwie z nich obok siebie.

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

Jeśli jesteś zbyt paranoikiem, postaw trzy.

Prostą odpowiedzią jest tak.

Raymond Chen napisał świetny artykuł na temat GUID i dlaczego nie ma gwarancji, że podciągi GUID są unikalne. W artykule szczegółowo omówiono sposób generowania identyfikatorów GUID i danych, których używają, aby zapewnić wyjątkowość, co powinno zająć trochę czasu, wyjaśniając, dlaczego są :-)

Na marginesie, bawiłem się z identyfikatorami GUID woluminu w systemie Windows XP. Jest to bardzo niejasny układ partycji z trzema dyskami i czternastoma woluminami.

\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
                                     | | | | |
                                     | | | | +-- 6f = o
                                     | | | +---- 69 = i
                                     | | +------ 72 = r
                                     | +-------- 61 = a
                                     +---------- 6d = m

Nie chodzi o to, że identyfikatory GUID są bardzo podobne, ale fakt, że wszystkie identyfikatory GUID mają w sobie ciąg „mario”. Czy to przypadek, czy kryje się za tym wyjaśnienie?

Teraz, kiedy googlowałem w części 4 w GUID, znalazłem około 125 000 trafień z GUID woluminów.

Wniosek: jeśli chodzi o GUID woluminów, nie są one tak unikalne jak inne GUID.

To nie powinno się zdarzyć. Jednak gdy .NET jest obciążony, możliwe jest uzyskanie duplikatów prowadnic. Mam dwa różne serwery sieciowe korzystające z dwóch różnych serwerów SQL. Poszedłem scalić dane i odkryłem, że mam 15 milionów przewodników i 7 duplikatów.

Tak, GUID powinien zawsze być unikalny. Opiera się zarówno na sprzęcie, jak i czasie, a także kilka dodatkowych bitów, aby upewnić się, że jest wyjątkowy. Jestem pewien, że teoretycznie możliwe jest uzyskanie dwóch identycznych, ale wyjątkowo mało prawdopodobne w prawdziwym świecie.

Oto świetny artykuł Raymonda Chena na temat Guids:

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Przewodniki są statystycznie wyjątkowe. Szanse dwóch różnych klientów generujących ten sam Guid są nieskończenie małe (zakładając, że nie ma błędów w kodzie generującym Guid). Równie dobrze możesz się martwić, że Twój procesor zepsuje się z powodu promienia kosmicznego i zdecydujesz, że 2 + 2 = 5 dzisiaj.

Wiele wątków przydzielających nowe prowadnice otrzyma unikalne wartości, ale powinieneś się upewnić, że funkcja, którą wywołujesz, jest wątkowa. W jakim środowisku to jest?

Eric Lippert napisał bardzo interesującą serię artykułów na temat GUID.

Na świecie dostępnych jest 2 ³⁰ komputerów osobistych (i oczywiście wiele urządzeń ręcznych lub urządzeń komputerowych innych niż PC, które mają mniej więcej taki sam poziom mocy obliczeniowej, ale zignorujmy je). Załóżmy, że postawiliśmy wszystkie komputery na świecie na zadanie generowania identyfikatorów GUID; jeśli każdy z nich może wygenerować, powiedzmy, 2 ²⁰ GUIDów na sekundę, to po zaledwie około 2 ⁷² sekundach - sto pięćdziesiąt bilionów lat - będziesz miał bardzo dużą szansę na wygenerowanie kolizji z twoim GUID. Szanse na kolizję stają się całkiem dobre po zaledwie trzydziestu bilionach lat.

• Przewodnik GUID, część pierwsza
• Przewodnik GUID, część druga
• Przewodnik GUID, część trzecia

Teoretycznie nie są wyjątkowe. Możliwe jest generowanie identycznego przewodnika w kółko. Jednak szanse na to są tak małe, że można założyć, że są wyjątkowe.

Przeczytałem wcześniej, że szanse są tak niskie, że naprawdę powinieneś stresować się czymś innym - na przykład spontanicznym spalaniem się serwera lub innymi błędami w kodzie. To znaczy, załóż, że jest unikalny i nie buduj żadnego kodu, aby „złapać” duplikaty - poświęć czas na coś, co może się wydarzyć (tj. Cokolwiek innego).

I podjął próbę opisania przydatności GUID do mojego bloga publiczności (nietechniczne memebers rodzinne). Stamtąd (za pośrednictwem Wikipedii) szanse na wygenerowanie duplikatu GUID:

• 1 na 2 ^ 128
• 1 na 340 undecillion (nie martw się, undecillion nie jest w quizie)
• 1 na 3,4 × 10 ^ 38
• 1 na 340 000 000 000 000 000 000 000 000 000 000 000 000 000

Wydaje się, że nikt nie wspomina o rzeczywistej matematyce prawdopodobieństwa jej wystąpienia.

Po pierwsze, załóżmy, że możemy wykorzystać całą 128-bitową przestrzeń (Guid v4 używa tylko 122 bitów).

Wiemy, że ogólne prawdopodobieństwo NIE otrzymania duplikatu w ntypach wynosi:

(1-1 / 2 ¹²⁸ ) (1-2 / 2 ¹²⁸ ) ... (1- (n-1) / 2 ¹²⁸ )

Ponieważ 2 ¹²⁸ jest znacznie większy niż n, możemy to przybliżyć do:

(1-1 / 2 ¹²⁸ ) ^{n (n-1) / 2}

A ponieważ możemy założyć, że njest znacznie większy niż 0, możemy to przybliżyć do:

(1-1 / 2 ¹²⁸ ) ^{n ^ 2/2}

Teraz możemy zrównać to z „akceptowalnym” prawdopodobieństwem, powiedzmy 1%:

(1-1 / 2 ¹²⁸ ) ^{n ^} 2/2 = 0,01

Które rozwiązujemy ni uzyskujemy:

n = sqrt (2 * log 0,01 / log (1-1 / 2 ¹²⁸ ))

Który Wolfram Alpha ma być 5.598318 × 10 ¹⁹

Aby spojrzeć na tę liczbę z perspektywy, weźmy 10000 maszyn, z których każda ma 4-rdzeniowy procesor, robi 4 GHz i wydaje 10000 cykli na wygenerowanie Guida i nic więcej. Wygenerowanie duplikatu zajęłoby wówczas około 111 lat.

Od http://www.guidgenerator.com/online-guid-generator.aspx

Co to jest GUID?

GUID (lub UUID) jest akronimem „Globalnie Unikalny Identyfikator” (lub „Uniwersalnie Unikalny Identyfikator”). Jest to 128-bitowa liczba całkowita używana do identyfikacji zasobów. Termin GUID jest na ogół używany przez programistów pracujących z technologiami Microsoft, podczas gdy UUID jest używany wszędzie indziej.

Jak wyjątkowy jest identyfikator GUID?

128 bitów jest wystarczająco duże, a algorytm generowania jest wystarczająco wyjątkowy, że gdyby wygenerowano 1 000 000 000 identyfikatorów GUID na sekundę przez 1 rok, prawdopodobieństwo duplikatu wynosiłoby tylko 50%. Lub gdyby każdy człowiek na Ziemi wygenerował 600 000 000 identyfikatorów GUID, prawdopodobieństwo duplikatu byłoby tylko 50%.

Wystąpił zduplikowany identyfikator GUID.

Używam skanera stacjonarnego Neat Receipts i jest on dostarczany z zastrzeżonym oprogramowaniem baz danych. Oprogramowanie ma funkcję synchronizacji z chmurą, a po synchronizacji ciągle pojawia się błąd. Gapiący się po polanach ujawnił niesamowitą linię:

„error”: [{„code”: 1, „message”: „creator_guid: jest już zajęty”, „guid”: „C83E5734-D77A-4B09-B8C1-9623CAC7B167”}]}

Byłem trochę niedowierzający, ale z pewnością, kiedy znalazłem drogę do mojej lokalnej bazy danych fajnych prac i usunąłem rekord zawierający ten identyfikator GUID, błąd przestał występować.

Aby odpowiedzieć na twoje pytanie niepotwierdzonymi dowodami, nie. Duplikat jest możliwy. Ale prawdopodobne jest, że przyczyną tego nie był przypadek, ale zwykła praktyka, której w jakiś sposób nie przestrzegano. (Po prostu nie mam tyle szczęścia) Nie mogę jednak powiedzieć na pewno. To nie jest moje oprogramowanie.

Ich obsługa klienta była BARDZO uprzejma i pomocna, ale nie musieli nigdy wcześniej napotykać tego problemu, ponieważ po ponad 3 godzinach rozmowy telefonicznej nie znaleźli rozwiązania. (FWIW, jestem pod wielkim wrażeniem Neat, a ta usterka, choć frustrująca, nie zmieniła mojej opinii na temat ich produktu).

MSDN :

Istnieje bardzo małe prawdopodobieństwo, że wartość nowego Guid jest zerowa lub równa dowolnemu innemu Guidowi.

Jeśli zegar systemowy jest ustawiony prawidłowo i nie jest zawinięty, a Twoja karta sieciowa ma własny adres MAC (tzn. Nie ustawiłeś niestandardowego adresu MAC), a dostawca karty sieciowej nie przetwarza adresów MAC (czego nie powinny robić) ale o których wiadomo, że występuje), a jeśli funkcja generowania identyfikatora GUID w systemie jest poprawnie zaimplementowana, system nigdy nie wygeneruje duplikatów identyfikatorów GUID.

Jeśli każdy na świecie, który generuje identyfikatory GUID, przestrzega tych zasad, wówczas identyfikatory GUID będą globalnie unikalne.

W praktyce liczba osób, które łamią reguły, jest niska, a ich identyfikatory GUID raczej nie „uciekną”. Konflikty są statystycznie nieprawdopodobne.

Czy GUID jest unikalny w 100% przypadków?

Nie gwarantuje się, ponieważ istnieje kilka sposobów ich wygenerowania. Możesz jednak spróbować obliczyć szansę na utworzenie dwóch identycznych identyfikatorów GUID i wpadniesz na pomysł: GUID ma 128 bitów, stąd są 2 ¹²⁸ odrębnych identyfikatorów GUID - znacznie więcej niż gwiazdy w znanym wszechświecie. Przeczytaj artykuł w Wikipedii, aby uzyskać więcej informacji.

W bardziej ogólnym znaczeniu jest to nazywane „problemem urodzinowym” lub „paradoksem urodzinowym”. Wikipedia ma całkiem niezły przegląd na stronie: Wikipedia - Problem urodzinowy

Mówiąc bardzo ogólnie, pierwiastek kwadratowy z wielkości puli jest przybliżonym przybliżeniem, kiedy można spodziewać się 50% szansy na duplikat. Artykuł zawiera tabelę prawdopodobieństwa wielkości puli i różne prawdopodobieństwa, w tym wiersz dla 2 ^ 128. Tak więc dla 1% prawdopodobieństwa kolizji można losowo wybrać 2,6 * 10 ^ 18 128-bitowych liczb. 50% szans wymaga 2,2 * 10 ^ 19 typów, a SQRT (2 ^ 128) to 1,8 * 10 ^ 19.

Oczywiście jest to idealny przypadek naprawdę losowego procesu. Jak inni wspominali, wiele dotyczy tego losowego aspektu - jak dobry jest generator i ziarno? Byłoby miło, gdyby istniało wsparcie sprzętowe wspomagające ten proces, które byłoby bardziej kuloodporne, z wyjątkiem tego, że wszystko można sfałszować lub zwirtualizować. Podejrzewam, że to może być powód, dla którego adresy MAC / znaczniki czasu nie są już włączone.

Aby uzyskać lepszy wynik, najlepszym sposobem jest dodanie identyfikatora GUID do znacznika czasu (aby upewnić się, że pozostaje unikalny)

Guid.NewGuid().ToString() + DateTime.Now.ToString();

Algorytmy GUID są zwykle implementowane zgodnie ze specyfikacją GUID v4, która jest zasadniczo pseudolosowym ciągiem. Niestety, należą one do kategorii „prawdopodobnie nieunikalne” z Wikipedii (nie wiem, dlaczego tak wielu ludzi ignoruje ten fragment): „... inne wersje GUID mają różne właściwości i prawdopodobieństwa unikalności, od gwarantowanej wyjątkowości do prawdopodobnej nietypowości ”.

Pseudolosowe właściwości JavaScriptu V8 Math.random()są OGROMNE w wyjątkowości, kolizje często pojawiają się już po kilku tysiącach iteracji, ale V8 nie jest jedynym winowajcą. Widziałem kolizje GUID w rzeczywistym świecie, używając zarówno implementacji GUID PHP, jak i Ruby.

Ponieważ coraz powszechniejsze staje się skalowanie generowania identyfikatorów na wielu klientach i klastrach serwerów, entropia ma ogromne znaczenie - szanse na to, że ten sam losowy materiał źródłowy zostanie użyty do wygenerowania eskalacji identyfikatora (czas jest często wykorzystywany jako losowy materiał wyjściowy w pseudolosowych generatorach), a kolizje GUID zwiększają się z „prawdopodobnie nieunikalnych” do „bardzo prawdopodobne, że spowodują wiele problemów”.

Aby rozwiązać ten problem, postanowiłem stworzyć algorytm ID, który można bezpiecznie skalować i zapewnić lepszą ochronę przed kolizją. Robi to za pomocą znacznika czasu, licznika klienta w pamięci, odcisku palca klienta i losowych znaków. Połączenie czynników tworzy złożoność addytywną, która jest szczególnie odporna na kolizje, nawet jeśli skalujesz ją na wielu hostach:

http://usecuid.org/

Doświadczyłem, że identyfikatory GUID nie są unikalne podczas testowania jednostek wielowątkowych / wieloprocesowych (też?). Wydaje mi się, że ma to związek z tym, że wszystkie inne parametry są równe, z identycznym wysiewem (lub brakiem wysiewu) pseudolosowych generatorów. Używałem go do generowania unikalnych nazw plików. Odkryłem, że system operacyjny jest w tym znacznie lepszy :)

Ostrzeżenie o trollowaniu

Pytasz, czy identyfikatory GUID są w 100% unikalne. To zależy od liczby identyfikatorów GUID, które muszą być unikalne. Ponieważ liczba identyfikatorów GUID zbliża się do nieskończoności, prawdopodobieństwo duplikatów identyfikatorów GUID zbliża się do 100%.

Odpowiedź „Czy identyfikator GUID jest w 100% unikalny?” to po prostu „Nie” .

• Jeśli chcesz 100% unikatowości GUID, wykonaj następujące czynności.

  1. wygeneruj GUID
  2. sprawdź, czy ten identyfikator GUID znajduje się w kolumnie tabeli, w której szukasz opcji uniquensess
  3. jeśli istnieje, to przejdź do kroku 1, a następnie do kroku 4
  4. użyj tego identyfikatora GUID jako unikalnego.

Najtrudniejsza część nie polega na generowaniu zduplikowanego Guida.

Najtrudniejszą częścią jest baza danych do przechowywania wszystkich wygenerowanych, aby sprawdzić, czy faktycznie jest zduplikowana.

Od WIKI:

Na przykład liczba losowych identyfikatorów UUID w wersji 4, które muszą zostać wygenerowane, aby prawdopodobieństwo 50% co najmniej jednego zderzenia wynosi 2,71 kwintylionów, obliczone w następujący sposób:

wprowadź opis zdjęcia tutaj

Liczba ta odpowiada wygenerowaniu 1 miliarda UUID na sekundę przez około 85 lat, a plik zawierający tak wiele UUID, przy 16 bajtach na UUID, byłby około 45 eksabajtami, wiele razy większymi niż największe obecnie istniejące bazy danych, które są na rząd setek petabajtów

GUID oznacza Global Unique Identifier

W skrócie: (wskazówka jest w nazwie)

Szczegółowo: identyfikatory GUID są zaprojektowane tak, aby były unikalne; są one obliczane za pomocą losowej metody opartej na zegarze komputera i samym komputerze, jeśli tworzysz wiele identyfikatorów GUID w tej samej milisekundie na tej samej maszynie, możliwe, że mogą się zgadzać, ale dla prawie wszystkich normalnych operacji powinny być uważane za unikalne.