Ist es sicher anzunehmen, dass eine GUID immer eindeutig ist?

123

Ich weiß, dass es eine winzige Möglichkeit eines Konflikts gibt, aber wenn ich (zum Beispiel) einen Stapel von 1000 GUIDs generieren würde, wäre es sicher anzunehmen, dass sie alle einzigartig sind, um das Testen jedes einzelnen zu speichern?

Bonus-Frage

Ein optimaler Weg, um eine GUID auf Eindeutigkeit zu testen? Bloom Filter vielleicht?

math unique guid probability collision Tom Savage
quelle
2
Mögliches Duplikat von Ist eine GUID 100% der Zeit eindeutig?
ChrisF
29
Nicht, wenn wir alle den Reload-Button auf dieser Seite weiter drücken
mipadi
12
Ich beschuldige alle meine Fehler mit GUID-Kollisionen. Es muss irgendwann passieren, oder?
Michael
8
Es ist viel wahrscheinlicher, dass ein Hai mit einer schönen Plaid-Muster-Farbe vom Himmel fällt und Ihren Computer in Stücke zerschmettert. Daher würde ich behaupten, dass Vorsichtsmaßnahmen dagegen eine angemessenere Zuweisung von Ressourcen als Teil Ihrer allgemeinen Risikominderung darstellen planen.
David Gladfelter
4
@mipadi: toller Link! Ich kann mir nur einen Entwickler vorstellen, der irgendwo jammert: "Guuuuys! Verschwenden Sie keine GUIDs! Ich brauche die!"
FrustratedWithFormsDesigner

Antworten:

360

Ja, du kannst. Da GUIDs 128 Bit lang sind, besteht zwar die Möglichkeit eines Zusammenstoßes in Minuten - aber das Wort "Minute" ist bei weitem nicht stark genug. Es gibt so viele GUIDs, dass Sie, wenn Sie mehrere Billionen davon zufällig generieren , immer noch eher von einem Meteoriten getroffen werden als von einer einzigen Kollision (aus Wikipedia ). Und wenn Sie sie nicht zufällig generieren, sondern z. B. den MAC-Adress- und Zeitstempel-Algorithmus verwenden, sind sie auch eindeutig, da MAC-Adressen unter Computern eindeutig sind und Zeitstempel auf Ihrem Computer eindeutig sind Computer.

Bearbeiten 1: Um Ihre Bonusfrage zu beantworten, können Sie eine Reihe von GUIDs optimal auf Einzigartigkeit testen, indem Sie einfach davon ausgehen, dass sie alle eindeutig sind. Warum? Denn angesichts der Anzahl der von Ihnen generierten GUIDs ist die Wahrscheinlichkeit einer GUID-Kollision geringer als die Wahrscheinlichkeit, dass ein kosmischer Strahl ein wenig in den Speicher Ihres Computers flippt und die Antwort eines "genauen" Algorithmus, den Sie interessieren, durcheinander bringt laufen. (Siehe diese StackOverflow-Antwort für die Mathematik.)

Es gibt eine enorme Anzahl von GUIDs. Um Douglas Adams Per Anhalter durch die Galaxis zu zitieren :

"Der Weltraum", heißt es, "ist groß. Wirklich groß. Sie werden einfach nicht glauben, wie unglaublich groß er ist. Ich meine, Sie denken vielleicht, es ist ein langer Weg zum Chemiker, aber das sind nur Erdnüsse zum Weltraum." , Hör mal zu…"

Und da es im Universum ungefähr 7 × 10 22 Sterne und knapp 2 128 GUIDs gibt, gibt es ungefähr 4,86 ​​× 10 15 - fast fünf Billiarden - GUIDs für jeden einzelnen Stern. Wenn jeder dieser Sterne eine Welt mit einer blühenden Bevölkerung wie unserer hätte, dann hätte jeder Mensch oder Außerirdische, der jemals gelebt hat , um jeden Stern herum Anspruch auf über 45.000 GUIDs. Für jeden Menschen in der Geschichte an jedem Stern im Universum. Der GUID-Raum ist genauso groß wie das gesamte Universum. Sie brauchen sich keine Sorgen zu machen.

( Edit 2: Nachdenken: Wow. Ich hatte mir nicht klar gemacht, was das bedeutet. Der GUID-Raum ist unverständlich riesig. Ich bin irgendwie voller Ehrfurcht davor.)

Antal Spector-Zabusky
quelle
1
WolframAlpha berichtet außerdem, dass es für jede Zelle in jeder Person, die jemals gelebt hat, 36 Billionen UUIDs gibt. Sie haben ungefähr 10^14Zellen in Ihrem Körper und 106,5 Milliarden Menschen haben jemals gelebt. Oder 2.385 * 10^23UUIDs für jeden Cent der US-Staatsverschuldung.
new123456
5
Obwohl die Zahlen immer noch hoch sind, liegt die Wahrscheinlichkeit einer GUID-Kollision bei 2 ^ 64 GUIDs bei über 50%.
NullUserException
1
Bei 2 ^ 64 GUIDs würde dies die Anzahl auf weniger als einen (0,00026) pro Stern im Universum und 2 * 10 ^ (- 15) für jeden Menschen oder Außerirdischen reduzieren, der jemals gelebt hat. Dies würde immer noch über 170 Millionen GUIDs für jeden Menschen ermöglichen , der jemals gelebt hat. Ich denke, wir sind immer noch gut.
NullUserException
12
Erwähnenswert ist, dass eine GUID-Kollision auch nur dann ein Problem darstellt, wenn sie sich im selben Geschäftsbereich befindet. Eine GUID, mit der ich eine Komponente in einer Software identifiziere, kann mit einer GUID identisch sein, die Sie in einer Datenbankzeile in Ihrer eigenen Anwendung verwenden, ohne Probleme zu verursachen
James Thorpe,
1
Die Tatsache, dass es 2 ^ 128 GUIDS gibt, ist irrelevant, und Sie sind nicht "immer noch gut" bei 50% Kollisionswahrscheinlichkeit, Sie sind nicht einmal gut bei 0,0000001%
BlackTigerX
40

Kurze Antwort: Aus praktischen Gründen ja.

Sie müssen jedoch das Geburtstagsparadoxon berücksichtigen!

Ich habe einige repräsentative Kollisionswahrscheinlichkeiten berechnet. Bei 122-Bit-UUIDs, wie im Wikipedia-Artikel angegeben , beträgt die Kollisionswahrscheinlichkeit 1/2, wenn Sie mindestens 2.71492e18UUIDs generieren . Bei 10 ^ 19 UUIDs beträgt die Wahrscheinlichkeit 0,999918. Mit 10 ^ 17 UUIDs, 0,000939953.

Einige Vergleichszahlen finden Sie auf Wikipedia. So können Sie jedem lebenden Menschen, jeder Galaxie im beobachtbaren Universum, jedem Fisch im Ozean und jeder einzelnen Ameise auf der Erde sicher eine UUID zuweisen. Allerdings , Kollisionen sind so gut wie sicher , wenn Sie einen UUID erzeugen für jeden Transistor der Menschheit in einem Jahr produziert, jedes Insekt auf der Erde, jedes Sandkorn auf der Erde, jeden Stern im beobachtbaren Universum, oder etwas größer.

Wenn Sie 1 Milliarde UUIDs pro Sekunde generieren, würde es ungefähr 36 Jahre dauern, bis eine Kollisionswahrscheinlichkeit von 10% erreicht wird.

Irgendwann wird es wahrscheinlich zu einer Kollision zwischen den UUIDs kommen, die im Laufe der Menschheitsgeschichte generiert wurden. Die Wahrscheinlichkeit, dass kollidierte UUIDs für denselben Zweck verwendet werden, ist jedoch verschwindend gering, sodass es in der Praxis kein Problem gibt.

Mechanische Schnecke
quelle
13
So endet das Universum ... Einige Programmierer gehen einfach davon aus, dass ihre GUIDs für ihren Mega-Todesstern immer einzigartig sein werden ...
pkr298
Da UUIDs auf nicht zufälligen Daten basieren, sind es 36 Jahre - Sie müssen sich nur um jede Millisekunde einzeln kümmern.
Mjaggard
@mjaggard UUIDs basieren auf zufälligen Daten. Jedenfalls jede moderne Art.
Trejkaz
8

Eine Analyse der Kollisionsmöglichkeit ist auf Wikipedia verfügbar: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Wie im Link erwähnt, wird dies durch die Eigenschaften des Zufallszahlengenerators beeinflusst.

Es besteht auch die Möglichkeit eines Fehlers im GUID-Generatorcode. Während die Chancen gering sind, sind sie wahrscheinlich höher als die Chancen einer Kollision basierend auf der Mathematik.

Ein Bloom-Filter könnte angebracht sein; Es kann Ihnen schnell sagen, ob eine GUID eindeutig ist, aber es besteht die Möglichkeit, dass eine Kollision falsch angezeigt wird. Eine alternative Methode, wenn Sie einen Stapel gleichzeitig testen, besteht darin, den Stapel zu sortieren und jedes aufeinanderfolgende Element zu vergleichen.

Mark Ransom
quelle
5

Im Allgemeinen ist es ja sicher anzunehmen.

Wenn Ihr GUID-Generator wirklich zufällig ist, ist die Wahrscheinlichkeit eines Konflikts innerhalb von 1000 GUIDs außerordentlich gering.

Das setzt natürlich einen guten GUID-Generator voraus. Die Frage ist also wirklich, wie sehr Sie dem Tool vertrauen, mit dem Sie die GUID generieren, und ob es eigene Tests hat.

Gehackt
quelle
0

Eine Kollision ist zwar möglich, aber höchst unwahrscheinlich. (Mathe hier .) Es ist sicher anzunehmen, dass sie tatsächlich verschieden sind.

VeeArr
quelle