- Auf modernen Systemen, auf denen mehrere physische Kerne gleichzeitig die Uhr auslesen, überschneiden sich selbst Nanosekunden-Zeitstempel leicht; bei gleichzeitiger Messung auf 4 physischen Kernen kollidierten etwa 5 % aller Samples
- Designs, die rohe Zeitstempel wie eindeutige Kennungen verwenden, sind riskant; die Kollisionshäufigkeit variiert je nach Betriebssystem und Ausführungsweise
- Go speichert mit
time.Now()sowohl die absolute Zeit als auch eine relative Zeit auf Basis der monotonen Uhr, sodass sich Unterschiede zwischen aufeinanderfolgenden Aufrufen und Duplikate absoluter Zeitstempel getrennt prüfen lassen - Unter Linux stieg die Zeit in einem einzelnen Thread immer an, und die kleinste Schrittweite betrug 32 ns; werden Threads getrennt ausgeführt, wird dieselbe absolute Zeit beobachtet
- Unter Mac OS X hat die absolute Zeit eine Mikrosekunden-Auflösung, weshalb es deutlich mehr Kollisionen gibt; selbst in einem einzelnen Thread wurde häufig beobachtet, dass die monotone Uhr nicht anstieg
Kollisionshäufigkeit bei parallelem Auslesen
- Die Kernfrage ist, wie häufig Nanosekunden-Zeitstempel-Kollisionen auf modernen Systemen tatsächlich auftreten
- Wenn auf 4 physischen Kernen gleichzeitig die Uhr ausgelesen wird, kollidieren etwa 5 % aller Samples
- Selbst wenn auf einem 4-Kern-System nur 2 Threads verwendet werden, überschneiden sich etwa 2 % der Zeitstempel
- Daher ist die Annahme nicht sicher, dass sich allein aus rohen Nanosekunden-Zeitstempeln eine eindeutige ID erzeugen lässt
Testmethode und Unterschiede zwischen Betriebssystemen
- Das Testprogramm wurde in Go geschrieben
- Go zeichnet mit
time.Now()bei jedem Aufruf absolute Zeit und relative Zeit auf Basis der monotonen Uhr auf- Der Test vergleicht die relativen Differenzen zwischen aufeinanderfolgenden Zeitstempeln
- Zusätzlich wird auf Duplikate der absoluten Zeitstempel selbst geprüft
-
Linux
- In einem einzelnen Thread nahmen absolute Zeit und monotone Zeit immer zu
- Die kleinste Schrittweite auf dem gemessenen System betrug 32 ns
- Zwischen Threads trat in etwa 5 % der Fälle auf, dass die absolute Zeit exakt mit der eines anderen Threads übereinstimmte
-
Mac OS X
- Da die absolute Zeit nur Mikrosekunden-Auflösung hat, treten im selben Test sehr viele Kollisionen auf
- Selbst in einem einzelnen Thread wurde häufig beobachtet, dass die monotone Uhr nicht anstieg
1 Kommentare
Hacker-News-Kommentare
Die Verwendung von IDs, die Zeitkomponente und Sequenznummer kombinieren, ist eine Möglichkeit, solche Probleme zu vermeiden
Zum Beispiel hat UUIDv7 eine Zeitkomponente in Millisekunden, ein Feld, das für jedes Ereignis innerhalb derselben Millisekunde hochgezählt wird, und genügend Zufallsbits, um die Wahrscheinlichkeit von Kollisionen zwischen auf verschiedenen Maschinen erzeugten IDs astronomisch klein zu machen
Natürlich ist die Bitzahl endlich, sodass bei zu vielen Ereignissen im selben Zeitfenster die Sequenz überlaufen kann, Kollisionen zwischen Maschinen tatsächlich auftreten können und wegen der Inkrement-Operation eine CPU-Synchronisation nötig sein kann, was die Ereigniserzeugungsrate begrenzen könnte
Trotzdem funktioniert UUIDv7 in realistischen Produktionsgrößenordnungen sehr gut
Im Internet finde ich nicht gut heraus, wie alt UUIDv7 eigentlich ist
Sie verbraucht nur Bits in der UUID und trägt kaum zur Entropie bei
Es ist zwar noch nicht im Kern enthalten, aber es gibt mehrere hervorragende pg-Erweiterungen, die uuidv7 bereitstellen, zusätzlich zur direkten Nutzung auf Anwendungsebene
Mehr noch als nur schwer zu verstehen: Es ist sogar sehr schwierig, sie mit bloßem Auge voneinander zu unterscheiden
Deshalb kann in manchen Fällen ein Bezeichner nützlich sein, der außer dem unbedingt Nötigen keinerlei Information oder Rauschen enthält
Ein überlaufender Inkrementzähler irgendeiner Form und ein paar Zufallsbits reichen im Allgemeinen aus, und wenn man es gut macht, geht beides ohne Verzweigungen
Dazu passend: Ich war früher Programmmanager für das Security Event Log von Windows
Wenn auf Multicore-Systemen Dinge gleichzeitig oder in sehr kurzem Abstand passieren, kann das Thread-Scheduling die beobachteten Ergebnisse stark beeinflussen
Zum Beispiel kann ein Thread-Quantum enden, bevor der Systemaufruf zum Holen des Zeitstempels erreicht wird oder bevor der Puffer übergeben wird, in den das Ereignis eingereiht wird, damit später ein Zeitstempel gesetzt werden kann
Tatsächlich war es auf Multiprozessorsystemen unter Windows in den 2000er-Jahren sehr häufig, dass Einträge im Ereignisprotokoll in vertauschter Reihenfolge erschienen, und auch die Genauigkeit der Log-Zeitstempel durfte man nicht zu fein interpretieren
Die sichere Untergrenze lag praktisch bei 1 Sekunde, und soweit ich mich erinnere, schnitten einige Komponenten Zeitstempel ab oder rundeten sie
Wenn man eine eindeutige Kennung braucht, nimmt man einfach eine Version-4-UUID, also eine zufällige UUID
Die Kollisionswahrscheinlichkeit ist ungefähr so groß wie die Wahrscheinlichkeit, dass wegen Quantenfluktuationen plötzlich ein ausgewachsener Dinosaurier im Schlafzimmer auftaucht
Etwas ernster gesagt ist, wenn man es verwenden kann, ein altmodischer Inkrementwert wahrscheinlich am besten
Er ist schnell und günstig, besonders in Datenbanken, aber es gibt Privatsphäre- und Sicherheitsprobleme, weil sich aus dem ID-Wert Informationen ableiten lassen
In solchen Fällen oder wenn man mit verteilten Systemen arbeitet, sind UUIDs besser
Selbst wenn die Auflösung in Nanosekunden angegeben ist, frage ich mich, wie hoch die tatsächliche Präzision der Computeruhr ist
Ich kann mir schwer vorstellen, dass sie wirklich im Nanosekundenbereich liegt, und das erinnert mich daran, wie ich in Physikpraktika Studierenden immer wieder einschärfte, dass die kleinste angezeigte Ziffer eines Messgeräts nicht dasselbe ist wie dessen Genauigkeit
Das heißt aber nicht, dass sie auf diesem Niveau genau ist, und in Multicore-Systemen sind die Uhren zwischen den Kernen möglicherweise nicht auf diesem Niveau synchronisiert
ARMv8 garantiert, dass die Uhr mit mindestens 1 GHz hochzählt, aber bei Intel und älteren ARM-Systemen ist es komplizierter
Die BEAM VM von Erlang/Elixir macht diesen Unterschied sehr deutlich sichtbar. Es geht um die Unterscheidung zwischen monoton steigend und strikt monoton steigend
https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
„In einer Sequenz monoton steigender Werte ist jeder Wert mit einem Vorgänger größer oder gleich diesem Vorgänger.“
Das lässt sich über die Funktion https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 verwenden
https://www.erlang.org/doc/apps/erts/time_correction.html#st...
„In einer Sequenz strikt monoton steigender Werte ist jeder Wert mit einem Vorgänger größer als dieser Vorgänger.“
Strikt monotone Werte bedeuten irgendeine Form von Synchronisation oder Abstimmung und verursachen bei vielen parallelen Prozessen Leistungskosten
Diese Funktion wird über https://www.erlang.org/doc/man/erlang.html#unique_integer-1 bereitgestellt, und auch die Dokumentation warnt davor, dass strikt monoton steigende Werte naturgemäß teuer in der Erzeugung sind und schlecht skalieren, weshalb man den Modifikator
monotonicnur übergeben sollte, wenn man ihn wirklich brauchtAnders gesagt: ähnlich wie UUIDv1 oder https://en.wikipedia.org/wiki/Snowflake_ID
Einen strikt monotonen globalen Bezeichner braucht man wirklich nur, wenn man einen sofort konsistenten Gewinner bei erstem/letztem Schreibzugriff benötigt
Wenn man stattdessen einen letztlich konsistenten Gewinner bei erstem/letztem Schreibzugriff verwenden kann, zum Beispiel wenn Schreibereignisse in einem Event Store oder einer Queue landen, die über IDs linearisiert wird, und man bei „gleichzeitigen“ Schreibvorgängen alles außer dem mit der höchsten ID-Priorität während der Verarbeitung oder beim Lesen verwerfen kann, würde ich zuerst ein komprimiertes Paar
(nodeID, seq)in Betracht ziehenWenn eine globale Reihenfolge von Ereignissen nötig ist, lohnt sich besonders eine Snowflake-ID-Form wie
(timestampMajor, nodeID, timestampMinor, seq)FreeBSD hat kein
CLOCK_MONOTONIC_RAW; nachdem ich es auskommentiert hatte, sah alles okay ausIch hatte verstanden, dass bei Kollisionen einige Zeitstempel wiederholt werden müssten, aber ich kann einfach keine Kollisionen erzeugen
clock_getres(CLOCK_REALTIME, ...)=1 ns,clock_getres(CLOCK_MONOTONIC, ...)=1 ns, und auch bei 30 Samples stieg der Unterschied im Bereich von ungefähr 29 bis 71 ns weiter anLetztlich scheint es doch irgendwann auf eine Frage der Instruction Set Architecture hinauszulaufen
Eine CPU mit 3 GHz bekommt 3 Taktzyklen pro Nanosekunde
Mit Compiler-Optimierungen scheint es gut möglich, dass Assembleraufrufe zum Lesen des Uhrenregisters direkt hintereinander landen
Wenn aufeinanderfolgende
time.Now()-Aufrufe innerhalb von 3 Taktzyklen passieren, ist es dann wirklich fair, tatsächlich einzigartige Nanosekundenpräzision zu erwarten?Auch wenn Kollisionen eher selten sind, ist ein paar Mal pro Tag deutlich schlechter als „passiert fast nie“
Das erinnert an die Legende über Lotus Notes
Früher sollen dort Zeitstempel mit 1-Sekunden-Auflösung als eindeutige IDs verwendet worden sein
Bei einer Kollision wurde einfach 1 Sekunde addiert, und am Ende gab es so viele Kollisionen, dass Einträge Zeitstempel aus der Zukunft bekamen
Absolut exakte Zeit ist ein Sicherheitsproblem
CPU-Designer haben schon seit sehr langer Zeit, etwa seit den DEC-Alpha-Tagen, absichtlich Clock-Jitter eingebaut, um vollständige Vorhersagbarkeit zu verhindern
Auch auf x86 müsste man wohl sehen können, dass die Zeitdifferenzen nicht exakt gleich sind, wenn man die Ausführung 3- oder 4-mal durchführt, die Werte in Registern speichert und sie erst am Ende ausgibt
Bei der Suche finde ich nicht viel; falls damit sogar frühe x86-Modelle gemeint sind, wäre es überraschend, dass man das Sicherheitsproblem präziser Uhren schon so früh erkannt hat
Persönlich hätte ich vor diesem Millennium wohl nichts von einem solchen Problem gewusst und vermutet, dass beobachtbarer Clock-Jitter durch Dinge wie Interrupts erklärt werden kann
Nicht dass ich glaube, dass es falsch ist, ich würde nur gern mehr darüber wissen
Ich habe zu viele Leute gesehen, die von Kollisionen bei Millisekunden- oder Mikrosekunden-Zeitstempeln überrascht waren
Der einprägsamste und unerquicklichste Fall ist, wenn ein Zeitstempel aus zwei Systemaufrufen zusammengesetzt wird
Einer liest die höherwertigen Stellen, der andere die niederwertigen; wenn wegen Prozesspräemption nach dem Lesen der höherwertigen Stellen die niederwertigen von 99x auf 00x springen, kann man einen Zeitstempel erzeugen, der vor dem Zeitpunkt liegt, der die Erzeugung der Entität überhaupt ausgelöst hat
Das lässt manchen Code spektakulär kaputtgehen, und ich habe mindestens zweimal Endlosschleifen gesehen
Wenn man sich das nicht als etwas einprägt, das man immer vermeiden muss, bestehen Tests zu 99,5 %, und dann muss jemand mit sehr gutem Pattern-Matching-Gespür bemerken, dass „derselbe Test anderthalb Monate lang einmal pro Woche rot wurde“
Das ist viel zu lange, als dass so eine Logikbombe ungefixt in CI/CD-Code überleben sollte