Алгоритмы консенсуса
Проблема консенсуса
Консенсус -- фундаментальная задача распределённых систем: как нескольким узлам договориться об одном значении, если часть узлов может отказать?
Где нужен консенсус
| Задача | Что согласовывают |
|---|---|
| Leader election | Кто текущий лидер |
| Atomic broadcast | Порядок сообщений |
| Distributed lock | Кто владеет блокировкой |
| State machine replication | Последовательность команд |
| Configuration | Текущая конфигурация кластера |
Требования к консенсусу
┌─────────────────────────────────────────────────┐
│ Свойства корректного консенсуса │
│ │
│ 1. Agreement -- все узлы решают одинаково │
│ 2. Validity -- решение предложено узлом │
│ 3. Termination -- процесс завершается │
│ 4. Integrity -- узел решает только один раз │
└─────────────────────────────────────────────────┘
FLP Impossibility
Фишер, Линч и Патерсон доказали (1985): детерминированный консенсус невозможен в асинхронной системе даже с одним отказавшим узлом.
Практический выход: Все реальные алгоритмы (Paxos, Raft) используют таймауты и рандомизацию, жертвуя гарантией termination в теории, но работая на практике.
Paxos
Лесли Лэмпорт предложил Paxos в 1989 году. Это первый алгоритм консенсуса, который корректно работает при crash-recovery отказах.
Роли в Paxos
- Proposer -- предлагает значение
- Acceptor -- голосует за предложения
- Learner -- узнаёт согласованное значение
На практике один узел может выполнять все три роли.
Basic Paxos (Single-Decree)
Согласование одного значения за раунд.
Proposer Acceptor 1 Acceptor 2 Acceptor 3
│ │ │ │
│ PREPARE(n=1) │ │ │
│─────────────────>│ │ │
│─────────────────────────────────> │
│──────────────────────────────────────────────> │
│ │ │ │
│ PROMISE(n=1) │ │ │
│<─────────────────│ │ │
│<───────────────────────────────── │
│<──────────────────────────────────────────────│
│ │ │ │
│ ACCEPT(n=1, v="X") │ │
│─────────────────>│ │ │
│─────────────────────────────────> │
│──────────────────────────────────────────────> │
│ │ │ │
│ ACCEPTED(n=1) │ │ │
│<─────────────────│ │ │
│<───────────────────────────────── │
│<──────────────────────────────────────────────│
│ │ │ │
▼ Consensus: v="X" (majority = 2+) ▼
Фазы Paxos
Фаза 1: Prepare / Promise
- Proposer выбирает уникальный номер
nи отправляетPREPARE(n)всем Acceptor - Acceptor, получив
PREPARE(n):- Если
n> всех ранее виденных номеров -- отвечаетPROMISE(n)+ ранее принятое значение (если есть) - Иначе -- игнорирует
- Если
Фаза 2: Accept / Accepted
- Proposer, получив
PROMISEот большинства:- Если кто-то уже принял значение -- использует его
- Иначе -- предлагает своё значение
v - Отправляет
ACCEPT(n, v)всем Acceptor
- Acceptor принимает
ACCEPT(n, v), если не обещал другому Proposer - Если большинство приняло -- консенсус достигнут
Проблемы Paxos
| Проблема | Описание |
|---|---|
| Dueling Proposers | Два Proposer бесконечно перебивают друг друга номерами |
| Сложность понимания | Лэмпорт сам признаёт: "Paxos is simple, but not easy" |
| Multi-Paxos | Для серии решений нужен Multi-Paxos, который плохо специфицирован |
| Производительность | 2 раунда сообщений на каждое решение |
Raft
Диего Онгаро и Джон Устерхаут создали Raft в 2014 году как понятную альтернативу Paxos.
Ключевая идея
Raft разделяет консенсус на 3 подзадачи:
- Leader Election -- выбор лидера
- Log Replication -- репликация журнала через лидера
- Safety -- гарантии корректности
Состояния узлов
timeout, start election
┌──────────────────────────────┐
│ │
▼ │
┌──────────┐ wins election ┌──────────┐
│ Candidate │─────────────────>│ Leader │
└──────────┘ └──────────┘
▲ │
│ timeout, │ discovers higher
│ no leader │ term leader
│ │
┌──────────┐<───────────────────────┘
│ Follower │
└──────────┘
(start)
Leader Election
Term 1: Leader = Node A
─────────────────────────────────────────
Node A (Leader) Node B (Follower) Node C (Follower)
│ heartbeat │ │
│──────────────────>│ │
│───────────────────────────────────────>│
│ │ │
X (crashes) │ │
│ │
election timeout expires... │
│ │
Term 2: Election │
Node B (Candidate) │
│ RequestVote(term=2) │
│───────────────────>│
│<───────────────────│
│ VoteGranted │
│ │
Node B = new Leader │
Алгоритм:
- Follower не получает heartbeat от лидера в течение election timeout (рандомизированный: 150-300 мс)
- Переходит в Candidate, увеличивает term, голосует за себя
- Отправляет
RequestVoteвсем узлам - Если получает большинство голосов -- становится Leader
- Начинает отправлять heartbeat
Рандомизация timeout предотвращает одновременные выборы (split vote).
Log Replication
Leader (Node B) Follower (Node C) Follower (Node D)
│ │ │
│ AppendEntries │ │
│ [term=2, entry="SET │ │
│ x=5"] │ │
│───────────────────────>│ │
│─────────────────────────────────────────────>│
│ │ │
│ ACK (success) │ │
│<───────────────────────│ │
│<─────────────────────────────────────────────│
│ │ │
│ Majority ACKed │ │
│ COMMIT entry │ │
│ │ │
│ Next AppendEntries │ │
│ includes commitIndex │ │
│───────────────────────>│ │
│ │ Apply committed │
│ │ entries │
Правила:
- Клиент отправляет команду лидеру
- Лидер добавляет запись в свой лог
- Рассылает
AppendEntriesвсем followers - Когда большинство подтвердило -- запись committed
- Лидер применяет запись и отвечает клиенту
- Followers узнают о commit в следующем heartbeat
Safety Properties
| Свойство | Гарантия |
|---|---|
| Election Safety | Один лидер в каждом term |
| Leader Append-Only | Лидер никогда не перезаписывает свой лог |
| Log Matching | Если два лога содержат запись с одинаковым index и term -- логи идентичны до этой записи |
| Leader Completeness | Committed запись есть в логах всех будущих лидеров |
| State Machine Safety | Все узлы применяют одинаковые записи в одинаковом порядке |
ZAB (ZooKeeper Atomic Broadcast)
ZAB -- протокол, используемый Apache ZooKeeper для репликации данных.
Сравнение с Raft
ZAB Raft
┌────────────────────┐ ┌────────────────────┐
│ 1. Leader Discovery│ │ 1. Leader Election │
│ 2. Synchronization │ │ (merged into │
│ 3. Broadcast │ │ election) │
└────────────────────┘ │ 2. Log Replication │
└────────────────────┘
ZAB: сначала лидер синхронизирует followers, потом принимает записи
Raft: лидер сразу начинает принимать записи, синхронизация через log
| Аспект | Raft | ZAB |
|---|---|---|
| Фаза восстановления | Нет отдельной фазы | Explicit synchronization phase |
| Порядок доставки | Total order через лидера | FIFO + causal ordering |
| Membership changes | Single-step joint consensus | Atomic reconfiguration |
| Реализации | etcd, Consul, CockroachDB | ZooKeeper |
Leader Election и Split-Brain
Проблема Split-Brain
┌──────────────────────────────────────────────────────┐
│ SPLIT-BRAIN │
│ │
│ Partition A │ Partition B │
│ ┌────────────┐ │ ┌────────────┐ │
│ │ Node 1 │ │ │ Node 3 │ │
│ │ (Leader!) │ X │ (Leader!) │ │
│ ├────────────┤ │ ├────────────┤ │
│ │ Node 2 │ │ │ Node 4 │ │
│ │ (Follower) │ │ │ (Follower) │ │
│ └────────────┘ │ │ Node 5 │ │
│ │ │ (Follower) │ │
│ Writes: v1 │ │ │ │
│ │ └────────────┘ │
│ │ Writes: v2 │
│ │
│ ДВА ЛИДЕРА = РАСХОЖДЕНИЕ ДАННЫХ! │
└──────────────────────────────────────────────────────┘
Решения Split-Brain
1. Majority Quorum (основной подход)
5 узлов majority = 3
Partition A: 2 узла нет majority НЕ МОЖЕТ быть лидером
Partition B: 3 узла есть majority единственный лидер
Правило: всегда нечётное число узлов (3, 5, 7)
2. Fencing Tokens
Epoch 1: Leader A получает token=42
Epoch 2: Leader B получает token=43
Storage принимает запись только с token >= последнего виденного.
Старый лидер A с token=42 ОТКЛОНЁН.
3. STONITH (Shoot The Other Node In The Head)
При подозрении на split-brain -- принудительная перезагрузка "другого" лидера через out-of-band канал (IPMI, управление питанием).
Сколько отказов выдерживает кластер
| Узлов | Majority | Допустимые отказы |
|---|---|---|
| 3 | 2 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
| 2N+1 | N+1 | N |
Почему не 4 или 6? Чётное число узлов не даёт преимущества: 4 узла выдерживают 1 отказ (как и 3), но стоят дороже.
Сравнение алгоритмов
| Критерий | Paxos | Raft | ZAB |
|---|---|---|---|
| Понятность | Сложный | Простой | Средний |
| Лидер | Опционально | Обязательный | Обязательный |
| Производительность | 2 RTT (basic) | 1 RTT (лидер) | 1 RTT (лидер) |
| Membership changes | Сложные | Joint consensus | Atomic reconfig |
| Отказоустойчивость | f < N/2 | f < N/2 | f < N/2 |
| Реализации | Chubby (Google) | etcd, Consul, TiKV | ZooKeeper |
| Гарантия порядка | Нет (basic) | Total order | FIFO + Causal |
Применение на практике
Когда что использовать
Задача Рекомендация
──────────────────────────────────────────────
Metadata store, config -> etcd (Raft)
Service discovery -> Consul (Raft) / ZooKeeper (ZAB)
Distributed lock -> ZooKeeper (ZAB) / etcd (Raft)
Replicated database -> Raft (CockroachDB, TiDB)
Message ordering -> ZAB / Raft-based log
Что говорить на интервью
- Не реализуйте консенсус сами -- используйте готовые решения (etcd, ZooKeeper)
- Raft проще объяснить -- если просят описать алгоритм, начните с Raft
- Majority quorum -- ключевая идея для предотвращения split-brain
- Leader-based -- упрощает систему, но лидер = bottleneck
- Нечётное число узлов -- 3 или 5, не 4 или 6