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

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?

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 ²² gwiazd i nieco poniżej 2 ¹²⁸ GUID, to na każdą gwiazdę przypada około 4,86 ​​× 10 ¹⁵ - 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.)

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.

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.

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?

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

Zwykle jest to dość bezpieczne założenie.

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Czy identyfikator GUID jest unikalny w 100% przypadków?