Leader Election

Multi-node системе часто нужен один координатор: для writes (primary), для job scheduling (cron leader), для config (controller). Leader election это процесс выбора этого узла + детекции его падения + переизбрания нового без split-brain.

Зачем

Распределённые системы любят симметрию: N одинаковых нод, любая может обработать запрос. Но многие операции не коммутативны и требуют единого координатора:

• Single-writer storage — Postgres primary, MongoDB primary, Kafka partition leader. Только один узел принимает writes, остальные реплицируют. Иначе конфликты, lost updates, data divergence.
• Cron / scheduled jobs — если задачу запустят 3 ноды одновременно (нагнали инвойсы, разослали емейлы), будет 3x duplicate side effects. Нужен один leader, который решает «я запускаю».
• Controller / orchestrator — Kubernetes controller-manager, Kafka Controller, Spark master. Один узел смотрит cluster state и принимает решения о placement/rebalance, иначе два контроллера будут гонять одни и те же поды туда-сюда.
• Distributed locks / coordination — назначение shard owner, allocation роутинга.

Leader election это всегда trade-off между двумя плохими исходами: no leader (система зависла, writes отвергаются) и two leaders (split-brain, writes расходятся). Хороший алгоритм минимизирует window без leader и математически исключает двух leader-ов одновременно.

Mental model

Представь команду из 5 человек, и им нужно выбрать капитана. Все равны, голосования нет. Правила:

1. Каждый имеет приоритет (ID, или вес).
2. Кто-то один считается капитаном. Он регулярно «отмечается» («я ещё жив»).
3. Если капитан перестал отмечаться N секунд — любой может объявить выборы.
4. Выборы должны быть детерминированы (одни и те же входные данные дают одного победителя) и безопасны (двух капитанов одновременно не бывает).

Безопасность достигается одним из трёх способов:

• Quorum — победитель тот, за кого проголосовало большинство (N/2+1). При split в 5 узлов на 2+3, сторона из 2 узлов просто не может набрать quorum, и leader там не выбирается.
• Lease — внешний consensus service (etcd, ZooKeeper, Consul) хранит запись «X = leader до момента T». Только один узел может удерживать lease атомарно. Если lease истёк — другой узел делает CompareAndSwap.
• Fencing token — каждое лидерство сопровождается монотонно растущим номером. Storage отвергает writes с устаревшим token-ом, даже если старый leader «воскрес» и думает что всё ещё главный.

Главная ловушка: сеть ненадёжна, и узел A не может отличить «B упал» от «B жив, но я его не вижу». Поэтому любой алгоритм, который полагается только на heartbeats и не использует quorum/lease, рано или поздно даст split-brain.

Что показывает диаграмма

Кластер из 5 узлов (node-1..node-5) и внешний coordination store (etcd / Consul). Между узлами — election edges (для классических алгоритмов), от каждого узла — edge к store (для lease-based). Это сознательно избыточная топология: разные сценарии используют разные подмножества рёбер.

• Mesh election edges между узлами — используется в Bully (узел шлёт ELECTION всем с higher priority).
• Edges к coordinator-store — используется в lease-based, fencing token и Patroni-сценариях.
• Цвет/состояние узлов меняется по ходу анимации: state: 'running' по умолчанию, flashError помечает падение, showError помечает невалидные сценарии (split-brain).

ADR на node-1 ([ADR-001] Leader election: один координатор без split-brain) суммирует выбор подхода и почему quorum + fencing token это must-have.

Сценарии

Пять сценариев, расположены от классического к production-grade:

1. Bully algorithm (legacy) — node-1 обнаруживает отсутствие leader-а, шлёт ELECTION всем с higher ID. node-4 отвечает, перехватывает выборы, шлёт ELECTION выше, не получает ответа от node-5 (down), объявляет себя COORDINATOR. Показывает: алгоритм работает, но генерирует O(N²) сообщений в худшем случае. На 100 узлах это неприемлемо.
2. Lease-based (etcd) — node-1 делает CompareAndSwap в etcd с TTL 30s, становится leader-ом, каждые 10s продлевает heartbeat. При падении lease истекает за 30s, node-2 делает CAS, становится новым leader-ом. Это паттерн Kubernetes, Patroni, ClickHouse Keeper.
3. Split-brain без quorum — network partition делит кластер на {1,2} и {3,4,5}. Обе стороны независимо избирают leader-а, обе принимают writes, данные расходятся. showError подсвечивает: «BOTH WRITE» — это корректное поведение алгоритма без quorum, и именно поэтому Bully/Ring без дополнительной защиты не подходят для production.
4. Fencing token защищает — node-1 лидерствует с token=42, теряет сеть, переизбирается node-3 с token=43. Когда node-1 «воскресает» и пытается записать с token=42, storage возвращает 409 STALE TOKEN. Это спасает от Old GC pause / process freeze, когда старый leader не знает, что его уже сместили (классический пример Kleppmann).
5. Real-world Patroni — продакшен пример: каждая Postgres-нода имеет Patroni-агента, лидерство хранится как key /service/cluster/leader в etcd с TTL. При падении primary PG-1 lease истекает, PG-2 делает CAS, выполняет pg_promote(), становится writable. Прокси (HAProxy / PgBouncer / pgcat) переключает клиентский трафик на новый primary.

Каждый сценарий запускается отдельно через scenario pills в плеере. Прогресс по концепту не трекается — это free wikipedia-style чтиво.

Trade-offs (ADR-001)

Context: нужен один координатор в кластере N узлов, при падении быстрый failover, без split-brain, без потерянных writes.

Decision matrix:

Decision: lease-based с fencing token. Аргументы:

• Quorum + lease даёт математическую гарантию одного leader-а: storage делает CAS, два узла физически не могут одновременно держать одну и ту же запись.
• Fencing token (monotonic counter) защищает от GC-пауз и network partitions, которые длятся дольше TTL — старый leader не сможет записать.
• Внешний consensus store (etcd/ZK) уже решён и оттестирован: не надо писать свой Raft.

Consequences:

• Цена: failover bounded by TTL (15-30s обычно), уменьшение TTL даёт быстрее failover, но больше ложных переизбраний при сетевых glitches.
• Зависимость от availability etcd/ZK: если consensus store упал, никто не лидер, writes отвергаются. Это лучше split-brain, но требует HA для самого store (3 или 5 узлов etcd).
• Heartbeat traffic: каждый кандидат пингует store раз в N секунд. На больших кластерах нужен sharding по leadership keys.

Реальные системы

Паттерн: на верхнем уровне почти все production системы либо используют внешний lease store (Patroni, K8s, Spark), либо встраивают Raft (etcd, CockroachDB, ClickHouse Keeper, modern Kafka). Bully/Ring остались в учебниках и legacy distributed Erlang.

Anti-patterns

• Bully algorithm в large cluster — O(N²) election traffic на каждую смену leader. На 100 узлах при flapping сети сеть зальёт election-сообщениями и сделает только хуже.
• Lease без fencing token — классическая дыра. Сценарий: leader попал в long GC pause (15s), lease истёк, переизбрался новый leader с tokenом N+1, начал писать. Старый leader проснулся, думает что он ещё leader, пишет с tokenом N — без fencing storage примет обе записи. Решение: storage обязан проверять token и отвергать stale.
• Quorum на чётном числе узлов — 4 узла, кворум 3, при split 2/2 ни одна сторона не имеет кворума, кластер встал. Если 6 узлов и split 3/3 — то же самое. Поэтому везде советуют нечётное число (3, 5, 7).
• Слишком короткий election timeout — 1s timeout на heartbeat звучит как «быстрый failover», но на любом 99-й перцентиль GC pause или network jitter будут ложные переизбрания. Каждое переизбрание = окно недоступности writes. Production: 10-30s timeout с jitter.
• Application-level leader election в БД-таблице без UPDATE..WHERE token= — банальный UPDATE leader SET node='me' WHERE TRUE без условия на текущего владельца это race condition. Должно быть UPDATE leader SET node='me', token=token+1 WHERE token=$current_token.
• Heartbeat без timeout backoff — нода считает себя leader-ом и продолжает heartbeat-ить, не проверяя, что store ещё подтверждает её lease. Если ответ от store потерялся в сети, нода думает «я ещё leader» и пишет, а на деле lease истёк и есть новый leader → split-brain.
• Gossip-based в strong-consistency сценарии — gossip даёт eventual consistency лидерства. Между gossip-раундами возможны transient два leader-а. Это ок для service discovery (Cassandra), катастрофа для primary database.

Когда НЕ использовать

Не каждая система нуждается в leader-е. Альтернативы:

• Stateless replicas + LB — если operation коммутативна (read-only, idempotent), просто пускай трафик на любую реплику. Никаких выборов, никакого split-brain.
• CRDT / multi-master — Cassandra, Riak, Dynamo: writes идут в любую ноду, конфликты резолвятся CRDT-логикой (LWW, vector clocks, OR-set). Это AP-выбор по CAP, отсутствие leader-а здесь это фича.
• Sharded leadership — вместо «один leader на кластер» сделай «один leader на shard». Kafka partition leader, MongoDB shard primary. Каждый shard переизбирается независимо, отказ одной ноды не блокирует весь кластер.
• Optimistic concurrency — версионирование документов + retry. Если конфликты редки, дешевле детектить их по version=N и ретраить, чем держать постоянный координатор.
• Atomic primitive в БД — для совсем простых задач (один cron на кластер) хватит SELECT ... FOR UPDATE SKIP LOCKED в Postgres. Leader election на уровне приложения — это overkill.

Если задача укладывается в любой из этих паттернов — leader election это лишняя сложность и лишний failure mode.

Дальше читать

• Concept: ::concept{slug="consensus-overview"} — почему leader election сводится к consensus problem.
• Concept: ::concept{slug="raft"} — Raft protocol (term, log replication, leader election as part of consensus).
• Concept: ::concept{slug="paxos"} — классический Paxos.
• Case: ::case{slug="kafka-broker-internals"} — controller election в Kafka (KRaft Raft).
• Case: ::case{slug="postgres-patroni-ha"} — Postgres HA через Patroni + etcd lease.
• Case: ::case{slug="kubernetes-cluster"} — leader election в K8s controller-manager через Lease object.
• DDIA Chapter 9 — Consistency and Consensus (Kleppmann): подробно про fencing token, FLP impossibility, Byzantine vs crash-stop failures.
• Martin Kleppmann — How to do distributed locking. Канонический разбор почему lease без fencing ломается на GC pause.
• System Design Space — Leader election patterns.
• Raft paper — In Search of an Understandable Consensus Algorithm (Ongaro, Ousterhout 2014).