Ist eine GUID in 100 % der Fälle eindeutig?

https://stackoverflow.com/questions/39771

09-06-2019
|

Frage

Bleibt es über mehrere Threads hinweg eindeutig?

Lösung

Während jede generierte GUID nicht garantiert eindeutig ist, ist die Gesamtzahl der eindeutigen Schlüssel (2¹²⁸ oder 3,4 × 10³⁸) ist so groß, dass die Wahrscheinlichkeit, dass die gleiche Anzahl zweimal erzeugt wird, sehr klein ist.Betrachten Sie beispielsweise das beobachtbare Universum, das etwa 5 × 10 enthält²²Sterne;Jeder Stern könnte dann 6,8 × 10 haben¹⁵ universell eindeutige GUIDs.

Aus Wikipedia.

Dies sind einige gute Artikel darüber, wie eine GUID erstellt wird (für .NET) und wie Sie in der richtigen Situation dieselbe GUID erhalten können.

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-two/

Andere Tipps

Die einfache Antwort lautet: Ja.

Raymond Chen schrieb a großartiger Artikel auf GUIDs und warum Teilzeichenfolgen von GUIDs so sind nicht garantiert einzigartig.Der Artikel geht eingehend auf die Art und Weise ein, wie GUIDs generiert werden, und auf die Daten, die sie verwenden, um die Eindeutigkeit sicherzustellen, was eine ausführliche Erläuterung erfordern sollte Warum sie sind :-)

Wenn Sie Angst vor denselben GUID-Werten haben, platzieren Sie zwei davon nebeneinander.

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

Wenn Sie zu paranoid sind, geben Sie drei ein.

Nebenbei bemerkt habe ich mit Volume-GUIDs in Windows XP herumgespielt.Dies ist ein sehr undurchsichtiges Partitionslayout mit drei Festplatten und vierzehn Volumes.

\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
                                     | | | | |
                                     | | | | +-- 6f = o
                                     | | | +---- 69 = i
                                     | | +------ 72 = r
                                     | +-------- 61 = a
                                     +---------- 6d = m

Es liegt nicht daran, dass die GUIDs sehr ähnlich sind, sondern daran, dass alle GUIDs die Zeichenfolge „mario“ enthalten.Ist das Zufall oder gibt es eine Erklärung dafür?

Jetzt, wenn Googeln Sie nach Teil 4 In der GUID habe ich ca. 125.000 Treffer mit Volumen-GUIDs gefunden.

Abschluss: Wenn es um Volume-GUIDs geht, sind sie nicht so eindeutig wie andere GUIDs.

Ja, eine GUID sollte immer eindeutig sein.Es basiert sowohl auf der Hardware als auch auf der Zeit, plus ein paar Extras, um sicherzustellen, dass es einzigartig ist.Ich bin mir sicher, dass es theoretisch möglich ist, am Ende zwei identische Exemplare zu haben, aber in einem realen Szenario ist das äußerst unwahrscheinlich.

Hier ist ein großartiger Artikel von Raymond Chen über Guids:

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Es sollte nicht passieren.Wenn .NET jedoch stark ausgelastet ist, ist es möglich, doppelte GUIDs zu erhalten.Ich habe zwei verschiedene Webserver, die zwei verschiedene SQL-Server verwenden.Ich habe die Daten zusammengeführt und festgestellt, dass ich 15 Millionen Guids und 7 Duplikate hatte.

Leitlinien sind statistisch eindeutig.Die Wahrscheinlichkeit, dass zwei verschiedene Clients dieselbe Guid generieren, ist verschwindend gering (vorausgesetzt, es liegen keine Fehler im Guid-Generierungscode vor).Sie können sich genauso gut Sorgen machen, dass Ihr Prozessor aufgrund einer kosmischen Strahlung ausfällt, und heute entscheiden, dass 2+2=5 ist.

Mehrere Threads, die neue Guids zuweisen, erhalten eindeutige Werte, aber Sie sollten sicherstellen, dass die Funktion, die Sie aufrufen, Thread-sicher ist.In welcher Umgebung ist das?

Eric Lippert hat eine sehr interessante Artikelserie über GUIDs geschrieben.

Es gibt auf der Bestellung 2³⁰ PC-Computer in der Welt (und natürlich viele Handgeräte oder Nicht-PC-Computergeräte, die mehr oder weniger die gleichen Rechenleistung haben, diese jedoch ignorieren).Nehmen wir an, dass wir all diese PCs der Welt auf die Aufgabe des Erstellens von Richtlinien einsetzen.wenn jeder einzelne beispielsweise 2 erzeugen kann²⁰ Guids pro Sekunde nach nur etwa 2⁷² Sekunden -- Einhundertfünfzig Billionen Jahre -- Du wirst eine haben sehr hoch Chance, eine Kollision mit Ihrer spezifischen GUID zu generieren.Und die Chancen der Kollision werden nach nur dreißig Billionen Jahren ziemlich gut.

Theoretisch nein, sie sind nicht einzigartig.Es ist möglich, immer wieder eine identische Anleitung zu generieren.Allerdings ist die Wahrscheinlichkeit dafür so gering, dass man davon ausgehen kann, dass es sich um Einzelfälle handelt.

Ich habe schon einmal gelesen, dass die Wahrscheinlichkeit so gering ist, dass Sie sich wirklich über etwas anderes Gedanken machen sollten – etwa einen spontanen Serverabsturz oder andere Fehler in Ihrem Code.Das heißt, gehen Sie davon aus, dass es einzigartig ist, und bauen Sie keinen Code ein, um Duplikate zu „fangen“ – verbringen Sie Ihre Zeit mit etwas, das wahrscheinlicher ist (z. B. irgendetwas anders).

ICH einen Versuch gemacht um meinem Blog-Publikum (nicht technisch versierte Familienmitglieder) den Nutzen von GUIDs zu beschreiben.Von dort aus (über Wikipedia) die Wahrscheinlichkeit, eine doppelte GUID zu generieren:

1 in 2^128
1 In 340 Undecillion (Mach dir keine Sorgen, Undecillion ist nicht auf dem Quiz)
1 in 3,4 × 10^38
1 zu 340.000.000.000.000.000.000.000.000.000.000.000.000

Keiner scheint die tatsächliche Berechnung der Eintrittswahrscheinlichkeit zu erwähnen.

Nehmen wir zunächst an, dass wir den gesamten 128-Bit-Speicherplatz nutzen können (Guid v4 verwendet nur 122 Bit).

Wir wissen, dass die allgemeine Wahrscheinlichkeit, KEIN Duplikat zu erhalten, hoch ist n Picks ist:

(1-1/2¹²⁸)(1-2/2¹²⁸)...(1-(n-1)/2¹²⁸)

Denn 2¹²⁸ ist viel viel größer als n, wir können dies wie folgt annähern:

(1-1/2¹²⁸)^n(n-1)/2

Und weil wir davon ausgehen können n viel, viel größer als 0 ist, können wir das wie folgt annähern:

(1-1/2¹²⁸)^{n^2/2}

Jetzt können wir dies mit der „akzeptablen“ Wahrscheinlichkeit gleichsetzen, sagen wir 1 %:

(1-1/2¹²⁸)^{n^2/2} = 0.01

Was wir lösen n und bekomme:

n = sqrt(2* log 0,01 / log (1-1/2¹²⁸))

Welcher Wolfram Alpha sein wird 5.598318 × 10¹⁹

Um diese Zahl ins rechte Licht zu rücken, nehmen wir 10.000 Maschinen, jede mit einer 4-Kern-CPU, 4 GHz und 10.000 Zyklen, um eine Guid zu generieren und nichts anderes zu tun.Es würde dann etwa 111 Jahre dauern, bis sie ein Duplikat erzeugen.

Aus http://www.guidgenerator.com/online-guid-generator.aspx

Was ist eine GUID?

GUID (oder UUID) ist ein Akronym für „Globally Unique Identifier“ (oder „Universally Unique Identifier“).Es handelt sich um eine 128-Bit-Ganzzahl, die zur Identifizierung von Ressourcen verwendet wird.Der Begriff GUID wird im Allgemeinen von Entwicklern verwendet, die mit Microsoft-Technologien arbeiten, während UUID überall sonst verwendet wird.

Wie eindeutig ist eine GUID?

128 Bit sind groß genug und der Generierungsalgorithmus ist einzigartig genug, dass bei der Generierung von 1.000.000.000 GUIDs pro Sekunde über ein Jahr hinweg die Wahrscheinlichkeit eines Duplikats nur 50 % beträgt.Oder wenn jeder Mensch auf der Erde 600.000.000 GUIDs generieren würde, bestünde die Wahrscheinlichkeit eines Duplikats nur bei 50 %.

MSDN:

Es besteht eine sehr geringe Wahrscheinlichkeit, dass der Wert der neuen Guid nur aus Nullen besteht oder mit einem anderen Guid übereinstimmt.

Wenn Ihre Systemuhr richtig eingestellt ist und nicht umgedreht ist und Ihre Netzwerkkarte über einen eigenen MAC verfügt (d. h.Sie haben keinen benutzerdefinierten MAC festgelegt) und Ihr NIC-Anbieter hat MACs nicht recycelt (was er nicht tun sollte, was aber bekanntermaßen vorkommt), und wenn die GUID-Generierungsfunktion Ihres Systems ordnungsgemäß implementiert ist, wird Ihr System dies tun Generieren Sie niemals doppelte GUIDs.

Wenn jeder auf der Welt, der GUIDs generiert, diese Regeln befolgt, sind Ihre GUIDs global eindeutig.

In der Praxis ist die Zahl der Personen, die gegen die Regeln verstoßen, gering, und es ist unwahrscheinlich, dass ihre GUIDs „entkommen“.Konflikte sind statistisch unwahrscheinlich.

Ich habe eine doppelte GUID festgestellt.

Ich verwende den Desktop-Scanner Neat Receipts und er wird mit proprietärer Datenbanksoftware geliefert.Die Software verfügt über eine Funktion zur Synchronisierung mit der Cloud, und bei der Synchronisierung wurde immer wieder eine Fehlermeldung angezeigt.Ein Blick auf die Protokolle brachte die beeindruckende Zeile zum Vorschein:

"errors":[{"code":1,"message":creator_guid:ist bereits genommen "," Guid ":" C83E5734-D77A-4B09-B8C1-9623CAC7B167 "}]}

Ich war etwas ungläubig, aber als ich einen Weg in meine lokale Neatworks-Datenbank fand und den Datensatz mit dieser GUID löschte, trat der Fehler tatsächlich nicht mehr auf.

Um Ihre Frage mit anekdotischen Beweisen zu beantworten: Nein.Ein Duplikat ist möglich.Es ist jedoch wahrscheinlich, dass der Grund, warum es passierte, nicht auf Zufall zurückzuführen war, sondern darauf, dass die übliche Praxis in irgendeiner Weise nicht eingehalten wurde.(Ich habe einfach nicht so viel Glück) Ich kann es jedoch nicht mit Sicherheit sagen.Es ist nicht meine Software.

Ihr Kundensupport war äußerst zuvorkommend und hilfsbereit, aber sie müssen dieses Problem noch nie zuvor gehabt haben, denn nach mehr als drei Stunden Telefonat fanden sie keine Lösung.(FWIW, ich bin sehr beeindruckt von Neat, und dieser Fehler, so frustrierend er auch sein mag, hat meine Meinung über ihr Produkt nicht geändert.)

Ist eine GUID in 100 % der Fälle eindeutig?

Keine Garantie, da es mehrere Möglichkeiten gibt, ein solches zu generieren.Sie können jedoch versuchen, die Chance zu berechnen, zwei identische GUIDs zu erstellen, und Sie erhalten die Idee:Eine GUID hat 128 Bit, also sind es 2¹²⁸ unterschiedliche GUIDs – viel mehr als es Sterne im bekannten Universum gibt.Lies das Wikipedia-Artikel für mehr Details.

GUID-Algorithmen werden normalerweise gemäß der v4-GUID-Spezifikation implementiert, bei der es sich im Wesentlichen um eine pseudozufällige Zeichenfolge handelt.Leider fallen diese in die Kategorie „wahrscheinlich nicht eindeutig“, 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 hin zu wahrscheinlicher Nichteindeutigkeit reichen.“

Die pseudozufälligen Eigenschaften von V8s JavaScript Math.random() sind hinsichtlich der Einzigartigkeit SCHRECKLICH, wobei Kollisionen oft schon nach ein paar tausend Iterationen auftreten, aber V8 ist nicht der einzige Übeltäter.Ich habe reale GUID-Kollisionen sowohl bei PHP- als auch bei Ruby-Implementierungen von v4-GUIDs gesehen.

Da es immer üblicher wird, die ID-Generierung über mehrere Clients und Servercluster hinweg zu skalieren, hat die Entropie einen großen Einfluss – die Wahrscheinlichkeit, dass derselbe Zufallsstartwert zum Generieren einer ID verwendet wird, steigt (Zeit wird oft als Zufallsstartwert verwendet). in Pseudozufallsgeneratoren) und GUID-Kollisionen eskalieren von „wahrscheinlich nicht eindeutig“ zu „sehr wahrscheinlich, dass sie viel Ärger 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 werden der Zeitstempel, ein In-Memory-Client-Zähler, ein Client-Fingerabdruck und zufällige Zeichen verwendet.Durch die Kombination dieser Faktoren entsteht eine additive Komplexität, die besonders kollisionsresistent ist, selbst wenn Sie sie über mehrere Hosts hinweg skalieren:

http://usecuid.org/

Ich habe festgestellt, dass die GUIDs bei Multithread-/Multiprozess-Unit-Tests (auch?) nicht eindeutig waren.Ich vermute, dass das, wenn alle anderen Parameter gleich bleiben, mit dem identischen Seeding (oder fehlenden Seeding) von Pseudozufallsgeneratoren zu tun hat.Ich habe es zum Generieren eindeutiger Dateinamen verwendet.Ich fand, 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 es eindeutig sein muss.Wenn sich die Anzahl der GUIDs der Unendlichkeit nähert, nähert sich die Wahrscheinlichkeit für doppelte GUIDs 100 %.

Im allgemeineren Sinne wird dies als „Geburtstagsproblem“ oder „Geburtstagsparadoxon“ bezeichnet.Wikipedia hat eine ziemlich gute Übersicht unter:Wikipedia – Geburtstagsproblem

Ganz grob ausgedrückt ist die Quadratwurzel aus der Größe des Pools ein grober Näherungswert dafür, wann Sie mit einer 50-prozentigen Wahrscheinlichkeit eines Duplikats rechnen können.Der Artikel enthält eine Wahrscheinlichkeitstabelle der Poolgröße und verschiedener Wahrscheinlichkeiten, einschließlich einer Zeile für 2^128.Bei einer Kollisionswahrscheinlichkeit von 1 % würde man also erwarten, dass 2,6*10^18 128-Bit-Zahlen zufällig ausgewählt werden.Eine Chance von 50 % erfordert 2,2*10^19 Tipps, während SQRT(2^128) 1,8*10^19 beträgt.

Das ist natürlich nur der Idealfall eines wirklich zufälligen Prozesses.Wie andere bereits erwähnt haben, hängt vieles davon ab zufällig Aspekt – wie gut sind der Generator und das Saatgut?Es wäre schön, wenn es Hardware-Unterstützung gäbe, die diesen Prozess unterstützt und sicherer wäre, mit der Ausnahme, dass alles gefälscht oder virtualisiert werden kann.Ich vermute, dass dies der Grund sein könnte, warum MAC-Adressen/Zeitstempel nicht mehr berücksichtigt werden.

Die Antwort von „Ist eine GUID zu 100 % eindeutig?“ ist einfach "NEIN" .

Wenn Sie eine 100 %ige Eindeutigkeit der GUID wünschen, gehen Sie wie folgt vor.
1. GUID generieren
2. Überprüfen Sie, ob diese GUID in Ihrer Tabellenspalte vorhanden ist, in der Sie nach Eindeutigkeit suchen
3. Wenn vorhanden, gehen Sie zu Schritt 1, andernfalls zu Schritt 4
4. Verwenden Sie diese GUID als eindeutig.

Der schwierigste Teil besteht nicht darin, eine duplizierte Guid zu generieren.

Der schwierigste Teil besteht darin, eine Datenbank zu erstellen, in der alle generierten Dateien gespeichert werden, um zu überprüfen, ob sie tatsächlich dupliziert sind.

Aus WIKI:

Beispielsweise beträgt die Anzahl der zufälligen UUIDs der Version 4, die generiert werden müssen, um eine 50-prozentige Wahrscheinlichkeit für mindestens eine Kollision zu haben, 2,71 Trillionen und wird wie folgt berechnet:

Geben Sie hier eine Bildbeschreibung ein

Diese Zahl entspricht der Generierung von 1 Milliarde UUIDs pro Sekunde über einen Zeitraum von etwa 85 Jahren, und eine Datei mit so vielen UUIDs und 16 Bytes pro UUID wäre etwa 45 Exabyte groß und damit um ein Vielfaches größer als die derzeit größten Datenbanken, die es gibt in der Größenordnung von Hunderten von Petabyte

GUID steht für Global Unique Identifier

In Kürze:(Der Hinweis liegt im Namen)

Im Detail:GUIDs sind so konzipiert, dass sie eindeutig sind.Sie werden mithilfe einer Zufallsmethode berechnet, die auf der Uhr des Computers und dem Computer selbst basiert. Wenn Sie viele GUIDs in derselben Millisekunde auf demselben Computer erstellen, ist es möglich, dass sie übereinstimmen, aber für fast alle normalen Vorgänge sollten sie als eindeutig betrachtet werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow