Logische Uhren: Lamport-Zeitstempel, Vektoruhren und Hybriduhren

Worum es geht

Lamports Arbeit von 1978 (aufgeführt auf seiner zitierten Publikationsseite) definiert die Relation "happened before" (geschah vor): Ereignis a geht b voraus, wenn beide im selben Prozess in dieser Reihenfolge auftreten, wenn a das Versenden einer Nachricht und b ihr Empfang ist, oder durch Transitivität. Eine Lamport-Uhr ist ein Zähler pro Prozess: bei jedem lokalen Ereignis erhöhen, jeder Nachricht anhängen und beim Empfang den Zähler auf das Maximum aus lokalem und empfangenem Wert plus eins setzen. Geschah a vor b, dann gilt clock(a) < clock(b); die Umkehrung gilt nicht, sodass gleiche oder nahe beieinanderliegende Zeitstempel nichts über Kausalität aussagen. Ties mit einer Prozesskennung aufzulösen ergibt eine totale Ordnung.

Eine Vektoruhr, wie im zitierten Dynamo-Paper beschrieben, ist eine Liste von (Knoten, Zähler)-Paaren, die jeder Version eines Objekts angehängt wird. Der Vergleich zweier Vektoren zeigt, ob eine Version von der anderen abstammt oder ob sie auf parallelen Zweigen liegen; so erkennt Dynamo widersprüchliche Schreibvorgänge, um sie beim Lesen abzugleichen.

Hybride logische Uhren (HLC) kombinieren beide Ideen. Die zitierte Dokumentation von CockroachDB beschreibt eine HLC als eine physische Komponente nahe der lokalen Systemzeit plus eine logische Komponente, die Ereignisse mit demselben physischen Wert unterscheidet, sodass die HLC-Zeit stets grösser oder gleich der Systemzeit ist und kausal verknüpfte Ereignisse dennoch ordnet.

Warum es wichtig ist

"Last Writer Wins" nach Zeitstempel verwirft stillschweigend Aktualisierungen, wenn Uhren stärker abweichen als die Zeit zwischen zwei Schreibvorgängen. Replizierte Daten, offlinefähige Clients und Multi-Region-Deployments stossen alle auf dieses Problem.

So wird es angewendet

• Jedem veränderlichen Datensatz einen Versionszähler geben, der bei jedem Schreibvorgang steigt, und ihn für optimistische Nebenläufigkeit verwenden (UPDATE ... WHERE version = $seen); das ist eine Lamport-Uhr pro Datensatz.
• In Event-Streams nach Sequenznummer innerhalb einer Partition ordnen, nicht nach dem Zeitstempel der erzeugenden Seite.
• Wo mehrere Replikate Schreibvorgänge annehmen, einen Versionsvektor pro Datensatz führen oder einen Datentyp mit definiertem Merge (ein CRDT) verwenden und Konflikte sichtbar machen, statt anhand der Systemzeit einen Gewinner zu bestimmen.
• Systemzeit-Zeitstempel für Anzeige und Aufbewahrung verwenden und die Uhrenquelle (NTP-synchronisiert oder nicht) im Design festhalten.

Stolpersteine

Vektoruhren wachsen mit der Anzahl der schreibenden Seiten und benötigen Regeln zum Kürzen (Pruning). Lamport-Uhren ordnen, können aber Gleichzeitigkeit nicht erkennen. Eine monotone Uhr auf einer Maschine sagt nichts über die Uhr einer anderen Maschine aus.