Czy możliwe są kolizje GUID?


130

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?


11
Wszyscy nie mówiąc już jest wrong.I zderzył 1 uniqueidentifier ze zbioru danych o mniej niż pół miliona rekordów, MSSQL 2008 R2
Behrooz

2
@Behrooz Yikes. Nie jest to niemożliwe dzięki paradoksowi urodzinowemu naszemu przyjacielowi, ale nadal jest to szalenie pechowe z całkowicie losowymi identyfikatorami GUID v4. Może korzystałeś ze słabszej strategii generowania GUID?
Craig Ringer

6
@Behrooz Wow. To szokujące szczęście.
Craig Ringer

6
@Behrooz to prawdopodobnie wadliwa liczba pseudolosowa używana w MSSQL (nie zdziwiłbym się, gdyby mieli 32-bitowe ziarno w swoim generatorze lub tym podobne, biorąc pod uwagę jakość ich oprogramowania). Matematyka nie kłamie. Ta możliwość jest tak mała, że ​​możesz wynosić 99,99999999999 (i wiele po 9)%, że albo generator guidów MSSQL jest uszkodzony (lub może być generatorem pseudolosowym, który jest używany do generowania identyfikatorów GUID) lub popełniłeś błąd.
Alex,

3
Uwielbiam to, jak dokładnie w tym momencie zarówno pytanie, jak i wybrana odpowiedź mają 128 punktów. Zbieg okoliczności? 🤔
Caio Cunha

Odpowiedzi:


131

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.


3
To właśnie pomyślałem, ale chciałem się tylko upewnić, że nie mogę tego wykluczyć. Nigdy nie wiadomo, jakie dziwne błędy mogą pojawić się w 8-letnim oprogramowaniu. :)
Jason Baker

6
Właściwie to już nie jest prawda. Było to prawdą dla identyfikatorów GUID v1, ale nie dla obecnych v4. Więcej informacji można znaleźć na stronie en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm .
Greg Beech

101
Głos w dół, ponieważ w zasadzie (w najbardziej surowej formie) mylisz się, mówiąc „nie” na pytanie „Czy kolizje GUID są możliwe?”. To bardzo możliwe. Prawdopodobieństwo tego jest niewielkie, ale jest możliwe. Nienawidzę brzmieć pedantycznie - ale w SO chodzi przede wszystkim o zwięzłość i dokładność.

13
wpisz „olve [1-exp [- (n ^ 2 / (2 * 2 ^ 128))]> 0.01, n] ”do wolframu alfa, aby otrzymać wynik za 1% ... Pamiętaj, że chociaż ta liczba wydaje się duża w w kontekście JEDNEJ aplikacji, z pewnością nie jest ona duża dla całego świata. Gdyby każdy komputer na Ziemi generował prawdziwe identyfikatory GUID, spowodowałby kolizję z prawdopodobieństwem 1% w ciągu około jednej sekundy, zakładając, że mogą generować GUID co nanosekundę (co jest prawdopodobnie całkiem realistyczne w dzisiejszych czasach). Jeśli więc używasz identyfikatorów GUID jako identyfikatorów baz danych, są one unikalne. Identyfikatory GUID dla wszystkich obliczeń wykonanych na Ziemi będą kolidować natychmiast.
św.

11
Powiedzenie „Nie” nie jest możliwe, a następnie stwierdzenie, że istnieje 1% szans na kolizję, gdy zostanie wygenerowana określona kwota, są to bezpośrednie konflikty. Prawidłowa odpowiedź powinna być Teoretycznie - tak, kolizja może nastąpić losowo. Jednak szanse na zderzenie są statystycznie mniejsze niż uderzenie asteroidy w Ziemię, odbicia się od Ziemi i odbicia od Księżyca, aby uderzyć w Ziemię po raz drugi, w ciągu następnej godziny.
Baaleos

113

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


38
Głosowano za. Zapisanie stanu i powtórka naprawdę wygenerowałoby zduplikowane wskazówki.
Joshua,

35
Najprawdopodobniej była to „zła” implementacja identyfikatora GUID. Te teoretyczne kursy były bardzo niskie, ale na Pocket PC ?? Kto może powiedzieć, że nie poszli na skróty, które podniosły te szanse do kategorii „nieprawdopodobne, ale możliwe”.
Dave Dopson,

9
To, że coś ma bardzo niskie prawdopodobieństwo, nie oznacza, że ​​tak się nie stanie.
Geeky Guy

3
Jak powiedziałem powyżej, szanse na to są tak małe, że można bezpiecznie założyć, że albo popełniłeś błąd, albo MSSQL używa wadliwego PRNG ( en.wikipedia.org/wiki/Pseudorandom_number_generator ). Np. Jest prawdopodobne, że ten PRNG jest inicjowany przez ziarno o małym rozmiarze. Wadliwe PRNG nie są rzadkie (patrz schneier.com/paper-prngs.html ) - na przykład niedawno odkryto jedną wadę w Android SDK - android-developers.blogspot.com/2013/08/… + usenix.org/conference/woot14 / program-warsztatów / prezentacja /…
Alex

2
@Alex, błąd polegał na „Save State and Restore” z Emulatora, który przywrócił cały obraz emulatora, w tym zegar emulatora. Tak więc po tysiącach operacji przywracania w ciągu jednego roku wygenerowano jedną kolizję przewodnika. Masz rację, był błąd!
Pop Catalin

35

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.


„ale z możliwymi numerami 3.4E38” - nie. Dwa identyfikatory GUID wygenerowane prawie jednocześnie na tej samej maszynie zakończyłyby się bardzo podobnymi identyfikatorami GUID.
Kirk Strauser

4
Zależałoby to od tego, w jaki sposób generowany jest identyfikator GUID, a niektóre implementacje oparte na czasie procesora lub milisekundach (miejmy nadzieję) wyolbrzymią wszelkie obliczenia oparte na ich podstawie, więc dwa identyfikatory GUID wygenerowane w odstępach milisekund będą miały ogromną różnicę.
Dalin Seivewright

4
W przypadku więcej niż jednego procesora na komputerze, jeśli identyfikator guid jest oparty na czasie i adresie MAC, każdy rdzeń może wydawać ten sam identyfikator guid w tym samym momencie.
AndyM,

12
Jestem prawie pewien, że żadna przyzwoita implementacja GUID nie będzie
Guillaume86

1
@MatthewLock Paradoks urodzin jest omówiony w źródle. Sprawdź link.
Zero3

21

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


2
Zgadzam się ze wszystkimi faktami, ale uważaj na matematykę. Stwierdzenie, że istnieje 1 na 10 ^ 19 szans na zderzenie dowolnych dwóch identyfikatorów GUID, zależy od tego, ile identyfikatorów GUID znajduje się w zestawie. Do tej szansy potrzebujesz ~ 2 ^ 32 identyfikatorów GUID, więc w prawie wszystkich rzeczywistych scenariuszach szanse są znacznie niższe.
DocMax

1
Masz literówkę 1 in 10^64 (10^19), która moim zdaniem powinna być 1 in 2^64 (10^19). Jestem też bardzo zdezorientowany, jak myślisz, że paradoks urodzin dotyczy tylko 2 liczb. Zakładam, że spojrzałeś na en.wikipedia.org/wiki/Birthday_paradox . Tabela pokazuje, ile poradników potrzebujesz, aby uzyskać dane prawdopodobieństwo duplikatu. Z tej tabeli prawdopodobieństwo 1 na 10 ^ 18 wymaga 2,6 * 10 ^ 10 guidów, a nie tylko dwóch identyfikatorów GUID.
Tony Lee,

Jeden punkt-guidy v1 są nadal w powszechnym użyciu i opierają się na adresach MAC, szczególnie w bazach danych, ponieważ mają pożądane cechy. Zobacz UuidCreateSequential i jego opakowanie SQL Server NewSequentialID ( msdn.microsoft.com/en-us/library/windows/desktop/ ... ).
EBarr

18

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.


Czy na pewno nie mógłbym uzbroić mojej sieci tak, że mniej niż 1 na 10 ^ 28 pakietów jest uszkodzonych?
Joshua,

13

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.


1
Właściwie w tej sytuacji brzytwa Ockhama wcale nie jest dobrym przewodnikiem! Occam's Razor mówi, że przypadek przy najmniejszych założeniach jest najprawdopodobniej poprawny. W tej sytuacji przypadek kolizji GUID jest właściwie dużo prostszy, ale Occam's Razor nie ma zastosowania w takiej sytuacji, w której już wiemy, że jeden z przypadków jest niesamowicie mało prawdopodobny.
śluza

11

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.





9

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.


Czy często zdarza się, że dwa różne komputery mają ten sam adres MAC w sieci Ethernet?
Dave Lucre

@DaveLucre: Nie, ale odnotowano incydenty.
Joshua

Jestem naprawdę ciekawy, jak to się dzieje. Czy jest bardziej prawdopodobne w przypadku maszyn wirtualnych, które losowo generują adresy MAC dla każdej karty sieciowej? Nigdy nie słyszałem o fizycznych kartach sieciowych produkowanych ze zduplikowanymi adresami MAC! W pewnym sensie wrzuca do prac potężny klucz, jeśli to możliwe!
Dave Lucre

Łał! Dzięki za link @Joshua! Co za kolosalna wpadka!
Dave Lucre

@DaveLucre Użyłem kilku bardzo tanich kart sieciowych USB, z których WSZYSTKIE są produkowane z tym samym MAC. Ale oczywiście nie ma to nic wspólnego z matematyką przypadkowości, a wszystko z lenistwem producenta.
rudolfbyker

5

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.


3
Był to konkretnie identyfikator GUID. Miało to coś wspólnego z identyfikatorem GUID generowanym przez maszyny, gdy przyłączały się do sieci. Dellowi zajęło kilka tygodni wymiana maszyn, ponieważ stwierdzili, że identyfikatory GUID nie mogą być takie same. Udało nam się odtworzyć problem, firma Dell odebrała maszyny i była w stanie uzyskać takie same wyniki w swoich sieciach. Skończyło się na wymianie obu maszyn. Jak powiedziałem, nie jestem osobą związaną z siecią, ale szczególnie pamiętam, że był to problem z identyfikatorami GUID.
John Kraft

5

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.


11
Zalecamy również, aby nie używać sieci. Albo komputery. Bity parzystości mogą zrobić tylko tyle!
Rushyo

Nie zrozumiałeś. W tym poście chciałem powiedzieć dwie rzeczy: 1) Jeśli potrzebujesz dużej liczby losowej, użyj dużej liczby losowej. Używanie identyfikatora GUID jako dużej liczby losowej jest niepotrzebnie mylące. (2)
Rick Yorgason

4
Z czego jestem w pełni świadomy. Stwierdziłeś, że „jeśli nie czułbyś się komfortowo używając dużej liczby losowej”. ale identyfikatory GUID są tak unikalne, że można by się przekonać, że prawie wszystko inne w komputerze jest bardziej losowe, nawet operacje, które przyjmujesz za pewnik. Jest większa szansa, że ​​dziwna usterka pamięci złamie twoją kolumnę tożsamości, niż nastąpi (prawdziwa) kolizja GUID. Nie powinieneś czuć się z nimi „skrępowany”. Jeśli nie są idealne do scenariusza, to w porządku - ale nie wymagają specjalnej ostrożności.
Rushyo,

3
Myślę, że to donikąd, ale ludzie próbują ci wyjaśnić, że mechanizmy wykrywania błędów w typowym sprzęcie, takim jak karty sieciowe lub dyski twarde, używają algorytmów, które mają większe szanse na nie wykrycie błędu niż ty na uzyskanie kolizji GUID, więc jeśli polegasz na nich, równie dobrze możesz polegać na identyfikatorach GUID
Guillaume86,

1
@Rick, zależy od tego, jak duży jest twój numer. Zdecydowanie nie z 4-bajtowym int lub 8-bajtowym bigintem. GUID = 16 bajtów, więc potrzebna byłaby niestandardowa implementacja dużej liczby 16 bajtów, aby uzyskać te same 2 ^ 128 możliwych kombinacji. Więc ogólnie rzecz biorąc, jeśli używasz „normalnych” liczb losowych int lub bigint, prawdopodobieństwo kolizji z identyfikatorem GUID jest mniejsze (pomijając przypadkowe algo dla każdego).
Wim Hollebrandse

3

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.


2

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.


1

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.


1
Potrzebujesz kolejnych 15 zer na końcu licznika, aby mieć 50% szans na powtórzenie. Ale, na miłość boską, nie rób tego!
Jim Birchall

0

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.


Identyfikatory GUID byłyby generowane na serwerze, więc karty sieciowe użytkownika nie wchodzą w grę.
Tom Ritter

0

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ść.


0

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?


-1

Czy jesteś matematykiem? W takim razie tak.

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.