Czy można bezpiecznie założyć, że identyfikator GUID zawsze będzie niepowtarzalny?

123

Wiem, że istnieje niewielkie prawdopodobieństwo kolizji, ale gdybym wygenerował partię 1000 identyfikatorów GUID (na przykład), czy byłoby bezpiecznie założyć, że wszystkie są unikalne, aby zapisać testowanie każdego z nich?

Pytanie dodatkowe

Optymalny sposób testowania niepowtarzalności identyfikatora GUID? Może filtr Bloom?

math unique guid probability collision Tom Savage
źródło
2
możliwy duplikat Czy identyfikator GUID jest unikalny w 100% przypadków?
ChrisF
29
Nie, jeśli wszyscy będziemy naciskać
mipadi
12
Winię wszystkie swoje błędy w kolizjach GUID. To musi się kiedyś wydarzyć, prawda?
Michael
8
O wiele bardziej prawdopodobne jest, że rekin o uroczej, kraciastej kolorystyce spadnie z nieba i rozbije komputer na kawałki, więc uważam, że podjęcie środków ostrożności jest bardziej odpowiednią alokacją zasobów w ramach ogólnej redukcji ryzyka plan.
David Gladfelter
4
@mipadi: świetny link! Mogę sobie po prostu wyobrazić jakiegoś programistę jęczącego „Guuuuys! Przestań marnować GUID! Potrzebuję ich!”
FrustratedWithFormsDesigner

Odpowiedzi:

361

Tak, możesz. Ponieważ identyfikatory GUID mają długość 128 bitów, co prawda istnieje niewielkie prawdopodobieństwo kolizji, ale słowo „minuta” nie jest wystarczająco silne. Jest tak wiele identyfikatorów GUID, że jeśli wygenerujesz losowo kilka bilionów z nich, nadal istnieje większe prawdopodobieństwo, że uderzy Cię meteoryt, niż nawet jedno zderzenie (z Wikipedii ). A jeśli nie generujesz ich losowo, ale używasz np. Algorytmu adresu MAC i znacznika czasu, to również będą unikalne, ponieważ adresy MAC są unikalne wśród komputerów, a znaczniki czasu są unikalne na twoim komputer.

Edycja 1: Aby odpowiedzieć na pytanie dodatkowe, optymalnym sposobem przetestowania zestawu identyfikatorów GUID pod kątem niepowtarzalności jest założenie, że wszystkie są unikalne. Czemu? Ponieważ biorąc pod uwagę liczbę generowanych identyfikatorów GUID, prawdopodobieństwo kolizji GUID jest mniejsze niż prawdopodobieństwo przerzucenia promienia kosmicznego w pamięci komputera i zepsucia odpowiedzi udzielonej przez dowolny „dokładny” algorytm, który by Cię interesował biegać. (Zobacz odpowiedź StackOverflow na temat matematyki).

Istnieje ogromna liczba identyfikatorów GUID. Cytując Douglas Adams's Hitchhiker's Guide to the Galaxy :

„Przestrzeń”, mówi, „jest duża. Naprawdę duża. Po prostu nie uwierzysz, jak ogromnie i oszałamiająco duża jest. Mam na myśli, że możesz pomyśleć, że droga do chemika jest długa, ale to tylko orzeszki ziemne w kosmos , słuchać…"

A ponieważ we Wszechświecie jest około 7 × 10 22 gwiazd i nieco poniżej 2 128 GUID, to na każdą gwiazdę przypada około 4,86 ​​× 10 15 - prawie pięć biliardów - GUID. Gdyby każda z tych gwiazd miała świat z kwitnącą populacją, taką jak nasza, to wokół każdej z nich każdy człowiek lub kosmita, który kiedykolwiek żył, miałby prawo do ponad czterdziestu pięciu tysięcy identyfikatorów GUID. Dla każdej osoby w historii, każdej gwiazdy we wszechświecie. Przestrzeń GUID jest na tym samym poziomie wielkości, co rozmiar całego wszechświata. Zdajesz nie trzeba się martwić.

( Edycja 2: Zastanawiając się nad tym: wow. Nie zdawałem sobie sprawy, co to oznacza. Przestrzeń GUID jest niezrozumiała. Jestem po części pod wrażeniem.)

Antal Spector-Zabusky
źródło
1
Ponadto WolframAlpha donosi, że na każdą komórkę w każdej osobie, która kiedykolwiek żyła, przypada 36 bilionów UUID. Masz około 10^14komórek w swoim ciele i 106,5 miliarda ludzi kiedykolwiek żyło. Lub 2.385 * 10^23identyfikatory UUID dla każdego centa długu publicznego USA.
nowy123456
5
Chociaż liczby są nadal wysokie, szanse na kolizję identyfikatorów GUID przekraczają 50% przy 2 ^ 64 identyfikatorach GUID.
NullUserException
1
Przy 2 ^ 64 GUID zmniejszyłoby to liczbę do mniej niż jednego (0,00026) na gwiazdę we Wszechświecie i 2 * 10 ^ (- 15) na każdego człowieka lub kosmitę, który kiedykolwiek żył. To nadal pozwoliłoby na ponad 170 milionów identyfikatorów GUID dla każdego człowieka, który kiedykolwiek żył, więc myślę, że nadal jesteśmy dobrzy.
NullUserException
12
Warto zauważyć, że kolizja GUID jest również problemem tylko wtedy, gdy występuje w tej samej przestrzeni biznesowej. Identyfikator GUID, którego używam do identyfikacji komponentu w oprogramowaniu, może być taki sam, jak identyfikator GUID, którego używasz w wierszu bazy danych we własnej aplikacji, nie powodując żadnych problemów
James Thorpe
1
Fakt, że istnieje 2 ^ 128 GUIDS jest nieistotny i nie jesteś "nadal dobry" przy 50% szansie na kolizję, nie jesteś nawet dobry przy 0,0000001%
BlackTigerX
40

Krótka odpowiedź: ze względów praktycznych tak.

Trzeba jednak wziąć pod uwagę paradoks urodzinowy!

Obliczyłem kilka reprezentatywnych prawdopodobieństw kolizji. W przypadku 122-bitowych identyfikatorów UUID określonych w artykule z Wikipedii prawdopodobieństwo kolizji wynosi 1/2, jeśli wygenerujesz co najmniej 2.71492e18identyfikatory UUID. Przy 10 ^ 19 UUID prawdopodobieństwo wynosi 0,9999918. Z 10 ^ 17 UUID, 0,000939953.

Niektóre liczby do porównania można znaleźć w Wikipedii. Możesz więc bezpiecznie przypisać UUID każdemu człowiekowi, który żył, każdej galaktyce w obserwowalnym wszechświecie, każdej rybie w oceanie i każdej mrówce na Ziemi. Jednak zderzenia są prawie pewne, jeśli wygenerujesz UUID dla każdego tranzystora, który ludzkość wyprodukuje w ciągu roku, każdego owada na Ziemi, każdego ziarenka piasku na Ziemi, każdej gwiazdy w obserwowalnym wszechświecie lub czegokolwiek większego.

Jeśli wygenerujesz 1 miliard identyfikatorów UUID na sekundę, uzyskanie prawdopodobieństwa kolizji na poziomie 10% zajmie około 36 lat .

W końcu prawdopodobnie dojdzie do kolizji między zestawem UUID wygenerowanym w ciągu historii ludzkości. Jednak prawdopodobieństwo, że zderzone identyfikatory UUID zostaną użyte do tego samego celu, jest znikome, więc w praktyce nie ma problemu.

Ślimak mechaniczny
źródło
13
Tak kończy się wszechświat ... Niektórzy programiści po prostu zakładają, że ich identyfikatory GUID zawsze będą unikalne dla ich mega Gwiazdy Śmierci ...
pkr298
Ponieważ identyfikatory UUID są oparte na danych nielosowych, 36 lat to - musisz się tylko martwić o każdą milisekundę z osobna.
mjaggard
Identyfikatory UUID @mjaggard są oparte na losowych danych. W każdym razie każdy nowoczesny.
Trejkaz,
8

Analiza możliwości kolizji jest dostępna w Wikipedii: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Jak wspomniano w linku, będzie to miało wpływ na właściwości generatora liczb losowych.

Istnieje również możliwość błędu w kodzie generatora GUID; podczas gdy szanse są niskie, prawdopodobnie są wyższe niż szanse na kolizję oparte na matematyce.

Może być odpowiedni filtr Blooma; może szybko stwierdzić, czy identyfikator GUID jest unikalny, ale istnieje szansa na fałszywe wskazanie kolizji. Alternatywną metodą, jeśli testujesz partię na raz, jest sortowanie partii i porównywanie każdego kolejnego elementu.

Mark Okup
źródło
5

Ogólnie tak, można bezpiecznie założyć.

Jeśli twój generator GUID jest naprawdę losowy, możliwości kolizji w obrębie 1000 identyfikatorów GUID są niezwykle małe.

Oczywiście zakłada to dobry generator GUID. Tak więc pytanie dotyczy tego, jak bardzo ufasz narzędziu, którego używasz do generowania GUID, i czy ma ono własne testy?

Haacked
źródło
0

Chociaż kolizja jest możliwa, jest wysoce nieprawdopodobna. ( Tutaj matematyka ). Można bezpiecznie założyć, że w rzeczywistości są one różne.

VeeArr
źródło