Выбор лидера в распределённых системах: bully, термы, lease, ZooKeeper и etcd
Как узлы кластера выбирают лидера: алгоритм задиры (bully), кворум и термы, аренда (lease) и часы, fencing tokens, рецепты на ZooKeeper, etcd и Kubernetes Lease. Модели на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Зачем нужен лидер | Одна точка принятия решений: порядок записей, раздача задач, планировщик, cron без дублей |
| Главная опасность | Два лидера одновременно (split brain): медленный узел неотличим от упавшего |
| Классические алгоритмы | Bully и кольцо: просты, но не переживают разделение сети |
| Что используют на практике | Кворум с номером поколения (терм, эпоха) или аренду в ZooKeeper, etcd, Kubernetes Lease |
| Что обязательно добавить | Fencing token: ресурс сам отклоняет запросы от «бывшего» лидера |
- Выбрать лидера легко, когда сеть надёжна. Вся сложность — в том, что узел, не ответивший за секунду, может быть жив и уверен, что лидер он.
- Безопасность (не больше одного лидера) обеспечивает кворум: два большинства всегда пересекаются. Liveness (лидер когда-нибудь появится) — таймауты и рандомизация.
- Аренда (lease) сама по себе безопасность не гарантирует: GC-пауза длиннее TTL — и у вас два лидера. Защищает только проверка номера поколения на стороне ресурса.
- Писать свой алгоритм выборов в проде почти никогда не нужно. Нужно знать, какие гарантии даёт готовый, и где они заканчиваются.
Зачем вообще нужен лидер
Многие задачи проще решаются, если решение принимает кто-то один:
- Репликация с одним мастером. Лидер упорядочивает записи, реплики применяют их в том же порядке. Так работают Postgres с потоковой репликацией, MongoDB replica set, Kafka (лидер у каждой партиции).
- Координация. Kafka-контроллер распределяет партиции по брокерам, kube-scheduler назначает поды на узлы, мастер в HDFS хранит метаданные.
- Задачи «ровно в одном экземпляре». Ежечасная выгрузка, отправка рассылки, очистка старых данных. Если сервис запущен в пяти репликах, cron в каждой выполнит работу пять раз.
Альтернатива лидеру — договариваться всем со всеми по каждому решению. Это дороже, поэтому выбор лидера — один из самых частых строительных блоков распределённых систем.
Чего мы хотим от выборов
Два свойства, которые стоит назвать на собеседовании:
- Safety (безопасность): в любой момент не больше одного узла считает себя лидером. Или в более слабой и реалистичной форме: не больше одного лидера в каждом поколении, а действия старых поколений отвергаются.
- Liveness (живучесть): если лидер упал, новый рано или поздно будет выбран, и все узлы о нём узнают.
Почему это трудно? В асинхронной сети нельзя отличить упавший узел от медленного. Лидер мог зависнуть в GC-паузе на 20 секунд, а потом проснуться и продолжить писать как ни в чём не бывало. Или сеть разделилась пополам, и каждая половина уверена, что другая упала. Если обе выберут себе лидера, получится split brain: два мастера принимают противоречивые записи, и потом их не склеить.
Теоретически это оформлено в результате FLP (Фишер, Линч, Патерсон, 1985): в асинхронной системе, где хотя бы один узел может упасть, нет детерминированного алгоритма консенсуса, который всегда завершается. Практические системы обходят это таймаутами: жертвуют liveness в плохие периоды, но никогда не жертвуют safety.
Алгоритм задиры (bully)
Классика из учебников (Гарсия-Молина, 1982). У каждого узла уникальный числовой id, лидером становится живой узел с максимальным id.
- Узел замечает, что лидер не отвечает, и шлёт
ELECTIONвсем узлам с id больше своего. - Если кто-то из старших ответил
OK, узел отступает: выборы продолжит старший. - Если за таймаут не ответил никто, узел объявляет себя лидером и рассылает
COORDINATORвсем. - Когда поднимается узел с большим id, он сразу начинает выборы и «задирает» текущего лидера — отсюда название.
Модель на Python, без сети, но с той же логикой:
class Node: def __init__(self, node_id, cluster): self.id = node_id self.cluster = cluster self.alive = True self.leader = None def start_election(self): print(f'{self.id}: начинаю выборы') higher = [n for n in self.cluster.nodes if n.id > self.id] answered = False for n in higher: if n.alive: # ELECTION -> OK print(f' {n.id} ответил OK узлу {self.id}') answered = True if not answered: self.become_leader() return # Старшие узлы продолжают выборы сами; запускаем их по возрастанию for n in sorted(higher, key=lambda x: x.id): if n.alive and self.cluster.leader_id() is None: n.start_election() def become_leader(self): print(f'{self.id}: я лидер, рассылаю COORDINATOR') for n in self.cluster.nodes: if n.alive: n.leader = self.id class Cluster: def __init__(self, ids): self.nodes = [Node(i, self) for i in ids] def leader_id(self): leaders = {n.leader for n in self.nodes if n.alive} return leaders.pop() if len(leaders) == 1 else None def node(self, node_id): return next(n for n in self.nodes if n.id == node_id) cluster = Cluster([1, 2, 3, 4, 5]) cluster.node(1).start_election() print('Лидер:', cluster.leader_id()) cluster.node(5).alive = False for n in cluster.nodes: n.leader = None # все заметили, что лидер молчит cluster.node(2).start_election() print('Лидер:', cluster.leader_id())
Хвост вывода:
4: начинаю выборы 4: я лидер, рассылаю COORDINATOR Лидер: 4
Когда узел 5 упал, выборы, начатые узлом 2, прокатились вверх через 3 и 4, и лидером стал 4 — самый старший из живых.
Сложность по сообщениям: в худшем случае, когда выборы начинает самый младший узел, — . В лучшем, когда отказ замечает второй по старшинству, — : он сразу рассылает COORDINATOR.
Кольцевой алгоритм
Альтернатива — узлы организованы в логическое кольцо (Chang–Roberts, LeLann). Инициатор отправляет по кольцу сообщение со своим id, каждый узел пропускает дальше максимум из своего и пришедшего. Когда сообщение возвращается к узлу с этим максимумом, тот объявляет себя лидером. В среднем это сообщений, в худшем . Поиск максимума за один проход — та же идея, что в задачах на поиск экстремума в массиве, только массив распределён по машинам.
Почему bully не годится для продакшена
Алгоритм молча предполагает, что «не ответил за таймаут» значит «упал». Посмотрим, что будет при разделении сети {1, 2, 3} | {4, 5}:
- в левой половине узел 3 не дозвался до 4 и 5 и стал лидером;
- в правой узел 5 остался лидером;
- клиенты по обе стороны пишут в разных лидеров. Split brain.
Есть и проблема помягче: узел с максимальным id, у которого «моргает» сеть, будет постоянно отбирать лидерство и вызывать каскад перевыборов.
Вывод: bully и кольцо — хорошая разминка на собеседовании и иллюстрация того, почему нужен кворум. Но в реальных системах их не используют для чего-либо, где важна корректность.
Кворум и номер поколения
Две идеи, на которых держатся все надёжные схемы выборов.
Кворум. Узел становится лидером, только если за него проголосовало строгое большинство кластера: узлов. Два большинства одного множества обязательно пересекаются хотя бы в одном узле, а узел голосует один раз за поколение — значит, два лидера в одном поколении невозможны. При разделении {1, 2, 3} | {4, 5} лидера сможет выбрать только левая половина, правая останется без лидера и перестанет принимать записи. Это осознанный выбор согласованности вместо доступности, подробнее — в статье о CAP-теореме.
Поэтому кластеры консенсуса делают из нечётного числа узлов: 3 узла переживают отказ одного, 5 — двух. Четвёртый узел в кластере из трёх ничего не добавляет к отказоустойчивости: большинство из 4 — это 3.
Номер поколения. Каждые выборы получают монотонно растущий номер: в Raft это терм (term), в ZooKeeper — эпоха (epoch), в Viewstamped Replication — номер представления (view). Любое сообщение несёт номер поколения отправителя. Узел, увидевший номер больше своего, понимает, что пропустил выборы, и подчиняется. Сообщение со старым номером отвергается.
Это и есть защита от «проснувшегося» лидера. Он может всё ещё думать, что главный, но первое же его сообщение с термом 7 придёт к узлам, которые уже живут в терме 8, и будет отклонено.
Как именно Raft проводит выборы — рандомизированные таймауты, RequestVote, условие «лог кандидата не отстаёт», почему нельзя коммитить записи старых термов, — подробно разобрано в статье про алгоритм Raft. Здесь важно другое: выбор лидера и консенсус — эквивалентные по сложности задачи. Если у вас есть надёжный выбор лидера, на нём можно построить консенсус, и наоборот. Поэтому на практике выборы не изобретают, а берут готовое консенсусное хранилище.
Аренда (lease)
Самый распространённый в прикладном коде способ: лидерство — это ключ с ограниченным сроком жизни в надёжном хранилище.
- Претендент атомарно пишет ключ
leader = meс TTL, если ключа нет. - Победитель продлевает аренду раньше, чем она истечёт: например, TTL 15 секунд, продление каждые 2–5 секунд.
- Если лидер упал и перестал продлевать, ключ истекает, следующий претендент его забирает.
- Если лидер не смог продлить аренду до своего дедлайна, он сам обязан перестать действовать как лидер.
Аренда решает проблему liveness — упавший лидер не держит роль вечно. Но safety она не гарантирует. Сценарий:
- Лидер A взял аренду на 10 секунд.
- A ушёл в GC-паузу на 15 секунд. Аренда истекла, лидером стал B.
- A проснулся. С его точки зрения прошла одна строчка кода. Он отправляет запись в базу.
Теперь A и B пишут одновременно. Уменьшить окно можно: лидер считает аренду истёкшей раньше, чем хранилище (TTL минус запас на расхождение часов), и проверяет её перед каждым действием. Но закрыть окно полностью проверкой на стороне лидера нельзя: пауза может случиться между проверкой и записью.
Fencing token
Решение — перенести проверку на сторону ресурса. Каждое получение лидерства выдаёт монотонно растущий номер (ревизия в etcd, zxid в ZooKeeper, терм в Raft). Лидер прикладывает его к каждой записи, а хранилище запоминает максимальный увиденный номер и отклоняет всё, что меньше.
import itertools class LeaseStore: """Модель etcd/ZooKeeper: линеаризуемое хранилище с арендой и ревизиями.""" def __init__(self): self.holder = None self.expires = 0.0 self.revision = itertools.count(1) self.token = 0 def try_acquire(self, node, now, ttl):
# Аналог Txn: если ключа нет (или аренда истекла) — записать
if self.holder is None or now >= self.expires:
self.holder = node
self.expires = now + ttl
self.token = next(self.revision)
return self.token
return None
def renew(self, node, token, now, ttl):
if self.holder == node and self.token == token and now < self.expires:
self.expires = now + ttl
return True
return False
class Storage: """Ресурс, который сам проверяет fencing token."""
def __init__(self):
self.max_token = 0
self.log = []
def write(self, token, value):
if token < self.max_token:
return f'отклонено: токен {token} < {self.max_token}'
self.max_token = token
self.log.append(value)
return 'ok'
store, db = LeaseStore(), Storage() TTL = 10
t_a = store.try_acquire('A', now=0, ttl=TTL) print('A стал лидером, токен', t_a) print('B пытается:', store.try_acquire('B', now=3, ttl=TTL)) print('A пишет:', db.write(t_a, 'A@1'))
A уходит в GC-паузу на 15 секунд и не продлевает аренду
t_b = store.try_acquire('B', now=12, ttl=TTL) print('B стал лидером, токен', t_b) print('B пишет:', db.write(t_b, 'B@13'))
A просыпается и, не зная о смене лидера, пытается писать
print('A продлевает:', store.renew('A', t_a, now=15, ttl=TTL)) print('A пишет:', db.write(t_a, 'A@15')) print('Журнал:', db.log)
Вывод:
```text
A стал лидером, токен 1
B пытается: None
A пишет: ok
B стал лидером, токен 2
B пишет: ok
A продлевает: False
A пишет: отклонено: токен 1 < 2
Журнал: ['A@1', 'B@13']
Запись проснувшегося A отклонена ресурсом, хотя сам A о смене лидера ещё не знал. Ограничение одно: ресурс должен уметь проверять токен. База — да (условие в UPDATE или отдельная колонка), внешний API платёжного провайдера — нет. Тогда остаётся идемпотентность операций и смирение с тем, что редкий дубль возможен. Та же механика подробно разобрана в статье о распределённых блокировках: лидерство по сути и есть долгоживущая блокировка.
Часы и аренда
Аренда опирается на время, поэтому важно, чьи часы считают TTL. В etcd и ZooKeeper срок отсчитывает сервер хранилища, клиент только продлевает. Клиенту нельзя считать «моя аренда до 12:00:15 по моим часам»: если его часы отстают на 3 секунды, он будет считать себя лидером на 3 секунды дольше, чем хранилище. Правильнее мерить длительность монотонными часами (time.monotonic()) от момента отправки запроса на продление и закладывать запас на дрейф.
Готовые рецепты
ZooKeeper
Рецепт выборов из документации ZooKeeper почти дословно повторяет рецепт блокировки:
- Каждый претендент создаёт узел
/election/n_с флагамиEPHEMERAL | SEQUENTIAL. ZooKeeper добавляет порядковый номер:n_0000000012. - Претендент с минимальным номером — лидер.
- Остальные ставят watch на узел с номером прямо перед своим. Когда он исчезает, проверяют, не стали ли они минимальными.
Эфемерный узел удаляется, когда истекает сессия клиента, — это и есть аренда, управляемая сервером. Watch на предшественника вместо watch на всю директорию спасает от herd effect: при смене лидера просыпается один узел, а не сотня. Руками это не пишут: в Java есть LeaderLatch и LeaderSelector из Apache Curator, в Python — Election из kazoo.
Долгие годы на этом держались Kafka (выбор контроллера), HBase, Hadoop. В Kafka 4.0 ZooKeeper окончательно убрали: метаданные и выбор контроллера теперь внутри самой Kafka в режиме KRaft — это Raft.
etcd
В etcd аналог эфемерного узла — ключ, привязанный к lease. Клиент на Go:
session, _ := concurrency.NewSession(cli, concurrency.WithTTL(10)) election := concurrency.NewElection(session, "/services/scheduler") // Блокируется, пока этот узел не станет лидером if err := election.Campaign(ctx, "node-1"); err != nil { return err } // ... работаем как лидер, пока жива session ... <-session.Done() // аренда потеряна — немедленно прекращаем работу
Внутри всё тот же порядок по ревизии создания ключа: побеждает ключ с минимальной create revision, остальные ждут удаления предшественника. Observe позволяет всем узлам следить, кто сейчас лидер, Resign — добровольно уступить. Ревизия ключа — готовый fencing token. Из командной строки то же самое делает etcdctl elect.
Kubernetes Lease
Если сервис живёт в Kubernetes, отдельный etcd не нужен: есть объект Lease в API coordination.k8s.io. Пакет leaderelection из client-go реализует выборы поверх него, и так работают сами kube-controller-manager и kube-scheduler. Их настройки по умолчанию хорошо показывают типичные пропорции:
| Параметр | Значение | Смысл |
|---|---|---|
lease-duration | 15 с | сколько кандидаты ждут, прежде чем забрать чужое лидерство |
renew-deadline | 10 с | за это время лидер обязан продлить аренду, иначе сдаётся сам |
retry-period | 2 с | как часто лидер продлевает и кандидаты пробуют захватить |
Важно, что renew-deadline меньше lease-duration: лидер отказывается от роли раньше, чем остальные начнут её забирать. Эти 5 секунд — запас на паузы и расхождение часов. Сам Lease при этом использует обычную оптимистическую конкуренцию по resourceVersion, а не консенсус между кандидатами: консенсус обеспечивает etcd под API-сервером.
Сравнение
| Способ | Безопасность при разделении сети | Fencing token | Когда брать |
|---|---|---|---|
| Bully, кольцо | Нет, возможен split brain | Нет | Учебные задачи, собеседование |
| Свой Raft | Да, кворум и термы | Терм | Почти никогда: только если вы пишете базу данных |
| ZooKeeper | Да, ZAB и кворум | zxid, номер узла | ZooKeeper уже есть в инфраструктуре |
| etcd | Да, Raft | Ревизия | Свой координатор, Go-сервисы |
| Kubernetes Lease | Да, за счёт etcd под API | Нет из коробки | Сервис уже в Kubernetes |
Redis SET NX PX | Нет при асинхронном failover | Нет | Только если двойная работа безвредна |
| Advisory lock в Postgres | Как у самой базы | Нет | Ресурс, который защищаем, — эта же база |
Когда выбор лидера не нужен
Лидер — это узкое место и точка отказа на время перевыборов (обычно секунды). Иногда без него проще:
- Задачу можно разбить на части. Вместо одного лидера, раздающего работу, — шардирование по ключу через консистентное хеширование: каждый узел обрабатывает свой диапазон.
- Операция идемпотентна. Если двойная выгрузка отчёта ничего не ломает, достаточно дедупликации по ключу задачи, а выборы — лишний механизм.
- Работу можно отдать очереди. Задачи лежат в очереди сообщений, воркеры конкурируют за них, брокер гарантирует, что сообщение получит один потребитель (с поправкой на повторную доставку).
- Leaderless-репликация. Cassandra и Dynamo-подобные хранилища пишут в любые из реплик и читают из , при чтение пересекается с записью. Выборов нет вообще, зато есть разрешение конфликтов.
Типичные ошибки
- «Не ответил по таймауту — значит, упал». Это допущение и ломает bully. Таймаут говорит только о том, что ответа не было.
- Лидер не проверяет потерю аренды. Сессия в etcd или ZooKeeper истекла, а код продолжает работать. Подписывайтесь на событие потери сессии и останавливайте работу сразу.
- Нет fencing token. Аренда без проверки на стороне ресурса даёт окно с двумя лидерами при любой длинной паузе.
- Чётное число узлов кворума. 4 узла переживают столько же отказов, сколько 3, а кворум собирать дольше.
- Таймауты сравнимы с задержками сети. Лидера постоянно переизбирают, система больше выбирает, чем работает. Election timeout должен быть на порядок больше времени круга до узлов.
- Чтение «с лидера» без проверки лидерства. Старый лидер в меньшинстве может отдавать устаревшие данные. Raft-системы для линеаризуемого чтения либо подтверждают лидерство у кворума (read index), либо опираются на аренду лидера с допущениями о часах.
Как отвечать на собеседовании
Вопрос обычно звучит как «у нас пять реплик сервиса, а эту задачу должен выполнять кто-то один — как?» или всплывает внутри большого дизайна. План ответа:
- Назовите требования: не больше одного активного лидера, быстрая замена упавшего.
- Объясните, почему это трудно: медленный узел неотличим от мёртвого, возможно разделение сети.
- Коротко опишите bully и покажите, где он ломается при разделении.
- Введите кворум и номер поколения — это закрывает split brain.
- Скажите, что сами Raft не пишете, а берёте etcd, ZooKeeper или Kubernetes Lease; объясните аренду и её параметры.
- Добавьте fencing token и проверку на стороне ресурса — именно этот пункт чаще всего отделяет сильный ответ.
- Обсудите, можно ли обойтись без лидера: шардирование, идемпотентность, очередь.
Если интервьюер копает в сторону консенсуса, переходите к деталям Raft: правило голосования, рандомизированные таймауты, коммит по большинству.