Выбор лидера в распределённых системах: bully, термы, lease, ZooKeeper и etcd

Как узлы кластера выбирают лидера: алгоритм задиры (bully), кворум и термы, аренда (lease) и часы, fencing tokens, рецепты на ZooKeeper, etcd и Kubernetes Lease. Модели на Python.

13 мин чтениясистемный дизайн · распределённые системы · консенсус · 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.

  1. Узел замечает, что лидер не отвечает, и шлёт ELECTION всем узлам с id больше своего.
  2. Если кто-то из старших ответил OK, узел отступает: выборы продолжит старший.
  3. Если за таймаут не ответил никто, узел объявляет себя лидером и рассылает COORDINATOR всем.
  4. Когда поднимается узел с большим 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 — самый старший из живых.

Сложность по сообщениям: в худшем случае, когда выборы начинает самый младший узел, — O(n2)O(n^2). В лучшем, когда отказ замечает второй по старшинству, — O(n)O(n): он сразу рассылает COORDINATOR.

Кольцевой алгоритм

Альтернатива — узлы организованы в логическое кольцо (Chang–Roberts, LeLann). Инициатор отправляет по кольцу сообщение со своим id, каждый узел пропускает дальше максимум из своего и пришедшего. Когда сообщение возвращается к узлу с этим максимумом, тот объявляет себя лидером. В среднем это O(nlog⁡n)O(n \log n) сообщений, в худшем O(n2)O(n^2). Поиск максимума за один проход — та же идея, что в задачах на поиск экстремума в массиве, только массив распределён по машинам.

Почему bully не годится для продакшена

Алгоритм молча предполагает, что «не ответил за таймаут» значит «упал». Посмотрим, что будет при разделении сети {1, 2, 3} | {4, 5}:

  • в левой половине узел 3 не дозвался до 4 и 5 и стал лидером;
  • в правой узел 5 остался лидером;
  • клиенты по обе стороны пишут в разных лидеров. Split brain.

Есть и проблема помягче: узел с максимальным id, у которого «моргает» сеть, будет постоянно отбирать лидерство и вызывать каскад перевыборов.

Вывод: bully и кольцо — хорошая разминка на собеседовании и иллюстрация того, почему нужен кворум. Но в реальных системах их не используют для чего-либо, где важна корректность.

Кворум и номер поколения

Две идеи, на которых держатся все надёжные схемы выборов.

Кворум. Узел становится лидером, только если за него проголосовало строгое большинство кластера: ⌊n/2⌋+1\lfloor n/2 \rfloor + 1 узлов. Два большинства одного множества обязательно пересекаются хотя бы в одном узле, а узел голосует один раз за поколение — значит, два лидера в одном поколении невозможны. При разделении {1, 2, 3} | {4, 5} лидера сможет выбрать только левая половина, правая останется без лидера и перестанет принимать записи. Это осознанный выбор согласованности вместо доступности, подробнее — в статье о CAP-теореме.

Поэтому кластеры консенсуса делают из нечётного числа узлов: 3 узла переживают отказ одного, 5 — двух. Четвёртый узел в кластере из трёх ничего не добавляет к отказоустойчивости: большинство из 4 — это 3.

Номер поколения. Каждые выборы получают монотонно растущий номер: в Raft это терм (term), в ZooKeeper — эпоха (epoch), в Viewstamped Replication — номер представления (view). Любое сообщение несёт номер поколения отправителя. Узел, увидевший номер больше своего, понимает, что пропустил выборы, и подчиняется. Сообщение со старым номером отвергается.

Это и есть защита от «проснувшегося» лидера. Он может всё ещё думать, что главный, но первое же его сообщение с термом 7 придёт к узлам, которые уже живут в терме 8, и будет отклонено.

Как именно Raft проводит выборы — рандомизированные таймауты, RequestVote, условие «лог кандидата не отстаёт», почему нельзя коммитить записи старых термов, — подробно разобрано в статье про алгоритм Raft. Здесь важно другое: выбор лидера и консенсус — эквивалентные по сложности задачи. Если у вас есть надёжный выбор лидера, на нём можно построить консенсус, и наоборот. Поэтому на практике выборы не изобретают, а берут готовое консенсусное хранилище.

Аренда (lease)

Самый распространённый в прикладном коде способ: лидерство — это ключ с ограниченным сроком жизни в надёжном хранилище.

  1. Претендент атомарно пишет ключ leader = me с TTL, если ключа нет.
  2. Победитель продлевает аренду раньше, чем она истечёт: например, TTL 15 секунд, продление каждые 2–5 секунд.
  3. Если лидер упал и перестал продлевать, ключ истекает, следующий претендент его забирает.
  4. Если лидер не смог продлить аренду до своего дедлайна, он сам обязан перестать действовать как лидер.

Аренда решает проблему 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 почти дословно повторяет рецепт блокировки:

  1. Каждый претендент создаёт узел /election/n_ с флагами EPHEMERAL | SEQUENTIAL. ZooKeeper добавляет порядковый номер: n_0000000012.
  2. Претендент с минимальным номером — лидер.
  3. Остальные ставят 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-duration15 ссколько кандидаты ждут, прежде чем забрать чужое лидерство
renew-deadline10 сза это время лидер обязан продлить аренду, иначе сдаётся сам
retry-period2 скак часто лидер продлевает и кандидаты пробуют захватить

Важно, что 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-подобные хранилища пишут в любые WW из NN реплик и читают из RR, при R+W>NR + W > N чтение пересекается с записью. Выборов нет вообще, зато есть разрешение конфликтов.

Типичные ошибки

  • «Не ответил по таймауту — значит, упал». Это допущение и ломает bully. Таймаут говорит только о том, что ответа не было.
  • Лидер не проверяет потерю аренды. Сессия в etcd или ZooKeeper истекла, а код продолжает работать. Подписывайтесь на событие потери сессии и останавливайте работу сразу.
  • Нет fencing token. Аренда без проверки на стороне ресурса даёт окно с двумя лидерами при любой длинной паузе.
  • Чётное число узлов кворума. 4 узла переживают столько же отказов, сколько 3, а кворум собирать дольше.
  • Таймауты сравнимы с задержками сети. Лидера постоянно переизбирают, система больше выбирает, чем работает. Election timeout должен быть на порядок больше времени круга до узлов.
  • Чтение «с лидера» без проверки лидерства. Старый лидер в меньшинстве может отдавать устаревшие данные. Raft-системы для линеаризуемого чтения либо подтверждают лидерство у кворума (read index), либо опираются на аренду лидера с допущениями о часах.

Как отвечать на собеседовании

Вопрос обычно звучит как «у нас пять реплик сервиса, а эту задачу должен выполнять кто-то один — как?» или всплывает внутри большого дизайна. План ответа:

  1. Назовите требования: не больше одного активного лидера, быстрая замена упавшего.
  2. Объясните, почему это трудно: медленный узел неотличим от мёртвого, возможно разделение сети.
  3. Коротко опишите bully и покажите, где он ломается при разделении.
  4. Введите кворум и номер поколения — это закрывает split brain.
  5. Скажите, что сами Raft не пишете, а берёте etcd, ZooKeeper или Kubernetes Lease; объясните аренду и её параметры.
  6. Добавьте fencing token и проверку на стороне ресурса — именно этот пункт чаще всего отделяет сильный ответ.
  7. Обсудите, можно ли обойтись без лидера: шардирование, идемпотентность, очередь.

Если интервьюер копает в сторону консенсуса, переходите к деталям Raft: правило голосования, рандомизированные таймауты, коммит по большинству.

Потренироваться в спокойной обстановке

Все задачи