Paxos (Informatik)

Ziel und Bedeutung

Paxos ist eine Gruppe von Kommunikationsprotokollen der Informatik. Ziel ist es, in einem Netzwerk unzuverlässiger Prozessoren einen Konsensus zu erzielen, also die Übereinstimmung einer Gruppe von Teilnehmern auf ein gemeinsames Ergebnis. Fehler bei Prozessoren oder im Kommunikationsmedium können dieses Problem erschweren.

Konsensusprotokolle bilden in verteilten Systemen die Grundlage für die Herangehensweise mittels Zustandsmaschinen. Paxos wurde von Leslie Lamport vorgeschlagen und von Fred B. Schneider begutachtet. Der Protokollentwurf wurde 1990 erstmals als Journalartikel eingereicht, aber erst 1998 veröffentlicht.

Paxos berücksichtigt verschiedene Kompromisse: die benötigte Anzahl an Prozessoren, die Zahl der Nachrichtenverzögerungen bis zum Lernen des vereinbarten Wertes, das Aktivitätsniveau der Teilnehmer, die Zahl der versandten Nachrichten und die zugelassenen Fehlertypen. Nach dem von Fischer, Lynch und Paterson bewiesenen Ergebnis kann kein deterministisches fehlertolerantes Konsensusprotokoll in einem asynchronen Netzwerk Fortschritt garantieren. Paxos garantiert jedoch Konsistenz; die Bedingungen, die Fortschritt verhindern können, sind schwierig herbeizuführen.

Das Protokoll wird vor allem wegen seiner Robustheit eingesetzt, etwa zur Replikation von Dateien oder Datenbanken. Es versucht auch dann Fortschritt zu erzielen, wenn eine begrenzte Zahl von Replikaten zeitweise nicht ansprechbar ist. Außerdem kann es permanent fehlerhafte Replikate entfernen oder neue Replikate hinzufügen. Bereits 1988 zeigten Lynch, Dwork und Stockmeyer, dass Konsensus in einer weitgefassten Gruppe semi-synchroner Systeme lösbar ist. Paxos weist zudem Ähnlichkeiten mit einem 1988 von Oki und Liskov veröffentlichten Protokoll der Viewstamped Replication auf.

Annahmen und Fehlertoleranz

Für die vereinfachte Darstellung gelten bestimmte Annahmen über Prozessoren und Netzwerk. Prozessoren arbeiten mit beliebigen Geschwindigkeiten, und bei ihnen können Störungen auftreten. Prozessoren mit stabilem Speicher können sich nach einer Störung wieder am Protokoll beteiligen. Sie versuchen nicht, das Protokoll zu umgehen; Byzantinische Fehler treten daher nicht auf.

Jeder Prozessor kann Nachrichten an jeden anderen Prozessor senden. Die Nachrichten werden asynchron versandt und können beliebig lange bis zum Empfang benötigen. Sie können verloren gehen, in anderer Reihenfolge eintreffen oder dupliziert werden. Eine Nachricht wird jedoch ohne Verfälschung übertragen, sodass auch im Netzwerk keine Byzantinischen Fehler auftreten.

Allgemein kann ein Konsensusalgorithmus Fortschritt erzielen, wenn 2F+1 Prozessoren eingesetzt werden und gleichzeitig F Prozessoren ausfallen. Durch Rekonfiguration kann ein Protokoll grundsätzlich eine beliebige Anzahl von Ausfällen überstehen, solange nicht mehr als F Prozessoren gleichzeitig ausfallen.

Rollen, Quoren und Vorschläge

Paxos beschreibt die Abläufe anhand der Rollen Client, Acceptor, Proposer, Learner und Leader. Ein einzelner Prozessor kann mehrere Rollen gleichzeitig übernehmen. Das verändert die Korrektheit des Protokolls nicht und kann die Latenz sowie die Zahl der Nachrichten verringern.

Der Client sendet eine Anfrage an das verteilte System und wartet auf eine Antwort, beispielsweise eine Schreibanfrage für eine Datei. Der Proposer vertritt diese Anfrage und versucht, die Acceptors zu einer Einigung zu bewegen. Bei Konflikten übernimmt er außerdem eine koordinierende Funktion.

Acceptors bilden den fehlertoleranten Speicher des Protokolls und können Quoren bilden. Nachrichten müssen an ein Quorum von Acceptors gesendet werden; Nachrichten an einzelne Acceptors werden ignoriert, bis Kopien von jedem Acceptor eines Quorums erhalten wurden. Ein Quorum ist eine Teilsumme der Gesamtheit aller Acceptors. Jedes Paar solcher Teilsummen muss mindestens einen gemeinsamen Teilnehmer enthalten. Üblicherweise besteht ein Quorum aus jeder beliebigen Mehrheit der beteiligten Acceptors.

Learner wirken als Replikationsfaktoren. Sobald Acceptors sich auf eine Clientanfrage geeinigt haben, können Learner die Anfrage ausführen und dem Client antworten. Weitere Learner können hinzugefügt werden, um die Verfügbarkeit der Verarbeitung zu verbessern.

Für Fortschritt braucht Paxos einen ausgewählten Proposer, den Leader. Mehrere Prozesse können zwar glauben, Leader zu sein, aber Fortschritt ist nur garantiert, wenn einer ausgewählt wird. Wenn zwei Prozesse gleichzeitig Leader sein wollen, können sie sich durch ständig kollidierende Vorschläge gegenseitig verzögern. Die Sicherheitseigenschaften bleiben dabei erhalten.

Jeder Versuch, einen vereinbarten Wert festzulegen, erfolgt über einen Vorschlag. Acceptors können einen Vorschlag annehmen oder ablehnen. Jeder Vorschlag besitzt für den jeweiligen Proposer eine eindeutige Nummer. Der zu einem nummerierten Vorschlag gehörende Wert kann optional als Teil des Paxos-Protokolls berechnet werden.

Sicherheit und typischer Einsatz

Paxos definiert drei Sicherheitseigenschaften, die unabhängig von auftretenden Fehlern eingehalten werden:

• Nicht-Trivialität: Nur Werte, die vorgeschlagen wurden, können gelernt werden.
• Sicherheit: Zu einem bestimmten Zeitpunkt kann nur ein einziger Wert gelernt werden. Zwei verschiedene Learner können daher nicht gleichzeitig zwei verschiedene Werte lernen.
• Lebendigkeit (C;L): Wird ein Wert C vorgeschlagen, lernt schließlich irgendwann ein Learner L einen Wert, solange genügend Prozesse fehlerfrei bleiben.

In den meisten Anwendungen übernimmt jeder teilnehmende Prozess zugleich die Rollen Proposer, Acceptor und Learner. Dadurch sinkt die Komplexität der Nachrichten deutlich, ohne dass die Korrektheit beeinträchtigt wird. Im Normalbetrieb senden Clients ihre Befehle an den Leader. Dieser empfängt die Befehle, bestimmt eine neue Befehlsnummer i und startet anschließend die i-te Instanz des Konsensusalgorithmus, indem er Nachrichten an eine Gruppe von Acceptorprozessen sendet.

Durch die Zusammenlegung der Rollen arbeitet Paxos wie ein effizientes „Client-Master-Replika“-Modell, wie es typischerweise bei Datenbanken verwendet wird. Der zentrale Vorteil besteht darin, dass die genannten Sicherheitseigenschaften auch bei den im Modell vorgesehenen Fehlern gewährleistet bleiben.