Распределённый консенсус
Предпосылки: CAP-теорема (CP-системы, кворум, partition tolerance), модели консистентности (linearizability), разрешение конфликтов (LWW, vector clocks, CRDT).
← Разрешение конфликтов | Профили нагрузки →
Стратегии разрешения конфликтов — LWW, vector clocks, CRDT — работают, когда расхождение допустимо: данные разошлись, потом слились. Но некоторые решения не терпят расхождений. Три узла etcd хранят метаданные кластера PostgreSQL — в том числе запись «primary = Node A», по которой десяток приложений направляет все записи. Если при сетевом разделении два узла независимо решат, что каждый из них — новый primary, приложения начнут писать в две разные базы. За минуты накопятся конфликтующие транзакции, которые невозможно слить автоматически — данные расходятся необратимо. Такой конфликт нельзя разрешить постфактум — его нужно предотвратить.
CP-система решает эту проблему, отказывая изолированным узлам в обслуживании при partition. Но как узлы договариваются, кто изолирован? Как выбирают нового лидера, если старый упал? Как гарантируют, что два узла не примут противоречащие решения одновременно? Это задача распределённого консенсуса: несколько узлов должны прийти к одному решению, даже если часть из них недоступна или сообщения теряются.
Почему консенсус — сложная задача
Node A упал, Node B и Node C должны выбрать нового лидера. Кажется, достаточно «проголосовать». Но в распределённой системе голосование наталкивается на три проблемы.
Одновременные кандидаты: Node B и Node C оба объявляют себя лидером — ни один не знает, кого из них поддержат остальные. Потерянные сообщения: Node B отправил запрос на голосование, но до Node C он не дошёл — Node C не знает, что выборы начались, и начинает собственные. Сбой посередине: новый лидер успел отправить обновление «primary = Node B» одному follower, упал до отправки другому — часть узлов считает primary = Node B, часть — по-прежнему Node A.
Все три проблемы ведут к одному: узлы расходятся в представлении о текущем состоянии. Самый опасный вариант — split brain: два узла одновременно считают себя лидером и принимают записи, данные расходятся необратимо. Алгоритм консенсуса должен гарантировать, что в любой момент максимум один узел считает себя лидером.
Raft: понятный алгоритм консенсуса
Paxos (Лэмпорт, ~1989, опубликован в 1998) — первый алгоритм консенсуса. Корректный, но известен сложностью понимания. Raft (Ongaro, Ousterhout, 2014) разработан для понятности: те же гарантии, проще реализовать и объяснить. Название — метафора: плот (raft) собирается из брёвен (logs), как алгоритм строится вокруг реплицированного журнала команд (replicated log), а сам плот позволяет «уплыть с острова Paxos». Большинство современных систем используют Raft или его вариации.
Терминология Raft построена на метафоре политических выборов: узлы-кандидаты (candidates) собирают голоса (votes), победитель становится лидером (leader) на срок полномочий (term), остальные — followers. Raft разделяет консенсус на три задачи: выбор лидера (leader election), репликация журнала (log replication) и гарантии корректности (safety). В нормальном режиме лидер принимает запросы клиентов и реплицирует их на followers. Когда лидер падает — кластер выбирает нового. Safety гарантирует, что при смене лидера ни одна подтверждённая запись не теряется.
Но прежде чем разбирать каждую задачу — два механизма, на которых держится защита от split brain.
Кворум и терм
Кворум — правило большинства, описанное в репликации: узел работает, только если связан с большинством кластера. Raft добавляет к нему два механизма.
Кворум: пересечение большинств. Любое решение требует согласия большинства узлов. Два большинства обязательно пересекаются — хотя бы один узел входит в оба, и он не проголосует за противоречащие решения.
5 узлов, кворум = 3
Группа 1: {A, B, C} — может принять решение
Группа 2: {C, D, E} — тоже может
C входит в обе → не допустит противоречия
Терм: монотонный номер эпохи. Каждый лидер получает уникальный терм (term, он же epoch) — монотонно растущий счётчик. Узлы игнорируют сообщения от лидеров с устаревшим термом.
Term 3: Node A — лидер. Падает.
Term 4: Node B избран лидером.
Node A «воскресает», думает что он лидер.
Node A (term 3): "Записываем X"
Node C (term 4): "Твой term 3 < текущий 4. Отклоняю. Мой term: 4."
Node A: видит term 4 > свой 3 → переходит в Follower.
Без терма Node A продолжал бы считать себя лидером — split brain. Кворум и терм пронизывают все три задачи Raft: выборы требуют кворума голосов, коммит записи — кворума подтверждений, а терм определяет, чьи сообщения актуальны.
Состояния узла
Кворум и терм определяют правила принятия решений — но конкретное поведение узла зависит от его текущей роли. Каждый узел в любой момент находится в одном из трёх состояний.
Follower — пассивен, отвечает на запросы от лидера и кандидатов. Candidate — участвует в выборах: голосует за себя и запрашивает голоса у других. Leader — обрабатывает запросы клиентов, реплицирует лог на followers.
таймаут большинство
┌──────────┐ ┌───────────┐ ┌──────────┐
│ Follower ├───────>│ Candidate ├───────>│ Leader │
└────^─────┘ └─────┬─────┘ └────┬─────┘
│ │ │
└────────────────────┴───────────────────┘
увидел узел с бо́льшим термом
Leader election
Каждый follower ждёт heartbeat (периодическое сообщение «я жив») от лидера. Если не получил в течение election timeout — считает лидера мёртвым, увеличивает term, переходит в состояние candidate и запрашивает голоса.
Node B (follower, таймаут истёк):
1. term = term + 1 (например, 3 → 4)
2. Голосует сам за себя
3. Отправляет RequestVote всем узлам
Node A: "Мой term < 4, ещё не голосовал в term 4. Голосую за B."
Node C: "Голосую за B."
Node B: 3 голоса из 3 — большинство. Становится лидером term 4.
Node B: рассылает heartbeat.
Каждый узел может отдать только один голос в данном терме. Это гарантирует, что максимум один кандидат наберёт большинство.
Рандомизированный таймаут. Если все узлы используют одинаковый election timeout, они одновременно станут кандидатами, каждый проголосует за себя, и никто не наберёт большинства. Raft рандомизирует таймаут (например, 150–300ms): узел с меньшим таймаутом становится кандидатом первым и собирает голоса до того, как остальные успели начать свои выборы.
Правило голосования. Follower голосует за кандидата, только если лог кандидата не менее актуален, чем собственный. Актуальность определяется: сначала сравнивается term последней записи (больше = актуальнее), при равенстве — длина лога (длиннее = актуальнее). Это обеспечивает выбор лидера с наиболее полным логом.
Log replication
Node B стал лидером и начинает принимать запросы. Лидер не применяет запись сразу: сначала добавляет команду в свой лог, реплицирует на followers и ждёт подтверждения от кворума. Только после этого запись считается committed, лидер применяет её и отвечает клиенту.
Клиент Leader Follower 1 Follower 2
│ │ │ │
│── SET X=5 ───>│ │ │
│ │─AppendEntries>│ │
│ │─AppendEntries─────────────>│
│ │<──── ACK ─────│ │
│ │<──── ACK ──────────────────│
│ │ │ │
│ │ кворум получил│ │
│ │ → committed │ │
│ │ применяет X=5 │ │
│<──── OK ──────│ │ │
│ │─commit index─>│ │
│ │─commit index──────────────>│
│ │ применяют X=5 │
Каждая запись в логе содержит индекс (позицию), терм (в каком терме добавлена) и команду. Commit index указывает, до какой записи лог закоммичен.
Лог лидера:
┌───────┬───────┬───────┬───────┬───────┐
│ idx 1 │ idx 2 │ idx 3 │ idx 4 │ idx 5 │
│ t:1 │ t:1 │ t:2 │ t:3 │ t:3 │
│ X=1 │ Y=2 │ X=3 │ Z=1 │ Y=5 │
└───────┴───────┴───────┴───────┴───────┘
^
commit index = 4
(idx 5 ещё не закоммичена)
Log Matching Property. Raft гарантирует: если два лога содержат запись с одинаковым индексом и термом, то записи содержат одинаковую команду, и все предыдущие записи тоже одинаковы. Это обеспечивается механизмом AppendEntries: лидер отправляет индекс и терм предыдущей записи, follower проверяет совпадение прежде чем добавить новую.
Гарантии: committed записи не теряются
Клиент записал значение, оно закоммичено на двух из трёх узлов. Теперь лидер падает — потеряется ли эта запись?
Committed запись есть на большинстве узлов. Новый лидер должен получить голоса большинства. Любые два большинства пересекаются — хотя бы один узел с committed записью участвует в выборах. Правило голосования не позволит ему проголосовать за кандидата с менее актуальным логом. Лидером станет узел, который имеет все committed записи.
Кластер: 3 узла, кворум = 2
Запись committed → есть на 2 узлах
Новый лидер нужен → голоса 2 узлов
Любые 2 из 3 пересекаются → лидер имеет запись
Некоммиченные записи (на меньшинстве узлов) могут потеряться при смене лидера. Если лидер упал до того, как запись реплицирована на кворум, новый лидер может быть избран без узлов, имеющих эту запись — и перезаписать их логи своим.
Для клиента это означает: получил «OK» от лидера → запись committed и безопасна. Не получил ответ (таймаут, ошибка) → запись могла примениться, а могла нет. Нужна идемпотентность или retry с проверкой.
Где используется Raft
| Система | Зачем консенсус |
|---|---|
| etcd | Хранилище конфигурации Kubernetes |
| Consul | Service discovery, distributed KV |
| CockroachDB | Распределённая SQL БД (консенсус на каждый range данных) |
| TiKV | Distributed KV под TiDB |
| Patroni | Выбор лидера для PostgreSQL HA-кластера |
| Kafka (KRaft) | Выбор controller’а и partition leader без внешнего ZooKeeper |
Patroni: консенсус для PostgreSQL
PostgreSQL не имеет automatic failover из коробки. Если primary упал, кто-то должен решить, какая replica станет новым primary. Patroni — агент, работающий на каждом узле PostgreSQL, который решает эту задачу, делегируя консенсус внешней системе (etcd, Consul или ZooKeeper).
Primary держит lease в etcd — ключ с TTL, который нужно продлевать каждые N секунд, иначе он истекает и лидерство считается свободным. Если primary не обновил lease (упал), lease истекает. Replicas обнаруживают свободный lease, начинают выборы, и побеждает replica с наиболее актуальными данными. Победитель захватывает lease и выполняет pg_promote(), становясь новым primary. Что происходит на уровне PostgreSQL при промоутировании — выход из recovery, переключение WAL timeline — описано в репликации PostgreSQL.
Patroni не реализует Raft сам — он использует etcd, который внутри использует Raft. Это паттерн делегирования консенсуса: вместо того чтобы встраивать сложный алгоритм в каждую систему, консенсус выносится в специализированный сервис.
Что не покрыто
Paxos — более общий алгоритм, Raft — его специализация для replicated log. Multi-Raft — когда система использует много независимых групп консенсуса (CockroachDB делит данные на ranges, каждый range имеет свою Raft-группу). Byzantine fault tolerance (BFT) — класс алгоритмов для случаев, когда узлы могут не просто падать, а вести себя злонамеренно (основа блокчейнов). Membership changes — безопасное добавление и удаление узлов из кластера без остановки.
Sources
- Ongaro, Ousterhout, 2014, In Search of an Understandable Consensus Algorithm (Raft) — оригинальная статья Raft
- Lamport, 1998, The Part-Time Parliament (Paxos) — оригинальная статья Paxos
- Kleppmann, 2017, Designing Data-Intensive Applications, Chapter 9: Consistency and Consensus
- raft.github.io — визуализация Raft