Зачем
Consensus — это когда N узлов договариваются об одном значении несмотря на сетевые задержки, partitions и крэши. Без него невозможно построить ничего серьёзно распределённого: ни strongly-consistent БД, ни leader election, ни distributed locks, ни replicated state machines. Каждый раз, когда Kubernetes говорит «один pod scheduled на этот node, не два», за этим стоит etcd с Raft. Каждый раз, когда CockroachDB подтверждает commit транзакции через 3 региона, за этим стоят 5 Raft-групп, каждая сделала кворум.
Проблема в том, что простого решения нет. FLP-теорема (Fischer-Lynch-Paterson, 1985) формально доказала: в полностью асинхронной системе с хотя бы одним возможным крэшем — детерминистичный консенсус невозможен. Все реальные алгоритмы (Paxos, Raft, Zab, PBFT) — это инженерные компромиссы вокруг этой теоремы. Они работают потому, что предполагают partial synchrony: «обычно сеть быстрая, иногда тормозит, но не вечно». Когда это допущение нарушается — система или встаёт (CP), или жертвует safety (AP).
Mental model
Большинство (quorum) определяет истину. Меньшинство отказывается работать, чтобы не врать.
Запомните три вещи, и 80% поведения консенсуса станет очевидным:
- Quorum = N/2 + 1. Любое решение требует подтверждения от большинства. На 5 нодах нужно 3, на 7 нужно 4. Это математическая гарантия: две группы по большинству пересекаются хотя бы в одном узле — а этот узел не даст принять конфликтующие решения.
- Минорная сторона при partition теряет write-доступность. Если кластер разорвало 2 vs 3, сторона из двух нод не сможет собрать кворум и зависнет на write-операциях. Это не баг — это safety: они не знают, что делает большая сторона, и не имеют права отвечать клиенту «закоммичено».
- Лидер — оптимизация, не суть. Raft и Paxos с лидером быстрее (один round-trip вместо двух), но если лидер умер — выборы. Leaderless варианты (EPaxos, Generalized Paxos) убирают bottleneck, но усложняют код в разы.
Дополнительная интуиция: консенсус — это медленно. Каждое решение = минимум 1 round-trip к большинству реплик. Внутри одного датацентра это 1-3 мс, между регионами — 50-200 мс. Поэтому Spanner стоит дорого и поэтому никто не делает консенсус на каждый чих — батчат, шардят, кэшируют.
Что показывает диаграмма
5-узловой кластер: один Leader и четыре Follower-а, плюс Client. Между лидером и followers — линки AppendEntries (так Raft называет репликацию журнала). Между followers — линки RequestVote (используются при выборах). Client пишет/читает только через лидера.
Пять сценариев анимации показывают разные режимы работы:
- Happy path quorum — нормальный write: Client → Leader, Leader → 4 followers, 2 ack-а превращают итог в 3/5 (с самим лидером) = quorum достигнут, commit, ответ клиенту. Оставшиеся followers догонят асинхронно.
- Network partition (minority side) — кластер разорвало на {leader, follower-1} и {follower-2, follower-3, follower-4}. Старый лидер на minority side не может собрать кворум (только 2/5) и зависает. Majority side выбирает нового лидера и продолжает работать. Safety сохранена — два конфликтующих writes невозможны.
- Split vote — лидер умер, все followers одновременно стали кандидатами, каждый проголосовал за себя, никто не получил большинство. Решается randomized backoff (election timeout 150-300 мс с разбросом) — кто проснулся первым, тот собирает голоса.
- FLP impossibility — иллюстрация фундаментальной проблемы: в async-системе невозможно отличить «нода крэшнулась» от «нода медленная» от «сеть лагает». Реальные алгоритмы обходят это через timeouts (partial synchrony).
- Paxos vs Raft vs Zab — landscape алгоритмов: Paxos фундаментален но сложен, Raft проектировался ради понятности, Zab — Atomic Broadcast для ZooKeeper, PBFT — для byzantine.
Сценарии
Happy path (3/5 quorum). Лидер получает write x=5 от клиента, реплицирует на followers через AppendEntries. Как только 2 follower-а ответили ack (вместе с самим лидером это 3/5 = большинство) — запись считается committed, клиент получает 200 OK. Это критически важный момент: клиенту НЕ нужно ждать ack от всех 5 нод. Если ждать всех, система потеряет fault tolerance — одна медленная нода затормозит всё.
Partition с minority stuck. Сеть разделилась. Старый лидер на стороне меньшинства честно пытается committee write — но получает ack только от 1 follower-а (минус сам себя = 2/5). Кворум не собран, write висит. Это правильное поведение: minority не имеет права отвечать клиенту «закоммичено», потому что majority side могла избрать нового лидера и принимать новые writes. После heal partition старый лидер увидит более высокий term и сложит полномочия (step down).
Split vote и randomized backoff. Лидер умер, все followers одновременно подняли election timer и стартанули election. Каждый проголосовал за себя — итог 1/5 у каждого кандидата. Никто не выиграл. Без рандомизации это livelock: они снова все одновременно стартанут следующий round. Raft решает через random election timeout 150-300 мс — кто проснулся первым, успевает разослать VoteRequest до того, как просыпаются остальные. Практическое следствие: при первом восстановлении после крэша ожидайте 200-500 мс unavailability.
FLP в реальности. Когда timeout сработал, лидер не знает: follower крэшнул, перегружен, или просто сеть подвисла? Он считает его failed и продолжает работу с оставшимися. Когда «failed» нода возвращается — она видит более высокий term, понимает что отстала, и догоняет журнал. False positive (зря посчитали failed) обходится одним лишним election.
Algorithms landscape. Paxos — оригинал, любая нода может стать proposer, два phase (prepare/accept), Multi-Paxos для streams. Raft — leader-based, один лидер, log replication, явные роли. Zab — ZooKeeper Atomic Broadcast, гарантирует total order broadcast. EPaxos — leaderless, один round-trip в good case, но сложен. PBFT — для byzantine (malicious) нод.
Trade-offs (ADR)
Контекст. Распределённые системы должны принимать одинаковые решения на N узлах при network delays, partitions, crashes. Без consensus невозможны strongly-consistent БД, leader election, distributed locks, replicated state machines.
Решение. Использовать consensus algorithm (Raft по умолчанию для новых систем, Paxos в legacy Google-стеке, Zab в ZooKeeper-экосистеме). Properties: Agreement (все honest nodes выбирают одно значение), Validity (выбранное было кем-то предложено), Termination (алгоритм заканчивается — формально невозможен в pure async, но достижим в partial synchrony).
Последствия.
- Цена в latency. 1 round-trip к большинству реплик на каждое решение. Внутри DC — 1-3 мс, cross-region — 50-200 мс. Для globally-distributed strong consistency это bottleneck.
- Цена в throughput. Лидер — single point of serialization. Multi-Raft (Spanner, CockroachDB) шардят кластер на тысячи Raft-групп, чтобы параллелить.
- Цена в fault tolerance. N=3 терпит 1 failure, N=5 терпит 2, N=7 терпит 3. Чётные N не дают выигрыша (quorum=N/2+1), поэтому всегда нечётное.
- Цена в operational complexity. Members membership change (добавить/убрать ноду) сам по себе требует консенсуса (joint consensus в Raft). Backups + restore меняют election state. Disk corruption на лидере может «отравить» followers.
Альтернативы (rejected).
- Leaderless replication с last-write-wins (Cassandra ONE). Быстрее, проще, но теряете strong consistency. Подходит только если конфликты допустимы.
- 2PC / 3PC (two/three-phase commit). Не tolerant к failures координатора, не масштабируется. Используется в XA-транзакциях, но это уже legacy.
- CRDTs. Отличный выбор для счётчиков, sets, maps — но не для произвольной state machine. Не заменяет consensus, дополняет.
Реальные системы
| Система | Алгоритм | Где применяется |
|---|
| etcd | Raft | Kubernetes control plane, конфигурация |
| Consul | Raft | Service discovery, distributed config |
| CockroachDB | Raft (per range) | Distributed SQL, NewSQL |
| TiKV / TiDB | Raft | Distributed KV под TiDB |
| Kafka (KRaft mode) | Raft | Метаданные кластера (заменили ZooKeeper) |
| MongoDB replica sets | Raft-like (custom) | Election + log replication |
| ZooKeeper | Zab | Координация Hadoop/HBase/Kafka (legacy) |
| Google Spanner | Paxos | Globally-distributed SQL с TrueTime |
| Google Chubby | Paxos | Distributed lock service (внутренний) |
| HashiCorp Vault | Raft (опционально) | Secrets storage HA |
Заметьте паттерн: Raft победил для нового кода. Paxos остался в legacy и в академических работах. PBFT и его наследники (HotStuff, Tendermint) используются в permissioned blockchain (Hyperledger Fabric, Cosmos).
Anti-patterns
- «Use consensus everywhere». Консенсус на каждый запрос убивает latency и throughput. Используйте только для критических решений: метаданные, leader election, конфигурация, sequencer. Данные пользователей чаще всего хорошо живут на eventually-consistent storage с per-key Raft там, где нужно (CockroachDB ranges).
- Quorum = N (требовать ack от всех). Это убивает fault tolerance — одна медленная нода тормозит всё. Никогда так не делайте; майнинг paranoia здесь не помогает, а вредит.
- Чётное N. N=4 даёт quorum=3, что то же самое, что у N=3. Лишняя нода = лишние деньги, без выигрыша. Всегда используйте нечётное (3, 5, 7).
- Один большой Raft group для всех данных. Lock contention, single leader bottleneck, журнал растёт бесконечно. Шардьте: CockroachDB делает Raft-группу на каждый 64MB range, etcd рекомендует держать DB < 8 GB на один cluster.
- Long election timeout. Если election timeout = 30 секунд, после крэша лидера у вас 30 секунд unavailability. Сделайте 150-300 мс (Raft default) — это даёт быстрый failover ценой редких false elections.
- Single-region кластер для global system. 5 нод в одном DC = вы потеряете всё при пожаре DC. 5 нод в 5 регионах = 200 мс на каждый write. Компромисс — 3 региона, по 2 ноды + 1 witness (Spanner-style).
- Игнорировать disk fsync на лидере. Raft требует, чтобы log записывался durably ДО ack. Если fsync отключён ради throughput — теряете safety при крэше с включенной репликой.
Когда НЕ использовать
- Если задача допускает eventual consistency. Лайки, view counters, feed timeline, рекомендации — здесь AP-системы (Cassandra, DynamoDB) дешевле и быстрее на порядки. CAP-теорема ваш друг: ::concept{slug="cap-theorem"}.
- Если N=1. Один узел не нуждается в консенсусе. Это очевидно, но люди ставят etcd-cluster из одной ноды и потом удивляются, почему «упало вместе с диском».
- Если данные read-mostly с rare writes. Используйте read replicas + simple leader-election для writes, не нужно полный Raft на каждый запрос. Например, DNS: master + slaves, zone transfer на NOTIFY.
- Если latency critical и можно жить со stale data. Quorum reads/writes дают линеаризуемость, но добавляют 50+ мс на cross-region. Если ваш SLO 10 мс — рассмотрите local-region reads с bounded staleness.
- Для координации внутри одного процесса. Mutex, channel, atomic operations — это shared-memory concurrency, не distributed consensus. Не путайте.
- Для byzantine окружения с ненадёжными участниками. Raft/Paxos предполагают crash failures, не malicious. Если ноды могут врать (permissionless blockchain, multi-party computation) — нужен PBFT/HotStuff/PoW/PoS, которые в 10-100 раз дороже.
Дальше читать
- ::concept{slug="cap-theorem"} — фундаментальный trade-off CP vs AP при partition
- ::concept{slug="leader-election"} — детальный механизм выборов в Raft
- ::concept{slug="quorum-reads-writes"} — quorum-математика, R+W>N, Dynamo-style
- ::concept{slug="raft"} — алгоритм Raft пошагово
- ::concept{slug="paxos"} — классический Paxos и Multi-Paxos
- ::concept{slug="zab"} — ZooKeeper Atomic Broadcast
- ::concept{slug="byzantine-fault-tolerance"} — PBFT и защита от malicious nodes
- ::concept{slug="linearizability-deep"} — формальная модель сильнейшей consistency
- ::case{slug="kafka-broker-internals"} — KRaft mode в Kafka, как заменили ZooKeeper
- ::case{slug="distributed-lock-service"} — Chubby/etcd locks на базе консенсуса
Книги и paper-ы.