Leader Election
Einen Knoten für exklusive Aufgaben wählen
Die Idee und ihr Nutzen
Der Rechnungsdienst einer Versicherung erstellt die Beitragsrechnungen. Er läuft als drei Exemplare desselben Programms auf verschiedenen Servern, damit der Ausfall eines Servers den Rechnungsdienst nicht stoppt. Die Exemplare heißen Kopie 1, Kopie 2 und Kopie 3, und weil alle drei dasselbe Programm sind, könnte jedes den Rechnungslauf ausführen. Den nächtlichen Rechnungslauf darf aber nur ein Exemplar starten, sonst erhalten Kunden doppelte Rechnungen. Die drei Exemplare wählen deshalb untereinander ein Exemplar zum Leader, auf Deutsch Anführer. Nur der Leader startet den Rechnungslauf. Fällt der Leader aus, wählen die übrigen Exemplare einen neuen. Jede Wahl erhält eine fortlaufende Nummer, die der Leader jedem Rechnungsauftrag mitgibt. Das Zielsystem, etwa eine Datenbank für die Rechnungen, führt die Rechnungsaufträge aus. Kommt nach Aufträgen mit der Nummer 18 noch ein verspäteter Auftrag eines abgelösten Leaders mit der Nummer 17, erkennt das Zielsystem den Auftrag an der kleineren Nummer und lehnt ihn ab. Dieses Verfahren heißt Leader Election, auf Deutsch Wahl eines Anführers.
Wie funktioniert es?
Zuerst startet Kopie 1 eine Wahl. Die fortlaufende Nummer der Wahl heißt Leitungsnummer und ist höher als alle bisherigen; diese Wahl hat die Leitungsnummer 17. Kopie 1 bittet die beiden anderen Exemplare um ihre Stimme. Kopie 2 und Kopie 3 stimmen für Kopie 1, und mit dieser Mehrheit ist Kopie 1 Leader. Als Leader schickt Kopie 1 in kurzen Abständen Lebenszeichen an die anderen Exemplare. Um 1 Uhr schickt nur Kopie 1 die Rechnungsaufträge an das Zielsystem, und jeder Auftrag trägt die Nummer 17. Das Zielsystem kann eine Datenbank oder ein anderer Dienst sein. Am nächsten Abend fällt der Server von Kopie 1 aus. Die Lebenszeichen von Kopie 1 bleiben aus, und nach einer festgelegten Wartezeit gilt Kopie 1 als ausgefallen. Kopie 2 bewirbt sich mit der Leitungsnummer 18. Kopie 3 stimmt zu, und mit zwei von drei Stimmen ist Kopie 2 neuer Leader. Um 1 Uhr startet Kopie 2 den Rechnungslauf mit Nummer 18, und das Zielsystem merkt sich 18 als höchste Nummer. Um 1:10 Uhr kommt Kopie 1 wieder hoch und schickt einen vorbereiteten Auftrag mit Nummer 17. Weil 17 kleiner als 18 ist, weist das Zielsystem den Auftrag ab. Kopie 2 teilt Kopie 1 mit, dass Kopie 2 mit Nummer 18 Leader ist, und Kopie 1 stellt ihre Arbeit ein.
Leader ist nur, wer die Stimmen einer Mehrheit der Exemplare erhält. Bei drei Exemplaren sind das zwei Stimmen, die eigene eingeschlossen. Drei Exemplare sind deshalb die kleinste sinnvolle Zahl: Fällt eines aus, bilden die beiden übrigen noch eine Mehrheit. Eine Mehrheit ist nötig, weil jedes Exemplar in einer Wahl nur einmal abstimmen darf. Bewerben sich zum Beispiel Kopie 1 und Kopie 2 gleichzeitig mit der Leitungsnummer 18, stimmt jede für sich selbst, und Kopie 3 kann nur einer der beiden ihre Stimme geben. So können nie zwei Leader mit derselben Leitungsnummer gewählt sein.
Die Prüfung im Zielsystem ist nötig, weil der Rechnungsdienst ein verteiltes System ist: Die drei Exemplare laufen auf verschiedenen Servern und tauschen nur über das Netz Nachrichten aus. Jedes Exemplar kann ausfallen, und das Netz kann einzelne Exemplare zeitweise voneinander trennen. Kein Exemplar kann sicher unterscheiden, ob ein anderes ausgefallen oder nur gerade nicht erreichbar ist. Ein abgelöster Leader weiß deshalb unter Umständen nicht, dass er abgelöst wurde. Hat er während einer Netzstörung nichts von der neuen Wahl mitbekommen, arbeitet er weiter und schickt Aufträge. Darum merkt sich das Zielsystem die höchste bisher gesehene Leitungsnummer und weist Aufträge mit einer kleineren Nummer ab.
Statt einer Wahl unter den Exemplaren kann auch ein eigener Koordinationsdienst die Rolle des Leaders für begrenzte Zeit vergeben. Ein Koordinationsdienst ist ein Programm, das selbst auf mehreren Servern läuft, damit es nicht mit einem Server ausfällt, und gemeinsame Einträge für alle Exemplare verwaltet. Die Exemplare bewerben sich dann bei diesem Koordinationsdienst um einen Eintrag mit Ablaufzeit. Das Exemplar, das den Eintrag erhält, ist Leader, solange der Eintrag gilt. Auch in diesem Fall muss das Zielsystem veraltete Aufträge erkennen. Leader Election garantiert außerdem nicht, dass ein einzelner Auftrag genau einmal ausgeführt wird. Bricht der Rechnungslauf des alten Leaders mittendrin ab, muss eigens geregelt sein, wie der neue Leader den Lauf fortsetzt. Der neue Leader kann dafür zum Beispiel einen gespeicherten Fortschritt lesen.
Leader Election: nur der gewählte Leader startet den Rechnungslauf
Wann ist es sinnvoll und wann nicht?
Leader Election lohnt sich
- Von mehreren Exemplaren eines Dienstes darf nur eines den nächtlichen Rechnungslauf starten. Legt das Team, das den Rechnungsdienst betreibt, fest, dass immer Kopie 1 den Lauf startet, bleibt der Lauf liegen, sobald Kopie 1 ausfällt, obwohl zwei weitere Exemplare bereitstehen. Mit der Wahl übernimmt Kopie 2 den Rechnungslauf ohne Eingreifen des Teams.
- Ohne Absprache würde jedes Exemplar selbst entscheiden, dass es zuständig ist. Dann laufen drei Rechnungsläufe gleichzeitig, und jeder Kunde erhält drei Rechnungen. Mit der Wahl startet nur der Leader den Lauf.
- Eine Warteschlange muss in fester Reihenfolge abgearbeitet werden. Auch das darf nur ein einziges Exemplar tun. Ohne Wahl nehmen mehrere Exemplare gleichzeitig Einträge aus der Warteschlange, und die Einträge werden in falscher Reihenfolge verarbeitet.
- Nur ein Exemplar darf in eine bestimmte Datei schreiben. Schreiben zwei Exemplare gleichzeitig in die Datei, überschreiben sie gegenseitig ihre Einträge.
- Ein Exemplar soll Arbeit auf die anderen Exemplare verteilen. Der Leader teilt dann zum Beispiel jedem Exemplar die Verträge zu, die das Exemplar abrechnet. Ohne Leader muss das Team die Aufteilung fest vorgeben und nach dem Ausfall eines Exemplars von Hand ändern.
Leader Election ist nicht das Richtige
- Es genügt, dass nie zwei Exemplare denselben Auftrag gleichzeitig bearbeiten. Mit Leader Election würde nur der Leader Aufträge bearbeiten, und die beiden anderen Exemplare würden warten. Stattdessen erwirbt das Exemplar, das einen Auftrag bearbeiten will, vorher einen Distributed Lock, also eine Sperre über mehrere Rechner, für genau diesen Auftrag und für begrenzte Zeit. Die Exemplare müssen keinen Leader wählen. Fällt ein Exemplar aus, bearbeiten die übrigen Exemplare die nächsten Aufträge weiter, ohne auf eine Neuwahl zu warten.
- Die Arbeit lässt sich auf alle Exemplare verteilen. Mit Leader Election würde nur der Leader rechnen, während die beiden anderen Exemplare warten. Stattdessen teilt das Team die Verträge fest auf die drei Exemplare auf, zum Beispiel nach Vertragsnummer, und jedes Exemplar rechnet nur seinen Teil ab. Alle drei Exemplare rechnen gleichzeitig, und die Wahl entfällt. Fällt Kopie 3 aus, bleibt ihr Teil allerdings liegen, bis das Team die Verträge von Kopie 3 auf Kopie 1 und Kopie 2 verteilt.
- Das Zielsystem kann keine Leitungsnummer prüfen, und es gibt auch keine eindeutigen Auftragskennungen. Dann schützt die Wahl allein nicht vor doppelten Rechnungen durch einen abgelösten Leader. Das Team lässt den Rechnungslauf stattdessen immer von Kopie 1 ausführen. Nach einem Ausfall prüft das Team, welche Rechnungen schon verschickt sind, und startet den Rest von Hand. Das braucht Handarbeit, aber es entstehen keine doppelten Rechnungen.
Nachteile und typische Fehler
Zwischen dem Ausfall des Leaders und der Neuwahl vergeht Zeit, in der niemand den Rechnungslauf erledigt. Eine kürzere Wartezeit verkürzt diese Lücke. Eine Wahl braucht außerdem eine erreichbare Mehrheit der Exemplare. Das Zielsystem muss die Leitungsnummer kennen und prüfen und hängt damit vom Wahlverfahren ab. Wer ein Wahlverfahren selbst programmiert, übersieht leicht Fälle wie eine Netzstörung mitten in einer Wahl. Deshalb nutzen Teams meist einen fertigen Koordinationsdienst, der dann zusätzlich betrieben werden muss.
Typische Fehler und woran man sie erkennt:
- Abgelöster Leader arbeitet weiter: Eine Netzstörung trennt Kopie 1 von Kopie 2 und Kopie 3. Kopie 2 und Kopie 3 wählen Kopie 2 mit Nummer 18 zum Leader. Kopie 1 erfährt davon nichts und schickt weiter Rechnungsaufträge mit Nummer 17 an das Zielsystem. Prüft das Zielsystem die Leitungsnummer nicht, führt es die Aufträge beider Exemplare aus, und Kunden erhalten doppelte Rechnungen. Erkennbar ist das an Aufträgen mit zwei verschiedenen Leitungsnummern im selben Zeitraum.
- Keine Mehrheit erreichbar: Eine Netzstörung trennt alle drei Exemplare voneinander. Jedes Exemplar bewirbt sich, erhält aber nur die eigene Stimme, also eine von drei. Kein Exemplar wird Leader, und der Rechnungslauf bleibt liegen. Erkennbar ist das an wiederholt gestarteten Wahlen ohne Ergebnis.
- Halb erledigter Lauf: Kopie 1 hat als Leader schon die Hälfte der Rechnungsaufträge an das Zielsystem geschickt. Dann fällt der Server von Kopie 1 aus. Kopie 2 wird Leader und beginnt den Rechnungslauf von vorn, weil kein gespeicherter Fortschritt zeigt, welche Rechnungen schon verschickt sind. Das Zielsystem nimmt die Aufträge mit Nummer 18 an, und die Kunden der ersten Hälfte erhalten zwei Rechnungen. Erkennbar ist das an doppelten Rechnungen nach einem Wechsel des Leaders.
- Zu kurze Wartezeit: Die Wartezeit ist kürzer als die Verspätung, die Lebenszeichen bei hoher Last haben. Kommt ein Lebenszeichen von Kopie 1 zu spät, gilt Kopie 1 als ausgefallen, obwohl Kopie 1 arbeitet. Kopie 2 bewirbt sich und wird Leader, und bei der nächsten Lastspitze wiederholt sich das mit dem neuen Leader. Erkennbar ist das an rasch steigenden Leitungsnummern, ohne dass ein Server ausgefallen ist.
- Zu wenige Exemplare: Läuft der Dienst nur in zwei Exemplaren, ist keine Mehrheit mehr möglich, sobald eines der beiden Exemplare ausfällt. Erkennbar ist das daran, dass schon der Ausfall eines Exemplars die Wahl blockiert.
Weiterführend
Verwandte Ansätze
- Consensus: Verfahren, mit dem sich mehrere Rechner verlässlich auf einen Wert einigen. Sichere Wahlen beruhen darauf.
- Master Worker: Aufbau mit einem verteilenden Hauptprogramm und vielen Arbeitsprogrammen. Fällt das Hauptprogramm aus, kann eine Wahl einen Ersatz bestimmen.
- Redundancy and Failover: beschreibt mehrfach vorhandene Systemteile und die Übernahme bei einem Ausfall.
Werkzeuge und Umsetzungen
- Kubernetes Leases: Einträge mit Ablaufzeit in Kubernetes, einer verbreiteten Plattform zum Betrieb von Anwendungen auf vielen Servern. Auf diesen Einträgen bauen Wahlen eines Leaders auf.
- etcd: Koordinationsdienst mit einer fertigen Funktion für Wahlen.
- Apache Curator: Java-Bibliothek mit fertigen Bausteinen für Wahlen auf Grundlage des Koordinationsdienstes Apache ZooKeeper.
- Spring Integration: bietet Java-Anwendungen die Wahl eines Leaders über verschiedene gemeinsame Koordinationsdienste.
Quellen
- Microsoft: Leader Election Pattern: beschreibt die Wahl unter gleichrangigen Exemplaren, das Erkennen eines ausgefallenen Leaders, Wahl über eine gemeinsame Sperre mit Ablaufzeit und einfachere Alternativen.
- Unmesh Joshi: Generation Clock: erklärt die fortlaufende Nummer je Wahl, mit der ein abgelöster Leader erkannt und seine Anfragen abgewiesen werden.
- Diego Ongaro, John Ousterhout: Raft Consensus Algorithm: Projektseite zu einem verbreiteten Einigungsverfahren, das weiterarbeitet, solange eine Mehrheit der Server erreichbar ist, mit Verweis auf den Originalaufsatz.