Czy można polegać na wyjątkowości losowych ints?

Wdrażam protokół sieciowy i wymagam, aby pakiety miały unikalne identyfikatory. Do tej pory właśnie generowałem losowe 32-bitowe liczby całkowite i zakładając, że jest astronomicznie mało prawdopodobne, że dojdzie do kolizji w trakcie trwania programu / połączenia. Czy jest to ogólnie uważane za dopuszczalną praktykę w kodzie produkcyjnym, czy też należy opracować bardziej złożony system, aby zapobiec kolizjom?

Strzeż się paradoksu urodzinowego .

Załóżmy, że generujesz sekwencję losowych wartości (równomiernie, niezależnie) z zestawu wielkości N (w twoim przypadku N = 2 ^ 32).

Następnie ogólna zasada paradoksu urodzinowego głosi, że po wygenerowaniu około wartości sqrt (N) istnieje co najmniej 50% szansy na kolizję, to znaczy, że istnieją co najmniej dwie identyczne wartości w wygenerowana sekwencja.

Dla N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Więc po wygenerowaniu około 65k identyfikatorów, bardziej prawdopodobne jest, że dwa z nich się zderzą! Jeśli wygenerujesz identyfikator na sekundę, nastąpi to w niecały dzień; nie trzeba dodawać, że wiele protokołów sieciowych działa o wiele szybciej.

Powszechnie uważa się, że dopuszczalne jest poleganie na unikatowych liczbach losowych, jeśli liczby te mają wystarczającą liczbę bitów. Istnieją protokoły kryptograficzne, w których powtarzanie losowej liczby złamie całe bezpieczeństwo. I dopóki nie ma poważnych luk w używanym generatorze liczb losowych, nie stanowi to problemu.

Jeden z algorytmów generowania UUID skutecznie wygeneruje identyfikator składający się ze 122 losowych bitów i przyjmie, że będzie unikalny. Dwa inne algorytmy wykorzystują wartość skrótu skróconą do 122 bitów, które są unikalne, co wiąże się z mniej więcej takim samym ryzykiem kolizji.

Istnieją więc standardy polegające na tym, że 122 bity wystarczą, aby losowy identyfikator był unikalny, ale 32 bity to zdecydowanie za mało. W przypadku 32-bitowych identyfikatorów potrzeba tylko około 2 1 identyfikatora, aby ryzyko kolizji osiągnęło 50%, ponieważ w przypadku identyfikatorów 2¹ znajdzie się blisko 2 3 pary, z których każda może być kolizją.

Nawet 122 bity to mniej niż poleciłbym w każdym nowym projekcie. Jeśli przestrzeganie niektórych normalizacji jest dla Ciebie ważne, użyj identyfikatorów UUID. W przeciwnym razie użyj czegoś większego niż 122 bity.

Funkcja skrótu SHA1 z wyjściem 160 bitów nie jest już uważana za bezpieczną, co jest częściowo spowodowane tym, że 160 bitów nie wystarcza do zagwarantowania wyjątkowości wyjść. Nowoczesne funkcje skrótu mają moc wyjściową od 224 do 512 bitów. Losowo generowane identyfikatory powinny dążyć do tych samych rozmiarów, aby zapewnić wyjątkowość z dobrym marginesem bezpieczeństwa.

Nazwałbym to złą praktyką. Generatory liczb losowych po prostu nie tworzą unikalnych liczb, po prostu tworzą liczby losowe. Rozkład losowy może zawierać pewne duplikaty. Możesz sprawić, by ta okoliczność była akceptowalnie mało prawdopodobna, dodając element czasu. Jeśli aktualny czas otrzymujesz z zegara systemowego w milisekundach. Coś takiego:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Przejdzie długą drogę. Oczywiście, aby naprawdę zagwarantować unikalność, musisz użyć UUID / GUID. Ale generowanie ich może być kosztowne, powyższe jest prawdopodobnie wystarczające, ponieważ jedyną możliwością nakładania się jest to, że generowanie losowe miało duplikat w tej samej milisekundie.

Zależy to zarówno od prawdopodobieństwa awarii, jak i konsekwencji awarii.

Pamiętam debatę między programistami i osobami zajmującymi się sprzętem, w której ludzie uważali, że algorytm z małym prawdopodobieństwem błędnych wyników (coś w rodzaju 1 awarii na 100 lat) jest akceptowalny, a ludzie oprogramowania uważali, że to anatema. Okazało się, że ludzie sprzętu rutynowo obliczali oczekiwane wskaźniki awarii i byli bardzo przyzwyczajeni do pomysłu, że wszystko daje czasem błędne odpowiedzi, np. Z powodu zakłóceń spowodowanych promieniami kosmicznymi; dziwne było, że ludzie oprogramowania oczekiwali 100% niezawodności.

Pewnie, masz dość małe prawdopodobieństwo, że dwie losowe 32-bitowe liczby całkowite będą sekwencyjne, ale nie jest to całkowicie niemożliwe. Właściwa decyzja inżynierska opiera się na konsekwencjach kolizji, szacunkowej ilości generowanych liczb, czasie życia, przez który wymagana jest wyjątkowość, i co się stanie, jeśli złośliwy użytkownik zacznie powodować kolizje.

Można założyć, że liczby losowe będą unikalne, ale musisz być ostrożny.

Zakładając, że twoje liczby losowe są równomiernie rozmieszczone, prawdopodobieństwo zderzenia wynosi mniej więcej (n ^2/2 ) / k, gdzie n jest liczbą generowanych liczb losowych, a k jest liczbą możliwych wartości, które może przyjąć „losowa” liczba.

Nie stawiasz liczb na astronomicznie mało prawdopodobne, więc weźmy to jako 1 na 2 ³⁰ (mniej więcej na miliard). Powiedzmy dalej, że generujesz 2 ³⁰ pakietów (jeśli każdy pakiet reprezentuje około kilobajta danych, oznacza to około terabajta danych ogółem, dużych, ale nie niewyobrażalnie). Okazuje się, że potrzebujemy liczby losowej o co najmniej 2 ⁸⁹ możliwych wartościach.

Po pierwsze, liczby losowe muszą być wystarczająco duże. 32-bitowa liczba losowa może mieć maksymalnie 2 ³² możliwe wartości. Dla zajętego serwera, który nie jest wystarczająco wysoki.

Po drugie, generator liczb losowych musi mieć wystarczająco duży stan wewnętrzny. Jeśli generator liczb losowych ma tylko 32-bitowy stan wewnętrzny, to bez względu na to, jak duża wartość z niego wygenerujesz, nadal otrzymujesz maksymalnie 2 ³² możliwe wartości.

Po trzecie, jeśli chcesz, aby liczby losowe były unikalne dla połączeń, a nie tylko w połączeniu, Twój generator liczb losowych musi być dobrze rozstawiony. Jest to szczególnie ważne, jeśli program jest często restartowany.

Zasadniczo „zwykłe” generatory liczb losowych w językach programowania nie są odpowiednie do takiego zastosowania. Generatory liczb losowych generowane przez biblioteki kryptograficzne są na ogół.

W niektórych z powyższych odpowiedzi wbudowane jest założenie, że generator liczb losowych jest rzeczywiście „płaski” - prawdopodobieństwo, że dowolne dwie liczby zostaną wygenerowane jako następne, jest takie samo.

Prawdopodobnie nie jest to prawdą w przypadku większości generatorów liczb losowych. Większość z nich stosuje wielomian wysokiego rzędu wielokrotnie nakładany na ziarno.

To powiedziawszy, istnieje wiele systemów, które zależą od tego schematu, zwykle z UUID. Na przykład każdy obiekt i zasób w Second Life ma 128-bitowy UUID, generowany losowo i rzadko się koliduje.

Wiele osób udzieliło już wysokiej jakości odpowiedzi, ale chciałbym dodać kilka drobnych punktów: po pierwsze, argument @nomadictype na temat paradoksu urodzinowego jest doskonały .

Kolejna kwestia: przypadkowość nie jest tak prosta do wygenerowania i zdefiniowania, jak zwykli ludzie przypuszczają. (W rzeczywistości dostępne są testy statystyczne losowości ).

To powiedziawszy, ważne jest, aby zdawać sobie sprawę z błędu Hazardzisty , który jest statystycznym błędem, w którym ludzie zakładają, że niezależne zdarzenia w jakiś sposób na siebie wpływają. Zdarzenia losowe są na ogół statystycznie niezależne od siebie - tj. Jeśli losowo wygenerujesz „10”, nie zmieni to twojego przyszłego prawdopodobieństwa wygenerowania więcej „10” w najmniejszym stopniu. (Może ktoś mógłby wymyślić wyjątek od tej reguły, ale spodziewałbym się, że tak będzie w przypadku prawie wszystkich generatorów liczb losowych).

Więc moja odpowiedź jest taka, że ​​jeśli można założyć, że wystarczająco długi ciąg liczb losowych był unikalny, to tak naprawdę nie byłyby to liczby losowe, ponieważ byłby to wyraźny wzorzec statystyczny. Oznaczałoby to również, że każdy nowy numer nie jest niezależnym zdarzeniem, ponieważ jeśli wygenerujesz, na przykład 10, oznaczałoby to, że prawdopodobieństwo wygenerowania jakichkolwiek przyszłych 10 będzie wynosić 0% (nie może się zdarzyć), plus oznaczałoby to, że zwiększyłbyś szanse na uzyskanie liczby innej niż 10 (tj. im więcej liczb wygenerujesz, tym większe prawdopodobieństwo każdej z pozostałych liczb).

Jeszcze jedna rzecz do rozważenia: szansa na wygraną w Powerball w grze pojedynczej wynosi, jak rozumiem, około 1 na 175 milionów. Jednak szanse na kogoś wygraną są znacznie wyższe niż to. Jesteś bardziej zainteresowany kursem kogoś „wygranej” (tj Będąc duplikat) niż w kursie danym numerem „zwycięskiego” / będącego duplikatem.

Nie ma znaczenia, ile bitów używasz - NIE MOŻESZ zagwarantować, że dwie „losowe” liczby będą różne. Zamiast tego sugeruję, abyś użył czegoś takiego jak adres IP lub inny adres sieciowy komputera i kolejny numer, najlepiej BIG kolejny kolejny numer - 128 bitów (oczywiście niepodpisany) brzmi jak dobry początek, ale 256 byłoby lepsze.

Nie, oczywiście nie. O ile nie używasz próbek bez zamiany, istnieje szansa - nawet niewielka - na powielenie.