Paxos und Raft

Paxos und Raft sind die beiden einflussreichsten praktischen Konsensprotokolle, die eine fehlertolerante Einigung über ein repliziertes Logbuch ermöglichen, das realen Koordinationssystemen zugrunde liegt.

Definition

Paxos und Raft sind Quorum-basierte Protokolle, die es einer Reihe von Replikaten ermöglichen, sich auf eine geordnete Abfolge von Befehlen (ein repliziertes Logbuch) zu einigen, trotz Absturzfehlern, und dabei sicherstellen, dass festgeschriebene Einträge niemals verloren gehen oder neu geordnet werden, solange eine Mehrheit der Replikate verfügbar bleibt.

Scope

Dieses Thema behandelt die Paxos-Familie – Single-Decree Paxos, Multi-Paxos und seine technischen Verfeinerungen – sowie das Raft-Protokoll, das dieselben Garantien um einen expliziten Leader, Log-Replikation und Mitgliedschaftsänderungen zur besseren Verständlichkeit neu organisiert. Es umfasst die Rollen von Proposern/Akzeptoren und Leadern/Followern, Quorum-Schnittmengen, Leader-Wahl und -Amtszeiten, Log-Matching sowie die praktischen Aspekte von Snapshots und Rekonfiguration.

Core questions

• Wie gewährleisten Quorum-Schnittmengen und Vorschlagsnummerierung die Sicherheit von Paxos über Runden und Leader-Wechsel hinweg?
• Wie zerlegt Raft den Konsens in Leader-Wahl, Log-Replikation und Sicherheit?
• Welche technischen Herausforderungen ergeben sich bei der Umsetzung dieser Protokolle in Produktionssysteme?

Key theories

Single-Decree und Multi-Paxos

Paxos erzielt eine Einigung über einen Wert durch Prepare- und Accept-Phasen, die durch monotone Vorschlagsnummern und Mehrheitsquoren gesteuert werden; Multi-Paxos amortisiert die Prepare-Phase über einen Strom von Entscheidungen, die von einem stabilen Leader geleitet werden, um ein repliziertes Logbuch zu erstellen.

Rafts Zerlegung

Raft erreicht dieselbe Sicherheit wie Paxos, indem es einen einzelnen Leader pro Amtszeit wählt, der Leader Einträge anhängt, die von Followern repliziert werden, und eine Log-Matching-Eigenschaft durchsetzt, wobei bewusst Minimalität gegen Verständlichkeit und Implementierungsfreundlichkeit eingetauscht wird.

Von der Spezifikation zum laufenden System

Die praktische Implementierung von Paxos erfordert den Umgang mit Festplattenausfällen, Leader-Leases, Log-Kompaktierung und Rekonfiguration – Details, die im ursprünglichen Algorithmus oft vernachlässigt, aber für Korrektheit und Leistung unerlässlich sind.

Clinical relevance

Paxos und Raft laufen in weit verbreiteten Koordinationsdiensten, verteilten Datenbanken und Konfigurationsspeichern; ihr Verständnis ist essenziell für den Aufbau oder Betrieb jedes Systems, das Replikate bei Ausfällen stark konsistent halten muss.

History

Lamport beschrieb Paxos 1998 in seinem Artikel „part-time parliament“ und präzisierte es in „Paxos made simple“ (2001); Chandra und Kollegen berichteten 2007 über die Realitäten der Skalierung; und Ongaro und Ousterhout führten Raft 2014 ein, um äquivalente Garantien wesentlich einfacher lehr- und implementierbar zu machen.

Debates

Verständlichkeit versus Minimalität bei Konsensprotokollen

Raft wurde explizit so konzipiert, dass es leichter zu verstehen ist als Paxos, was eine Debatte darüber auslöste, ob seine zusätzliche Struktur (ein starker Leader) an Flexibilität einbüßt; Befürworter argumentieren, dass Verständlichkeit Implementierungsfehler reduziert, während andere anmerken, dass Paxos-Varianten allgemeiner sein können.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Sind Paxos und Raft grundlegend unterschiedliche Algorithmen?

Nein – sie lösen dasselbe Problem mit demselben Mehrheitsquorum-Kern und äquivalenten Sicherheitsgarantien. Raft reorganisiert Paxos hauptsächlich um einen starken Leader und ein explizites Logbuch, um das Protokoll leichter verständlich und implementierbar zu machen.