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

42

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?

Feniks
źródło
47
Dlaczego użycie liczb całkowitych sekwencyjnych nie zamierza tego wyciąć?
whatsisname
20
Dlaczego po prostu nie użyjesz inkrementacji int? Identyfikatory GUID , które zostały zaprojektowane tak, aby opisywać właściwości unikatowości, mają rozmiar 128 bitów, a nie 32.
Robert Harvey
21
Alternatywnie przypisz numer kanału do każdego podłączonego komputera i użyj identyfikatora sekwencji inkrementacji. Dwie liczby połączone (z numerem kanału zajmującym bity wysokiego rzędu) stają się twoim nowym unikalnym identyfikatorem.
Robert Harvey
27
Jeśli Twój „generator liczb losowych” gwarantuje, że określona liczba nie będzie powtarzana, dopóki nie zostanie wygenerowana każda inna liczba, jest to bardzo słaby generator liczb losowych! Zgodnie z tą samą logiką, jedyną możliwą „losową” sekwencją rzutów monetą będzie HTHTHTHTHT ....
alephzero,
17
„Wymagam, aby pakiety miały unikalne identyfikatory”. Jaka jest konsekwencja naruszenia tego wymogu? Jeśli potrzebujesz unikalnych identyfikatorów, w najściślejszym czytaniu tego słowa, musisz mieć scentralizowany system wykrywający identyfikatory (takie jak sposób przypisywania adresów MAC poszczególnym firmom obsługującym karty sieciowe). Najprawdopodobniej masz bardziej miękką definicję „wymagaj”. Zrozumienie tego poziomu miękkości radykalnie zmieni otrzymywane odpowiedzi.
Cort Ammon

Odpowiedzi:

142

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.

koczownik
źródło
11
+1. W mojej ostatniej pracy jeden z naszych partnerów faktycznie zastosował to podejście do generowania losowych identyfikatorów (nie dla pakietów sieciowych, ale dla wspólnego obiektu biznesowego ostatecznie utworzonego przez klientów końcowych). Kiedy zapytałem o dane, zwracając uwagę na to, stwierdziłem, że średnio były dwie lub trzy pary duplikatów każdego dnia. (Na szczęście wszystko to zepsuło się tylko wtedy, gdy duplikaty powstały w ciągu czterech godzin od siebie, co zdarzało się nieco rzadziej. Ale mimo to.)
ruakh
6
(kliknij tutaj, aby renderować matematykę) Przybliżenie wartości $ \ sqrt {N} $ jest dokładne z zachowaniem stałego współczynnika; dla $ N = 2 ^ {32} $ rzeczywisty próg wynosi 77164, ponieważ jest to najmniejsza wartość $ n $ taka, że ​​$ \ prod_ {k = 1} ^ {n-1} (1 - k / N) <1 / 2. $
wchargin
4
@wchargin: Nie ma nic magicznego w prawdopodobieństwie trafienia 0,5; godne uwagi jest to, że prawdopodobieństwo rośnie stosunkowo szybko wraz ze wzrostem N. Jeśli 32-bitowe identyfikatory miałyby niewielką, ale nietrywialną szansę na losową kolizję, 40-bitowy identyfikator nie miałby prawie żadnego.
supercat
3
@ superupat: To wszystko prawda. Właśnie pomyślałem, że jeśli zapewni się taką stałą, równie dobrze można podać dokładną wartość :-)
wchargin
2
@wchargin: Wolę myśleć w kategoriach, gdzie trzeba zacząć martwić się duplikatami. Jeśli ktoś zejdzie znacznie poniżej sqrt (N), prawdopodobieństwo kolizji gwałtownie spada, do tego stopnia, że ​​można śmiało powiedzieć, że się nie zdarzy, chyba że wystąpi poważna wada generatora losowego.
supercat
12

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.

kasperd
źródło
12
SHA-1 jest uważany za niebezpieczny, ponieważ istnieją określone ataki (tj. Nielosowe) przeciwko samemu algorytmowi, które mogą znajdować kolizje szybciej niż brutalna siła, nie dlatego, że istnieje duża szansa na kolizję losową. Z grubsza szacuje się, że przy 122 bitach i szybkości generowania 1 miliarda (10 ^ 9) identyfikatorów na sekundę zajęłoby to 73 lata, zanim osiągnięto 50% szansy na kolizję.
8bittree
sqrt(2^122)= 2,3
biliarda biliarda
2
@ 8bittree Sieć bitcoin oblicza 2 ⁷⁰ SHA2 co 10 minut. Gdyby to były skróty SHA1, wywołanie kolizji zajęłoby tydzień. Jeśli UUID zostałyby wyprodukowane z taką samą prędkością, jak bitcoin oblicza hasze, wygenerowanie kolizji zajęłoby mniej niż 2 sekundy.
kasperd
Bitcoin polega na próbach znalezienia kolizji i jest niezwykle popularny i ma dedykowany sprzęt zaprojektowany specjalnie do wyszukiwania skrótów. Oczywiście, jeśli OP planuje stworzyć niezwykle popularną kryptowalutę lub coś podobnego, mogą potrzebować setek lub tysięcy bitów na identyfikator. Ale natychmiastowe założenie, że są to wymagania, może zachęcać do znacznie więcej pracy niż to konieczne, jeśli standardowa biblioteka UUID jest wystarczająca.
8bittree
@ 8bittree Jeśli korzystanie ze standardowych bibliotek jest zaletą, to zdecydowanie skorzystaj z UUID. Ale wyciągnięcie losowych bajtów urandomnie jest więcej pracy niż użycie biblioteki UUID. Właśnie zaimplementowałem oba w Pythonie dla porównania, a każda metoda miała dokładnie 25 znaków kodu źródłowego.
kasperd
3

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.

Fresheyeball
źródło
9
W niektórych systemach czas 1ms może być długi.
quant_dev
7
To wcale nie zmniejsza szansy na kolizję. Prawdopodobieństwo kolizji po liczbach N jest dokładnie równe oryginalnemu rozwiązaniu OP. Sztuczka polegająca na wykorzystaniu bieżącej godziny jako zarodka jest zwykle stosowana przy sekwencyjnym przypisywaniu kluczy.
Cort Ammon
2
@Fresheyeball Jestem pewien, że nie ma to żadnego wpływu, chyba że Random.makeInt () nie generuje w rzeczywistości równomiernego rozkładu od minimalnej wartości liczby całkowitej do maksymalnej wartości liczby całkowitej. Dla każdej przeszłej wartości generowanej przez tę funkcję istnieje losowa wartość z makeInt, która dla tego dokładnego kroku czasowego generuje tę wartość, tworząc kolizję. Ponieważ wszystkie wartości z makeInt są możliwe do sprawdzenia, prawdopodobieństwo kolizji jest dokładnie równe prawdopodobieństwu kolizji bez dodania czasu.
Cort Ammon
2
@CortAmmon nie korzysta z bieżącego czasu jako zarodka i na pewno robi różnicę, o ile te wszystkie liczby N nie zostały wygenerowane w ciągu tej samej milisekundy, ponieważ dwie liczby z różnymi częściami znaczników czasu nigdy się nie kolidują. Jeśli wyobrażasz sobie przykład z inną odpowiedzią, że jeden pakiet na sekundę ma 50% szansy na kolizję w mniej niż jeden dzień, ta ma 0% szansy na kolizję z jednym pakietem na sekundę, przynajmniej do czasu, który się currentTimeMilliskończy.
hobbs
3
@ Hobbs Zapomniałeś o przepełnieniu liczb całkowitych. Teraz, jeśli kluczem użytym przez OP była struktura zawierająca 2 liczby całkowite, jedną zawierającą System.currentTimeMillisi jedną zawierającą Random.makeInt(), wówczas prawdopodobieństwo kolizji znacznie spada. Jednak nie to robi kod w tym przykładzie. Biorąc pod uwagę każdą poprzednią czas i wartość losową i żadnego aktualnego czasu, prawdopodobieństwo kolizji jest identyczna z prawdopodobieństwem dwóch liczb losowych zderzających się w pierwszej kolejności.
Cort Ammon
3

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.

Michael Kay
źródło
1

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.

Sean McSomething
źródło
0

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 30 (mniej więcej na miliard). Powiedzmy dalej, że generujesz 2 30 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 89 możliwych wartościach.

Po pierwsze, liczby losowe muszą być wystarczająco duże. 32-bitowa liczba losowa może mieć maksymalnie 2 32 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 32 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ół.

Peter Green
źródło
0

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.

Anniepoo
źródło
0

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.

EJoshuaS - Przywróć Monikę
źródło
Jeśli jeden generuje 4096-bitowy identyfikator w taki sposób, że każdy bit prawdopodobnie będzie równy 0 lub 1 niezależnie od dowolnego innego bitu, który został wygenerowany w tym samym lub innym identyfikatorze, prawdopodobieństwo, że jakiekolwiek dwa identyfikatory kiedykolwiek pasują być znikomo małe, nawet gdyby losowo wygenerować inny identyfikator dla każdego z około 4,0E81 atomów w obserwowalnym wszechświecie. Fakt, że takie identyfikatory byłyby prawie na pewno unikalne, w żaden sposób nie czyni ich „nieprzypadkowymi”
supercat
@ superuper To prawda - biorąc pod uwagę wystarczająco dużą liczbę, jest bardzo mało prawdopodobne, że pojawią się duplikaty, ale nie jest to niemożliwe. Naprawdę zależy od tego, jak złe są konsekwencje niejednoznaczności, czy to, co OP opisuje, jest dobrym pomysłem.
EJoshuaS - Przywróć Monikę
Jeśli prawdopodobieństwo przypadkowej kolizji losowej jest mniejsze niż prawdopodobieństwo, że uderzenie meteoru zniszczy urządzenia oparte na unikalnych identyfikatorach, z punktu widzenia inżynierii nie trzeba się martwić o te pierwsze. Konieczna byłaby obawa o wszystko, co mogłoby spowodować, że losowe liczby nie byłyby niezależne, ale przypadkowe kolizje nie byłyby problemem.
supercat
@ supercat Myślę, że źle to interpretujesz, zobacz inną odpowiedź na temat paradoksu urodzinowego, myślę, że kolizja jest znacznie bardziej prawdopodobna niż się spodziewasz - PO używa tylko 32-bitowej liczby, więc nie jestem pewien, gdzie jesteś ponownie otrzymuję 4096, i jak pokazał typ nomadów, prawdopodobieństwo ostatecznego zderzenia z liczbą o tej długości jest w rzeczywistości zaskakująco wysokie.
EJoshuaS - Przywróć Monikę
Masz rację, że liczba 32-bitowa jest zbyt krótka, nawet dla małych populacji, jeśli kolizje są całkowicie niedopuszczalne. Jeśli użyje się liczby, która jest wystarczająco duża, można zmniejszyć prawdopodobieństwo przypadkowych kolizji do punktu, w którym można bezpiecznie założyć, że po prostu się nie zdarzy, aw wielu przypadkach użycie większej liczby może być lepsze niż próba użycia innych środków zapewniając wyjątkowość, ponieważ ta ostatnia na ogół wymaga dostępu do przejść stanu, których nie można cofnąć ani przywrócić, nawet jeśli zegar systemu zostanie zresetowany lub system zostanie ponownie załadowany z kopii zapasowej.
supercat
0

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.

Bob Jarvis
źródło
-1

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

Dr Drew
źródło