Jak dobry jest identyfikator UUID.randomUUID Java?

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?

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.

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.

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ś ¹ !

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.}

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ą;)

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.

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.

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!

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

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)

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