Definition - Vector Clock

• Eigenschaften:
  • Erkennen veralteter Datenstände in verteilten Systemen
  • Erkennen von Inkonsistenzen in verteilten Systemen
• Involvierte Definitionen:
• Veranstaltung: DEDS
• Referenz: @storl2024 (KE6, NoSQL: Datenmodelle und Techniken; Teil 2.5)

⠀

Definition: Vector Clock

Als Vector Clock (auch Lamport Vector Clock) bezeichnen wir einen Mechanismus zur Verfolgung der Kausalität und der Reihenfolge von Ereignissen in verteilten Systemen.

Jeder Knoten in einem verteilten System führt einen Vektor von logischen Zeitstempeln (auch Lamport Clock), der die letzte bekannte logische Zeit jedes anderen Knotens im System speichert. Dadurch kann man feststellen, ob Ereignisse gleichzeitig aufgetreten sind, voneinander abhängen oder in welcher Reihenfolge sie passiert sind.

Die logische Zeit eines Knotens wird dabei nicht bspw. als Unix-Zeitstempel repräsentiert, sondern als Integer, das bei jedem Update um hochgezählt wird:

Seien zwei Nodes. Node hat nun eine Vector Clock . Für jeden bekannten Knoten hat diese Vector Clock einen Eintrag, als und .

• Update von einem Client:
  • Enthält der -te Node eine Transaktion , so inkrementieren wir die Vector Clock von um , also .
• Update von einem Node:
  • Enthält der -te Node eine Transaktion von dem Node und gilt weiter, dass , so passieren drei Dinge:
    1. wir inkrementieren die Vector Clock von um , also ,
    2. wir aktualisieren ,
    3. wir aktualisieren alle Einträge , für die .

Achtung: Abweichende Vorschriften im Kurs DEDS

Im Kurs DEDS werden die Vektoruhren beim Update durch einen anderen Node nicht hochgezählt (Schritt 1.).

Anmerkungen

Anmerkung

Beispiel: Vector Clock

Seien die Vector-Clocks der Knoten gegeben durch

Wir sprechen nun das folgende Beispiel durch:

Erste Transaktion

Wir starten mit einer Transaktion an dem Knoten und setzen

Dieses Update wird nun an die Knoten propagiert und wir setzen nun auch

Zweite Transaktion

Nun erhält der Knoten eine Transaktion. Wir setzen daher

Das Update wird nun an und propagiert:

Dritte Transaktion

Nun erhält der Knoten eine Transaktion. Wir setzen daher

und propagieren das Update wieder

Vierte Transaktion

Der Knoten erhält eine Transaktion. Wir setzen daher

und propagieren das Update weiter

Fünfte Transaktion und read

Der Knoten erhält eine Transaktion. Wir setzen daher

Bevor wir das Update jedoch propagieren können, erhalten Knoten und Knoten jeweils eine read-Anfrage.

Das System kann nun durch einen Abgleich der Vector Clocks und erkennen, dass der Knoten einen aktuelleren Stand als der Knoten hat.

Link to original