Eindeutige IDs im kosmischen Maßstab

• Untersucht wird, wie man Geräten oder Objekten absolut kollisionsfreie IDs zuweist, wobei zufällige (random) und deterministische Ansätze verglichen werden
• Beim zufälligen Ansatz lässt sich die Kollisionswahrscheinlichkeit mit ausreichend vielen Bits praktisch auf 0 senken; es gibt verschiedene Größenordnungen von UUID (122 Bit) bis zur gesamten Rechengrenze des Universums (798 Bit)
• Für deterministische Ansätze werden mehrere Schemata vorgeschlagen, darunter zentraler Zähler, delegierte Hierarchie (Dewey), binärer Baum (Binary) und Token, und die Wachstumseigenschaften der ID-Länge werden per Simulation analysiert
• Außerdem wird mathematisch bewiesen, dass alle deterministischen Schemata lineares Wachstum im Worst Case nicht vermeiden können
• Im Ergebnis zeigt sich: Auch bei Expansion im kosmischen Maßstab ist die praktikable und effiziente Methode die Erzeugung zufälliger IDs; deterministische Ansätze sind ineffizient

---

Die Notwendigkeit eindeutiger IDs und die Problemstellung

• Objektidentifikation ist die Grundlage aller Systeme in Fertigung, Logistik, Kommunikation, Sicherheit usw.; bei großer Skalierung ist die Vergabe duplikatfreier IDs eine Kernaufgabe
• Selbst wenn sich die Menschheit auf galaktische Größenordnungen ausdehnt, wird ein ID-System ohne Duplikate benötigt
• Die Fragestellung lautet: „Wie kann man IDs erzeugen, die absolut nie doppelt vorkommen?“

Zufälliger (Random-)Ansatz

• Die einfachste Methode ist die Auswahl einer zufälligen Zahl
  • Sie kann überall ohne zentrale Verwaltung oder Synchronisierung erzeugt werden
• Die Kollisionswahrscheinlichkeit lässt sich durch mehr Bits steuern und auf praktisch 0 absenken
• Bei UUID (122 Bit) ist bei etwa $2^{61}$ erzeugten IDs mit Kollisionen zu rechnen
• Berücksichtigt man die gesamte Rechengrenze des Universums (10¹²⁰ Operationen), werden 798 Bit benötigt
  • Auf Atomebene (10⁸⁰ Stück) sind es 532 Bit, für 1-g-Nanobots (10⁵⁶ Stück) 372 Bit
• Entscheidend ist echte Zufälligkeit; empfohlen werden CSPRNGs oder Quanten-Zufallsquellen
  • Gewöhnliche Seeds oder konstante IDs (z. B. all-zero) müssen ausgeschlossen werden

Deterministischer Ansatz

• Beim zentralen Zähler vergibt ein einzelner Server IDs der Reihe nach
  • Wegen Erreichbarkeitsproblemen wird eine Delegationsstruktur zwischen Satelliten und Geräten (Dewey) vorgeschlagen
• Das Dewey-Schema: hierarchische IDs in der Form A.B.C, dargestellt mit Elias-Omega-Codierung
  • Je nach Baumstruktur ergibt sich logarithmisches oder lineares Wachstum
• Das Binary-Schema teilt den ID-Raum als binären Baum auf und ist in manchen Fällen effizienter als Dewey
• 2-adische Bewertung (2-Adic Valuation) garantiert mathematische Eindeutigkeit und ist eine Variante von Binary
• Das Token-Schema zeigt in Kettenstrukturen logarithmisches Wachstum, wechselt bei größerer Breite jedoch zu linearem Wachstum

Beweis der Unvermeidbarkeit linearen Wachstums

• Unter der Voraussetzung, dass alle Wege der ID-Vergabe eindeutig sein müssen, wird die Zahl möglicher Pfade berechnet
• Bei n Knoten steigt die erforderliche Zahl der IDs auf $2^{n-1}$
• Daher gilt: Die ID-Länge muss mindestens O(n) sein, also ist lineares Wachstum im Worst Case unvermeidbar
• Kein Algorithmus kann in allen Fällen logarithmisches Wachstum beibehalten

Simulation von Skalierungsmodellen

• Es wird mit verschiedenen Wachstumsmodellen experimentiert, darunter Random Recursive Tree, Preferential Attachment und Fitness Model
  • Im kleinen Maßstab (2.048 Knoten) ist Binary überlegen, Dewey und Token unterscheiden sich je nach Situation
  • Im Preferential-Modell ist Dewey am effizientesten
  • Im Fitness-Modell zeigen Dewey und Binary ähnliche Leistung
• Auch in Experimenten mit einer Million Knoten behalten Dewey und Token logarithmisches Wachstum
  • Die ID-Länge lässt sich näherungsweise als ≈ 6.55 × ln(n) ausdrücken

Modelle für Expansion im galaktischen und kosmischen Maßstab

• Interplanetare Ausbreitung wird als Wellenfront mit konstanter Geschwindigkeit modelliert
  • Jeder Planet erzeugt etwa 10⁹ IDs und breitet sich dann zum nächsten Planeten aus
• Bei einem Galaxieradius von etwa 2.121 Planeten beträgt die ID-Länge bei vollständiger Ausbreitung rund 288.048 Bit
• Berücksichtigt man auch die Ausbreitung zwischen Galaxien (etwa 7.816 Schritte), werden etwa 2,2 Milliarden Bit (281 MB) benötigt
• Deterministische Ansätze sind ineffizient; der zufällige Ansatz (unter 798 Bit) ist überwältigend effizienter

Sicherheit und weitere Überlegungen

• Um ID-Fälschung zu verhindern, kann ein signaturbasiertes Verifikationssystem eingesetzt werden
  • Bei zufälligen IDs kann der öffentliche Schlüssel als ID dienen; bei deterministischen Schemata signiert der Elternknoten den Schlüssel des Kindknotens
• Fehlerkorrekturcodes und Versionsverwaltung sind erforderlich
• Objekte, die keine ID speichern können (z. B. Planeten), werden über mehrere IDs und deren Zuordnung verwaltet
• Es wird diskutiert, ob eine ID bei Austausch von Bestandteilen bestehen bleibt, ähnlich dem Schiff des Theseus
• Verwandte Konzepte: Decentralized Identifiers (DID), Ancestry Labeling Schemes

Fazit

• Deterministische Schemata sind theoretisch interessant, aber praktisch wenig brauchbar
• Die Erzeugung zufälliger IDs ist auch im kosmischen Maßstab realistisch und effizient
• Die Kollisionswahrscheinlichkeit von IDs auf „praktisch 0“ zu senken, ist die sicherste und praktikabelste Wahl

[mammal]

Lest unbedingt den Originaltext. Er erklärt es mit Formeln und Visualisierungen aus Simulationen, sodass ich ihn mit großem Vergnügen gelesen habe.

[princox]

Zeitbasiert erzeugte IDs müsste man dann wohl als linear betrachten, oder..?
Ich sollte mir wohl erst den Originaltext ansehen. Eine interessante Geschichte.

[hmmhmmhm]

Wenn es zu einer Kollision kommt, hat man wohl kosmisch gesehen unfassbares Pech … (?)

[GN⁺]

Hacker-News-Kommentare

• Diese Analyse ist nicht ganz fair. Beim Entwurf von UUIDs wird Lokalität (locality) berücksichtigt, also die Lichtgeschwindigkeit, bei der Berechnung der Kollisionswahrscheinlichkeit jedoch ignoriert. In der Praxis wäre eine Kollision nur dann relevant, wenn zwei UUIDs nach ihrer Erzeugung in kausalen Kontakt (causal contact) geraten. Daher ist es falsch, einfach das Geburtstagsparadoxon (birthday paradox) anzuwenden. Wenn man Lokalität berücksichtigt, dürfte die benötigte UUID-Größe viel kleiner sein als die im Artikel genannten 800 Bit. Ich habe es nicht durchgerechnet, aber mehr als 256 Bit scheinen kaum nötig zu sein. Ich mag HN wirklich, weil es einer der wenigen Orte ist, an denen solche pedantisch-technischen Diskussionen ernsthaft geführt werden

  • Ich habe einmal eine Hypothese zur kosmischen Expansion gelesen, nach der sich Galaxien so weit voneinander entfernen, dass kein Informationsaustausch mehr möglich ist. Dieser Hypothese zufolge würden intelligente Lebensformen zur Sicherung ihres Überlebens zu Orten mit der höchsten Massendichte konvergieren. Am Ende könnte es vor dem Wärmetod des Universums zu einem großen Zusammentreffen außerirdischer Zivilisationen kommen. Vielleicht treten dann UUID-Kollisionen auf. Ich stelle mir vor, wie die Vogonen an jedes XML-Tag eine UUID hängen und damit die Statistik ruinieren
  • Ich habe einmal eine Kiste mit Intel-NICs bekommen, und sie hatten alle dieselbe MAC-Adresse. Ich erinnere mich noch daran, wie ich tagelang nach der Ursache gesucht habe
  • Wenn man über extrem kleine Wahrscheinlichkeiten spricht, sollte man auch die Möglichkeit berücksichtigen, dass wir die Kosmologie falsch verstehen könnten. Der Lichtkegel (light cone) ist vielleicht nicht die kausale Grenze
  • Man muss sowohl Zeit als auch Lokalität berücksichtigen. Bis Protonen zerfallen und Materie verschwindet, vergehen nur etwa 10^56 Nanosekunden
  • Diese Kritik ist zutreffend. Der Originaltext ist ein interessantes Gedankenexperiment, überschätzt das Problem aber, weil er Kausalität ignoriert. In der Praxis sind UUID-Kollisionen nur innerhalb von Systemen relevant, die tatsächlich miteinander kommunizieren. Solche Systeme sind durch den Lichtkegel begrenzt. 128 Bit reichen für Systeme aus, die die Menschheit in tausend Jahren bauen wird, und 256 Bit sind selbst für das gesamte Universum übertrieben

• Wenn man die Anzahl adressierbarer Objekte berechnet, muss man berücksichtigen, dass die Adresse jedes Objekts mindestens einmal irgendwo gespeichert werden muss. Wenn zum Speichern eines Bits Npb-Teilchen benötigt werden, sinkt die Zahl adressierbarer Objekte mit wachsender Adressbitzahl. Daher lässt sich die maximal adressierbare Anzahl mit einer Beziehung der Form Nthg = Np / (Npb * f(Ntng)) bestimmen

• Ich musste einmal argumentieren, dass eine 256-Bit-Zufalls-ID ausreicht und man keine Kollisionsprüfung braucht. Kollegen wollten zusätzliche Logik zur Kollisionsprüfung einbauen, aber ich erklärte, dass 2^256 ungefähr der Größenordnung der Zahl der Atome im beobachtbaren Universum entspricht. Ich überzeugte sie damit, dass die Wahrscheinlichkeit, dass vorher das Rechenzentrum millionenfach explodiert, höher ist. Am Ende kamen wir zu dem Schluss, dass sogar 128 Bit ausreichen

  • Wenn in einer verteilten Umgebung jedoch nicht vertrauenswürdige Akteure IDs erzeugen, muss man wegen möglicher absichtlicher Kollisionen prüfen. In einem Einzelsystem reicht dagegen ein einfacher Zähler, und bei mehreren Servern kann man mit einem geshardeten Zähler die Bereiche aufteilen
  • Tatsächlich ist die Rechnung noch einfacher. Das gesamte Datenvolumen der Menschheit liegt noch unter 1 Yottabyte. Nach dem Geburtstagsparadoxon liegt die 50%ige Kollisionswahrscheinlichkeit bei etwa 2^128 Werten. Eine 256-Bit-ID ist 32 Byte groß, also benötigt man für 2^128 * 32 Byte rund 10^16 Yottabyte. Das heißt, die Kollisionswahrscheinlichkeit ist astronomisch gering

• Es gibt eine Rechnung, nach der etwa 532 Bit nötig wären, wenn man jedem Atom eine ID geben wollte. In der Praxis möchte man aber wahrscheinlich auch Atomgruppen (z. B. Mikrochips, Autos usw.) IDs geben, also könnte es noch mehr werden

  • Tatsächlich braucht man nicht für jedes Teilchen eine eigene ID, sondern nur eine ID pro Teilchentyp. Nach den Gesetzen der Physik sind identische Teilchen nicht unterscheidbar
  • Auch wenn man Atomgruppen berücksichtigt, würden kaum zusätzliche Bits hinzukommen
  • Wären UUIDv∞ dann mindestens etwa 536 Bit? Mit Gruppen-ID oder Zeitstempel vielleicht eher 1024 Bit
  • Muss man Neutrinos jedes Mal eine neue ID geben, wenn sie oszillieren? Zum Glück reicht für Elektronen eine einzige

• Es gibt die Idee, IDs mit einem Kartendeck darzustellen. Wenn man jede der 52 Karten als Unicode-Zeichen ausdrückt, ist das gut lesbar, schwer manuell zu bearbeiten und günstig für Mustererkennung. Wenn man ein echtes Kartendeck mischt und mit der Kamera einliest, kann es auch als Zufalls-Seed dienen. Eine ähnliche Idee sind DiceKeys

  • Aber die größte Schwachstelle ist, „richtig zu mischen“

• Tolle Visualisierung und Einsicht. Ich habe Datenbanken immer um möglichst kleine zufällige Kennungen herum entworfen. Ich denke, solche universellen Identifikatoren sind praktisch die einzigen echten „goldenen Schallplatten“. In wissenschaftlichem Datenmanagement oder der Bibliothekswissenschaft wird dieses Konzept unterschätzt. Viele Probleme großer Organisationen hätten sich mit besserem Identifikator-Design lösen lassen.
  Verwandte Artikel: Identifiers Deep Dive, Trible Structure

  • Die Identität einer Entität kann auch intrinsisch (intrinsic) definiert werden. Warum reicht dann ein Konsistenzvertrag (consistency contract) nicht?

• Ich lese gerade etwa Seite 281 von Becky Chambers’ The Galaxy, and the Ground Within.
  Beispiel aus dem Buch:

  Received Message
  Encryption: 0
  From: GC Transit Authority --- Gora System (path: 487-45411-479-4)
  To: Ooli Oht Ouloo (path: 5787-598-66)
  Subject: URGENT UPDATE
  

  Ich liebe diese Reihe wirklich. Spannend finde ich die Vorstellung eines Vielvölker-Universums mit einem zentral abgestimmten Pfad-Adresssystem

  • Ein ähnliches Beispiel wäre Vernor Vinges A Fire Upon The Deep, das ich empfehlen würde. Die Art, wie intergalaktische Kommunikation dort beschriftet wird, ist interessant
  • Besonders eindrücklich war die Szene, in der man sich vor dem Konzept von Käse fürchtet. Das zweite Buch der Reihe, A Closed and Common Orbit, war das beste

• Ich habe vor Kurzem Snowflake IDs kennengelernt. Sie werden bei Twitter, Discord, Instagram, Mastodon usw. verwendet. Die IDs werden durch eine Kombination aus Zeitstempel und Zufall kompakter, und ich finde es schade, dass der Artikel das nicht behandelt.
  Siehe Snowflake-ID auf Wikipedia und Tom Scotts Video.
  Wenn man einige Bits des Snowflake-Zeitstempels durch Zufallsbits ersetzt, könnte man wohl 4 Milliarden IDs pro Sekunde erzeugen

  • Eigentlich ist Snowflake strukturell fast dasselbe wie UUID v1. Es ist nur halb so groß
  • Eine ähnliche Idee gibt es auch bei DRUUID
  • Aber es ist nahezu unmöglich, dass sich das gesamte Universum auf eine einzige Uhr einigt
  • Dieses Verfahren ähnelt auch der BSON-ID

• Ich frage mich, ob man IDs auf Basis beobachtbarer Phänomene erzeugen könnte. Durch Merkmale, die sich über Zeit und Distanz unterscheiden, ließe sich vielleicht Eindeutigkeit garantieren. Zum Beispiel kann das Sternenlichtmuster zu einem bestimmten Zeitpunkt nur von einer einzigen Person gesehen werden. Das wäre ähnlich wie bei der Nutzung von Rauschen als Entropiequelle, etwa bei einer Lava-Lampe. Wenn man ein universelles Koordinatensystem definieren könnte, dann müsste eine Kombination aus lokaler Zeit + x + y + z + Salt eine eindeutige ID ergeben

• Der Ansatz mit zufälligen UUIDs ist im Hinblick auf die Lebensdauer viel besser. Die Anzahl gleichzeitig aktiver Geräte ist begrenzt, und anders als bei baumbasierten UUIDs kann man IDs wiederverwenden, wenn Geräte ausgemustert werden. Realistisch gesehen wäre wahrscheinlich ein hybrider Algorithmus am praktikabelsten, der einen ortsbasierten Root + zufällige untergeordnete Bits kombiniert