Warum NornicDB auf einen eigenen monotonen Zähler für MVCC setzt

NornicDB, eine moderne Datenbanklösung mit Fokus auf effiziente Transaktionsverwaltung, setzt bei der Implementierung ihrer Multiversion Concurrency Control (MVCC) auf einen selbst entwickelten monotonen Zähler. Statt sich auf die Standardfunktionen von Go oder Linux zu verlassen, nutzt das System ein Paar aus (CommitTimestamp, CommitSequence), wobei der CommitTimestamp zwar aus time.Now().UnixNano() stammt, die eigentliche Reihenfolge jedoch über einen atomaren uint64-Zähler bestimmt wird. Diese Entscheidung basiert auf drei zentralen Problemen mit wall-clock-basierten Timestamps:

• Nicht-monotone Wall-Clock-Zeit: Die Linux-Funktion clock_gettime(CLOCK_REALTIME) kann durch NTP-Korrekturen rückwärts springen oder bei Live-Migrationen von virtuellen Maschinen abrupt angepasst werden.
• Parser-Geschwindigkeit übertrifft Clock-Auflösung: Ein einfacher Cypher-Befehl wie MATCH (n) RETURN n wird in nur 39 Nanosekunden verarbeitet – zu schnell, um durch die Auflösung von UnixNano() zuverlässig unterschieden zu werden.
• Go’s monotone Uhr ist nicht global: Die interne Uhr von Go ist pro time.Time-Instanz definiert und wird bei der Umwandlung in UnixNano() entfernt, was zu inkonsistenten Vergleichen führt.

Das CI-Problem, das die Lösung erzwang

Ein wiederkehrendes CI-Fehlerbild in TestExecuteCypher_SetInvalidatesManagedEmbeddings brachte die Entwickler von NornicDB dazu, ihre MVCC-Logik zu überdenken. Der Fehler trat auf, obwohl keine konkurrierenden Schreiboperationen vorlagen:

conflict: node 0x7f3a... changed after transaction start

Die Fehlermeldung zeigte an, dass die Transaktionsisolation eine Konfliktsituation erkannt hatte, obwohl die Leseoperation nach dem Commit der vermeintlich konkurrierenden Transaktion gestartet worden war. Die Ursache lag in der falschen Annahme, dass CommitTimestamp-Werte eine globale Monotonie garantieren könnten.

Warum time.Now().UnixNano() für globale Reihenfolgen ungeeignet ist

Konkrete Probleme mit der Systemzeit

Die Funktion time.Now() in Go nutzt letztlich clock_gettime(CLOCK_REALTIME) auf Linux-Systemen. Dieser Mechanismus unterliegt mehreren potenziellen Störfaktoren:

• NTP-Slew-Effekte: Das Betriebssystem passt die Systemzeit kontinuierlich an (bis zu 500 ppm), um sie an eine Referenzzeit anzugleichen. Dadurch können selbst benachbarte Timestamps rückwärts springen.
• NTP-Stepping: Bei zu großen Abweichungen wird die Uhr abrupt angepasst, was zu Zeitrücksprüngen führt.
• PTP-Korrekturen in Containern: Virtuelle Maschinen oder Container können durch Precision Time Protocol (PTP) beeinflusst werden.
• Live-Migration von VMs: Beim Verschieben einer virtuellen Maschine springt die Systemzeit auf die des Ziel-Hosts.
• TSC-Skew zwischen CPU-Kernen: Moderne CPUs nutzen pro Kern einen eigenen Time Stamp Counter (TSC). Bei der Umrechnung in UnixNano() können unterschiedliche Kerne leicht abweichende Werte liefern.

Ein konkretes Szenario, das die Schwäche von wall-clock-basierten Timestamps demonstriert:

1. Eine Transaktion A schreibt einen Datensatz mit Timestamp 1_700_000_000_000_000_100.
2. Nach 5 Mikrosekunden wendet der Kernel eine NTP-Korrektur an, die die Uhr um 500 Nanosekunden zurückstellt.
3. Eine Transaktion B beginnt und erfasst den Timestamp 1_700_000_000_000_000_050.
4. Die Transaktionsisolation erkennt einen Konflikt, obwohl kein zweiter Schreibvorgang stattfand.

Die Parser-Geschwindigkeit als entscheidender Faktor

Die Benchmarks von NornicDB zeigen, dass der eigene Parser extrem schnell ist – schneller als die Auflösung von UnixNano():

BenchmarkParserValidationIsolation/Nornic/simple_match-16       30,066,961    ops/s @ 39.09 ns/op
BenchmarkParserValidationIsolation/Nornic/match_with_label-16    21,996,284    ops/s @ 53.20 ns/op
BenchmarkParserValidationIsolation/Nornic/create_node-16         17,062,600    ops/s @ 70.40 ns/op

Ein einfacher MATCH (n) RETURN n-Befehl wird in nur 39 Nanosekunden verarbeitet, während herkömmliche Parser wie ANTLR um den Faktor 120 langsamer sind und deutlich mehr Speicher allozieren:

BenchmarkParserValidationIsolation/ANTLR/simple_match-16         494,116      ops/s @ 4,725 ns/op
BenchmarkParserValidationIsolation/ANTLR/create_node-16           425,192      ops/s @ 5,649 ns/op

Diese Geschwindigkeit ist kein Zufall, sondern der Grund, warum UnixNano() als globaler Reihenfolge-Indikator versagt. Langsamere Parser würden Schreiboperationen natürlich weiter voneinander trennen, doch bei einer Verarbeitungsrate von Millionen Operationen pro Sekunde kommt es unweigerlich zu Kollisionen innerhalb desselben Timestamp-Bereichs.

Mathematische Berechnung der Kollisionen

Die Wahrscheinlichkeit, dass zwei Schreiboperationen denselben Timestamp erhalten, lässt sich wie folgt abschätzen:

P(collision) ≈ 1 - e^(-Q·R / 1e9)

Dabei steht Q für die Anzahl der Schreiboperationen pro Sekunde und R für die effektive Auflösung der Systemuhr (typischerweise zwischen 1 und 40 Nanosekunden). Bei einer Million Schreiboperationen pro Sekunde und einer Auflösung von 20 Nanosekunden ergibt sich eine Kollisionswahrscheinlichkeit von etwa 1,98 % – also fast zwei Kollisionen pro Sekunde. Die Verwendung eines atomaren Zählers eliminiert dieses Problem vollständig, da er eine garantierte, globale Monotonie sicherstellt.

Der atomare uint64-Zähler von NornicDB bietet zudem eine enorme Skalierbarkeit: Selbst bei einer Rate von einer Milliarde Schreiboperationen pro Sekunde würde es etwa 584 Jahre dauern, bis der Zähler überläuft. Diese Lösung ist nicht nur zuverlässiger als wall-clock-basierte Ansätze, sondern auch deutlich effizienter als komplexe Synchronisationsmechanismen.

Die Entscheidung für einen eigenen monotonen Zähler unterstreicht, wie wichtig es ist, Systemzeit nicht als alleinige Grundlage für kritische Abläufe zu nutzen – insbesondere in Hochgeschwindigkeitsumgebungen, in denen Performance und Konsistenz gleichermaßen entscheidend sind.