Paxos (Informatik)

Paxos ist eine Gruppe von Protokollen mit dem Ziel, einen Konsensus in einem Netzwerk von unzuverlässigen Prozessoren zu erzielen. Konsensus bezeichnet hierbei die Übereinstimmung auf ein gemeinsames Ergebnis in einer Gruppe von Teilnehmern. Die Lösung dieses Problems kann erschwert werden, wenn bei den Teilnehmern oder ihrem Kommunikationsmedium Fehler auftreten.

Konsensusprotokolle sind in verteilten Systemen die Grundlage für die Herangehensweise mittels Zustandsmaschinen, vorgeschlagen von Leslie Lamport und begutachtet von Fred B. Schneider.

Das Paxos-Protokoll wurde erstmals im Jahr 1990 als Journalartikel eingereicht (erst 1998 wurde es veröffentlicht) und nach einem fiktionalen legislativen Konsensussystem benannt, das auf der Insel Paxos in Griechenland verwendet wurde.

Paxos geht verschiedene Kompromisse bezüglich der Anzahl an Prozessoren, der Anzahl an Nachrichtenverzögerungen vor dem Lernen des vereinbarten Wertes, des Aktivitätslevels der einzelnen Teilnehmer, der Anzahl an versandten Nachrichten und den Fehlertypen ein. Obwohl kein deterministisches fehlertolerantes Konsensusprotokoll Fortschritt in einem asynchronen Netzwerk garantieren kann (dies wurde in einem wissenschaftlichen Artikel von Fischer, Lynch und Paterson bewiesen), garantiert Paxos Konsistenz, und die Bedingungen, die einen Fortschritt verhindern könnten, sind schwierig herbeizuführen.

Paxos wird üblicherweise wegen seiner Robustheit eingesetzt (zum Beispiel zur Replikation einer Datei oder einer Datenbank). Das Protokoll versucht sogar dann Fortschritt zu erzielen, wenn Phasen auftreten, in denen eine begrenzte Anzahl von Replikaten nicht ansprechbar sind. Außerdem besitzt Paxos einen Mechanismus, um permanent fehlerhafte Replikate zu entfernen oder neue hinzuzufügen.

Geschichte

1988 demonstrierten Lynch, Dwork und Stockmeyer die Lösbarkeit des Konsensusproblems in einer weitgefassten Gruppe von „semi-synchronen“ Systemen. Paxos hat viele Ähnlichkeiten mit einem Protokoll, das zur Übereinstimmung in der viewstamped replication verwendet wird, erstmals veröffentlicht im Jahr 1988 von Oki and Liskov.

Annahmen

Um die Funktionsweise von Paxos einfacher präsentieren zu können, werden folgende Annahmen und Definitionen explizit getroffen:

Prozessoren

• Prozessoren arbeiten in arbiträren Geschwindigkeiten.
• Störungen in Prozessoren können auftreten.
• Prozessoren mit einem stabilen Speicher können sich nach einer Störung wieder mit dem Protokoll verbinden.
• Prozessoren versuchen nicht, das Protokoll zu umgehen, das heißt, es treten keine Byzantinischen Fehler auf.

Netzwerk

• Prozessoren können Nachrichten an jeden anderen Prozessor senden.
• Nachrichten werden asynchron versandt und benötigen eine arbiträre Empfangszeit.
• Nachrichten können verloren gehen, neu angeordnet oder dupliziert werden.
• Nachrichten werden ohne Korruption übermittelt, das heißt, es treten keine Byzantinischen Fehler auf.

Anzahl an Prozessoren

Allgemein kann ein Konsensusalgorithmus Fortschritte erzielen, indem 2F+1 Prozessoren verwendet werden, obwohl es zu einem gleichzeitigen Ausfall von F Prozessoren kommt. Durch Rekonfiguration kann allerdings ein Protokoll verwendet werden, welches eine beliebige Anzahl an Ausfällen übersteht, solange nicht mehr als F Prozessoren gleichzeitig ausfallen.

Rollen

Paxos beschreibt die Aktionen der Prozesse durch ihre jeweiligen Rollen im Protokoll: Client, Acceptor, Proposer, Learner und Leader. In typischen Implementationen kann ein einzelner Prozessor eine oder mehrere dieser Rollen gleichzeitig innehaben. Dies beeinflusst nicht die Korrektheit des Protokolls, es ist üblich, Rollen zusammenzufügen, um die Latenz bzw. die Anzahl der Nachrichten im Protokoll zu verbessern.

Der Client versendet eine Anfrage an das verteilte System und wartet auf eine Antwort. Beispielsweise könnte dies eine Schreibanfrage für eine Datei auf einem Server des verteilten Systems sein.

Der Acceptor handelt als der fehlertolerante „Speicher“ des Protokolls. Acceptors können Quoren bilden. Jede Nachricht, die an einen Acceptor gesandt wird, muss an ein Quorum von Acceptors gesandt werden. Nachrichten an einen Acceptor werden solange ignoriert, bis Kopien von jedem Acceptor in einem Quorum erhalten wurden.

Ein Proposer vertritt eine Clientanfrage und versucht die Acceptors dazu zu bringen, sich auf diese zu einigen. Außerdem handeln sie als Koordinatoren, sollte es zu Konflikten kommen.

Learner handeln als Replikationsfaktoren im Protokoll. Sobald sich die Acceptors auf eine Clientanfrage geeinigt haben, können die Learner handeln (zum Beispiel das Ausführen der Anfrage und das Senden einer Antwort an den Client). Es ist möglich, weitere Learner hinzuzufügen, um die Verfügbarkeit der Verarbeitung zu verbessern.

Um Fortschritt zu gewährleisten, benötigt Paxos einen ausgewählten Proposer, der Leader genannt wird. Prozesse können glauben, dass sie die Leader sind, aber Fortschritt ist nur dann gewährleistet, wenn einer von diesen ausgewählt wird. Wenn zwei Prozesse glauben, dass sie Leader wären, können sie den Prozess verzögern, indem sie kontinuierlich kollidierende Updates vorschlagen. Aber auch in diesem Fall werden die Sicherheitseigenschaften eingehalten.

Quoren

Quoren gewährleisten, dass zumindest einige wenige Prozessoren und mit ihnen Wissen über das Resultat überleben. Quoren sind so als Teilsummen der Summe aller Acceptors definiert, dass jedes Paar von Teilsummen zumindest einen Teilnehmer teilt. Üblicherweise ist ein Quorum jede beliebige Mehrheit von teilnehmenden Acceptors.

Vorgeschlagene Zahl & Vereinbarter Wert

Jeder Versuch einen vereinbarten Wert zu definieren, wird durch Vorschläge durchgeführt, welche von Acceptors angenommen oder abgelehnt werden können. Jeder Vorschlag hat eine einzigartige Nummer für den jeweiligen Proposer. Der zu dem jeweils nummerierten Vorschlag zugehörige Wert kann optional als Teil des Paxos-Protokolls berechnet werden.

Sicherheitseigenschaften

Um Sicherheit zu garantieren, definiert Paxos drei Sicherheitseigenschaften und gewährleistet, dass diese unabhängig von auftretenden Fehlern eingehalten werden:

Typischer Einsatz

In den meisten Anwendungen von Paxos hat jeder teilnehmende Prozess drei Rollen inne: Proposer, Acceptor und Learner. Dies reduziert die Komplexität der Nachrichten signifikant, ohne dabei die Korrektheit zu beeinträchtigen:

„In Paxos senden Clients Befehle an Leader. Während des normalen Betriebs empfangen Leader die Befehle der Clients, bestimmen eine neue Anzahl an Befehlen i und beginnen dann die i-te Instanz des Konsensusalgorithmus, indem sie Nachrichten an eine Gruppe von Acceptorprozessen senden.“

Indem Rollen zusammengeführt werden, arbeitet das Protokoll im Stil eines effizienten „Client-Master-Replika“-Modells, so wie es typischerweise bei Datenbanken eingesetzt wird. Der Vorteil von Paxos ist dabei die Gewährleistung seiner Sicherheitseigenschaften.

Einzelnachweise

1. Marshall Pease, Robert Shostak, Leslie Lamport: Reaching Agreement in the Presence of Faults. In: Journal of the Association for Computing Machinery. 27. Jahrgang, Nr. 2, April 1980, S. 228–234, doi:10.1145/322186.322188 (englisch, microsoft.com [abgerufen am 2. Februar 2007]). 
2. Leslie Lamport: Time, Clocks and the Ordering of Events in a Distributed System. In: Communications of the ACM. 21. Jahrgang, Nr. 7, Juli 1978, S. 558–565, doi:10.1145/359545.359563 (englisch, microsoft.com [abgerufen am 2. Februar 2007]). 
3. Fred Schneider: Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. In: ACM Computing Surveys. 22. Jahrgang, 1990, S. 299–319, doi:10.1145/98163.98167 (englisch, cornell.edu [PDF]). 
4. Leslie Lamport: The Part-Time Parliament. In: ACM Transactions on Computer Systems. 16. Jahrgang, Nr. 2, Mai 1998, S. 133–169, doi:10.1145/279227.279229 (englisch, microsoft.com [abgerufen am 2. Februar 2007]). 
5. Leslie Lamport's history of the paper. In: microsoft.com. Abgerufen im 1. Januar 1 (englisch). 
6. M. Fischer, N. Lynch, M. Paterson: Impossibility of distributed consensus with one faulty process. In: Journal of the ACM. 32. Jahrgang, Nr. 2, April 1985, S. 374–382, doi:10.1145/3149.214121 (englisch, acm.org [PDF]). 
7. Leslie Lamport, Mike Massa, Massa: Cheap Paxos. Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004). 2004 (englisch, microsoft.com). 
8. Leslie Lamport: Fast Paxos. 2005; abgerufen im 1. Januar 1 (englisch). 
9. Leslie Lamport: Generalized Consensus and Paxos. 2005; abgerufen im 1. Januar 1 (englisch). 
10. Miguel Castro: Practical Byzantine Fault Tolerance. (PDF) 2001; abgerufen im 1. Januar 1 (englisch). 
11. Cynthia Dwork, Nancy Lynch, Larry Stockmeyer: Consensus in the Presence of Partial Synchrony. In: Journal of the ACM. 35. Jahrgang, April 1988, S. 288–323, doi:10.1145/42282.42283 (englisch, mit.edu [PDF]). 
12. Brian Oki, Barbara Liskov, Liskov: Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of Distributed Computing. 1988, S. 8–17, doi:10.1145/62546.62549 (englisch, acm.org). 
13. Leslie Lamport: Lower Bounds for Asynchronous Consensus. 2004; abgerufen im 1. Januar 1 (englisch). 
14. Tushar Chandra, Robert Griesemer, Joshua Redstone: Paxos Made Live – An Engineering Perspective. In: PODC '07: 26th ACM Symposium on Principles of Distributed Computing. 2007 (englisch, google.com).