Czy możliwe są kolizje GUID?

Pracuję nad bazą danych w SQL Server 2000, która używa identyfikatora GUID dla każdego użytkownika używającego aplikacji, z którą jest powiązana. W jakiś sposób dwóch użytkowników otrzymało ten sam identyfikator GUID. Wiem, że firma Microsoft używa algorytmu do generowania losowego identyfikatora GUID, który ma bardzo małe prawdopodobieństwo spowodowania kolizji, ale czy kolizja jest nadal możliwa?

Zasadniczo nie. Myślę, że ktoś majstrował przy twojej bazie danych. W zależności od używanego identyfikatora GUID wersji wartość jest albo unikalna (w przypadku identyfikatorów GUID wersji 1), albo jednocześnie unikalna i nieprzewidywalna (w przypadku identyfikatorów GUID w wersji 4). Wydaje się, że implementacja SQL Server dla ich funkcji NEWID () używa 128-bitowej liczby losowej, więc nie dojdzie do kolizji.

Aby uzyskać 1% szans na kolizję, musisz wygenerować około 2 600 000 000 000 000 000 identyfikatorów GUID.

Zasadniczo nie są one możliwe! , szanse są astronomicznie niskie .

Ale ... Jestem jedyną osobą na świecie, którą znam, która kiedyś miała kolizję GUID (tak!).

Jestem tego pewien i że to nie był błąd.

Jak to się stało, że w małej aplikacji działającej na Pocket PC pod koniec operacji należy wydać polecenie, które ma wygenerowany identyfikator GUID. Polecenie po wykonaniu na serwerze było przechowywane w tabeli poleceń na serwerze wraz z datą wykonania. Pewnego dnia, kiedy debugowałem, wydałem polecenie modułu (z dołączonym nowo wygenerowanym identyfikatorem GUID) i nic się nie stało. Zrobiłem to ponownie (z tym samym guid, bo guid był generowany tylko raz na początku operacji) i znowu i nic, w końcu próbując dowiedzieć się, dlaczego polecenie się nie wykonuje, sprawdziłem tabelę poleceń, i ten sam identyfikator GUID, co obecny, został wstawiony 3 tygodnie temu. Nie wierząc w to, przywróciłem bazę danych z kopii zapasowej z 2 tygodni, a guid tam był. Sprawdziłem kod, nowy guid został świeżo wygenerowany, nie ma co do tego wątpliwości.

Edycja: istnieje kilka czynników, które mogły znacznie zwiększyć szansę na to, aplikacja działała na emulatorze PocketPC, a emulator ma funkcję zapisywania stanu, co oznacza, że ​​za każdym razem, gdy przywracany jest stan, przywracany jest również czas lokalny a guid jest oparty na wewnętrznym zegarze ... również algorytm generowania guidów dla kompaktowej struktury może być mniej kompletny niż na przykład COM ...

Teoretycznie są możliwe, ale przy 3.4E38 możliwych liczbach, jeśli utworzysz dziesiątki bilionów identyfikatorów GUID w ciągu roku, szansa na jeden duplikat wynosi 0,00000000006 ( źródło ).

Gdyby dwóch użytkowników miało ten sam identyfikator GUID, założyłbym się, że w programie jest błąd, który powoduje kopiowanie lub udostępnianie danych.

Najpierw spójrzmy na możliwość kolizji dwóch identyfikatorów GUID. Nie jest to, jak stwierdziły inne odpowiedzi, 1 na 2 ^ 128 (10 ^ 38) z powodu paradoksu urodzinowego , co oznacza, że ​​dla 50% szans na zderzenie dwóch identyfikatorów GUID prawdopodobieństwo wynosi w rzeczywistości 1 do 2 ^ 64 (10 ^ 19), który jest dużo mniejszy. Jednak jest to nadal bardzo duża liczba, dlatego prawdopodobieństwo kolizji przy założeniu, że używasz rozsądnej liczby identyfikatorów GUID, jest niskie.

Należy również zauważyć, że identyfikatory GUID nie zawierają sygnatury czasowej ani adresu MAC, jak wielu ludzi również uważa. Tak było w przypadku identyfikatorów GUID v1, ale teraz używane są identyfikatory GUID v4, które są po prostu liczbami pseudolosowymi, co oznacza, że ​​prawdopodobieństwo kolizji jest prawdopodobnie większe, ponieważ nie są już unikalne dla czasu i maszyny.

Tak więc zasadniczo odpowiedź brzmi: tak, kolizje są możliwe. Ale są bardzo mało prawdopodobne.

Edycja: naprawiono na 2 ^ 64

Szanse na kolizję dwóch losowych identyfikatorów GUID (~ 1 na 10 ^ 38) są mniejsze niż prawdopodobieństwo niewykrycia uszkodzonego pakietu TCP / IP (~ 1 na 10 ^ 10). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf , strona 11. Dotyczy to również napędów dyskowych, napędów CD itp.

Identyfikatory GUID są statystycznie unikalne, a dane odczytywane z bazy danych są tylko statystycznie poprawne.

Uważam brzytwę Ockhama jako przewodnik dobre w tym przypadku. Jest niezwykle mało prawdopodobne, że wystąpi kolizja identyfikatora GUID. O wiele bardziej prawdopodobne jest, że masz błąd lub ktoś manipuluje Twoimi danymi.

Zobacz artykuł Wikipedii o unikalnych globalnych identyfikatorach . Istnieje kilka sposobów generowania identyfikatorów GUID. Najwyraźniej stary (?) Sposób używał adresu Mac, znacznika czasu do bardzo krótkiej jednostki i unikalnego licznika (do zarządzania szybkimi generacjami na tym samym komputerze), więc ich duplikowanie jest prawie niemożliwe. Ale te identyfikatory GUID zostały usunięte, ponieważ można ich użyć do śledzenia użytkowników ...

Nie jestem pewien nowego algorytmu używanego przez Microsoft (artykuł mówi, że można przewidzieć sekwencję identyfikatorów GUID, wygląda na to, że nie używają już sygnatury czasowej? W artykule Microsoftu, do którego link znajduje się powyżej, jest coś innego ...).

Teraz identyfikatory GUID są starannie zaprojektowane, aby z nazwy były unikalne w skali globalnej, więc zaryzykuję, że jest to niemożliwe lub o bardzo bardzo niskim prawdopodobieństwie. Szukałbym gdzie indziej.

Dwie maszyny Win95, które mają karty Ethernet ze zduplikowanymi adresami MAC, będą wystawiać zduplikowane GUIDS w ściśle kontrolowanych warunkach, zwłaszcza jeśli, na przykład, w budynku wyłączy się zasilanie i obie uruchamiają się dokładnie w tym samym czasie.

Przedmówię to słowami: „Nie jestem osobą sieciującą, więc mogę tworzyć zupełnie niespójne zdania”.

Kiedy pracowałem na Illinois State University, mieliśmy dwa komputery stacjonarne Dell, zamawiane w różnym czasie. Pierwszą umieściliśmy w sieci, ale gdy próbowaliśmy umieścić drugą w sieci, zaczęły pojawiać się szalone błędy. Po wielu czynnościach związanych z rozwiązywaniem problemów ustalono, że obie maszyny wytwarzają ten sam identyfikator GUID (nie jestem pewien, do czego dokładnie, ale sprawiło to, że nie można ich było używać w sieci). Firma Dell faktycznie wymieniła oba urządzenia jako wadliwe.

Wiem, że ludzie lubią dobrą odpowiedź, że identyfikatory GUID są magiczne i gwarantują unikalność, ale w rzeczywistości większość identyfikatorów GUID to tylko 121-bitowe liczby losowe (siedem bitów jest marnowanych na formatowanie). Jeśli nie czułbyś się komfortowo używając dużej liczby losowej, nie powinieneś czuć się komfortowo używając identyfikatora GUID.

Czy kod użyty do wygenerowania identyfikatora GUID może zawierać błąd? Tak, oczywiście, że tak. Ale odpowiedź jest taka sama, jak w przypadku błędu kompilatora - Twój własny kod jest o rzędy wielkości bardziej podatny na błędy, więc spójrz najpierw tam.

Oczywiście, że to możliwe ... Prawdopodobne? Mało prawdopodobne, ale jest to możliwe.

Pamiętaj, że ta sama maszyna generuje każdy identyfikator GUID (serwer), więc wiele „przypadkowości”, która jest oparta na informacjach specyficznych dla komputera, zostaje utraconych.

Aby się uśmiechnąć, wypróbuj następujący skrypt ... (działa na SQL 2005, nie jestem pewien co do 2000)

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

Powtarzanie tego (zajmuje mniej niż sekundę) daje dość szeroki zakres od pierwszego wyboru, nawet z BARDZO krótką przerwą czasową. Jak dotąd druga selekcja nic nie przyniosła.

Niemożliwe, jeśli użytkownicy mają różne komputery z kartami sieciowymi, a nawet jeśli nie, jest to nadal skrajnie marginalne, prawie teoretyczne ryzyko.

Osobiście szukałbym gdzie indziej, ponieważ jest to bardziej prawdopodobne, że jest to błąd niż zderzenie GUID ...

Oczywiście pod warunkiem, że nie odetniesz kawałków identyfikatora GUID, aby był krótszy.

Jasne, że jest to możliwe, a może nawet prawdopodobne. To nie jest tak, że każdy identyfikator GUID znajduje się w losowej części możliwej przestrzeni liczbowej. W przypadku, gdy dwa wątki próbowały wygenerować jeden jednocześnie, z wyjątkiem jakiejś scentralizowanej funkcji GUID z semaforem wokół niej, mogą otrzymać tę samą wartość.

Jest bardzo mało prawdopodobne, że wystąpią kolizje GUID, jeśli generujesz je za pomocą czegoś takiego jak NEWID() funkcji w SQL Server (choć oczywiście jest to możliwe, jak podkreślają inne odpowiedzi). Jedną z rzeczy, których nie zauważyli, jest to, że jest całkiem prawdopodobne, że napotkasz kolizje, jeśli generujesz identyfikatory GUID w JavaScript w przeglądarkach na wolności. Nie tylko czasami występują problemy z RNG w różnych przeglądarkach, ale napotkałem również problemy, w których pająki Google wydają się buforować wyniki takich funkcji i wielokrotnie przekazywały ten sam identyfikator GUID do naszych systemów.

Zobacz różne odpowiedzi tutaj, aby uzyskać więcej informacji:

Kolizje podczas generowania identyfikatorów UUID w JavaScript?

Czy jesteś matematykiem? W takim razie tak.

Czy jesteś inżynierem? W takim razie nie.