// HEISE ONLINE — MOBILE & WEB
Won’t fix! – Teil 3: Warum verteilter Konsens schwer bis unmöglich ist
In verteilten Systemen ist Einigkeit nicht bloß schwierig, sondern unter bestimmten Bedingungen mathematisch beweisbar unmöglich.
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.
Golo Roden ist Gründer und CTO von the native web GmbH. Er beschäftigt sich mit der Konzeption und Entwicklung von Web- und Cloud-Anwendungen sowie -APIs, mit einem Schwerpunkt auf Event-getriebenen und Service-basierten verteilten Architekturen. Sein Leitsatz lautet, dass Softwareentwicklung kein Selbstzweck ist, sondern immer einer zugrundeliegenden Fachlichkeit folgen muss.
Die Serie "Wont' fix" behandelt Probleme in der Softwareentwicklung, die sich nicht wegoptimieren lassen, mit denen man aber lernen kann umzugehen:
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.
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 we