Ist eine GUID zu 100% eindeutig?

Question

Ist eine GUID zu 100 % eindeutig?

Bleibt sie über mehrere Threads hinweg eindeutig?

Answer 1

Ich glaube, wenn die Menschen ihre Gedanken und Ängste in Statistiken vergraben, vergessen sie das Offensichtliche. Wenn ein System wirklich zufällig ist, dann ist das Ergebnis, das man am wenigsten erwartet (z. B. alle Einsen), genauso wahrscheinlich wie jeder andere unerwartete Wert (z. B. alle Nullen). Weder das eine noch das andere schließt aus, dass diese Werte nacheinander auftreten, auch nicht innerhalb des ersten Stichprobenpaares (auch wenn das statistisch gesehen "wirklich schockierend" wäre). Und genau das ist das Problem bei der Messung des Zufalls: Die Kritikalität (und das Pech) werden dabei völlig außer Acht gelassen.

WENN es jemals passiert, was ist das Ergebnis? Funktioniert Ihre Software nicht mehr? Wird jemand verletzt? Stirbt jemand? Explodiert die Welt?

Je extremer die Kritikalität ist, desto schlechter sitzt das Wort "Wahrscheinlichkeit" im Mund. Letztendlich ist die Verkettung von GUIDs (oder deren XOR-Verknüpfung oder was auch immer) das, was Sie tun, wenn Sie (subjektiv) Ihre besondere Kritikalität (und Ihr Gefühl von "Glück") für inakzeptabel halten. Und wenn es das Ende der Welt bedeuten könnte, dann verwenden Sie bitte im Namen aller, die nicht an Nuklearexperimenten im Large Hadron Collider beteiligt sind, keine GUIDs oder irgendetwas anderes Indeterministisches!

Answer 2

Ich habe die Erfahrung gemacht, dass die GUIDs bei Multi-Thread-/Multi-Process-Unit-Tests nicht eindeutig sind (auch?). Ich vermute, das hat mit dem identischen Seeding (oder dem Fehlen von Seeding) der Pseudo-Zufallsgeneratoren zu tun, wenn alle anderen Dinge gleich sind. Ich habe es für die Erzeugung eindeutiger Dateinamen verwendet. Ich habe festgestellt, dass das Betriebssystem das viel besser kann :)

Trolling-Alarm

Sie fragen, ob GUIDs 100% eindeutig sind. Das hängt von der Anzahl der GUIDs ab, unter denen sie eindeutig sein muss. Wenn die Anzahl der GUIDs gegen unendlich geht, nähert sich die Wahrscheinlichkeit für doppelte GUIDs 100%.

Answer 3

GUID-Algorithmen werden in der Regel gemäß der v4-GUID-Spezifikation implementiert, die im Wesentlichen eine pseudozufällige Zeichenkette ist. Leider fallen diese in die Kategorie der "wahrscheinlich nicht einmalig" aus Wikipedia (ich weiß nicht, warum so viele Leute diesen Teil ignorieren): "... andere GUID-Versionen haben unterschiedliche Eindeutigkeitseigenschaften und Wahrscheinlichkeiten, die von garantierter Eindeutigkeit bis zu wahrscheinlicher Nicht-Eindeutigkeit reichen."

Die pseudozufälligen Eigenschaften von V8-JavaScript Math.random() sind SCHLECHT, was die Eindeutigkeit angeht, und Kollisionen treten oft schon nach ein paar tausend Iterationen auf, aber V8 ist nicht der einzige Übeltäter. Ich habe reale GUID-Kollisionen sowohl mit PHP- als auch Ruby-Implementierungen von v4-GUIDs gesehen.

Da es immer häufiger vorkommt, dass die ID-Generierung über mehrere Clients und Server-Cluster hinweg skaliert wird, nimmt die Entropie einen großen Schaden - die Wahrscheinlichkeit, dass derselbe zufällige Seed für die Generierung einer ID verwendet wird, steigt (Zeit wird oft als zufälliger Seed in Pseudo-Zufallsgeneratoren verwendet), und GUID-Kollisionen steigen von "wahrscheinlich nicht eindeutig" zu "sehr wahrscheinlich, um viele Probleme zu verursachen".

Um dieses Problem zu lösen, habe ich mir vorgenommen, einen ID-Algorithmus zu entwickeln, der sicher skaliert werden kann und bessere Garantien gegen Kollisionen bietet. Dazu verwendet er den Zeitstempel, einen speicherinternen Client-Zähler, einen Client-Fingerabdruck und Zufallszeichen. Durch die Kombination dieser Faktoren entsteht eine additive Komplexität, die besonders kollisionssicher ist, selbst wenn man sie auf mehrere Hosts verteilt:

http://usecuid.org/

Answer 4

In einem allgemeineren Sinn ist dies als "Geburtstagsproblem" oder "Geburtstagsparadoxon" bekannt. Wikipedia hat einen ziemlich guten Überblick unter: Wikipedia - Geburtstagsproblem

Ganz grob gesagt ist die Quadratwurzel der Größe des Pools ein grober Anhaltspunkt dafür, wann man mit einer 50%igen Chance auf ein Duplikat rechnen kann. Der Artikel enthält eine Wahrscheinlichkeitstabelle für die Poolgröße und verschiedene Wahrscheinlichkeiten, einschließlich einer Zeile für 2^128. Bei einer Kollisionswahrscheinlichkeit von 1 % müssten Sie also 2,6*10^18 128-Bit-Zahlen zufällig auswählen. Eine 50%ige Wahrscheinlichkeit erfordert 2,2*10^19 Auswahlen, während SQRT(2^128) 1,8*10^19 ist.

Das ist natürlich nur der Idealfall eines echten Zufallsprozesses. Wie bereits erwähnt, hängt viel davon ab, dass zufällig Aspekt - wie gut ist der Generator und das Saatgut? Es wäre schön, wenn es eine Hardwareunterstützung für diesen Prozess gäbe, die sicherer wäre, aber alles kann gefälscht oder virtualisiert werden. Ich vermute, dass dies der Grund dafür sein könnte, dass MAC-Adressen/Zeitstempel nicht mehr integriert sind.

Answer 5

Die Antwort von "Ist eine GUID zu 100% eindeutig?" ist einfach "Nein" .

• Wenn Sie eine 100%ige Einzigartigkeit der GUID wünschen, gehen Sie wie folgt vor.

  1. GUID erzeugen
  2. Prüfen Sie, ob diese GUID in der Tabellenspalte, in der Sie nach Eindeutigkeit suchen, vorhanden ist
  3. wenn vorhanden dann weiter zu Schritt 1 sonst Schritt 4
  4. diese GUID als eindeutig verwenden.