Распределённые системы
Консенсус: Paxos и Raft
Цели урока
- Понимать что такое консенсус и его три формальных требования
- Знать FLP-невозможность и три способа её обойти на практике
- Разбираться в двух фазах алгоритма Paxos и инварианте выбора значения
- Понимать state machine Raft и log matching property
- Выбирать между Paxos и Raft для конкретных задач
Предварительные знания
- CAP-теорема: CP vs AP trade-off
- Понятие кворума и репликации
- Базовые failure modes (crash, network partition)
etcd - это мозг каждого Kubernetes кластера. Без консенсуса в etcd - кластер не знает где какой под, кто лидер, какая конфигурация актуальна. Консенсус - это не академия, это буквально сердцебиение production-инфраструктуры.
- **etcd (Kubernetes)** - хранит всё состояние кластера на Raft, 3-5 узлов, кворум обязателен
- **Google Chubby** - distributed lock service на Paxos, координирует тысячи internal сервисов Google
- **CockroachDB** - Raft на каждый range данных, глобально распределённая SQL БД
- **Apache ZooKeeper** - ZAB (ZooKeeper Atomic Broadcast) - вариант Paxos. Координировал Kafka до 4.0 (март 2025; теперь KRaft), всё ещё координирует HBase и Hadoop
- **Consul** - Raft для service discovery и конфигурации, стандарт в HashiCorp стеке
Лэмпорт и история Paxos
В 1989 Лэмпорт описал Paxos через метафору греческого парламента острова Паксос. Статью отклонили в TOCS: "слишком несерьёзная подача". Лэмпорт убрал метафору и отправил снова - отклонили снова. Опубликована только в 1998 после того как Google и другие начали использовать алгоритм в production и ссылаться на технический отчёт. За Paxos и другие работы Лэмпорт получил Turing Award в 2013.
Проблема консенсуса
**etcd хранит конфигурацию каждого Kubernetes-кластера в мире. 1 апреля 2020 Cloudflare потеряла связь между дата-центрами: 180 секунд без консенсуса - и 1/3 подов по всему кластеру зависла в состоянии Unknown.** Консенсус - это механизм, при котором несколько независимых узлов приходят к одному решению несмотря на сбои части из них. Модель сбоев за словами "сбои части из них" задана во введении в распределённые системы.
**Формальные требования консенсуса (Lamport, 1982):** 1. **Agreement** - все корректные узлы принимают одинаковое значение. 2. **Validity** - принятое значение было предложено хотя бы одним узлом. 3. **Termination** - каждый корректный узел в итоге принимает решение.
Где консенсус применяется в production
| Задача | Почему нужен консенсус | Что сломается без него |
|---|---|---|
| Выбор лидера кластера | Только один узел должен быть primary | Split-brain: две записи в два несовместимых primary |
| Репликация лога транзакций | Все реплики должны видеть одни операции в одном порядке | Расхождение данных между репликами |
| Распределённые блокировки | Только один клиент держит lock в данный момент | Два клиента одновременно модифицируют один ресурс |
| Согласование конфигурации | Все узлы видят одинаковый конфиг | Половина кластера работает по старому конфигу |
Split-brain без консенсуса
Два узла PostgreSQL теряют связь друг с другом на 30 секунд. Без консенсуса оба считают себя primary и принимают записи. Сеть восстанавливается - данные на двух узлах расходятся. Какой набор данных правильный? Ответа нет. PostgreSQL с Patroni использует etcd (Raft) именно чтобы такого не было: при потере кворума primary переходит в read-only.
Консенсус нужен только при Byzantine-сбоях (злонамеренных узлах)
Консенсус нужен при любых независимых сбоях, включая обычные crash и сетевые разделы
Crash-fault tolerant консенсус (Paxos, Raft) защищает от самых частых сбоев - падений узлов и сетевых разделов. Byzantine fault tolerant (PBFT, CometBFT - бывш. Tendermint) - дорогостоящее расширение для недоверенных участников (блокчейны). 99% production систем используют crash-FT.
Кластер из 5 узлов. Один узел упал, два потеряли связь с остальными (сетевой раздел). Сколько узлов могут принять решение по консенсусу?
FLP-невозможность и обходные пути
**1985. Fischer, Lynch, Paterson публикуют результат, который потряс CS-сообщество: в полностью асинхронной системе с хотя бы одним возможным сбоем узла - детерминированный алгоритм консенсуса, гарантированно завершающийся, не существует.** Это не ограничение реализации - это математическое доказательство.
**FLP (Fischer-Lynch-Paterson, 1985):** В асинхронной системе с хотя бы одним потенциально сбойным узлом невозможен детерминированный алгоритм консенсуса, который гарантирует одновременно Safety (agreement) и Liveness (termination).
Проблема в том, что в асинхронной сети нельзя отличить медленный узел от упавшего. Алгоритм не знает: ждать ответа ещё секунду или узел мёртв и надо двигаться дальше без него. Это создаёт неразрешимое противоречие.
Три способа обойти FLP на практике
| Метод | Идея | Применение |
|---|---|---|
| Частичная синхронность (таймауты) | Система может быть асинхронной, но периодически ведёт себя синхронно. Таймаут = решение что узел упал. | Paxos, Raft - election timeout 150-300ms |
| Рандомизация | Алгоритм делает случайные шаги. Завершение гарантировано с вероятностью 1, но не детерминировано. | Ben-Or 1983, randomized consensus протоколы |
| Failure detectors | Отдельный механизм (Oracle) который говорит алгоритму кто упал. Детектор может ошибаться, но eventual accuracy. | Chandra-Toueg 1996, heartbeat-based detectors |
**Почему Raft и Paxos работают:** они жертвуют Liveness (могут зависнуть) ради Safety. При сетевом разделе они останавливаются и ждут, а не принимают противоречивые решения. Availability падает, но данные не расходятся - это CP в модели CAP.
Raft-кластер из 5 узлов теряет связь и не может провести выборы лидера 10 секунд. Это нормально или баг?
Paxos: алгоритм двух фаз
**Лесли Лэмпорт придумал Paxos в 1989, описал через легенду о греческом парламенте. Первая версия статьи была отклонена TOCS как "не серьёзная". Опубликована в 1998. ZooKeeper, Chubby (Google), Cassandra - всё на Paxos или его вариантах.** Расширенная семья Paxos разобрана в уроке про Paxos.
Роли участников
| Роль | Функция | Кто в реальной системе |
|---|---|---|
| Proposer | Предлагает значение, координирует голосование | Клиент или leader-узел |
| Acceptor | Голосует за предложения, хранит обещания | Узлы кластера (кворум) |
| Learner | Узнаёт о принятом решении и применяет его | Реплики, клиенты |
Фаза 1: Prepare / Promise
Фаза 2: Accept / Accepted
**Ключевой инвариант Paxos:** если значение v было принято кворумом в раунде n, то любой будущий Proposer с номером n' > n получит Promise от кворума, в котором хотя бы один Acceptor сообщит о принятом (n, v). Proposer вынужден выбрать то же v. Именно так Paxos гарантирует Agreement.
В Paxos Proposer всегда предлагает своё значение
Proposer обязан предложить значение с наивысшим ранее принятым номером из Promise-ответов
Это ключевой механизм safety. Если другой Proposer уже достиг консенсуса в раунде n=5 со значением 'X', новый Proposer с n=7 получит эту информацию в Promise и продолжит с 'X'. Без этого правила два Proposer могли бы достичь разных консенсусов.
Proposer получил Promise от 2 из 3 acceptors. Один Promise содержит highestAccepted = {n: 5, value: 'X'}. Какое значение Proposer должен предложить в фазе Accept?
Raft: консенсус для людей
**2014. Диего Онгаро и Джон Остерхаут публикуют Raft: "In Search of an Understandable Consensus Algorithm". Цель - не новый алгоритм, а тот же консенсус, но понятный человеку. etcd (Kubernetes), CockroachDB, TiKV, Consul - все выбрали Raft.** Разница с Paxos не в гарантиях, а в decomposition: Raft явно разделяет leader election, log replication, safety. Production-тюнинг Raft разобран в уроке про Raft.
Три состояния узла
Paxos vs Raft: что выбрать
| Аспект | Paxos (Multi-Paxos) | Raft |
|---|---|---|
| Понятность | Высокая сложность, много неявных деталей | Явная декомпозиция, легче реализовать |
| Лидер | Опционален (leaderless возможен) | Обязателен, все записи через него |
| Репликация | Одно значение за раунд | Непрерывный лог операций |
| Производительность | Можно параллельно (Multi-Paxos) | Последовательно через лидера |
| Применение | ZooKeeper (ZAB ~= Paxos), Chubby | etcd, Consul, CockroachDB, TiKV |
**Log matching property в Raft:** если две записи в логах разных узлов имеют одинаковые index и term - все предшествующие записи тоже одинаковы. Leader никогда не перезаписывает свой лог. Followers подгоняются под лидера при расхождении. Это ключевое safety-свойство.
Raft безопаснее Paxos потому что проще
Raft и Paxos дают эквивалентные safety-гарантии; простота Raft - это простота реализации, а не большая надёжность
Оба алгоритма решают одну и ту же задачу с одинаковыми ограничениями (FLP). Raft проще понять и правильно реализовать, что на практике снижает количество багов в имплементации. Но формально их гарантии идентичны при crash-fault модели.
В Raft-кластере из 5 узлов лидер упал сразу после того как записал команду в свой лог, но не успел разослать её на followers. Что произойдёт с этой командой?
Ключевые идеи
- **Консенсус** - три требования Лэмпорта: Agreement (все решают одинаково), Validity (значение было предложено), Termination (каждый узел решает)
- **FLP-невозможность** - в асинхронной системе с хотя бы одним сбойным узлом детерминированный алгоритм не может гарантировать одновременно Safety и Liveness
- **Обход FLP** - частичная синхронность (таймауты в Paxos/Raft), рандомизация, failure detectors; Raft и Paxos жертвуют Liveness ради Safety
- **Paxos (две фазы)** - Prepare/Promise блокирует старые раунды; Accept/Accepted коммитит значение с наивысшим принятым номером
- **Raft** - явная декомпозиция: leader election (рандомный timeout), log replication (AppendEntries), safety (log matching property)
- **Paxos vs Raft** - одинаковые safety-гарантии; Raft проще реализовать корректно - именно поэтому etcd, CockroachDB, Consul выбрали Raft
- **Кворум** - для кластера из N нужно большинство (floor(N/2)+1); нечётное число узлов практичнее из-за чёткого большинства
Вопросы для размышления
- etcd рекомендует 3 или 5 узлов, но не 4 или 6. Почему чётное число узлов менее практично для кворума чем нечётное?
Связанные уроки
- ds-04-clocks — Логическое упорядочивание лежит под согласием по последовательности событий
- dist-08-paxos — Multi-Paxos и Fast Paxos строятся поверх двухфазного протокола
- dist-09-raft — Варианты Raft (Joint Consensus) расширяют leader-based ядро
- dist-10-byzantine — PBFT и CometBFT (бывш. Tendermint) обобщают консенсус на враждебные узлы
- ds-02-cap-theorem — Кворум и CP-поведение приходят из CAP trade-off
- st-12-organizations — Голосование в демократиях повторяет quorum-based согласие
- ibd-21-docker-k8s-interview
- alg-12-bfs