Jak dobry jest identyfikator UUID.randomUUID Java?

311

Wiem, że randomizowane UUID mają bardzo, bardzo, bardzo małe prawdopodobieństwo kolizji w teorii, ale zastanawiam się w praktyce, jak dobra jest Java randomUUID()pod względem braku kolizji? Czy ktoś ma jakieś doświadczenie?

Alvin
źródło
10
Z mojego doświadczenia nigdy nie widziałem kolizji ;-)
Thilo
4
Algorytmy są określone w RFC1422: ietf.org/rfc/rfc4122.txt
skaffman
8
@skaffman: RFC absolutnie nic nie mówi o algorytmie używanym do generowania losowych cyfr.
Michael Borgwardt,
4
Ponieważ jest to pytanie bardziej otwarte, myślę, że nie oznaczę żadnej odpowiedzi jako poprawnej; zamiast tego dam jeden głos na każdą odpowiedź, która moim zdaniem jest dobra :)
Alvin
5
Z wikipedii: ... Innymi słowy, tylko po wygenerowaniu 1 miliarda UUID co sekundę przez następne 100 lat, prawdopodobieństwo utworzenia tylko jednego duplikatu wyniesie około 50%.
MaVRoSCy

Odpowiedzi:

168

Używa UUID java.security.SecureRandom, który ma być „kryptograficznie silny”. Chociaż rzeczywista implementacja nie jest określona i może różnić się między maszynami JVM (co oznacza, że ​​wszelkie konkretne instrukcje są ważne tylko dla jednej konkretnej maszyny JVM), nakazuje, aby dane wyjściowe musiały przejść test statystycznego generatora liczb losowych.

Implementacja zawsze zawiera subtelne błędy, które wszystko to psują (patrz błąd generowania klucza OpenSSH), ale nie sądzę, żeby istniał jakiś konkretny powód, aby martwić się o losowość UUID-ów Java.

Michael Borgwardt
źródło
34
„Implementacja może zawierać subtelne błędy ...” - Lub (zakładanie kapelusza z folii aluminiowej)… celowe subtelne wady. <:-)
Stephen C
25
Siła kryptograficzna jest całkowicie nieistotna w przypadku kolizji.
osa
14
@osa: Brak wywoływania kolizji (więcej niż można się spodziewać po doskonałej losowości) jest właściwie najniższym wymogiem jakości dla RNG, podczas gdy siła kryptograficzna jest najwyższa. Innymi słowy, kryptograficznie silny RNG z całą pewnością nie spowoduje więcej kolizji niż oczekiwano.
Michael Borgwardt
3
Warto jednak zauważyć, że jeśli np. Uruchomisz JVM wyrzucającą UUID w blogs.vmware.com/cto/… , prawdopodobnie spotkasz wiele kolizji. Wszystkie oprogramowanie RNG są PRNG i ostatecznie są tak dobre, jak ich źródło entropii; dwa PRNG, które zostaną zaszczepione identycznie, będą również zachowywać się identycznie, co może się zdarzyć zaskakująco często przy spójnych, dokładnie zduplikowanych konfiguracjach serwera i procedurach uruchamiania.
user508633
@ user508633: Właściwie spodziewałbym się 100% współczynnika kolizji w tym konkretnym przypadku, ale jest to bardzo konkretny przypadek, który wykracza daleko poza „spójne, dokładne duplikowanie ustawień serwera i procedur uruchamiania”. Jestem prawie pewien, że nie uzyskasz żadnych zwiększonych współczynników kolizji, jeśli po prostu sklonujesz maszynę wirtualną i uruchomisz ją normalnie. Samosiewanie SecureRandom bardzo mocno próbuje uzyskać prawdziwą entropię, do tego stopnia, że ​​blokuje wykonanie, jeśli nie może jej znaleźć: seancassidy.me/wiggle-the-mouse-to-fix-the-test.html
Michael Borgwardt,
114

Wikipedia ma bardzo dobrą odpowiedź http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

liczba losowych 4 identyfikatorów UUID, które muszą zostać wygenerowane w celu uzyskania 50% prawdopodobieństwa co najmniej jednego zderzenia, wynosi 2,71 kwintilliona, obliczonego w następujący sposób:

...

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.

...

Zatem, aby istniała jedna szansa na miliard duplikacji, należy wygenerować 103 bilionów UUID wersji 4.

sheki
źródło
56
Cytuję również z tej strony: „Prawdopodobieństwo jednego duplikatu wynosiłoby około 50%, gdyby każda osoba na ziemi posiadała 600 milionów UUID”.
Jeff Axelrod
24
Dotyczy to tylko prawdziwej losowości, a nie liczb pseudolosowych, takich jak UUID javascript.
Markus
9
@Markus: całkowicie źle. Prawdopodobieństwo kolizji dla dobrych pseudolosowych RNG, szczególnie silnych kryptograficznie, nie różni się od „prawdziwej” losowości.
Michael Borgwardt,
6
@Eric - Myślę, że na tobie spoczywa obowiązek uzupełnienia twojego twierdzenia. FWIW, jedyne możliwe scenariusze, w których UUID typu 4 kolidowałyby częściej niż teoria prawdopodobieństwa mówi, że powinny to być: 1) złe źródło liczb losowych w krypto lub 2) biblioteka UUID, która została naruszona.
Stephen C,
13
To nie odpowiada na zadane pytanie. Pytanie dotyczy jakości losowości w Javie UUID.randomUUID(), a nie teoretycznych szans na dany idealny generator liczb losowych.
kratenko
69

Czy ktoś ma jakieś doświadczenie?

Możliwe są 2^122wartości dla UUID typu 4. (Specyfikacja mówi, że tracisz 2 bity dla typu i kolejne 4 bity dla numeru wersji).

Zakładając, że miałbyś wygenerować 1 milion losowych UUID na sekundę, szanse na zduplikowanie w twoim życiu byłyby znikomo małe. Aby wykryć duplikat, musisz rozwiązać problem porównywania 1 miliona nowych UUID na sekundę ze wszystkimi UUID, które wcześniej wygenerowałeś 1 !

Szanse, że ktokolwiek doświadczył (tj. Rzeczywiście zauważył ) duplikat w prawdziwym życiu, są jeszcze mniejsze niż znikające ... ze względu na praktyczną trudność w poszukiwaniu kolizji.

Teraz zwykle będziesz używać generatora liczb pseudolosowych, a nie źródła liczb naprawdę losowych. Ale myślę, że możemy być pewni, że jeśli używasz wiarygodnego dostawcy losowych liczb siły kryptograficznej, to będzie to siła kryptograficzna, a prawdopodobieństwo powtórzeń będzie takie samo, jak dla idealnego (nie stronniczego) generatora liczb losowych .

Jeśli jednak użyjesz JVM z „zepsutym” krypto-losowym generatorem liczb, wszystkie zakłady są wyłączone. (I może to obejmować niektóre obejścia problemów związanych z „brakiem entropii” w niektórych systemach. Lub możliwość, że ktoś majstrował przy twoim JRE, albo w twoim systemie, albo w górę).


1 - Zakładając, że użyłeś „jakiegoś binarnego drzewa binarnego”, jak zaproponował anonimowy komentator, każdy UUID będzie potrzebował O(NlogN)bitów pamięci RAM do reprezentowania Nróżnych UUID przy założeniu niskiej gęstości i losowego rozkładu bitów. Teraz pomnóż to przez 1 000 000 i liczbę sekund, przez które zamierzasz przeprowadzić eksperyment. Nie sądzę, aby było to praktyczne ze względu na czas potrzebny do testowania kolizji wysokiej jakości RNG. Nawet przy (hipotetycznych) sprytnych przedstawieniach.

Stephen C.
źródło
4
„(Aby wykryć duplikat, musiałbyś rozwiązać problem porównywania 1 miliona nowych UUID na sekundę ze wszystkimi UUID, które wcześniej wygenerowałeś!)” - ta część jest stosunkowo prosta, zakładając, że przechowałeś swoje UUID w niektórych rodzaj binarnej struktury drzewa, byłoby to tylko jedno zejście drzewa na nowego użytkownika. Nie trzeba porównywać go indywidualnie ze wszystkimi wcześniej wygenerowanymi identyfikatorami.
user467257
20

Nie jestem ekspertem, ale zakładam, że dość inteligentnych ludzi patrzyło na generator liczb losowych Java na przestrzeni lat. Dlatego też zakładam, że losowe UUID są dobre. Więc powinieneś naprawdę mieć teoretyczne prawdopodobieństwo kolizji (które wynosi około 1: 3 × 10 ^ 38 dla wszystkich możliwych UUID. Czy ktoś wie, jak to się zmienia tylko dla losowych UUID? Czy to 1/(16*4)z powyższego?)

Z praktycznego doświadczenia nigdy nie widziałem żadnych kolizji. Prawdopodobnie wyrośnie mi zadziwiająco długa broda w dniu, w którym otrzymam swoją pierwszą;)

sfussenegger
źródło
10
Z wikipedii: ... Innymi słowy, tylko po wygenerowaniu 1 miliarda UUID co sekundę przez następne 100 lat, prawdopodobieństwo utworzenia tylko jednego duplikatu wyniesie około 50%.
MaVRoSCy
1
W rzeczywistości wikipedia mówi, że będzie to przez następne 85 lat ... Mówię, że nie licz na to, że ktoś gdzieś wygenerował ten sam UUID co ty
smac89
12

U byłego pracodawcy mieliśmy unikalną kolumnę zawierającą losowy numer UUID. Mamy kolizję w pierwszym tygodniu po jej wdrożeniu. Jasne, szanse są niskie, ale nie są zerowe. Właśnie dlatego Log4j 2 zawiera UuidUtil.getTimeBasedUuid. Wygeneruje identyfikator UUID, który jest unikalny przez 8925 lat, o ile nie wygenerujesz więcej niż 10 000 UUID / milisekundę na jednym serwerze.

rgoers
źródło
2
Tak. Ale pytanie dotyczy losowych UUID typu 4.
Stephen C,
1
Pytanie dotyczy prawdopodobieństwa zderzenia. Sugeruje to, że chce być pewien, że ich uniknie.
rgoers,
1
(Kolizja była najprawdopodobniej spowodowana zepsutym źródłem losowości podczas wysiewu PRNG. Pomyślałem, że możliwe, że było to spowodowane czystym przypadkiem.)
Stephen C
9

Pierwotny schemat generowania UUID polegał na połączeniu wersji UUID z adresem MAC komputera, który generuje UUID, oraz liczbą interwałów 100 nanosekund od przyjęcia kalendarza gregoriańskiego na Zachodzie. Reprezentując pojedynczy punkt w przestrzeni (komputer) i czas (liczbę interwałów), prawdopodobieństwo zderzenia wartości jest praktycznie zerowe.

Alex2Ustas
źródło
1
To wyjaśnienie sprawia, że ​​optymistycznie nie widzę kolizji w praktyce. Czy możesz wskazać odniesienie do tej instrukcji (niektóre kody źródłowe byłyby jeszcze lepsze)?
Dragan Marjanović
Znalazłem to w specyfikacji ietf.org/rfc/rfc4122.txt . Niemniej jednak byłoby wspaniale zobaczyć wdrożenie.
Dragan Marjanović
1
Jednak ten schemat nie jest tym, co implementuje Java. Java implementuje UUID typu 4, który jest całkowicie losowy i nie zawiera adresu MAC ani czasu. Nawiasem mówiąc, ponieważ istnieje obecnie wiele fizycznych i wirtualnych urządzeń, w których można wybrać adres MAC, oryginalny algorytm nie gwarantuje unikalności.
Søren Boisen
8

Wiele odpowiedzi mówi o tym, ile UUID musiałoby zostać wygenerowanych, aby osiągnąć 50% szansy na kolizję. Ale 50%, 25%, a nawet 1% szansa na kolizję jest bezwartościowa w przypadku aplikacji, w której kolizja musi być (praktycznie) niemożliwa.

Czy programiści rutynowo odrzucają jako „niemożliwe” inne zdarzenia, które mogą się zdarzyć?

Kiedy zapisujemy dane na dysk lub pamięć i odczytujemy je ponownie, przyjmujemy za pewnik, że dane są poprawne. Korzystamy z korekcji błędów urządzenia, aby wykryć wszelkie uszkodzenia. Ale szansa na niewykrycie błędów wynosi około 2–50 .

Czy nie ma sensu stosowanie podobnego standardu do losowych UUID? Jeśli to zrobisz, przekonasz się, że możliwa jest „niemożliwa” kolizja w zbiorze około 100 miliardów losowych UUID (2 36,5 ).

Jest to liczba astronomiczna, ale aplikacje takie jak wyliczanie szczegółowych rachunków w krajowym systemie opieki zdrowotnej lub rejestrowanie danych z czujników wysokiej częstotliwości na wielu urządzeniach może zdecydowanie przekroczyć te limity. Jeśli piszesz kolejny Przewodnik Autostopowicza po Galaktyce, nie próbuj przypisywać UUID do każdego artykułu!

erickson
źródło
Dla porównania, szansa na wygranie jackpota Powerball wynosi 1 na 300 milionów, ale sprzedaż od 10 do 20 milionów biletów jest typowa. Chodzi o to, że wiele osób definiuje „niemożliwe” jako coś mniej niż jedną szansę na setki milionów.
erickson,
4

Ponieważ większość odpowiedzi skupiała się na teorii, myślę, że mogę coś dodać do dyskusji, wykonując test praktyczny. W mojej bazie danych mam wygenerowanych około 4,5 miliona UUID przy użyciu Java 8 UUID.randomUUID (). Oto niektóre z nich:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb


b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64


4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

Gdyby to było naprawdę losowe, prawdopodobieństwo posiadania tego rodzaju podobnych UUID byłoby znacznie niskie (patrz edycja), ponieważ rozważamy tylko 4,5 miliona wpisów. Tak więc, chociaż ta funkcja jest dobra pod względem braku kolizji, dla mnie nie wydaje się tak dobra, jak mogłaby być w teorii.

Edytuj :

Wydaje się, że wiele osób nie rozumie tej odpowiedzi, więc wyjaśnię swój punkt widzenia: wiem, że podobieństwa są „małe” i dalekie od pełnego zderzenia. Chciałem jednak porównać UUID.randomUUID () z Javą z prawdziwym generatorem liczb losowych, co jest właściwym pytaniem.

W prawdziwym generatorze liczb losowych prawdopodobieństwo wystąpienia ostatniego przypadku wyniesie około 0,007%. Dlatego myślę, że moje wnioski są słuszne.

Formuła została wyjaśniona w tym artykule wiki en.wikipedia.org/wiki/Birthday_problem

André Pinheiro
źródło
6
To nie jest prawda. Tego rodzaju podobieństwa powstałyby nawet przy prawdziwym generatorze liczb losowych na 4,5 milionach płynów. Podobieństwa między podanymi przez Ciebie identyfikatorami UUID są małe i dalekie, och, jak dotąd, od pełnego zderzenia.
user3711864,
Całkowicie się z tobą zgadzam, że podobieństwa są „małe” i dalekie od pełnego zderzenia. Chciałem jednak porównać UUID.randomUUID Javy () z prawdziwym generatorem liczb losowych (oto pytanie). Z niektórych obliczeń wynika, że ​​w prawdziwym generatorze liczb losowych prawdopodobieństwo wystąpienia ostatniego przypadku wyniesie około 1-e ^ (- 4500000 ^ 2 / (2 * 36 ^ 11)) = 0,007% = 1 w 13 tys. Musiałbym mieć dużo szczęścia :)
André Pinheiro,
1
Z 4,5 milionami przedmiotów i szansą 1 na 13 tysięcy, czy częściowa kolizja nie byłaby oczekiwana 346 razy?
Ben Lee
Nie @BenLee, obliczyłem prawdopodobieństwo wystąpienia tego zdarzenia, biorąc pod uwagę, że mamy 4,5 miliona pozycji. Dla każdego przedmiotu nie jest to szansa 1 na 13 tys. Wzór, którego użyłem, można znaleźć w tym artykule wiki en.wikipedia.org/wiki/Birthday_problem
André Pinheiro
2
Jakie były twoje oczekiwania? Podobne to nie to samo, prawda?
Koray Tugay
3

Gram w loterii w zeszłym roku i nigdy nie wygrałem ... ale wygląda na to, że w loterii są zwycięzcy ...

doc: http://tools.ietf.org/html/rfc4122

Typ 1: nie zaimplementowano. kolizje są możliwe, jeśli identyfikator UUID jest generowany w tym samym momencie. impl może być sztucznie synchronizowany w celu ominięcia tego problemu.

Typ 2: nigdy nie zobacz implementacji.

Typ 3: skrót md5: możliwa kolizja (128 bitów-2 bajty techniczne)

Typ 4: losowy: możliwa kolizja (jako loteria). zauważ, że jdk6 impl nie używa „prawdziwej” bezpiecznej losowości, ponieważ algorytm PRNG nie jest wybierany przez programistę i możesz zmusić system do używania „słabej” algi PRNG. Twój UUID jest przewidywalny.

Typ 5: skrót sha1: nie zaimplementowano: możliwa kolizja (160 bitów technicznych 2 bajty)

Giher
źródło
4
Prawdopodobieństwo wygranej w loterii wynosi może jeden na 10 lub 100 milionów (10 ^ 7 lub 10 ^ 8) lub coś takiego. Prawdopodobieństwo kolizji ze 128-bitową liczbą losową wynosi 3,4 * 10 ^ 28. Daj mi los na loterię w dowolnym momencie!
Stephen C
0

Używamy losowego UUID Javy w naszej aplikacji od ponad roku i to bardzo szeroko. Ale nigdy nie spotykamy się z kolizją.

Afsar
źródło