Paxos ist der grundlegende Konsens-Algorithmus für verteilte Systeme. Er wurde von Leslie Lamport entwickelt und formalisiert, wie mehrere unabhängige Knoten sich trotz Ausfällen auf einen gemeinsamen Wert einigen können. Paxos ist der direkte Vorgänger und Konkurrent von Raft und bildet die theoretische Grundlage vieler Produktionssysteme.
Herkunft und Verständlichkeit
Lamport beschrieb Paxos 1990 in seinem Papier „The Part-Time Parliament" als Allegorie auf das Parlament der fiktiven Insel Paxos; veröffentlicht wurde es erst 1998 in den ACM Transactions on Computer Systems. Wegen der ungewöhnlichen Erzählform galt das Papier lange als schwer verständlich — Lamport schrieb deshalb 2001 die vereinfachte Fassung „Paxos Made Simple". Genau diese mangelnde Verständlichkeit war später ein Motiv für die Entwicklung von Raft (Ongaro & Ousterhout 2014).
Rollen und Ablauf
Paxos unterscheidet drei Rollen:
- Proposer: schlägt einen Wert vor und treibt den Ablauf voran.
- Acceptor: stimmt über Vorschläge ab und merkt sich die höchste gesehene Vorschlagsnummer sowie den zuletzt akzeptierten Wert.
- Learner: erfährt das Ergebnis und leitet es an die Anwendung weiter.
Der Ablauf (Basic Paxos) besteht aus zwei Phasen: In der Prepare-Phase sendet der Proposer eine Vorschlagsnummer n an alle Acceptors; diese antworten mit einem Promise, künftig keine Vorschläge mit Nummer kleiner oder gleich n mehr zu akzeptieren. In der Accept-Phase sendet der Proposer den Vorschlag (n, Wert); ein Acceptor akzeptiert ihn, solange n mindestens so hoch ist wie die zuletzt versprochene Nummer. Sobald eine Mehrheit (Quorum) akzeptiert hat, ist der Wert entschieden.
Warum Paxos korrekt ist
Die Korrektheit beruht auf dem Quorum-Prinzip: Zwei beliebige Mehrheiten überlappen sich in mindestens einem Knoten. Dadurch kann es keine zwei konkurrierenden Werte geben, die beide eine Mehrheit erreichen — die Sicherheit (Safety) ist garantiert. Der Fortschritt (Liveness) ist dagegen nur probabilistisch: Konkurrieren mehrere Proposer gleichzeitig, können sie sich gegenseitig überstimmen. In der Praxis wählt man daher einen einzigen führenden Proposer (Distinguished Proposer) oder verzahnt Paxos mit einer Leader Election.
Multi-Paxos und Produktion
Multi-Paxos erweitert den Algorithmus zur Log-Replikation: Nach einer Leader-Wahl überspringt der führende Proposer die Prepare-Phase für alle weiteren Logeinträge und bündelt Vorschläge, wodurch der Durchsatz steigt. Google nutzte Paxos erstmals großflächig in Chubby (2006), einem Lock- und Metadaten-Dienst für GFS und Bigtable; auch Spanner und viele andere Systeme bauen auf Paxos-Varianten auf. Paxos umgeht die Unmöglichkeit des Konsens-Problems (FLP-Theorem) durch Mehrheits-Quoren und Zeitlimits statt durch theoretisch perfekte Synchronität.
Verwandte Grundlagen: Raft, Konsens, Quorum, CAP-Theorem, Datenbank-Replikation.