Распределённые системы
Выбор лидера (Leader Election)
Цели урока
- Понимать зачем кластеру нужен единственный лидер и какие проблемы он решает
- Знать механику Bully Algorithm и его ограничения
- Объяснять lease-based election и роль Fencing Token
- Понимать что такое split-brain и как Quorum + Fencing Token его предотвращают
Предварительные знания
- Концепции распределённых систем: узлы, сбои, partition
- Базовое понимание консенсуса и репликации
- CAP-теорема и CP vs AP trade-off
Kubernetes управляет миллионами контейнеров - и пережить смерть мастер-узла за 30 секунд позволяет именно leader election в etcd. Без этого алгоритма failover занимал бы часы ручной работы.
- **etcd (Kubernetes)** - Raft leader election: мастер etcd умер, новый выбран за 150-300мс, кластер продолжает работу
- **Kafka KRaft (2022)** - убрали ZooKeeper, перешли на встроенный Raft для выборов partition leader
- **Patroni (PostgreSQL HA)** - lease в etcd/Consul: автоматический failover PostgreSQL primary за 10-30 секунд
- **MongoDB replica set** - elections при падении primary: driver автоматически переключается на нового primary
- **GitHub 2013** - split-brain в PostgreSQL кластере: 6 часов потери данных из-за некорректного Pacemaker config
Garcia-Molina и Bully Algorithm (1982)
Hector Garcia-Molina (Стэнфорд) опубликовал Bully Algorithm в 1982 году в статье 'Elections in a Distributed Computing System'. Идея проста до элегантности: наибольший ID всегда побеждает, поэтому не нужно голосование - только объявление. Алгоритм сохраняет образовательную ценность по сей день, хотя production-системы давно перешли на Raft и lease-based. Garcia-Molina известен также созданием WebBase - первого крупного web crawler, предшественника Google.
Зачем кластеру один лидер
**2020 год. Kubernetes-кластер в Netflix обрабатывает 200 000 подов. etcd-мастер падает. Через 30 секунд новый мастер уже координирует кластер - без единого ручного вмешательства.** Это не магия - это Raft leader election, встроенный в etcd. Без алгоритма выбора лидера кластер при сбое превращается в анархию: каждый узел принимает противоречивые решения.
В распределённой системе без лидера при конкурентных записях два узла могут одновременно обновить одну запись до разных значений. Кто прав? Без координирующего узла - никто не знает. Лидер решает это: все записи идут через него, он определяет порядок.
- **Консенсус без лидера** - O(n^2) сообщений на каждое решение. С лидером - O(n).
- **Конкурентные операции** - лидер сериализует их в единый linearizable порядок.
- **Метаданные кластера** - кто жив, кто упал, как перераспределить данные - всё через лидера.
| Система | Что делает лидер | Алгоритм выбора |
|---|---|---|
| etcd | Принимает все записи, реплицирует на followers | Raft |
| Kafka | Partition leader принимает producer-записи | ZooKeeper / KRaft |
| PostgreSQL (Patroni) | Primary принимает write-запросы | etcd/Consul lease |
| Redis Sentinel | Master принимает write, sentinel голосует за failover | Quorum vote |
| Elasticsearch | Master-eligible node управляет shards и mappings | Zen discovery / Raft |
**Формальные требования к алгоритму:** Safety - одновременно не более одного лидера (иначе split-brain). Liveness - система в конечном итоге выберет лидера (иначе кластер завис). Fairness (опционально) - любой узел может победить, не только фаворит.
Лидер нужен только для производительности - чтобы не было bottleneck на запись
Лидер нужен прежде всего для корректности - сериализации конкурентных операций и консистентного состояния кластера
Без лидера два узла могут одновременно решить переназначить один и тот же shard разным серверам. Результат - потеря данных. Производительность вторична, корректность первична.
Почему при leader election критична гарантия Safety (не более одного лидера)?
Bully Algorithm: простейший выбор
Bully Algorithm - алгоритм 1982 года (Garcia-Molina, Гарвард): побеждает узел с наибольшим ID. Название отражает механику - старший по рангу 'задавливает' (bullies) остальных. Используется в MongoDB replica set elections как один из факторов, в ранних версиях Hadoop YARN.
Протокол выбора
| Сообщение | От кого | Смысл |
|---|---|---|
| ELECTION | Узел с меньшим ID | Начинаю выборы, есть ли кто старше? |
| OK | Узел с большим ID | Жив, участвую в выборах - меньший ID отстраняется |
| COORDINATOR | Победитель | Я новый лидер, запишите |
**Сложность Bully:** O(n^2) сообщений в худшем случае - каждый узел шлёт ELECTION всем старшим. При 1000 узлах - миллион сообщений. Поэтому в production используют Raft или lease-based, а не Bully.
В кластере 5 узлов с ID 1-5. Лидер (ID=5) упал. Node 2 обнаружила это первой. Кто станет лидером по Bully Algorithm?
Lease-based Election: production-подход
**etcd (Kubernetes), Consul (HashiCorp), ZooKeeper (Kafka, HBase)** - все используют lease-based election. Идея: лидерство - это распределённая блокировка с TTL. Кто первым захватил блокировку - лидер. Если TTL истёк и не обновлён - лидерство освобождается автоматически. Kubernetes с 2016 года полностью на этом механизме.
**Fencing Token** - монотонно возрастающий номер в lease. Хранилище отвергает записи с token меньше последнего виденного. Защита от zombie-лидера: упавший лидер восстановился, думает что ещё лидер - его записи отклоняются, потому что новый лидер уже выдал больший token.
Если лидер завис на 5 секунд, система без лидера на эти 5 секунд
При корректно настроенном TTL и продлении новый лидер выбирается до истечения TTL старого
Типичная настройка: TTL=10s, renewal каждые 3.3s. Лидер пропустил 3 renewal (10s) - lease истёк. Новый кандидат захватывает lease за ~100ms. Итого downtime ~10 секунд, не 5 минут ручного вмешательства.
Зачем lease-based election использует Fencing Token при записи?
Split-Brain: когда возникают два лидера
**2013, GitHub. PostgreSQL-кластер с Pacemaker. Сеть разделилась на два сегмента. Pacemaker в каждом сегменте решил что другой primary умер - и промоутировал собственного. Два primary начали принимать записи. 6 часов потери данных до обнаружения.** Это split-brain - ситуация когда два узла одновременно считают себя лидерами.
| Причина split-brain | Сценарий | Последствие |
|---|---|---|
| Network partition | Datacenter A и B потеряли связь | Каждый DC выбирает своего лидера |
| GC pause | Лидер завис на 15s (GC stop-the-world) | Новый лидер выбран, старый ожил - два лидера |
| Clock skew | NTP рассинхронизировал часы кластера | Lease-timeout срабатывает некорректно |
| Неверный TTL | TTL слишком короткий для нагруженного узла | Ложные failover при нормальном лидере |
Защита 1: Quorum
Лидер может писать только если получил подтверждение от кворума (majority) узлов. При network partition меньший сегмент не имеет кворума - не может стать лидером. Raft и Paxos строятся на этом принципе: из 5 узлов нужно 3 подтверждения. При разбиении 2+3 лидером становится только сторона с 3.
Защита 2: Fencing Token в хранилище
Кворум защищает от split-brain в момент выборов. Fencing Token защищает от zombie-лидера который уже не лидер, но ещё пытается писать. Вместе они дают надёжную защиту: даже если алгоритм выборов ошибся - хранилище отклонит устаревшую запись.
Split-brain можно предотвратить просто быстрым обнаружением отказа лидера
Split-brain - следствие network partition, а не медленного обнаружения. Quorum - единственная надёжная защита
Быстрое обнаружение ускоряет выборы нового лидера, но не решает проблему двух сегментов сети. Если оба сегмента быстро обнаружат проблему - они оба быстро выберут своих лидеров. Только кворум гарантирует что только большинство может избрать лидера.
Кластер из 5 узлов потерял сетевую связность и разбился на группы 2 и 3 узла. Как quorum защищает от split-brain?
Вопросы для размышления
- Выбор TTL для lease - нетривиальная задача. Слишком маленький TTL даёт частые ложные failover (лидер жив, но не успел обновить lease). Слишком большой TTL даёт долгий downtime при реальном сбое. Как бы определить оптимальный TTL для конкретного кластера?
Связанные уроки
- ds-03-consensus — Выбор лидера - частный случай консенсуса
- ds-02-cap-theorem — Ограничения CAP применимы к протоколам выборов
- dist-08-paxos — Paxos использует выбор лидера как под-протокол
- dist-09-raft — Raft объединяет выбор лидера с репликацией журнала
- dist-10-byzantine — Византийский выбор лидера должен учитывать узлы, которые лгут
- alg-12-bfs