Sind GUID Kollisionen möglich?
https://stackoverflow.com/questions/184869
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich arbeite an einer Datenbank in SQL Server 2000, die eine GUID für jeden Benutzer verwendet, die die App nutzen es gebunden ist. Irgendwie endete zwei Benutzer mit demselben GUID auf. Ich weiß, dass Microsoft einen Algorithmus verwendet eine zufällige GUID zu generieren, die eine äußerst geringe Chance, dass Kollisionen, ist aber eine Kollision noch möglich?
Lösung
Im Grunde genommen nicht. Ich glaube, jemand ging mit Ihrer Datenbank Ausmisten. Je nach Version GUID Sie den Wert verwenden entweder eindeutig (für Dinge wie Version 1 GUIDs) oder beide einzigartig und unvorhersehbar (für Dinge wie Version 4 GUIDs). SQL Server-Implementierung für ihre NEWID () Funktion erscheint eine 128-Bit-Zufallszahl zu verwenden, so dass Sie gehen nicht um eine Kollision zu erhalten.
Für eine 1% ige Chance einer Kollision, dann würden Sie generieren müssen über 2.600.000.000.000.000.000 GUIDs.
Andere Tipps
Im Grunde sie ist nicht möglich! , die Chancen sind, astronomisch niedrig .
Aber ... ich bin die einzige Person, die ich die Welt, die ich kenne, dass hatte eine GUID einmal colision (yep!).
Und ich bin überzeugt davon, und dass es kein Fehler.
Wie kam es dazu, in einer kleinen Anwendung, die auf dem Pocket PC ausgeführt wurde, am Ende einer Operation ein Befehl, der eine generierte GUID ausgegeben werden muss hat. Der Befehl, nachdem er wurde auf dem Server ausgeführt es in einer Befehlstabelle auf dem Server zusammen mit dem Ausführungsdatum gespeichert wurde. Ein Tag, als ich die Debuggen ich den Modul Befehl ausgegeben (mit dem neu generierten GUID angebracht) und es ist nichts passiert. Ich habe es wieder (mit dem gleichen guid, weil die guid nur einmal zu Beginn der Operation erzeugt wurde), und wieder, und nichts, schließlich versuchen, herauszufinden, warum der Befehl nicht ausgeführt wird, überprüfte ich die Befehlstabelle, und die gleiche GUID wie die aktuellen wurde vor 3 Wochen eingeführt. Nicht diese glauben, restauriert ich eine Datenbank ab 2 Wochen Backup und die guid war da. Überprüft den Code wurde die neue guid frisch keinen Zweifel darüber erzeugt. Pow guid Kollision passiert nur einmal, aber ich wünschte wirklich, ich würde bei Lotto statt gewonnen haben, ist die Chance größer :).
Edit: es gibt einige Faktoren, die stark erhöht die Chance, dass dies geschieht, haben könnte, lief die Anwendung auf dem PocketPC-Emulator, und der Emulator hat einen Zustand Funktion speichern, was bedeutet, dass der Staat jedes Mal die lokale Zeit wiederhergestellt auch und die guid gestellt wird, wird auf dem internen Timer basierend auf .... auch der gUID-Erzeugungsalgorithmus für Compact Framework möglicherweise weniger vollständig als zum Beispiel des COM ein ...
Sie sind theoretisch möglich, aber mit 3.4E38 möglichen Zahlen, wenn man zig Billionen von GUIDs in einem Jahr schafft die Chance, mit einem Duplikat ist ,00000000006 ( Quelle ).
Wenn zwei Benutzer mit demselben GUID enden, würde ich wetten, dass es ein Fehler in dem Programm, das die Daten verursacht kopiert oder gemeinsam genutzt werden.
Zuerst lässt die Chance einer Kollision von zwei GUIDs suchen. Es ist nicht, wie die anderen Antworten erwähnt, 1 in 2 ^ 128 (10 ^ 38) wegen des Geburtstagsparadox , was bedeutet, daß für eine Chance von 50% zwei GUIDs der Wahrscheinlichkeit kollidierende tatsächlich 1 in 2 ^ 64 (10 ^ 19), die sehr viel kleiner ist. Dies ist jedoch nach wie vor eine sehr große Zahl, und als solche die Wahrscheinlichkeit einer Kollision vorausgesetzt, Sie eine angemessene Anzahl von GUIDs verwenden, ist gering.
Beachten Sie auch, dass GUIDs enthalten keine Zeitstempel oder die MAC-Adresse, so viele Menschen scheinen auch zu glauben. Dies galt für v1 GUIDs aber jetzt v4 GUIDs verwendet werden, die nur eine Pseudo-Zufallszahlen sind was bedeutet, dass die Möglichkeit einer Kollision ist wohl höher, weil sie zu einer Zeit und eine Maschine nicht mehr eindeutig sind.
So im Wesentlichen die Antwort ja ist, Kollisionen möglich sind. Aber sie sind sehr unwahrscheinlich.
Edit: fixiert zu sagen 2 ^ 64
Die Chancen, zwei zufällige GUIDs kollidierende (~ 1 in 10 ^ 38) niedriger ist als die Wahrscheinlichkeit von nicht eine beschädigte TCP / IP-Paket (~ 1 in 10 ^ 10) zu detektieren. http: //wwwse.inf.tu-dresden .de / data / Kurse / SE1 / SE1-2004-lec12.pdf , Seite 11. Dies gilt auch für Plattenlaufwerke, cD-Laufwerke, etc ...
GUIDs sind statistisch eindeutig und die Daten, die Sie aus dem db lesen ist nur statistisch korrekt ist.
Ich würde Ockhams Rasiermesser als eine gute Führung in diesem Fall in Betracht ziehen. Es ist unglaublich unwahrscheinlich, dass Sie eine GUID Kollision haben. Es ist viel wahrscheinlicher, Sie einen Fehler haben oder jemand verwirren mit Ihren Daten.
Siehe Wikipedia Globally Unique Identifier Artikel. Es gibt mehrere Möglichkeiten GUIDs zu erzeugen. Anscheinend ist die alte (?) Art und Weise verwendete Mac-Adresse, ein Zeitstempel auf eine sehr kurze Einheit und einen einzigartigen Zähler (zu schnelle Generationen auf demselben Computer verwalten), so duplizieren macht sie ist fast unmöglich. Aber diese GUIDs wurden fallen gelassen, weil sie verwendet werden könnten Nutzer auf die Spur ...
Ich bin nicht sicher, ob der neue Algorithmus verwendet von Microsoft (der Artikel sagt eine Folge von GUIDs vorhergesagt werden kann, sieht aus wie sie nicht mehr Zeitstempel verwenden? Der Artikel Microsoft oben verlinkten sagt etwas anderes ...).
Nun sind GUIDs vorsichtig zu sein, namentlich entworfen, global eindeutig, also werde ich riskieren, es ist unmöglich, oder von sehr sehr sehr geringer Wahrscheinlichkeit. Ich würde an anderer Stelle suchen.
Zwei Win95-Maschinen, die Ethernet-Karten mit doppelten MAC-Adressen haben wird Thema doppelten GUIDS unter streng kontrollierten Bedingungen, vor allem, wenn zum Beispiel der Leistung in dem Gebäude erlischt und sie beiden Boote genau zur gleichen Zeit.
Ich kenne Leute, wie die Wohlfühl Antwort, die GUIDs sind magisch und einzigartig sein garantiert, aber in Wirklichkeit sind die meisten GUIDs sind nur 121-Bit-Zufallszahlen (sieben der Bits auf Formatierung verschwendet). Wenn Sie sich nicht wohl fühlen würde, eine große Zufallszahl verwenden, dann sollten Sie sich nicht wohl fühlen, eine GUID verwenden.
Kann der Code verwendet, um eine GUID zu generieren hat einen Fehler drin? Ja, natürlich könnte es. Aber die Antwort ist die gleiche wie für einen Compiler Fehler wäre -. Ihren eigenen Code ist um Größenordnungen häufiger buggy sein, so sehen es erste
Natürlich ist es möglich .... Wahrscheinliche? Wahrscheinlich nicht, aber es ist möglich.
Denken Sie daran, die gleiche Maschine jede GUID (Server) zu erzeugen, so viel von der „Zufälligkeit“, die auf maschinenspezifische Informationen basieren verloren.
Nur für grins, versuchen Sie das folgende Skript ... (funktioniert auf SQL 2005, nicht sicher 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
wiederholtes Laufen (dauert weniger als eine Sekunde) erzeugt einen ziemlich weiten Bereich von der ersten Auswahl, sogar mit einer extrem kurzen Zeitlücke. Bisher ist die zweite Auswahl hat noch nichts produziert.
Unmöglich, wenn die Benutzer verschiedene Maschinen mit Netzwerkkarten haben, und selbst wenn nicht ist es immer noch ein äußerst marginal fast theoretisches Risiko.
Persönlich würde ich an andere Stelle suchen, da es eher ein Problem ist eher als ein GUID Zusammenstoß ...
Die Bereitstellung natürlich, dass Sie es nicht kürzer Bits aus der GUID hacken zu machen.
Sicher ist es möglich, und vielleicht sogar wahrscheinlich. Es ist nicht wie jede GUID in einem zufälligen Teil des möglichen Zahlenraumes ist. Für den Fall, dass zwei Threads eine versuchten gleichzeitig zu erzeugen, eine Art zentraler GUID-Funktion mit einer Semaphore um es abgesehen, konnten sie mit dem gleichen Wert am Ende.
Ich werde das Vorwort mit „Ich bin kein Netzwerk Person, so dass ich kann völlig inkohärent Sätze folgenden machen.“.
Als ich an der Illinois State University arbeitete, hatten wir zwei Dell-Desktops, bestellt zu unterschiedlichen Zeiten. Wir stellen die erste auf dem Netzwerk, aber wenn wir die zweite auf das Netzwerk zu setzen versucht, haben wir begonnen, verrückt Fehler zu empfangen. Nach viel Fehlerbehebung, es wurde bestimmt, dass beide Maschinen die gleiche GUID produziert wurden (ich bin nicht sicher genau, was, aber es machte sie sowohl auf dem Netzwerk unbrauchbar). Dell ersetzt tatsächlich beide Maschinen als fehlerhaft.
Es ist höchst unwahrscheinlich, dass Sie in GUID Kollisionen führen werden, wenn man sie durch so etwas wie die NEWID() Funktion in SQL Server ist zu erzeugen (obwohl natürlich möglich, wie andere Antworten betont haben). Eine Sache, die sie nicht darauf hingewiesen haben, ist, dass es eigentlich ziemlich wahrscheinlich, dass Sie in Kollisionen laufen werden, wenn Sie GUIDs in JavaScript auf Browser in der freien Natur sind zu erzeugen. Nicht nur ist es manchmal Probleme in der RNG in verschiedenen Browsern, aber ich habe auch auf Probleme stoßen, wo die Google Spinnen die Ergebnisse von Funktionen wie das cachen scheinen, und am Ende immer wieder die gleiche GUID vorbei bis zu unseren Systemen.
die verschiedenen Antworten hier für weitere Informationen:
