Konsistenz, Zeit und Koordination Teil 2: Fencing Tokens und Konsistenzmodelle

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

Worum es geht

In Teil 1 hast du gesehen, dass es keine gemeinsame Uhr gibt und dass Zähler (Lamport, Vector) Ordnung liefern. Jetzt geht es um die Folgen für Koordination: Wie fallen Knoten aus (Fehlermodelle), warum ist ein verteilter Lock mit Timeout ohne Fencing Token nicht sicher, und wie unterscheiden sich Linearizability und Eventual Consistency aus Sicht des Nutzers.

Du baust einen Speicher mit Fencing-Prüfung selbst und klassifizierst Historien nach Konsistenzmodell. Wie in Teil 1 läuft alles als Simulation mit Ticks als Zeit.

Was du aus Teil 1 brauchst: dass Wanduhren nicht übereinstimmen (Offset, Drift) und dass eine Reihenfolge von einem Zähler kommen sollte, nicht von einer Uhr. Genau diese Idee kehrt beim Fencing Token wieder.

Plane ehrlich 45 Minuten ein: etwa 15 Minuten Lesen, etwa 30 Minuten für drei Übungen. Schritt 4 ist ein Überblick zum Einordnen.

Von JS/TS her gedacht

Im Node-Prozess kennst du blockierte Event Loops: Ein langer synchroner Block, und alle Timer feuern verspätet. Im verteilten System heißt das: Du weißt nicht, wie lange du “schläfst”, und währenddessen läuft deine Lease ab. Ein Lock, den du vor der Pause hattest, gehört dir danach vielleicht nicht mehr.

Konzept	JS/TS	Python (hier)
Lock mit Ablauf	Redis `SET key val NX PX 10000` (bitte prüfen)	Klasse `Lockdienst` mit `ablauf`
Pause ohne Vorwarnung	Garbage Collection (GC) im Node-Prozess, blockierter Event Loop	ein Sprung der Zeit im Skript
Nummer, die nur wächst	ein `number`-Feld, das eine einzige Stelle hochzählt	`self.zaehler += 1` im Lockdienst

Konzept

Schritt 4: Fehlermodelle und Koordination im Überblick

Dieser Schritt ist ein Überblick zum Einordnen, es gibt keine Übung dazu. Lies ihn zügig und merke dir vor allem Lease, Leader und die Mehrheitsrechnung. FLP und Raft musst du hier nur als Begriffe kennen.

Bevor Koordination Sinn ergibt, brauchst du ein Bild davon, wie Knoten ausfallen können. Das nennt man Fehlermodell (failure model):

Fehlermodell	Was passiert	Beispiel
Crash	Der Knoten läuft korrekt, bis er stehen bleibt (und kommt evtl. später wieder)	Prozess wird beendet, Rechner stürzt ab
Omission	Der Knoten verliert Nachrichten (senden oder empfangen)	Paketverlust, volle Warteschlange
Byzantine	Der Knoten tut beliebig Falsches, auch böswillig	Bug mit Datenmüll, kompromittierter Server

Die meisten Systeme im Alltag nehmen Crash und Omission an, nicht Byzantine (allgemeines Fachwissen). Das Schwierige daran: Von außen siehst du bei einem langsamen Knoten nicht, ob er tot oder nur langsam ist. Daraus folgt die Intuition hinter dem FLP-Ergebnis (benannt nach Fischer, Lynch, Paterson): In einem Netzwerk ohne Zeitgrenzen kann kein Algorithmus garantieren, dass sich alle Knoten sicher einigen, wenn auch nur ein Knoten ausfallen kann. In der Praxis umgeht man das mit Timeouts. Dann ist “tot” nur eine Vermutung, und die kann falsch sein. Genau hier setzt der nächste Schritt an.

Leader Election (Anführerwahl): Statt dass alle Knoten gleichzeitig dieselbe Arbeit machen, wählt man einen Leader. Ein Lock (Sperre) mit Lease (Mietvertrag, ein Lock mit Ablaufzeit) ist die einfachste Form: Wer den Lock bekommt, ist bis zum Ablauf der Lease der Leader. Fällt er aus, läuft die Lease ab, und ein anderer übernimmt. Ohne Ablaufzeit würde ein toter Lock-Halter alles für immer blockieren.

Konsens mit Raft (nur Überblick): Raft ist ein Algorithmus, mit dem eine Gruppe von Knoten sich auf eine Folge von Einträgen einigt. Ein Leader nimmt Schreibzugriffe an und repliziert sie, ein Eintrag gilt als bestätigt, wenn eine Mehrheit (Quorum) ihn hat. Wird ein neuer Leader gewählt, bekommt er eine höhere Term-Nummer (Epoche). Das merkst du dir: Die Term-Nummer ist genau die Idee des Fencing Tokens im nächsten Schritt. Mit n Knoten braucht man n // 2 + 1 für die Mehrheit und übersteht so n minus Mehrheit Ausfälle:

Knoten `n`	Mehrheit	übersteht Ausfälle
3	2	1
5	3	2
7	4	3

(aus n // 2 + 1 berechnet)

Schritt 5: Der Lock mit Lease und die GC-Pause

Jetzt das Kernproblem. Ein Lockdienst vergibt den Lock für eine Lease von 10 Ticks. Mit jeder Vergabe zählt er einen Fencing Token hoch (eine immer größer werdende Nummer). Client A bekommt Token 1, danach vielleicht B Token 2. Ein Speicher nimmt Schreibzugriffe an.

Das Szenario, in dem es schiefgeht:

t=0: A bekommt den Lock (Token 1, Lease bis t=10) und schreibt bei t=1.
t=9: A prüft kurz vorher, ob seine Lease noch gilt: ja.
Dann hängt A in einer GC-Pause (garbage collection pause) bis t=15. Genauso gut: ein langsamer Netzwerkaufruf, ein blockierter Prozess, eine VM, die angehalten wurde. A merkt davon nichts.
t=10: Die Lease läuft ab. t=11: B bekommt den Lock (Token 2) und schreibt bei t=12 und t=13.
t=15: A wacht auf, glaubt immer noch, den Lock zu haben, und schreibt.

sequenceDiagram
    participant A as Client A
    participant L as Lockdienst
    participant B as Client B
    participant S as Speicher
    A->>L: Lock anfordern (t=0)
    L-->>A: Token 1, Lease bis t=10
    A->>S: schreibe A1 (Token 1)
    Note over A: Pause von t=9 bis t=15
    B->>L: Lock anfordern (t=11)
    L-->>B: Token 2, Lease bis t=21
    B->>S: schreibe B1, B2 (Token 2)
    A->>S: schreibe A2 (Token 1)

Hier der Simulator. Zwei Klassen: Lockdienst vergibt Leases und Token. SpeicherNaiv ignoriert den Token, so schreiben viele Systeme.

Ausgabe:

t=0  A bekommt den Lock, Token 1 (Lease bis t=10)
t=1  A schreibt A1: True -> Wert A1
t=9  A prüft: Lease gültig? True (danach GC-Pause bis t=15)
t=11 B bekommt den Lock, Token 2
t=12 B schreibt B1: True -> Wert B1
t=13 B schreibt B2: True -> Wert B2
t=15 A schreibt A2: True -> Wert A2

Am Ende steht A2 im Speicher, obwohl B längst der Lock-Halter war. A hat B’s Arbeit überschrieben. Zwei Dinge zu diesem Fehler:

Die Prüfung vor dem Schreiben hilft nicht. A hat bei t=9 geprüft (True) und bei t=15 geschrieben. Dazwischen lagen 6 Ticks Pause. Prüfen und Handeln sind zwei Schritte, dazwischen kann alles passieren (check-then-act, wie in konzepte/01).
Der Lockdienst kann das nicht verhindern. Er weiß nichts davon, dass A noch schreibt. Nur der Speicher sieht jeden Schreibzugriff.

Darum die Reparatur: Jeder Schreibzugriff trägt den Fencing Token mit, den der Client beim Lock bekommen hat. Der Speicher merkt sich den höchsten Token, den er je akzeptiert hat, und lehnt jeden Schreibzugriff mit kleinerem Token ab. A’s Token 1 ist kleiner als B’s Token 2, also scheitert A2. Das ist deine Übung 2. Die Zeit spielt keine Rolle mehr, nur die Nummer. Das ist der Unterschied zu Schritt 1 in Teil 1: Die Reihenfolge kommt nicht von einer Uhr, sondern von einem Zähler, den eine einzige Stelle (der Lockdienst) vergibt.

Schritt 6: Konsistenzmodelle aus Sicht des Nutzers

Ein Konsistenzmodell (consistency model) legt fest, was ein Leser sehen darf, wenn mehrere Kopien der Daten existieren. Die vier aus der Quelle, vom stärksten zum schwächsten:

Modell	Versprechen	Für den Nutzer
Linearizability	Das System verhält sich, als gäbe es eine Kopie. Jede Operation wirkt zu einem Zeitpunkt zwischen Start und Ende. Wer nach dem Ende eines Schreibzugriffs liest, sieht ihn.	“Ich habe gespeichert, mein Freund liest danach, er sieht es.”
Sequential	Alle sehen dieselbe Reihenfolge aller Operationen, die Reihenfolge jedes einzelnen Clients bleibt erhalten. Die Echtzeit darf missachtet werden.	Alle sehen dieselbe Geschichte, aber evtl. mit Verzögerung.
Causal	Ursache kommt vor Wirkung: Wer eine Antwort sieht, sieht auch die Frage. Unabhängige Dinge dürfen verschieden angeordnet erscheinen.	Kommentar-Threads ergeben Sinn.
Eventual	Wenn niemand mehr schreibt, sind irgendwann alle Kopien gleich. Dazwischen: keine Garantie.	Mal alt, mal neu, eventuell springt der Wert zurück.

Dazwischen gilt (allgemeines Fachwissen): Linearizability ist stärker als Sequential, das ist stärker als Causal, das ist stärker als Eventual.

Was kostet Linearizability? Damit jeder Leser das Neueste sieht, muss jede Operation sich mit einer Mehrheit der Kopien oder dem Leader abstimmen. Das kostet mindestens einen Netzwerk-Rundweg pro Operation (Latenz), und bei einer Netzwerkpartition (Teile des Systems sehen sich nicht mehr) kann die kleinere Seite nicht mehr antworten (Verfügbarkeit). Das ist die Aussage von CAP (siehe konzepte/04), aber nur für den Fall einer Partition. PACELC liest es vollständiger: Bei Partition (P) wählst du Verfügbarkeit (A) oder Konsistenz (C), sonst (E, else) wählst du Latenz (L) oder Konsistenz (C). Weil Partitionen selten sind, ist der Alltagspreis fast immer die Latenz. Eventual Consistency antwortet dagegen lokal und schnell, auch bei Partition, und bezahlt mit veralteten Lesezugriffen und Konflikten, die gelöst werden müssen (Schritte 1 bis 3).

Zum Prüfen gibt es eine Faustregel, die du in Übung 3 anwendest. Eine Historie ist eine Liste von Operationen mit Client, Art, Wert, Start und Ende. Ein Register startet bei 0. Eine Historie ist

linearisierbar (L), wenn es eine Reihenfolge gibt, die (a) die Reihenfolge jedes Clients erhält, (b) die Echtzeit erhält (endete Operation X vor dem Start von Y, steht X vor Y) und (c) bei der jeder Lesezugriff den zuletzt geschriebenen Wert sieht,
nur sequentiell (S), wenn es eine Reihenfolge mit (a) und (c) gibt, aber keine mit (b),
sonst weder noch (N).

So prüfst du von Hand (das brauchst du in Übung 3):

Schreibe die Operationen mit Start und Ende auf. Überlappende Operationen dürfen in beliebiger Reihenfolge stehen.
Frage zuerst nur nach Sequential: Gibt es eine Reihenfolge, in der jeder Client seine Operationen in seiner eigenen Reihenfolge behält und jeder Lesezugriff den zuletzt geschriebenen Wert sieht? Beginne bei den Lesezugriffen: Welcher Schreibzugriff muss jeweils davor liegen?
Gibt es so eine Reihenfolge, frage danach, ob eine davon auch die Echtzeit beachtet (endete X vor dem Start von Y, steht X davor). Dann ist die Historie linearisierbar (L), sonst nur sequentiell (S).
Gibt es schon in Schritt 2 keine Reihenfolge, lautet die Antwort N.

Der Code unten probiert alle Reihenfolgen durch. Er ist nur für kleine Historien brauchbar (bei n Operationen gibt es n! Reihenfolgen), aber er zeigt die Definition genau.

Ausgabe:

Bob sieht 0: S
Bob sieht 1: L

Das Beispiel: Alice hat ihren Schreibzugriff abgeschlossen, ruft Bob an, Bob liest und sieht den alten Wert. Es gibt eine Reihenfolge ohne Widerspruch (Bobs Lesen vor Alices Schreiben), aber sie verletzt die Echtzeit. Das ist sequentiell, nicht linearisierbar. Bei Eventual Consistency wäre das normal. Bei Linearizability ist es verboten.

Falle

Lock mit Timeout als Garantie. Ein Lock mit Lease sagt dir, dass du bis t=10 dran bist, aber nicht, dass du es um t=15 immer noch bist, und deine Uhr und dein Prozess können dich im Stich lassen. Ohne Prüfung im Speicher (Fencing Token) ist der Lock nur eine Optimierung, keine Garantie (Schritt 5).
Prüfen vor Schreiben auf dem Client. if lock.gueltig(): schreibe() ist check-then-act. Die Pause liegt genau dazwischen.
CAP als Dauerzustand lesen. “Ich muss mich entscheiden: C oder A” gilt nur während einer Partition. Im Normalbetrieb ist die echte Wahl Latenz gegen Konsistenz (PACELC).

Übungen

Übung 1: Mehrheit und Partition (Vorhersage, ca. 6 Min.)

In Schritt 4 hast du die Mehrheitsrechnung gesehen: Mit n Knoten braucht ein Beschluss (oder die Wahl eines Leaders) n // 2 + 1 Stimmen aus dem ganzen Cluster, nicht nur aus der Seite, auf der du gerade sitzt. Jetzt rechnest du ein Cluster mit anderen Größen durch.

Ein Cluster hat 9 Knoten. Später ein zweites mit 6 Knoten. Trage ein Tupel (a, b, c, d) ein:

a: Wie viele Stimmen sind beim 9-Knoten-Cluster für eine Mehrheit nötig?
b: Wie viele Knoten dürfen beim 9-Knoten-Cluster ausfallen, ohne dass die Mehrheit verloren geht?
c: Das 6-Knoten-Cluster spaltet sich durch einen Netzwerkfehler in eine Seite mit 4 und eine mit 2 Knoten. Kann die 4er-Seite einen neuen Leader wählen (True oder False)?
d: Dasselbe Cluster spaltet sich in 3 und 3. Kann eine der beiden Seiten einen Leader wählen (True oder False)?

antwort = (5, 4, True, False)
antwort

Bei n = 9 ist die Mehrheit 9 // 2 + 1 = 5, übrig bleiben 9 - 5 = 4 erlaubte Ausfälle. Beim 6-Knoten-Cluster ist die Mehrheit 6 // 2 + 1 = 4: Die 4er-Seite erreicht sie, bei 3 und 3 hat keine Seite genug Stimmen. Darum nimmt man ungerade Knotenzahlen: Ein 6er-Cluster übersteht nur 2 Ausfälle, genau wie ein 5er.

Übung 2: Fencing Token im Speicher (ca. 12 Min.)

Der Simulator aus Schritt 5 ist schon geladen: Lockdienst, SpeicherNaiv und szenario. Schreibe die Klasse Speicher mit Fencing-Prüfung:

Attribut wert startet bei None.
schreibe(token, wert) gibt True zurück und speichert den Wert, wenn token mindestens so groß ist wie der höchste Token, den der Speicher bisher akzeptiert hat. Sonst gibt es False zurück und ändert nichts.
Derselbe Client schreibt mit demselben Token mehrmals. Das muss weiter gehen.

Der Check spielt mehrere Szenarien durch, unter anderem das aus Schritt 5 (A pausiert, B übernimmt, A wacht auf), ein Szenario, in dem A nach dem Aufwachen zweimal schreibt, und eines mit drei Clients nacheinander.

class Speicher:
    def __init__(self):
        self.wert = None
        self.hoechster = 0

    def schreibe(self, token, wert):
        if token < self.hoechster:
            return False
        self.hoechster = token
        self.wert = wert
        return True

Speicher

Der höchste akzeptierte Token ist die einzige Information, die der Speicher braucht. Kleiner heißt veraltet, gleich heißt derselbe Lock-Halter schreibt weiter. Ein abgelehnter Schreibzugriff ändert nichts, auch nicht den höchsten Token. Die Entscheidung trifft der Speicher, weil nur er jeden Schreibzugriff sieht. Der Lockdienst und die Uhren spielen dabei keine Rolle mehr.

Übung 3: Historien klassifizieren und Modell wählen (ca. 10 Min.)

Teil 1 bis 3: Drei Historien eines Registers (Startwert 0). Format (Client, Art, Wert, Start, Ende), "w" schreibt, "r" liest und hat den gelesenen Wert als Wert. Prüfe wie in Schritt 6 (nutze nicht den Code, rechne selbst): "L" für linearisierbar, "S" für nur sequentiell (nicht linearisierbar), "N" für weder noch.

Teil 4: Welches Modell passt?

Eine Kommentarfunktion läuft in drei Regionen. Jede Region hat ein eigenes Replikat und schreibt lokal. Anforderungen: (1) Eine Antwort darf nie vor dem Kommentar erscheinen, auf den sie sich bezieht. (2) Schreiben bleibt schnell und funktioniert auch dann, wenn die Verbindung zwischen den Regionen ausfällt. (3) Kurz veraltete Kommentare auf dem Bildschirm sind in Ordnung.

A Linearizability: Jeder Schreibzugriff wird erst bestätigt, wenn eine Mehrheit der Regionen ihn hat.
B Causal Consistency: Replikate liefern eine Antwort erst aus, wenn sie auch die Frage haben, auf die sie antwortet.
C Eventual Consistency ohne weitere Regel: Jedes Replikat zeigt an, was es gerade hat, irgendwann gleichen sich alle an.
D Eventual Consistency, Anzeige sortiert nach der Uhrzeit des Servers, auf dem der Kommentar geschrieben wurde.

Trage (Teil 1, Teil 2, Teil 3, Teil 4) ein, z. B. ("L", "L", "L", "A").

antwort = ("S", "L", "N", "B")
antwort

H1, S. B liest 1 und ist fertig (Ende 2), danach beginnt C (Start 3) und liest 0. Linearisierbar wäre das nur, wenn der Schreibzugriff vor B’s Lesen wirkt (B sieht 1) und nach C’s Lesen (C sieht 0), aber C kommt nach B. Das widerspricht sich. Ohne Echtzeitregel geht es: C liest 0, A schreibt, B liest 1. Also sequentiell, nicht linearisierbar.

H2, L. Reihenfolge: A schreibt 1, B liest 1, C liest 1, B liest 1 (dessen Lesen überlappt A’s zweiten Schreibzugriff und darf davor liegen), A schreibt 2, C liest 2. Alle Echtzeit- und Client-Regeln stimmen.

H3, N. B liest erst 2, dann 1. A schreibt aber erst 1 und dann 2, und diese Reihenfolge ist fest. Wer 2 gesehen hat, kann danach nicht wieder 1 sehen: Der Wert springt zurück in der Zeit. Das verletzt schon Sequential.

Teil 4, B. Causal Consistency erfüllt die Reihenfolge Frage vor Antwort, braucht keine globale Mehrheit (also kein Warten über Regionen) und funktioniert bei Partition lokal weiter. A scheitert an Anforderung 2, C an 1, D an 1, weil Serveruhren nicht übereinstimmen und die Antwort so vor der Frage einsortiert werden kann.

Merksatz

Sichere Locks mit Fencing Tokens im Speicher, rechne Mehrheiten aus dem ganzen Cluster und wähle das schwächste Konsistenzmodell, das deine Anwendung noch richtig macht, weil Linearizability Latenz und Verfügbarkeit kostet.

Prüfstein

Warum reicht ein verteilter Lock mit Timeout nicht ohne Fencing Token?
Wie unterscheidet sich Linearizability von Eventual Consistency aus Sicht des Nutzers, und was kostet sie?

Quelle: quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 7 “Verteilte Systeme und Zuverlässigkeit” (Konsistenzmodelle: Linearizability, Sequential, Causal, Eventual; CAP und PACELC richtig gelesen; Fehlermodelle: Crash, Omission, Byzantine, FLP-Unmöglichkeit als Intuition; Koordination: Leader Election, Leases, verteilte Locks und Fencing Tokens, Konsens mit Raft; beide Prüfsteine).

Über die Quelle hinaus (allgemeines Fachwissen): die Definitionen der Fehlermodelle und der FLP-Intuition, die Rolle der Term-Nummer in Raft, die Mehrheitsrechnung n // 2 + 1 und die Partitions-Beispiele in Übung 1, die Konstruktion von Lease, Lockdienst und Fencing Token, die Definitionen von Linearizability, Sequential, Causal und Eventual Consistency samt Stärkeordnung, die Einordnung der Latenz- und Verfügbarkeitskosten und PACELC, die Aussage, dass Causal Consistency bei Partition lokal weiterarbeiten kann (bitte prüfen), Redis SET NX PX als Lock-Beispiel (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.

Zurück zu Teil 1: Uhren, Lamport und Vector Clocks.