Verteilte Systeme verstehen: Ein Tutorial zu Quorum-Protokollen und Paxos am Beispiel von PingMe

Einführung in verteilte Systeme und das PingMe-Szenario

Stellen Sie sich vor, Sie entwickeln eine Social-Media-App wie PingMe, mit der Nutzer weltweit in Echtzeit ihren Status teilen können. Um eine hohe Verfügbarkeit und Fehlertoleranz zu gewährleisten, betreiben Sie sechs Replikatserver in Pittsburgh, Boston, Los Angeles, Rom, London und Mumbai. Jeder Server speichert eine Kopie der Nutzerdatenbank. Damit alle Nutzer stets den aktuellen Status sehen, muss das System Ein-Kopie-Semantik (one-copy semantics) sicherstellen – selbst bei Netzwerkausfällen oder Partitionen. In diesem Tutorial lernen Sie zwei zentrale Konzepte verteilter Systeme kennen: Quorum-Protokolle und den Paxos-Algorithmus. Wir verwenden aktuelle Beispiele aus der App-Welt, um die Theorie greifbar zu machen.

Grundlagen der Quorum-Protokolle

Ein Quorum-Protokoll legt fest, wie viele Server an einer Lese- oder Schreiboperation beteiligt sein müssen, um Konsistenz zu gewährleisten. Typischerweise wählt man Lesequorum R und Schreibquorum W so, dass R + W > N (wobei N die Gesamtzahl der Server ist). Dadurch überschneiden sich Lese- und Schreibquoren immer, sodass ein Lesevorgang garantiert die letzte geschriebene Version sieht. Im Folgenden betrachten wir verschiedene Szenarien mit sechs Servern und einer Serververfügbarkeit von p = 0,6.

A. Maximierung der Lese-Verfügbarkeit

Um die Wahrscheinlichkeit einer erfolgreichen Leseoperation zu maximieren, wählen wir ein möglichst kleines Lesequorum. Da R + W > 6 gelten muss, ist das minimale R = 1 und dann W = 6. Mit R = 1 ist ein Lesevorgang bereits erfolgreich, wenn irgendein Server verfügbar ist. Die Wahrscheinlichkeit dafür ist 1 - (0,4)^6 ≈ 0,995. Ein Schreibvorgang benötigt alle 6 Server, also (0,6)^6 ≈ 0,0467. Dies ist extrem niedrig – ein Kompromiss zugunsten der Leseverfügbarkeit.

B. Maximierung der Schreib-Verfügbarkeit

Analog wählen wir für maximale Schreibverfügbarkeit ein minimales Schreibquorum: W = 1, dann R = 6. Die Schreibwahrscheinlichkeit ist dann 0,995, die Lesewahrscheinlichkeit nur 0,0467. In der Praxis sind solche extremen Quoren selten sinnvoll; man wählt oft R = W = 4 (da 4+4 > 6). Damit erhält man sowohl Lese- als auch Schreibwahrscheinlichkeit von etwa 0,544 (Binomialverteilung).

Serverauswahl für optimale Latenz

Angenommen, ein Nutzer in Philadelphia möchte einen kleinen Status (1 Byte) lesen. Das Lesquorum ist 3, die Server werden parallel angefragt. Um die Latenz zu minimieren, wählt der Client die drei Server mit der geringsten Antwortzeit. Typische Latenzen (in ms) könnten sein: Pittsburgh 10, Boston 20, Los Angeles 70, Rom 100, London 80, Mumbai 200. Für Philadelphia wäre die optimale Wahl: Pittsburgh, Boston und Los Angeles (oder London, je nach genauen Werten). Für einen Nutzer in Athen wären Rom, London und Mumbai am schnellsten.

Lastverteilung

Wenn die meisten Nutzer aus Nordamerika und Europa kommen, werden die Server in Pittsburgh, Boston und Rom (oder London) am häufigsten angefragt. Dies führt zu einer ungleichen Lastverteilung. Um dies zu beheben, könnte man gewichtete Quoren einführen: Server in stark nachgefragten Regionen erhalten weniger Stimmen, sodass weniger Lesevorgänge auf ihnen lasten. Alternativ könnte man Caching oder Content-Delivery-Netzwerke (CDNs) einsetzen, um die Last zu verteilen.

Ein-Kopie-Semantik mit gewichteten Stimmen

Ein neuer Entwickler hat die Stimmenanzahl pro Server geändert: Pittsburgh 2, Boston 2, Los Angeles 1, Rom 1, London 1, Mumbai 1. Das Lesequorum ist 3, das Schreibquorum ebenfalls 3. Ist die Ein-Kopie-Semantik gewahrt? Nein, denn es ist möglich, dass ein Lesequorum aus {Pittsburgh, Boston} (Stimmen 2+2=4) und ein Schreibquorum aus {Los Angeles, Rom, London} (Stimmen 1+1+1=3) gebildet werden – diese überschneiden sich nicht. Ein Leser könnte dann eine veraltete Version sehen. Die Bedingung R + W > Gesamtstimmen (hier 8) muss erfüllt sein: 3+3=6 < 8, also verletzt. Erst wenn R+W > 8 wäre, wäre die Semantik gesichert.

Paxos-Algorithmus verstehen

Paxos ist ein Protokoll zur Konsensfindung in verteilten Systemen. Es stellt sicher, dass sich mehrere Knoten auf einen Wert einigen, selbst wenn einige ausfallen. Wir betrachten einige Beispielsequenzen und prüfen ihre Gültigkeit.

Beispiel A (3 Knoten)

Die Sequenz zeigt einen gültigen Paxos-Ablauf: S1 startet eine Vorbereitungsphase mit Proposal-Nummer 101, erhält Versprechen von sich selbst und S3, sendet eine Accept-Nachricht, erhält Bestätigungen. Später versucht S2 mit derselben Proposal-Nummer 101 eine Vorbereitung, erhält aber von S3 ein Versprechen, das bereits einen akzeptierten Wert (von S1) enthält (Zeile 10). S2 muss daher den Wert v1 übernehmen – korrekt. Die Sequenz ist gültig.

Beispiel B (10 Knoten)

Hier wird die Prepare-Phase nicht korrekt abgeschlossen: S1 sendet Prepare an mehrere Knoten, aber erhält nicht genügend Versprechen (nur 6 von 10). Trotzdem sendet S1 bereits Accept-Nachrichten (Zeile 14). Das ist ungültig, da ein Akzeptieren erst nach Erhalt einer Mehrheit von Versprechen erfolgen darf. Mögliche Folge: Ein anderer Knoten könnte einen höheren Vorschlag machen und den Konsens brechen.

Beispiel C (2 Knoten)

Gültig: S1 und S2 führen unabhängige Vorbereitungen durch, aber S2 erfährt von S1s akzeptiertem Wert (101, v1) und übernimmt ihn. Der Konsens wird auf v1 erreicht.

Beispiel D (3 Knoten)

Ungültig: S1 und S2 konkurrieren mit unterschiedlichen Proposal-Nummern (101 und 102). S3 gibt S2 ein Versprechen (Zeile 8) und akzeptiert später von S2 den Wert v1 (Zeile 11). Dann akzeptiert S3 aber auch von S1 den Wert v2 (Zeile 12) – das ist ein Verstoß, da S3 bereits einen Wert akzeptiert hat. Die Ein-Kopie-Semantik ist verletzt.

Fazit und Ausblick

Quorum-Protokolle und Paxos sind essenziell für die Konsistenz in verteilten Systemen. Am Beispiel von PingMe haben Sie gesehen, wie sich Lese- und Schreibverfügbarkeit beeinflussen und wie Serverauswahl die Latenz optimiert. Der Paxos-Algorithmus mag komplex erscheinen, aber mit etwas Übung lassen sich typische Fehler erkennen. Wenn Sie mehr über verteilte Systeme, Konsensalgorithmen oder Datenbankreplikation lernen möchten, vertiefen Sie sich in die Literatur. Viel Erfolg im Studium!