Won’t fix! – Teil 3: Warum verteilter Konsens schwer bis unmöglich ist

Bestimmte Eigenschaften von Programmen sind mathematisch unentscheidbar, und kein Werkzeug der Welt kann daran etwas ändern. Sobald Software jedoch auf mehrere Maschinen verteilt wird, kommt eine ganz andere Klasse von Grenzen hinzu. Die machen schon das einfachste Koordinationsproblem im allgemeinen Fall unmöglich. Wie Teil 2 dieser Serie gezeigt hat, lassen sich selbst Bugs nicht systematisch eliminieren.

Wer mit relationalen Datenbanken arbeitet, kennt die Funktion AUTO_INCREMENT. Sie liefert für jede neue Zeile einen ganzzahligen Wert, der lückenlos und monoton ansteigt: 1, 2, 3, 4 und so weiter. Die Funktion ist so unauffällig, dass kaum jemand darüber nachdenkt, wie sie eigentlich funktioniert. Sie funktioniert eben.

Sobald die Datenbank aber auf mehrere Knoten verteilt ist, wird daraus eine der folgenschwersten Fragen der Informatik: Welcher Knoten vergibt die nächste ID? Was geschieht, wenn zwei Knoten gleichzeitig eine neue Zeile einfügen? Was passiert, wenn das Netzwerk zwischen ihnen für einige Sekunden ausfällt? Was scheinbar harmlos klingt, führt direkt zu einer Reihe theoretischer Resultate, die zeigen: Eine perfekte Lösung kann es nicht geben. Nicht aus Mangel an Sorgfalt, sondern aus mathematisch nachweisbaren Gründen.

Die Versuchung der zentralen Lösung

Der erste Reflex liegt nahe: Wenn die verteilte Vergabe schwierig ist, dann führt eben ein einziger Dienst Buch über die nächste freie Zahl. Alle Knoten fragen ihn an, er antwortet, fertig. Solange dieser Dienst läuft und das Netzwerk steht, funktioniert das tadellos.

Die Probleme zeigen sich erst, sobald sich die Realität meldet. Fällt der Dienst aus, kann kein Knoten mehr Daten anlegen. Wird er zum Engpass, weil tausende Anfragen pro Sekunde eintreffen, bremst er das gesamte System aus. Reißt das Netzwerk zwischen ihm und einem Teil der Knoten ab, sind diese Knoten effektiv arbeitsunfähig, obwohl sie selbst völlig in Ordnung sind. Was als zentrale Lösung gedacht war, wird zum Single Point of Failure.

Eine naheliegende Erweiterung lautet: Dann eben mehrere Dienste, die sich abstimmen. Doch genau damit beginnt das eigentliche Problem. Wie stimmen sich diese Dienste ab? Wer entscheidet bei einer Meinungsverschiedenheit? Was geschieht, wenn die Verbindung zwischen ihnen ausfällt? Die Frage nach der nächsten ID ist nichts anderes als die Frage nach Konsens zwischen mehreren Knoten, und dieser Konsens ist genau das Problem.

Die zwei Generäle und ihre Boten

Ein Gedankenexperiment, das in den 1970er-Jahren formuliert wurde, bringt das Grundproblem auf den Punkt. Zwei Generäle wollen eine feindliche Stadt einnehmen. Ihre Armeen sind so positioniert, dass ein gemeinsamer Angriff sicher zum Sieg führt, ein einseitiger Angriff aber zur Niederlage. Sie können sich nur über Boten verständigen, die durch das von Feinden besetzte Tal zwischen ihnen laufen müssen. Jeder Bote kann unterwegs gefangen werden.

General A schickt einen Boten mit der Nachricht: „Wir greifen morgen früh um sechs Uhr an.“ Damit der Plan aufgeht, muss A wissen, dass B die Nachricht erhalten hat. Also schickt B einen Boten zurück mit der Bestätigung. Doch nun muss B wissen, dass A diese Bestätigung erhalten hat, denn ohne dieses Wissen kann A immer noch denken, B hätte die ursprüngliche Nachricht nie bekommen. Also bestätigt A die Bestätigung. Doch dann braucht A wieder eine Bestätigung dieser Bestätigung. Und so weiter, ad infinitum.

Wie lässt sich beweisen, dass keine endliche Anzahl von Bestätigungen genügt? Angenommen, eine Folge von n Boten würde reichen. Dann betrachtet man den letzten Boten in dieser Folge. Da er gefangen werden könnte, kann sein Absender sich nicht darauf verlassen, dass die Nachricht angekommen ist. Also kann er nicht mit Sicherheit angreifen. Folglich kann auch n minus eins keine Sicherheit geben. Per Induktion zeigt sich: Keine endliche Anzahl funktioniert.

Das Two-Generals-Problem ist nicht nur eine hübsche Anekdote, sondern die fundamentale Wahrheit hinter jedem verteilten System. Zwei Knoten, die über ein unzuverlässiges Netzwerk kommunizieren, können niemals mit absoluter Sicherheit feststellen, dass der jeweils andere eine bestimmte Nachricht erhalten hat. Was beim TCP-Handshake mit drei Schritten so robust aussieht, ist in Wahrheit nur eine pragmatische Annäherung. Auch ein Drei-Wege-Handshake liefert keine theoretische Garantie, sondern lediglich eine ausreichend hohe Wahrscheinlichkeit für die meisten Anwendungsfälle. Jede praktische Lösung in der Softwareentwicklung ist ein Kompromiss, der diese Unsicherheit zu einem akzeptablen Restrisiko reduziert, aber niemals beseitigt.

Das CAP-Theorem

Im Jahr 2000 stellte der Informatiker Eric Brewer auf einer Konferenz eine These auf, die seither die Diskussion über verteilte Systeme prägt. Sie ist heute als CAP-Theorem bekannt und besagt, dass ein verteiltes System nicht gleichzeitig drei wünschenswerte Eigenschaften garantieren kann.

Diese drei Eigenschaften sind Consistency (Konsistenz), Availability (Verfügbarkeit) und Partition Tolerance (Toleranz gegenüber Netzwerkpartitionen). Konsistenz bedeutet, dass alle Knoten zu jedem Zeitpunkt denselben Wert für eine bestimmte Information liefern. Verfügbarkeit bedeutet, dass jede Anfrage in endlicher Zeit eine Antwort erhält. Partition Tolerance bedeutet, dass das System auch dann weiterarbeitet, wenn das Netzwerk zwischen einigen Knoten zusammenbricht. Garantieren lassen sich höchstens zwei dieser drei Eigenschaften gleichzeitig. Zwei Jahre später lieferten Seth Gilbert und Nancy Lynch den formalen Beweis für diese Aussage.

In der Praxis ist die Wahl weniger frei, als das Theorem zunächst vermuten lässt. Netzwerkpartitionen lassen sich nicht vermeiden. Ein Kabel wird durchtrennt, ein Switch fällt aus, ein Rechenzentrum verliert kurzzeitig die Verbindung zur Außenwelt. Wer ein verteiltes System baut, muss mit Partitionen rechnen, ob das gewollt ist oder nicht. Damit reduziert sich die Wahl in der Praxis auf eine Entscheidung zwischen Konsistenz und Verfügbarkeit.

Ein konsistentes System wird im Falle einer Partition lieber Anfragen ablehnen als möglicherweise veraltete Daten zu liefern. Datenbanken wie etcd, Zookeeper oder Consul, die Konfigurationsdaten und Koordinationsinformationen verwalten, arbeiten nach diesem Prinzip. Lieber für einige Sekunden nicht erreichbar als kurzzeitig falsche Auskünfte zu geben. Ein verfügbares System hingegen liefert auch bei einer Partition eine Antwort, akzeptiert dafür aber, dass diese Antwort möglicherweise nicht den aktuellen Stand widerspiegelt. Datenbanken wie Cassandra oder DynamoDB folgen diesem Ansatz, weil ihre Anwendungsfälle Verfügbarkeit höher gewichten.

Auf das ursprüngliche Problem der nächsten ID übertragen heißt das: Wer lückenlos aufsteigende IDs garantieren will, muss bei einer Netzwerkpartition aufhören, neue IDs zu vergeben. Wer hingegen jederzeit eine ID vergeben können will, muss Lücken in der Folge oder Verletzungen der Reihenfolge in Kauf nehmen. Beides gleichzeitig ist nicht möglich, und das ist keine Frage besserer Algorithmen, sondern eine mathematische Grenze.

Besonders heimtückisch ist der Fall, in dem zwei Teile eines partitionierten Systems beide weiterarbeiten, ohne voneinander zu wissen. Dieses Phänomen ist als Split-Brain bekannt: Beide Teile vergeben für sich genommen konsistente IDs, doch sobald die Partition aufgehoben ist, kollidieren ihre Datenbestände. Aus zwei in sich stimmigen Welten wird eine widersprüchliche, und die Aufräumarbeit ist im Allgemeinen nicht automatisch möglich. Genau deshalb wählen viele Systeme im Zweifel die Unverfügbarkeit. Lieber kein Schreibvorgang als ein Schreibvorgang, der später nicht mehr eindeutig zugeordnet werden kann.

Brewer selbst hat 2012 darauf hingewiesen, dass die einfache „Zwei aus drei“-Formulierung in der Praxis subtiler ist, als sie klingt. Konsistenz und Verfügbarkeit sind keine binären Eigenschaften, sondern Spektren, und reale Systeme bewegen sich auf diesen Spektren. Der Begriff der Eventual Consistency beschreibt einen weit verbreiteten Mittelweg: Das System ist verfügbar und nimmt Schreibvorgänge auch bei Partitionen an, garantiert aber nur, dass alle Knoten irgendwann denselben Zustand erreichen, sobald die Kommunikation wiederhergestellt ist. Das ist keine Konsistenz im strengen Sinne, aber für viele Anwendungsfälle eine praktikable Garantie. An der grundsätzlichen Aussage des CAP-Theorems ändern diese Differenzierungen jedoch nichts.

Wenn schon ein einziger Ausfall reicht

Bereits 1985 hatten Michael Fischer, Nancy Lynch und Michael Paterson ein noch fundamentaleres Resultat bewiesen. Ihr Aufsatz mit dem Titel Impossibility of Distributed Consensus with One Faulty Process zeigte: In einem asynchronen verteilten System, in dem auch nur ein einziger Knoten ausfallen kann, gibt es kein deterministisches Verfahren, das Konsens in endlicher Zeit garantiert. Asynchron heißt dabei, dass Nachrichten beliebig lange unterwegs sein können und Knoten beliebig langsam reagieren dürfen. Genau dieses Modell beschreibt reale Netzwerke recht gut.

Das FLP-Resultat (Fischer, Lynch, Paterson) ist schärfer als das CAP-Theorem, weil es bereits einen einzigen möglichen Ausfall ausreichen lässt, um Konsens unmöglich zu machen. Der Beweis ist technisch anspruchsvoll, die Intuition aber zugänglich: In einem asynchronen System lässt sich ein langsamer Knoten nicht von einem ausgefallenen unterscheiden. Wartet das System auf eine Antwort, könnte es ewig warten. Gibt es das Warten auf, könnte es sich gegen einen Knoten entscheiden, der gleich darauf antworten würde.

Wenn deterministischer Konsens im asynchronen Modell unmöglich ist, wieso funktionieren dann Algorithmen wie Paxos und Raft, die in der Praxis täglich Millionen Konsensentscheidungen treffen? Die Antwort liegt in den Schlupflöchern, die das FLP-Resultat offenlässt. Es spricht über deterministische Verfahren in rein asynchronen Modellen. Praktische Algorithmen umgehen diese Voraussetzungen, indem sie Timeouts einführen, Zufall hinzunehmen oder schwächere Konsensbegriffe akzeptieren. Mit Timeouts lässt sich entscheiden, einen Knoten als ausgefallen zu betrachten, wenn er innerhalb einer bestimmten Zeit nicht antwortet. Das ist eine Heuristik, kein Beweis, und kann zu Fehlentscheidungen führen, aber in der Praxis funktioniert sie meistens.

Hinzu kommt das Prinzip der Mehrheitsentscheidung. Statt zu verlangen, dass alle Knoten zustimmen, genügt eine Mehrheit, ein sogenanntes Quorum. Bei fünf Knoten reichen drei Stimmen, um eine Entscheidung verbindlich zu machen. Da bei fünf Knoten höchstens eine Mehrheit existieren kann, schließt dieses Prinzip Split-Brain-Szenarien aus: Eine Minderheit weiß, dass sie eine Minderheit ist, und enthält sich. Der Preis dafür ist Verfügbarkeit. Fällt die Mehrheit aus oder wird das System so partitioniert, dass keine Seite eine Mehrheit hat, kann nicht mehr entschieden werden. Quorum-basierte Verfahren sind also keine Lösung des grundlegenden Problems, sondern eine bewusste Entscheidung für Konsistenz auf Kosten der Verfügbarkeit, genau in dem Sinne, den das CAP-Theorem beschreibt.

Der Pakt mit den UUIDs

Was die Branche aus dieser Lage gemacht hat, ist ein bemerkenswerter Pakt. Statt sich auf einen gemeinsamen Wert zu einigen, wird die Frage abgeschafft. UUIDs, also Universally Unique Identifiers, sind die populärste Antwort. Sie haben 128 Bit, sind groß genug, dass die Wahrscheinlichkeit einer Kollision verschwindend gering ist, und können von jedem Knoten unabhängig erzeugt werden. Keine Koordination, kein Konsens, keine Wartezeiten.

Der Preis für diese Bequemlichkeit ist allerdings hoch. UUIDs in der Variante 4 bestehen aus 122 zufälligen Bits und enthalten keinerlei Information über Reihenfolge oder Zeitpunkt der Erzeugung. Wer eine Liste neuer Datensätze chronologisch sortieren will, muss eine separate Zeitspalte mitführen. UUIDs sind außerdem deutlich größer als ganzzahlige IDs, was Speicherbedarf und Index-Performance beeinträchtigt, insbesondere bei sehr großen Datenmengen. Und sie sind für Menschen praktisch nicht lesbar, was Debugging und manuelle Eingriffe erschwert.

Neuere Varianten versuchen, einige dieser Nachteile zu beheben. UUIDs in der Variante 7, im Jahr 2024 in RFC 9562 standardisiert, codieren einen Zeitstempel in den führenden Bits und sind dadurch zeitlich sortierbar. ULIDs folgen einem ähnlichen Ansatz und liefern zusätzlich eine kompaktere Darstellung als String. Twitter Snowflake, 2010 als Open Source veröffentlicht, kombiniert einen Zeitstempel mit einer Worker-ID und einem Sequenzzähler in 64 Bit, was kompakter ist als ein UUID, aber eine zentrale Vergabe der Worker-IDs voraussetzt.

Allen diesen Verfahren ist gemeinsam, dass sie das Konsensproblem nicht lösen, sondern umgehen. Sie tauschen Garantien gegen Verteilbarkeit. Wer eine garantiert lückenlose Folge braucht, etwa für Rechnungsnummern aus regulatorischen Gründen, kommt damit nicht aus. Für die meisten Anwendungsfälle aber genügen die schwächeren Garantien, und der Verzicht auf Koordination ist den Verlust wert.

Welche Kompromisse, nicht ob Kompromisse

Der Bogen vom AUTO_INCREMENT der Einzeldatenbank über das Two-Generals-Problem, das CAP-Theorem und das FLP-Resultat bis zu UUIDs zeigt ein durchgängiges Muster. Verteilter Konsens ist nicht bloß schwierig zu erreichen, sondern unter realistischen Annahmen über Netzwerke und Ausfälle nachweislich unmöglich im strengen Sinne. Jede praktische Lösung ist ein Kompromiss, der bestimmte Garantien gegen andere eintauscht. Lückenlosigkeit gegen Verfügbarkeit. Reihenfolge gegen Verteilbarkeit. Sicherheit gegen Geschwindigkeit.

Die richtige Frage in verteilten Systemen lautet daher nicht, wie sich Konsens erreichen lässt, sondern welche Garantien für den jeweiligen Anwendungsfall wirklich nötig sind und auf welche sich verzichten lässt. Diese Frage muss bewusst beantwortet werden, denn die Voreinstellungen vieler Datenbanken und Frameworks treffen die Entscheidung implizit. Wer sie nicht hinterfragt, lebt mit Kompromissen, die nicht bewusst gewählt wurden. Wer verteilte Systeme entwickelt, ohne die theoretischen Grenzen zu kennen, läuft Gefahr, gegen sie anzuprogrammieren statt mit ihnen zu arbeiten.

Ein verwandter Befund zeigt sich übrigens beim Versuch, ein anderes scheinbar einfaches Konzept messbar zu machen: die Qualität von Code. Auch hier scheitert die Suche nach der einen Zahl, mit der sich eine vielschichtige Eigenschaft erfassen ließe. Der nächste Teil dieser Serie zeigt, warum.

(mro)