Wie Maschinen sich einig werden: Verteilter Konsens von FLP über Paxos zu Raft

Der Aufhänger: Das schwierigste einfache Problem der Informatik

Stell dir eine banale Frage vor: Drei Freunde wollen sich auf ein Restaurant einigen. Kein Problem – sie reden, sie stimmen ab, sie gehen essen. Nun erschwere die Sache Schritt für Schritt. Die drei dürfen nur noch schriftliche Nachrichten austauschen. Manche Briefe kommen mit Stunden Verspätung an, manche gar nicht. Einer der Freunde könnte mitten im Austausch einschlafen und erst Stunden später wieder aufwachen – ohne Vorwarnung, und niemand kann von außen unterscheiden, ob er schläft oder nur der Brief noch unterwegs ist. Und trotzdem müssen am Ende alle wachen Freunde beim selben Restaurant landen, und zwar bei einem, das tatsächlich vorgeschlagen wurde.

Das klingt fast trivial, ist aber eines der tiefsten und folgenreichsten Probleme der verteilten Datenverarbeitung: das Konsensproblem. Jedes Mal, wenn eine Gruppe von Rechnern gemeinsam eine verbindliche Entscheidung treffen muss – welcher Server ist gerade der Anführer, welche Transaktion gilt als committet, welcher Wert steht in dieser Datenbankzelle –, steht dieses Problem im Maschinenraum. Es ist das Fundament, auf dem etcd und damit ganz Kubernetes ruht, auf dem CockroachDB, Consul, TiKV, ZooKeeper und letztlich große Teile der heutigen Cloud-Infrastruktur gebaut sind.

Das Bemerkenswerte: Für dieses „einfache" Problem gibt es einen mathematischen Beweis, dass es unter realistischen Annahmen prinzipiell unlösbar ist. Und trotzdem lösen wir es jeden Tag millionenfach. Dieser scheinbare Widerspruch ist kein Skandal, sondern der Kern einer der elegantesten Geschichten der Informatik – einer Geschichte darüber, wie man ein unmögliches Problem so präzise umformuliert, dass es in der Praxis doch beherrschbar wird.

Dieser Artikel nimmt dich auf die ganze Strecke mit: von der genauen Definition dessen, was Konsens eigentlich verlangt, über das berühmte FLP-Unmöglichkeitsresultat, hin zu Paxos – Leslie Lamports berüchtigt schwer verständlicher, aber grundlegender Lösung – und schließlich zu Raft, dem Algorithmus, dessen erklärtes Designziel Verständlichkeit war und der deshalb heute die Praxis dominiert. Am Ende steht eine Denkfigur, die weit über verteilte Systeme hinausreicht.

Teil 1: Was Konsens wirklich verlangt

Drei Eigenschaften, die zusammen den Ärger machen

Bevor wir über Lösungen reden, müssen wir das Problem sauber fassen. „Sich einigen" ist umgangssprachlich; die Informatik verlangt Präzision. Ein Konsensprotokoll muss, wenn eine Menge von Prozessen jeweils einen Wert vorschlägt, am Ende genau drei Bedingungen erfüllen:

Agreement (Übereinstimmung): Keine zwei korrekten Prozesse entscheiden sich für verschiedene Werte. Es darf am Ende nicht zwei Fraktionen geben, die glauben, unterschiedliche Wahrheiten seien beschlossen worden.

Validity (Gültigkeit): Der entschiedene Wert muss von einem der Prozesse tatsächlich vorgeschlagen worden sein. Das Protokoll darf sich nicht auf einen frei erfundenen Wert einigen, nur um formal „einig" zu sein.

Termination (Terminierung): Jeder korrekte Prozess entscheidet sich irgendwann. Das Protokoll darf nicht ewig unentschlossen bleiben.

Die ersten beiden Eigenschaften nennt man Sicherheitsbedingungen (safety): Sie besagen, dass „nie etwas Schlimmes passiert". Die dritte ist eine Lebendigkeitsbedingung (liveness): Sie besagt, dass „irgendwann etwas Gutes passiert". Diese Unterscheidung wird sich als der entscheidende Hebel der gesamten Geschichte erweisen.

Das Fehlermodell: Womit müssen wir rechnen?

Warum ist das schwer? Weil die reale Welt der verteilten Systeme unangenehme Eigenschaften hat, die man in einem Fehlermodell zusammenfasst. Der Klassiker der Theorie ist das asynchrone System mit Crash-Fehlern. Drei Zutaten machen es giftig.

Erstens die Asynchronität: Es gibt keine obere Schranke für die Zeit, die eine Nachricht unterwegs sein darf, und keine Schranke dafür, wie unterschiedlich schnell Prozesse rechnen. Eine Nachricht kann eine Millisekunde brauchen oder eine Stunde – beides ist „erlaubt".

Zweitens die Crash-Fehler: Ein Prozess darf zu jedem beliebigen Zeitpunkt dauerhaft anhalten, ohne Vorwarnung. Er wird nicht bösartig, er lügt nicht – er hört einfach auf.

Drittens, und das ist die eigentliche Falle: die Ununterscheidbarkeit. In einem asynchronen System kann ein Beobachter prinzipiell nicht unterscheiden, ob ein anderer Prozess abgestürzt ist oder ob seine Antwort nur sehr, sehr langsam unterwegs ist. Ein ausbleibendes Signal hat zwei mögliche Ursachen, und keine Beobachtung von außen kann sie trennen. Genau an dieser Ununterscheidbarkeit hängt das gesamte Drama.

Teil 2: Die Unmöglichkeit – das FLP-Theorem

Ein Beweis, der die Grenzen absteckt

1985 veröffentlichten Michael Fischer, Nancy Lynch und Michael Paterson ein Papier mit dem nüchternen Titel Impossibility of Distributed Consensus with One Faulty Process. Das Resultat, heute schlicht FLP genannt, ist eines der wichtigsten der Informatik und wurde später mit dem Dijkstra-Preis für die einflussreichsten Arbeiten des Feldes ausgezeichnet.

Die Aussage ist so knapp wie erschütternd: In einem vollständig asynchronen System gibt es keinen deterministischen Algorithmus, der das Konsensproblem garantiert löst, wenn auch nur ein einziger Prozess abstürzen darf. Nicht „keinen effizienten", nicht „keinen bekannten" – schlicht keinen, der existieren kann.

Man muss die Feinheit betonen, damit das Resultat nicht überinterpretiert wird: FLP sagt nicht, dass Konsens immer scheitert. Es sagt, dass jeder korrekte Algorithmus mindestens eine unendliche Ausführung besitzt, in der nie eine Entscheidung fällt. Es gibt also keinen Algorithmus, der Sicherheit und Terminierung gleichzeitig und unter allen Umständen garantiert. Sicherheit (nie zwei widersprüchliche Entscheidungen) kann man immer wahren – aber niemand kann garantieren, dass die Entscheidung überhaupt fällt, wenn das Netz maximal bösartig trödelt.

Die Idee des Beweises: der schwebende Zustand

Der Beweis ist elegant und lohnt eine intuitive Skizze. Man betrachtet die möglichen Systemzustände und teilt sie in drei Sorten: Zustände, aus denen nur noch „0" entschieden werden kann; Zustände, aus denen nur noch „1" entschieden werden kann; und bivalente Zustände, aus denen je nach weiterem Verlauf noch beides herauskommen kann – der Ausgang schwebt noch.

Fischer, Lynch und Paterson zeigen zwei Dinge. Erstens: Jedes korrekte Konsensprotokoll besitzt einen anfänglichen bivalenten Zustand – die Entscheidung ist am Start noch offen. Zweitens, und das ist der Trick: Aus jedem bivalenten Zustand lässt sich durch geschicktes Verzögern genau einer Nachricht ein weiterer bivalenter Zustand erreichen. Der Widersacher – man denke sich einen bösartigen Netzwerk-Scheduler – muss die Entscheidung nie erzwingen; er muss nur immer die eine kritische Nachricht so lange zurückhalten, bis das System in den nächsten schwebenden Zustand kippt. So entsteht eine unendliche Kette von Bivalenz: Das System entscheidet nie. Weil der Scheduler dabei nie eine Nachricht verliert (er verzögert sie nur endlich, aber beliebig lange), verletzt er keine einzige Regel des asynchronen Modells.

Warum die Welt trotzdem funktioniert

Wenn Konsens beweisbar unmöglich ist – wie kann dann Kubernetes laufen? Die Antwort liegt in einer feinen Lücke im FLP-Modell. FLP nimmt perfekte Asynchronität an: Nachrichten dürfen beliebig lange brauchen, ohne je eine Schranke zu verletzen. Die reale Welt ist milder. Meistens antworten Netzwerke innerhalb von Millisekunden; lange Verzögerungen sind selten und vorübergehend.

Praktische Algorithmen nutzen genau das aus. Sie geben die kompromisslose Garantie „terminiert immer" auf und ersetzen sie durch: „terminiert immer dann, wenn das Netz sich für eine Weile hinreichend gutartig verhält." Sicherheit halten sie unbedingt – sie treffen also nie eine falsche oder widersprüchliche Entscheidung, egal wie chaotisch das Netz ist. Nur die Lebendigkeit wird an eine milde Realitätsannahme geknüpft. Man formalisiert das etwa über Timeouts (die eine Vermutung „der ist wohl abgestürzt" erzeugen) oder über partielle Synchronie (Dwork, Lynch, Stockmeyer 1988: Es gibt eine Schranke, sie gilt aber erst ab einem unbekannten Zeitpunkt). FLP umgeht man auch mit Randomisierung. Der praktische Kompromiss aber lautet fast überall: Sicherheit immer, Lebendigkeit fast immer. Merke dir diese Formel – sie ist der Schlüssel zu Paxos und Raft.

Teil 3: Paxos – die grundlegende Lösung

Das Parlament, das niemand verstand

1989 – veröffentlicht wurde es erst 1998 – schrieb Leslie Lamport (derselbe, dessen logische Uhren im Spanner-Artikel eine Rolle spielten, siehe Uhren, die ihre eigene Unsicherheit kennen: Google Spanner, TrueTime und die Beherrschung der Zeit in der Cloud) das Papier The Part-Time Parliament. Er kleidete den Algorithmus in eine Allegorie: ein fiktives Parlament auf der griechischen Insel Paxos, dessen Abgeordnete nur teilzeitlich anwesend sind und dennoch konsistente Beschlüsse fassen müssen. Die Verpackung war so verschnörkelt, dass die Fachwelt den eigentlichen Algorithmus jahrelang ignorierte oder missverstand. 2001 kapitulierte Lamport halb ironisch und schrieb Paxos Made Simple – vier Seiten, die auf die Allegorie verzichten und den Kern in Klartext hinstellen. Der berühmte erste Satz lautet sinngemäß: „Der Paxos-Algorithmus ist, wenn man ihn in einfachem Englisch erklärt, sehr einfach." Viele Leser fanden ihn trotzdem quälend schwer – ein Umstand, der später Raft überhaupt erst motivierte.

Drei Rollen und ein Versprechen

Paxos verteilt die Arbeit auf drei logische Rollen, die ein und dieselbe Maschine gleichzeitig spielen kann. Proposer schlagen Werte vor (typischerweise im Auftrag eines Clients). Acceptors bilden das kollektive Gedächtnis: Sie nehmen Vorschläge an oder lehnen sie ab, und ihre Mehrheit entscheidet, was gilt. Learner erfahren schließlich, welcher Wert gewählt wurde, und führen ihn aus.

Der entscheidende Baustein ist die Mehrheit (das Quorum). Ein Wert gilt genau dann als gewählt, wenn eine Mehrheit der Acceptors ihn angenommen hat. Warum Mehrheit? Weil sich je zwei Mehrheiten in mindestens einem Acceptor überschneiden. Dieser eine gemeinsame Acceptor ist der stille Held des ganzen Verfahrens: Er verhindert, dass zwei verschiedene Mehrheiten unbemerkt zwei verschiedene Werte wählen. Die Schnittmenge zweier Mehrheiten ist nie leer – und genau das trägt die Sicherheitsgarantie.

Die zwei Phasen

Basis-Paxos wählt einen einzigen Wert in zwei Runden. Jeder Vorschlag trägt eine eindeutige, monoton wachsende Vorschlagsnummer.

In Phase 1 (Prepare) schickt ein Proposer eine Prepare(n)-Nachricht mit seiner Nummer n an eine Mehrheit der Acceptors. Ein Acceptor, der n empfängt, gibt zwei Versprechen ab, sofern n größer ist als alles, was er bisher gesehen hat: Erstens ignoriert er künftig alle Vorschläge mit kleinerer Nummer. Zweitens verrät er dem Proposer, ob er bereits einen Wert angenommen hat – und wenn ja, welchen und mit welcher Nummer.

In Phase 2 (Accept) wertet der Proposer die Antworten aus. Hat irgendein Acceptor bereits einen Wert angenommen, dann darf der Proposer nicht seinen eigenen Wunschwert durchsetzen, sondern muss den Wert mit der höchsten bereits angenommenen Nummer übernehmen. Nur wenn kein Acceptor je einen Wert angenommen hat, ist er frei, seinen eigenen zu wählen. Diesen Wert schickt er als Accept(n, wert) an die Mehrheit. Nehmen genug Acceptors an, ist der Wert gewählt.

Die zunächst kontraintuitive Regel in Phase 2 – „übernimm den fremden Wert" – ist das eigentliche Herzstück. Sie sorgt dafür, dass ein einmal (womöglich unbemerkt) gewählter Wert von keinem späteren Vorschlag mehr überschrieben werden kann. Ist ein Wert erst von einer Mehrheit angenommen, wird jeder spätere Proposer in Phase 1 zwangsläufig auf mindestens einen Acceptor stoßen, der diesen Wert kennt, und ihn dann selbst weitertragen. So bleibt die Entscheidung stabil, egal wie viele Proposer gleichzeitig auftreten oder abstürzen.

Multi-Paxos und das Problem der Verständlichkeit

Basis-Paxos einigt sich auf einen Wert. Eine echte Datenbank aber braucht eine ganze Folge von Entscheidungen – Eintrag 1, Eintrag 2, Eintrag 3 –, praktisch ein repliziertes Logbuch (verwandt mit dem Gedanken des unveränderlichen Ereignis-Logs, siehe Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen). Die naive Lösung, für jeden Eintrag ein volles Zwei-Phasen-Paxos zu fahren, ist teuer. Multi-Paxos optimiert das: Ein Proposer, der sich einmal als stabiler Anführer etabliert hat, darf Phase 1 überspringen und für viele Log-Einträge direkt in Phase 2 gehen. Das ist schnell – aber die Papiere ließen viele Details offen: Wie genau wählt man diesen Anführer? Wie behandelt man Lücken im Log? Wie ändert man die Mitgliedermenge im laufenden Betrieb? Jede Firma implementierte ihre eigene Variante, und keine glich der anderen. Genau diese Kluft zwischen dem eleganten Kern und dem unterspezifizierten Praxisgebilde war der Nährboden für Raft.

Teil 4: Raft – Verständlichkeit als Designziel

Ein Algorithmus mit einer ungewöhnlichen Zielfunktion

2014 stellten Diego Ongaro und John Ousterhout von der Stanford University Raft vor, im Papier mit dem programmatischen Titel In Search of an Understandable Consensus Algorithm. Ihr erklärtes Hauptziel war ungewöhnlich für einen Algorithmus: nicht in erster Linie Geschwindigkeit oder minimale Nachrichtenzahl, sondern Verständlichkeit. Sie erzeugt ein Ergebnis, das gleichwertig zu Multi-Paxos und ähnlich effizient ist – aber ihre Struktur ist bewusst so gebaut, dass ein Mensch sie im Kopf behalten kann. Die Autoren führten sogar eine Nutzerstudie durch: Studierende verstanden Raft nachweislich leichter als Paxos.

Der zentrale didaktische Kniff: Raft zerlegt das Problem in drei weitgehend unabhängige Teilprobleme – Leader-Wahl, Log-Replikation und Sicherheit – und erzwingt eine stärkere Kohärenz, um die Zahl der zu bedenkenden Zustände zu verringern.

Ein starker Anführer und die Amtszeiten

Raft macht eine Designentscheidung, die Paxos scheut: einen starken Anführer. Zu jeder Zeit ist genau ein Knoten Leader; alle Client-Anfragen laufen über ihn, und der Datenfluss geht ausschließlich vom Leader zu den Followern. Das macht das System leichter zu durchdenken, denn es gibt einen einzigen Ort, an dem die Wahrheit entsteht.

Die Zeit teilt Raft in Terms (Amtszeiten) ein – fortlaufend nummerierte Perioden, die jeweils mit einer Wahl beginnen. Ein Term ist Rafts logische Uhr: Jede Nachricht trägt die Term-Nummer, und ein Knoten, der eine höhere Term-Nummer sieht als seine eigene, erkennt sofort, dass er veraltet ist, tritt zurück und aktualisiert sich. Ein Term hat höchstens einen Leader; manche Terms enden ergebnislos (Stimmengleichheit), dann beginnt einfach der nächste.

Jeder Knoten ist zu jeder Zeit in einem von drei Zuständen: Follower (passiv, folgt dem Leader), Candidate (bewirbt sich gerade um die Führung) oder Leader.

Die Leader-Wahl

Follower erwarten regelmäßige Heartbeat-Nachrichten vom Leader. Bleiben diese über eine zufällig gewählte Zeitspanne (das Election-Timeout) aus, vermutet der Follower, der Leader sei tot, erhöht seine Term-Nummer, wechselt in den Candidate-Zustand und bittet die anderen um Stimmen (RequestVote). Jeder Knoten vergibt pro Term höchstens eine Stimme, nach dem Prinzip „wer zuerst kommt". Erhält ein Candidate die Stimmen einer Mehrheit, wird er Leader und beginnt sofort, Heartbeats zu senden, um seine Autorität zu festigen.

Der elegante Trick gegen endlose Patt-Situationen sind die zufälligen Timeouts. Weil jeder Knoten eine leicht andere Wartezeit auswürfelt (etwa 150–300 ms), startet meist nur einer die Wahl, gewinnt sie schnell und beendet damit das Rennen, bevor andere überhaupt loslaufen. Kommt es doch einmal zum Gleichstand, sorgt neues Würfeln in der nächsten Runde fast sicher für eine baldige Entscheidung. Das ist FLP in Aktion: Die Terminierung ist nicht garantiert, aber praktisch sicher – genau der Kompromiss aus Teil 2.

Log-Replikation

Sobald ein Leader steht, nimmt er Client-Befehle entgegen, hängt jeden als neuen Eintrag an sein eigenes Log und schickt ihn per AppendEntries an alle Follower. Jeder Log-Eintrag trägt den Befehl, den Term und einen Index. Hat eine Mehrheit der Knoten den Eintrag gespeichert, gilt er als committet: Jetzt – und erst jetzt – wendet der Leader ihn auf seine Zustandsmaschine an und meldet dem Client den Erfolg. Committete Einträge gehen niemals verloren.

Damit die Logs konsistent bleiben, gilt die Log-Matching-Eigenschaft: Jede AppendEntries-Nachricht enthält Index und Term des unmittelbar vorangehenden Eintrags. Passt das beim Follower nicht, lehnt er ab, und der Leader tastet sich rückwärts, bis beide Logs einen gemeinsamen Punkt finden; ab da überschreibt der Leader die abweichenden Follower-Einträge mit seinen eigenen. So konvergieren alle Logs zwangsläufig auf die Version des Leaders.

Die Sicherheitsgarantie

Der subtilste Teil ist, sicherzustellen, dass ein neuer Leader keine bereits committeten Einträge „vergisst". Raft löst das über eine Wahleinschränkung: Ein Candidate bekommt eine Stimme nur, wenn sein eigenes Log mindestens so aktuell ist wie das des Wählers (verglichen über Term und Index des letzten Eintrags). Weil ein committeter Eintrag per Definition auf einer Mehrheit liegt, und weil jede Wahl eine Mehrheit braucht, überschneiden sich beide Mengen: Der künftige Leader muss jeden committeten Eintrag bereits besitzen. So kann nur gewinnen, wer die vollständige committete Historie kennt. Diese eine Bedingung ist das Rückgrat von Raffts Sicherheit – und ein Paradebeispiel dafür, wie sich das Quorum-Überschneidungsargument aus Paxos in Raft in verständlicher Form wiederfindet.

Teil 5: Die Mathematik der Fehlertoleranz

Warum es fast immer ungerade Zahlen sind

Sowohl Paxos als auch Raft brauchen für jede Entscheidung eine Mehrheit (\(\lfloor N/2 \rfloor + 1\) von \(N\) Knoten). Daraus folgt eine einfache, aber oft missverstandene Formel: Um \(f\) gleichzeitige Crash-Ausfälle zu überleben, braucht man \(N = 2f + 1\) Knoten.

Die Tabelle erklärt, warum Produktionscluster fast immer ungerade Knotenzahlen verwenden. Ein 4-Knoten-Cluster verträgt genau so viele Ausfälle wie ein 3-Knoten-Cluster (nämlich einen), kostet aber einen Server mehr und verlangt für jede Entscheidung eine Antwort von dreien statt zweien – schlechter in jeder Hinsicht. Der Sprung von 3 auf 5 dagegen erhöht die Fehlertoleranz echt von eins auf zwei. Ungerade Größen maximieren also die Ausfallsicherheit pro Server.

Split-Brain und warum die Minderheit schweigen muss

Der wichtigste praktische Nutzen der Mehrheitsregel zeigt sich bei einer Netzpartition. Zerfällt ein 5-Knoten-Cluster in eine Gruppe zu 3 und eine zu 2, dann kann nur die Dreiergruppe eine Mehrheit bilden und weiterarbeiten. Die Zweiergruppe kann keinen Leader wählen und keine Schreibvorgänge committen – sie verweigert sich, bis die Verbindung zurückkehrt. Das ist kein Fehler, sondern die zentrale Schutzfunktion: Sie verhindert das gefürchtete Split-Brain, bei dem zwei Teilcluster unabhängig voneinander widersprüchliche Entscheidungen träfen. Lieber steht die Minderheit still, als dass sie die Konsistenz zerstört. Hier zahlt sich der Kompromiss aus Teil 2 erneut aus: Sicherheit wird unbedingt gewahrt, Verfügbarkeit auf der Minderheitsseite geopfert – eine unmittelbare Konsequenz des CAP-Theorems.

Teil 6: Konsens in der freien Wildbahn

Die Theorie ist kein Selbstzweck; sie läuft heute in praktisch jeder ernsthaften Cloud-Infrastruktur.

etcd und Kubernetes. etcd ist ein verteilter Schlüssel-Wert-Speicher, der Raft implementiert und den gesamten Cluster-Zustand von Kubernetes hält. Jede Zustandsänderung – ein neuer Pod, ein geändertes Deployment – geht durch Raft-Konsens in etcd. Fällt etcd ohne Mehrheit aus, „friert" die Steuerungsebene von Kubernetes ein: Laufende Container bleiben zwar am Leben, aber es lassen sich keine neuen Entscheidungen mehr treffen. Die etcd-Raft-Bibliothek gilt seit Jahren als eine der meistgenutzten der Welt und bedient täglich zehntausende Cluster.

Consul von HashiCorp kombiniert Service-Discovery, Health-Checks und einen KV-Speicher. Für die Cluster-Mitgliedschaft nutzt es ein Gossip-Protokoll (Serf), für den konsistenten Zustand aber Raft.

CockroachDB und TiKV treiben die Idee auf die Spitze. Eine einzelne Raft-Gruppe skaliert nicht über Terabytes, weil ein einziger Leader zum Flaschenhals würde. Deshalb zerlegen beide die Daten in viele Bereiche (Ranges) und betreiben pro Bereich eine eigene Raft-Gruppe – Multi-Raft. So verteilt sich die Konsens-Last über den ganzen Cluster.

Google Spanner schließlich nutzt für die Replikation jedes Datenbereichs Paxos-Gruppen und kombiniert das mit der TrueTime-Uhr aus dem früheren Artikel. Konsens sorgt dort für die Ordnung innerhalb einer Replikationsgruppe, TrueTime für die global konsistente Zeit zwischen ihnen – zwei Bausteine, die zusammen die externe Konsistenz tragen.

Was Konsens nicht löst: byzantinische Fehler

Eine wichtige Grenze: Paxos und Raft gehen von Crash-Fehlern aus – ein Knoten hört auf, aber er lügt nie. Er sendet keine widersprüchlichen oder böswillig gefälschten Nachrichten. Fällt diese Annahme – etwa weil ein Knoten kompromittiert wurde oder Hardware bizarr fehlerhaft antwortet –, spricht man von byzantinischen Fehlern (nach Lamports „Byzantine Generals Problem"). Diese abzuwehren verlangt andere, teurere Algorithmen (PBFT und Nachfolger) und, wie man zeigen kann, \(N = 3f + 1\) statt \(2f + 1\) Knoten. Blockchains mit gegenseitig misstrauischen Teilnehmern operieren in genau dieser byzantinischen Welt; die klassische Cloud-Infrastruktur dagegen vertraut ihren eigenen Servern und kommt mit dem günstigeren Crash-Modell aus.

Ein Framework zum Mitnehmen: Paxos vs. Raft

Beide Algorithmen ruhen auf demselben mathematischen Fundament – der nichtleeren Schnittmenge zweier Mehrheiten. Der Unterschied ist weniger technischer als didaktischer Natur: Raft trifft an vielen Stellen eine konkrete, etwas restriktivere Wahl, wo Paxos einen Freiheitsgrad offenlässt. Diese Selbstbeschränkung kostet theoretische Allgemeinheit und gewinnt dafür etwas ungemein Wertvolles: einen Algorithmus, den ein Team tatsächlich korrekt implementieren kann.

Erkenntnis zum Mitnehmen

Die tiefste Lektion dieser Geschichte ist nicht ein bestimmtes Protokoll, sondern eine Haltung zum Umgang mit Unmöglichkeit. FLP beweist, dass man Sicherheit und Terminierung nicht gleichzeitig und unbedingt haben kann. Die naive Reaktion wäre Resignation. Die geniale Reaktion war, das Problem umzuformulieren: Sicherheit wird nie aufgegeben, Lebendigkeit wird an eine milde Realitätsannahme geknüpft. Man verzichtet auf ein absolutes Versprechen, das die Theorie ohnehin verbietet, und tauscht es gegen ein bedingtes, das die Praxis fast immer einlöst.

Für die tägliche Ingenieursarbeit steckt darin eine übertragbare Denkfigur. Wenn du das nächste Mal vor einer unmöglich erscheinenden Anforderung stehst – „immer verfügbar und immer konsistent und über Kontinente verteilt" –, dann suche nicht nach dem Bruch der Naturgesetze, sondern nach der einen Eigenschaft, die du unbedingt halten musst (meist die Sicherheit: keine Datenkorruption), und der anderen, die du an eine Bedingung knüpfen darfst (meist die Verfügbarkeit: „solange eine Mehrheit erreichbar ist"). Konsensalgorithmen sind das kanonische Beispiel dafür, dass man ein bewiesenermaßen unlösbares Problem gewinnt, indem man aufhört, das Falsche zu verlangen.

Und ganz konkret: Wenn du das nächste Mal einen etcd-, Consul- oder CockroachDB-Cluster dimensionierst, wähle eine ungerade Knotenzahl (3, 5 oder 7), verteile die Knoten über Fehlerzonen so, dass keine einzelne Zone die Mehrheit hält, und mach dir bewusst: In dem Moment, in dem die Mehrheit unerreichbar wird, soll dein System lieber Schreibvorgänge verweigern, als die Konsistenz zu riskieren. Dieses Schweigen der Minderheit ist kein Defekt – es ist der Beweis, dass der Algorithmus funktioniert.

Reflexionsfrage

In deiner eigenen Systemlandschaft: Welche Komponente triffst du gerade implizit eine Konsensentscheidung, ohne einen echten Konsensmechanismus dahinter zu haben – etwa zwei Dienste, die unabhängig entscheiden, wer „der Aktive" ist, oder ein verteilter Cache, dessen Knoten bei einer Partition auseinanderdriften dürften? Und wärst du bereit, in dieser Komponente im Ernstfall die Verfügbarkeit der Minderheit zu opfern, um die Konsistenz zu retten – oder ist es genau umgekehrt, und du brauchst dort gar keinen strengen Konsens?

Querverweise im Vault

• Uhren, die ihre eigene Unsicherheit kennen: Google Spanner, TrueTime und die Beherrschung der Zeit in der Cloud – Spanner nutzt Paxos-Gruppen für die Replikation und ergänzt sie um TrueTime; dort auch Lamports logische Uhren.
• Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen – das replizierte Log als „einzige Quelle der Wahrheit" ist die gemeinsame Denkfigur von Konsens und Event Sourcing.

Quellen

• Fischer, Lynch, Paterson (1985): Impossibility of Distributed Consensus with One Faulty Process. FLP-Papier (PDF) · Erläuterung des Beweises (INRIA ANTIQUE)
• Lamport (1998/2001): The Part-Time Parliament und Paxos Made Simple. Paxos Made Simple (PDF)
• Ongaro, Ousterhout (2014): In Search of an Understandable Consensus Algorithm (Raft). Raft-Papier (PDF) · USENIX ATC '14
• etcd Raft-Bibliothek (GitHub) – Referenzimplementierung hinter Kubernetes und vielen anderen Systemen.
• Consul Consensus (HashiCorp) – Raft in einem Produktionssystem.

← All articles