Leader Election ist das Problem, in einem verteilten System genau einen Knoten als Leader, Koordinator oder Primary zu bestimmen — auch wenn Knoten ausfallen. Viele Systeme brauchen einen einzelnen Entscheider: eine Primärdatenbank, einen Partition-Leader in Kafka, den Controller im Cluster oder einen Scheduler für Aufträge. Die gewählte Instanz koordiniert die Arbeit; fällt sie aus, muss eine neue Wahl einen Nachfolger bestimmen.
Klassische Algorithmen
- Bully-Algorithmus (Hector Garcia-Molina, 1982): Der Knoten mit der höchsten ID gewinnt. Ein Knoten, der den Ausfall des Leaders bemerkt, sendet eine Election-Nachricht an alle Knoten mit höherer ID; antwortet keiner, erklärt er sich selbst zum Leader — antwortet jemand, übernimmt dieser die Wahl.
- Ring-Algorithmus: Die Knoten sind logisch im Kreis angeordnet. Eine Wahl-Nachricht wandert einmal durch den Ring und sammelt die höchste gesehene ID; der Knoten mit dieser ID wird Leader und teilt das Ergebnis mit.
- Raft-Election: Der Kandidat erhöht den aktuellen Raft-Term und fordert Stimmen an; gewählt ist, wer die Mehrheit erhält. Zufällig gestreute Timeouts verhindern, dass sich mehrere Kandidaten dauerhaft gegenseitig blockieren (Split Vote).
- ZooKeeper / etcd: Knoten erstellen sequenzielle, flüchtige ZNodes; der kleinste Sequenz-Index ist der Leader. Fällt er aus, übernimmt automatisch der nächste. Auf diesem Muster basiert auch die Leader-Election von Kubernetes (Leases).
Leases, Heartbeats und Split-Brain
Ein Leader bekommt seine Position üblicherweise für eine begrenzte Zeit (Lease) und verlängert sie durch regelmäßige Heartbeats. Läuft die Lease ab, weil der Leader nicht mehr antwortet, startet eine neue Wahl. Die gefährlichste Fehlerlage ist der Split-Brain: Zwei Netzpartitionen wählen gleichzeitig je einen Leader und nehmen beide Schreiboperationen vor. Dagegen helfen Quoren (nur die Partition mit Mehrheit darf entscheiden) und Fencing Tokens: monoton steigende Nummern, mit denen alte Leaders abgewiesen werden, sobald ein neuer gewählt ist.
Bezug zu Konsens und Transaktionen
Die Leader-Wahl ist eng mit dem Konsens-Problem verwandt: Paxos und Raft kombinieren die Wahl eines Leaders mit der Replikation eines Logs. Auch das Two-Phase-Commit-Protokoll braucht eine zentrale Instanz — dort spricht man traditionell vom Koordinator; die Frage, wie dieser einzelne Knoten bestimmt und abgelöst wird, beantwortet die Leader Election.
Verwandte Grundlagen: Raft, Paxos, Quorum, Hochverfügbarkeit, Datenbank-Cluster.