Czy GUID jest unikalny w 100% przypadków?
Czy pozostanie wyjątkowy w wielu wątkach?
language-agnostic
guid
David Basarab
źródło
źródło
Odpowiedzi:
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
źródło
2^128
wypisywane jest w przybliżeniu:34,028,236,692,093,846,346,337,460,743,177,000,000
. Statystycznie, jeśli obliczysz 1000 identyfikatorów GUID na sekundę, uzyskanie duplikatu zajęłoby tryliony lat.Jeśli boisz się tych samych wartości GUID, umieść dwie z nich obok siebie.
Jeśli jesteś zbyt paranoikiem, postaw trzy.
źródło
999999999
w twojej formie, myślę, że Paranoia podzieli moją przeglądarkę.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ą :-)
źródło
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.
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.
źródło
msiexec
, wyświetli on wszystkie identyfikatory GUI MSI programu pakietu Office. Wszyscy się przeliterowali0FF1CE
. Wygląda na to, że Microsoft ma dość ... luźną ... interpretację sposobu generowania identyfikatora GUID;)0FF1CE
identyfikatory GUID są objęte sekcją RFC-4122 „Kompatybilność wsteczna NCS”, ale jest mało prawdopodobne, aby Microsoft przestrzegał reguł NCS dla tych wartości.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.
źródło
Guid.NewGuid
zawsze generuje GUID v4 (i zawsze ma). Tim musiał mieć bardzo słabe źródła entropii.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
źródło
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?
źródło
Eric Lippert napisał bardzo interesującą serię artykułów na temat GUID.
źródło
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:
źródło
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
n
typach wynosi:Ponieważ 2 128 jest znacznie większy niż
n
, możemy to przybliżyć do:A ponieważ możemy założyć, że
n
jest znacznie większy niż 0, możemy to przybliżyć do:Teraz możemy zrównać to z „akceptowalnym” prawdopodobieństwem, powiedzmy 1%:
Które rozwiązujemy
n
i uzyskujemy:Który Wolfram Alpha ma być 5.598318 × 10 19
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.
źródło
Od http://www.guidgenerator.com/online-guid-generator.aspx
źródło
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ę:
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).
źródło
MSDN :
źródło
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.
źródło
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 128 odrębnych identyfikatorów GUID - znacznie więcej niż gwiazdy w znanym wszechświecie. Przeczytaj artykuł w Wikipedii, aby uzyskać więcej informacji.
źródło
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.
źródło
Aby uzyskać lepszy wynik, najlepszym sposobem jest dodanie identyfikatora GUID do znacznika czasu (aby upewnić się, że pozostaje unikalny)
źródło
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/
źródło
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%.
źródło
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.
źródło
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
źródło
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.
źródło