Konsistenz, Zeit und Koordination Teil 1: Uhren, Lamport und Vector Clocks

Track Konzepte · Verteilte Systeme und Zuverlässigkeit · ca. 45 Min.

Worum es geht

Zwei Server schreiben dasselbe Feld. Beide haben einen Zeitstempel dazugeschrieben, und das System behält den Schreibzugriff mit dem höheren Zeitstempel (Last-Write-Wins, LWW). Klingt vernünftig. Aber die Uhren der beiden Server gehen nicht gleich. Der Server, dessen Uhr 5 Sekunden vorgeht, gewinnt immer, auch wenn sein Schreibzugriff älter ist. Der neuere Wert verschwindet, ohne Fehlermeldung. Das ist die Grundtatsache dieser Lektion: In einem verteilten System gibt es keine gemeinsame Uhr (no shared clock).

In diesem ersten Teil erklärst du, warum Uhrzeiten lügen und was man stattdessen benutzt: Lamport Clocks (Ursache und Wirkung) und Vector Clocks (Nebenläufigkeit erkennen). Du baust eine Lamport-Uhr und einen Vektoruhr-Vergleich selbst. Teil 2 (Locks, Fencing Tokens und Konsistenzmodelle) baut darauf auf.

Alles läuft als Simulation im Browser. Zeit ist ein Zähler (ein Tick ist ein Zeitschritt), Pausen und Ausfälle sind Zeilen in einem Skript. So ist jeder Lauf gleich, und du kannst jede Zahl nachrechnen.

Plane ehrlich 45 Minuten ein: etwa 20 Minuten Lesen, etwa 25 Minuten für drei Übungen. Eine Pause passt nach Übung 2.

Von JS/TS her gedacht

Im Frontend kennst du Date.now() auf dem Client des Nutzers, und du weißt, dass man dieser Uhr nicht trauen darf (falsche Zeitzone, falsch gestellt). Auf Servern ist es subtiler: Die Uhren sind meist fast richtig, aber eben nicht exakt gleich. Und await bedeutet im verteilten System: Du weißt nicht, wie lange du schläfst.

Konzept JS/TS Python (hier)
Wanduhr (wall clock) Date.now() time.time(), im Simulator eine Funktion uhr(t, offset, drift)
Logischer Zähler ein number-Feld, das du selbst hochzählst self.zeit += 1 in einer Klasse
Vektor number[] list[int] mit zip

Die Lamport-Uhr in TypeScript (hier als JavaScript mit node ausgeführt, ohne Typannotationen). Du schreibst sie in Übung 2 in Python:

class LamportUhr {
  zeit: number = 0;
  ereignis(): number { return ++this.zeit; }
  senden(): number { return ++this.zeit; }
  empfangen(ts: number): number {
    this.zeit = Math.max(this.zeit, ts) + 1;
    return this.zeit;
  }
}

Ausgabe von node für p1.senden(), p2.ereignis(), p2.empfangen(1), p2.empfangen(7):

P1 sendet: 1
P2 lokal: 1
P2 empfängt ts=1: 2
P2 empfängt ts=7: 8

Konzept

Schritt 1: Warum Uhrzeiten lügen

Jeder Rechner hat eine eigene Quarzuhr. Zwei Dinge sind mit ihr passiert:

  • Offset (Versatz): Die Uhr zeigt zu einem Zeitpunkt etwas anderes als eine andere Uhr.
  • Drift (Gang): Die Uhr geht ein wenig zu schnell oder zu langsam, der Versatz wächst mit der Zeit.

Synchronisation mit einem Zeitserver (NTP) verkleinert den Fehler, macht ihn aber nicht null (allgemeines Fachwissen). Für unser Beispiel genügt: Es gibt immer einen Rest.

Der Simulator unten rechnet mit ganzen Zahlen. Die Uhr eines Knotens zeigt t + offset + t * drift // 100. Das heißt: drift = 10 bedeutet 10 Ticks Abweichung je 100 echte Ticks. LWW nimmt von mehreren Schreibzugriffen den mit dem größten Zeitstempel. Bei Gleichstand muss es eine feste Regel geben, sonst entscheiden die Replikate verschieden. Wir nehmen willkürlich: der größere Knotenname gewinnt.

Ausgabe:

Beide Uhren richtig:
  wahre Zeit 10, Knoten A: Zeitstempel 10, Wert 'alt'
  wahre Zeit 12, Knoten B: Zeitstempel 12, Wert 'neu'
  Endwert: neu
Uhr von A geht 5 Ticks vor:
  wahre Zeit 10, Knoten A: Zeitstempel 15, Wert 'alt'
  wahre Zeit 12, Knoten B: Zeitstempel 12, Wert 'neu'
  Endwert: alt

Im zweiten Lauf hat B später geschrieben (wahre Zeit 12 gegen 10), vielleicht sogar nachdem B den Wert von A gelesen hat. Trotzdem gewinnt alt, weil 15 größer ist als 12. B’s Update geht still verloren (lost update). Das ist kein Randfall, sondern die Folge davon, dass du eine Uhrzeit als Ordnung benutzt.

Die Lehre: Uhrzeiten taugen für Anzeige, Logs und grobe Fristen. Für die Frage “was passierte vor was” brauchst du etwas anderes.

Schritt 2: Lamport Clocks, Ordnung ohne Uhr

Wichtig ist meist nicht die Uhrzeit, sondern die Ursache: Hat Ereignis A das Ereignis B beeinflusst (A happened-before B, geschrieben A → B)? Das ist der Fall, wenn beide im selben Prozess nacheinander passieren oder wenn A das Senden einer Nachricht ist und B ihr Empfang (und transitiv daraus).

Eine Lamport Clock ist ein Zähler pro Prozess mit drei Regeln:

  1. Lokales Ereignis: Zähler um 1 erhöhen.
  2. Senden: Zähler um 1 erhöhen, den neuen Wert als Zeitstempel an die Nachricht hängen.
  3. Empfangen: Zähler auf max(eigener Zähler, Zeitstempel der Nachricht) + 1 setzen.

Durchgerechnet für drei Prozesse P1, P2, P3 (aus der Referenzimplementierung berechnet):

Reihenfolge Prozess Ereignis Zähler danach
1 P1 lokal a 1
2 P1 sendet m1 2
3 P3 lokal x 1
4 P2 lokal b 1
5 P2 empfängt m1 (Zeitstempel 2) max(1, 2) + 1 = 3
6 P2 sendet m2 4
7 P3 empfängt m2 (Zeitstempel 4) max(1, 4) + 1 = 5
8 P1 lokal e 3 

sequenceDiagram
    participant P1
    participant P2
    participant P3
    Note over P1: a = 1
    P1->>P2: m1 (ts 2)
    Note over P3: x = 1
    Note over P2: b = 1, empfängt m1 = 3
    P2->>P3: m2 (ts 4)
    Note over P3: empfängt m2 = 5
    Note over P1: e = 3

Was die Uhr garantiert: Wenn A → B, dann ist L(A) < L(B). Beim Empfang ist der Zeitstempel immer größer als beim Senden (Zeile 5: 3 gegen 2). Was sie nicht garantiert: die Umkehrung. Das Ereignis x in P3 hat Zähler 1, das Ereignis e in P1 hat Zähler 3. Es gilt 1 < 3, aber x und e haben nichts miteinander zu tun (keine Nachricht verbindet sie). Auch a und b haben beide den Zähler 1, ohne dass eines das andere verursacht hat. Ein kleinerer Lamport-Zähler heißt also nur “kann Ursache sein”, nicht “ist Ursache”.

Will man eine totale Ordnung (alle Ereignisse in eine Reihe, z. B. für Locks), sortiert man nach (Zähler, Prozess-ID). Gleichstand bricht die Prozess-ID, wieder willkürlich, aber für alle gleich. Die Reihenfolge stimmt dann mit der Kausalität überein, hat aber sonst keine Bedeutung.

Schritt 3: Vector Clocks, Nebenläufigkeit erkennen

Mit Lamport siehst du nicht, ob zwei Ereignisse nebenläufig (concurrent) sind. Das brauchst du aber, wenn zwei Replikate gleichzeitig dasselbe Feld ändern: War die zweite Änderung eine Antwort auf die erste (dann überschreibt sie), oder haben beide nichts voneinander gewusst (dann ist es ein Konflikt)?

Eine Vector Clock (Vektoruhr) hat pro Prozess einen eigenen Zähler. Bei zwei Prozessen ist sie [zähler_von_A, zähler_von_B]. Regeln für Prozess i:

  1. Lokales Ereignis oder Senden: v[i] um 1 erhöhen.
  2. Empfangen: elementweise Maximum aus eigenem und fremdem Vektor bilden, dann v[i] um 1 erhöhen.

Zwei Vektoren a und b vergleicht man so:

Beziehung Bedingung
a vorher b jede Stelle von a ist kleiner oder gleich der von b, und a ist nicht gleich b
a nachher b dasselbe andersherum
gleich alle Stellen gleich
nebenläufig keine der Bedingungen (mal ist a größer, mal b)

Durchgerechnetes Beispiel mit Replikat A und B (Vektor [A, B]):

Schritt Ereignis Vektor
1 A schreibt “Milch” A: [1, 0]
2 B schreibt “Brot”, ohne A gesehen zu haben B: [0, 1]
3 B empfängt A’s Stand [1, 0] B: Maximum [1, 1], dann B-Stelle plus 1: [1, 2]

Vergleich nach Schritt 2: [1, 0] gegen [0, 1]. An Stelle 0 ist A größer, an Stelle 1 ist B größer. Keine Seite ist überall größer oder gleich: nebenläufig. Das System weiß jetzt, dass es einen Konflikt gibt, und kann beide Werte behalten (Milch und Brot, im Einkaufswagen einfach zusammenführen) statt still einen zu verwerfen. Vergleich nach Schritt 3: [1, 0] gegen [1, 2]. Überall kleiner oder gleich, und nicht gleich: [1, 0] ist vorher. B hat A’s Schreibzugriff gesehen, und B’s neuer Stand ersetzt ihn sauber.

Der Preis: Der Vektor wächst mit der Zahl der Prozesse (allgemeines Fachwissen). In der Quelle steht außerdem Hybrid Logical Clock (HLC): eine Mischung aus Wanduhr und logischem Zähler, damit Zeitstempel lesbar bleiben und trotzdem die Kausalität respektieren (nur zur Kenntnis, bitte prüfen, wenn du es genauer brauchst).

Falle

  1. Wanduhr als Ordnung. ORDER BY updated_at und LWW mit Serverzeit sehen aus wie Ordnung, sind aber eine Wette auf synchrone Uhren (Schritt 1).
  2. Lamport-Zähler als “gleichzeitig”-Test. Zwei Ereignisse mit kleinerem und größerem Zähler können unabhängig sein. Nebenläufigkeit erkennst du erst mit Vector Clocks (Schritt 2 und 3).

Übungen

Übung 1: Last-Write-Wins mit driftenden Uhren (Vorhersage, ca. 6 Min.)

Du hast in Schritt 1 gesehen, wie ein Offset einen neueren Schreibzugriff verliert. Hier drei neue Szenarien. In jedem schreiben mehrere Knoten, alle mit ihrem Zeitstempel aus uhr(t, offset, drift). Der Zeitstempel ist t + offset + t * drift // 100. Bei Gleichstand gewinnt der größere Knotenname. Der Endwert ist der Wert mit dem größten Zeitstempel.

Trage ein Tupel (a, b, c) mit den drei Endwerten ein, also den Strings der Werte, z. B. "x1".

Rechne für jeden Schreibzugriff zuerst den Zeitstempel aus, mit Offset und Drift (ganzzahlige Division). Der echte Zeitpunkt ist nur Eingabe, entscheidend ist der Zeitstempel. Was passiert bei zwei gleichen Zeitstempeln?

antwort = ("x1", "y2", "z2")
antwort
  1. A: 100 + 0 + 100 * 10 // 100 = 110. B: 106. Es gewinnt x1, obwohl x2 später geschrieben wurde.
  2. Zeitstempel: A 30, B 31 + 2 = 33, C 32. Es gewinnt y2, weder der erste noch der letzte Schreibzugriff.
  3. A: 40 + 1 = 41, B: 41. Gleichstand, der größere Knotenname (“B”) gewinnt: z2. Hier ist das Ergebnis zufällig auch der echte letzte Schreibzugriff, aber nur wegen der Tie-Break-Regel.

Übung 2: Lamport Clock selbst schreiben (ca. 10 Min.)

Schreibe die Klasse LamportUhr nach den drei Regeln aus Schritt 2 (die TypeScript-Version aus dem Abschnitt “Von JS/TS her gedacht” ist das Vorbild). Das Attribut zeit startet bei 0. Jede der drei Methoden gibt den neuen Zählerstand zurück:

Methode Verhalten
ereignis() Zähler plus 1, Rückgabe neuer Stand
senden() Zähler plus 1, Rückgabe neuer Stand (das ist der Zeitstempel der Nachricht)
empfangen(ts) Zähler auf max(eigener, ts) + 1, Rückgabe neuer Stand

Beispiele, die der Check unter anderem prüft: Neue Uhr, ereignis() gibt 1, senden() gibt 2, empfangen(1) gibt 3 (der fremde Zeitstempel ist kleiner, der Zähler wächst trotzdem), empfangen(10) gibt 11.

Was soll beim Empfangen passieren, wenn die Nachricht aus der Zukunft kommt (Zeitstempel größer als dein Zähler)? Und was, wenn sie aus der Vergangenheit kommt? Soll der Zähler in beiden Fällen weiterlaufen?

class LamportUhr:
    def __init__(self):
        self.zeit = 0

    def ereignis(self):
        self.zeit += 1
        return self.zeit

    def senden(self):
        self.zeit += 1
        return self.zeit

    def empfangen(self, ts):
        self.zeit = max(self.zeit, ts) + 1
        return self.zeit

LamportUhr

Das max sorgt dafür, dass der Empfang nach dem Senden liegt (Ursache vor Wirkung). Das + 1 sorgt dafür, dass das Empfangen selbst ein Ereignis ist und die Zeit nie stehen bleibt.

Übung 3: Vector Clocks vergleichen (ca. 10 Min.)

Schreibe die Funktion vergleiche(a, b) für zwei Vektoren gleicher Länge (Listen von ganzen Zahlen). Sie gibt einen von vier Strings zurück: "vorher" (a liegt vor b), "nachher" (a liegt nach b), "gleich" oder "nebenlaeufig". Die Bedingungen stehen in der Tabelle in Schritt 3.

Beispiele, die der Check unter anderem prüft:

a b Ergebnis
[1, 0] [1, 2] "vorher"
[1, 2] [1, 0] "nachher"
[1, 0] [0, 1] "nebenlaeufig"
[2, 1, 0] [2, 1, 0] "gleich"
[4, 4] [3, 5] "nebenlaeufig"

Du brauchst zwei Fragen: “Ist a an jeder Stelle kleiner oder gleich b?” und “Ist a an jeder Stelle größer oder gleich b?”. Was folgt, wenn beide mit Ja, nur eine mit Ja oder beide mit Nein beantwortet werden? Eine Summe der Einträge beantwortet diese Fragen nicht.

def vergleiche(a, b):
    a_kleiner_gleich = all(x <= y for x, y in zip(a, b))
    a_groesser_gleich = all(x >= y for x, y in zip(a, b))
    if a_kleiner_gleich and a_groesser_gleich:
        return "gleich"
    if a_kleiner_gleich:
        return "vorher"
    if a_groesser_gleich:
        return "nachher"
    return "nebenlaeufig"

vergleiche

Beide Fragen mit Ja heißt: alle Stellen gleich. Keine mit Ja heißt: mal ist a vorn, mal b. Das ist nebenläufig. [4, 4] gegen [3, 5] hat dieselbe Summe 8 und ist trotzdem nebenläufig, darum reicht kein Zahlenvergleich.

Merksatz

Uhrzeiten lügen: Ordne mit Zählern, mit Lamport Clocks für Ursache und Wirkung und mit Vector Clocks, wenn du Nebenläufigkeit erkennen willst.

Prüfstein

  1. Warum ist Last-Write-Wins mit Serverzeit gefährlich, und was nimmst du stattdessen?
  2. Woran erkennst du mit Vector Clocks, dass zwei Schreibzugriffe nebenläufig sind, und was tut ein System dann?

Weiter geht es in Teil 2: Locks, Fencing Tokens und Konsistenzmodelle.

Quelle: quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 7 “Verteilte Systeme und Zuverlässigkeit” (Zeit und Ordnung: Lamport Clocks, Vector Clocks, Hybrid Logical Clocks, warum Uhrzeiten lügen); quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “7. Verteilte Systeme und Betrieb” (Grundprobleme: keine gemeinsame Uhr).

Über die Quelle hinaus (allgemeines Fachwissen): die Erklärung von Offset, Drift und NTP, Last-Write-Wins mit Zeitstempeln, die Regeln der Lamport Clock und der Vector Clock samt Vergleich, die Beschreibung der Hybrid Logical Clock (bitte prüfen). Alle Zahlen und Ausgaben im Text stammen aus dem Ausführen des Codes dieser Lektion (Simulatoren mit festen Parametern), nicht aus Messungen realer Systeme.