Алгоритмы консенсуса

1) Что такое консенсус и зачем он нужен

Консенсус — согласование одного и того же значения/последовательности значений между несколькими узлами при сбоях и задержках. Традиционно решается задача репликации состояния (State Machine Replication, SMR): есть детерминированная машина состояний и общий порядок операций.

• Консенсус (SMR): единый тотальный порядок команд → линейризуемое хранилище/реестр, метаданные кластера, транзакционные координаторы.
• Кворумные операции без тотального порядка (Dynamo-подобные, CRDT): допускают дивергенцию и последующее слияние; не заменяют консенсус там, где нужна глобальная сериализация.

2) Модель времени и отказов

2.1 Модель времени

Асинхронная сеть: задержки неограниченны; теорема FLP ⇒ невозможно гарантировать и safety, и liveness без дополнительных предположений.
Частично-синхронная (часто на практике): после неизвестного T система «ведет себя» синхронно — большинство алгоритмов (Raft, Paxos) полагаются именно на это.
Синхронная: жесткие тайм-лимиты на каналы (редко в проде, кроме специальных сетей/ПТП).

2.2 Модель отказов

Crash-fault tolerant (CFT): узлы могут падать/виснуть, но не ведут себя злонамеренно.
Byzantine-fault tolerant (BFT): узлы могут лгать/подделывать сообщения. Требуется 3f+1 узлов для толерантности к f византийским.

3) Свойства консенсуса

Safety (безопасность): непротиворечивость (два корректных узла не решат разные значения).
Liveness (живучесть): если сеть «здоровая», решение достигается.
Линеаризуемость (линейность): операции «видятся» как атомарные в едином порядке.
Долговечность: принятые решения не откатываются (защита журналом/кворумом).

4) Кворумы, большинство и пересечения

В CFT-мире классика: кворум > N/2. Записи и выборы лидера используют пересечение кворумов, поэтому две «валидные» операции не конфликтуют.
В BFT-мире: кворумы 2f+1 из 3f+1 обеспечивают пересечение минимум в f+1 честных узлов.

Правило пересечений: любой два кворума должны иметь ≥1 общий честный узел (CFT) или ≥f+1 (BFT).

5) Репликация состояния (журнал + применение)

• Снапшоты (срез состояния, после которого ранние записи можно удалить/скомпактировать).
• Компакцию журнала и лог-триим.
• Проверки детерминизма (одинаковая версия кода/конфигов).

6) Лидерские и нелидерские схемы

Лидерские (Raft, Multi-Paxos, ZAB): один лидер сериализует записи → проще ментально и операционно, лучше latency на стабильном лидере.
Безлидерные/мультилидерные (EPaxos, Caesar): больше параллелизма и толерантность к лидеру, но сложнее реализация и конфликт-решение; прибыль видна при малых конфликтностях команд.

7) Классические CFT-алгоритмы

7.1 Paxos / Multi-Paxos (и практики)

Идея: два фазы (prepare/propose), обещания акцепторов, мажоритарные кворумы. Multi-Paxos оставляет «стабильного лидера» и превращает операции в однораундовые (для новых записей) после «прогрева».

• Гибкая, но сложная для реализации модель.
• Ре-конфигурации через особые записи (joint consensus).
• На практике — библиотеки/движки (Chubby/Spanner-поколение).

7.2 Raft

Декомпозирован для обучаемости: выбор лидера, репликация логов, ре-конфигурация.

Election: случайные таймауты, голосование по термам; один лидер на срок.
AppendEntries: лидер стримит записи, следит за совпадением префикса (индекс/терм), коммит по мажоритарной фиксации.
Read-path: lease-reads (при сильном лидере) или read-index для линейных чтений.
Reconfig: «совместная конфигурация» (joint) — узлы голосуют в двух кластерах до перехода.

Плюсы: проще для разработки/дебага, сильные инварианты порядка. Минусы: лидер — точка давления.

7.3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: лидер широковещает транзакции, фаза восстановления, zxid (эпоха+индекс).
VRR: «виды» (views) с первичным репликантом, похож на Multi-Paxos по духу.

8) Нелидерские/мультилидерные CFT

8.1 EPaxos

Нет постоянного лидера: любой узел может инициировать команду.
Конфликтные команды получают частичный порядок; бесконфликтные — коммитятся в 1–2 RTT локально.
Выигрыш в геораспределении при низкой конфликтности, но сложные коды зависимостей/графов.

8.2 Caesar, Mencius

Вариации, оптимизирующие задержки/балансировку и работу в WAN.

9) BFT-алгоритмы и PoS-семейство

9.1 PBFT (Practical BFT)

Три фазы (pre-prepare/prepare/commit), требует 3f+1 узлов.
Низкая латентность на локальных сетях, дорог многошаговостью и O(N²) сообщениями.

9.2 Tendermint (BFT-PoS стиль)

Раунды с proposal и двумя голосованиями (prevote/precommit).
Детерминированный валидатор-предложитель, тайм-ауты, частичная синхронность.
Хорош для permissioned/PoS-сетей с десятками/сотнями валидаторов.

9.3 HotStuff (и производные)

Унифицирована трехфазная схема в «пакеты» с кворумными сертификатами (QC).
Линейная сложность коммуникаций, поддержка пакетирования и параллельной пайплайнизации, удобна для реализаций в блокчейнах (например, Diem/Move-экосистема).
С пороговыми подписями (threshold signatures) уменьшается трафик.

9.4 PoW/накопительный консенсус (вкратце)

Не BFT в строгом смысле, а вероятностная конвергенция (цепочка с наибольшей работой). Достоинства: простота/открытость; недостатки: энергия, ~секунд-минуты до финальности.

10) Чтения: линейные, последовательные и кэшированные

Линейные чтения: лидер с активным lease или через read-index (Raft) → подтверждение через кворум.
Последовательные: можно читать с любого узла, но без гарантий свежести.
Follower reads: допустимы при слабых требованиях; для кэшей — ok.

11) Ре-конфигурация (смена состава кластера)

Требует двух перекрывающихся конфигураций (joint consensus): любые коммиты проходят кворумы обеих конфигураций → без «дырок».
Добавляйте/удаляйте по одному, соблюдайте размер кворума.
Перенос лидерства (leadership transfer) снижает паузы.

12) Производительность и тюнинг

12.1 Задержки

Лидерские алгоритмы: 1 RTT на запись (при стабильном лидере) + репликация.
Геораспределение: WAN RTT доминирует → используйте локальные регионы + кросс-региональную реplikацию или EPaxos/HotStuff-подходы.

12.2 Пропускная

Batching (группировка команд), параллельные AppendEntries, пейдж-кеш журнала, параллельное применение (когда операции коммутируют).
Диски: NVMe/Журнал на отдельном устройстве, `O_DIRECT`/AIO, большой `fsync`-интервал с ограничениями SLA (компромисс durability/latency).

12.3 Хвосты p99

Избегайте горячих узлов (лидер постоянно один): периодическая ротация или read-offload на фолловеров.
Контролируйте GC-паузы (JVM/Go), пины CPU, NUMA.

13) География и топологии

1 регион, 3 зоны: классический CFT-кластер (N=3/5).
2 регионы: избегайте — не получается надежный кворум при разделении 1–1.
3+ регионов: лидер в «середине» или безлидерные алгоритмы; возможны региональные прокси/локальные фронты с асинхронным журналом.

14) Практические вопросы эксплуатации

14.1 Снапшоты и восстановление

Порог по размеру журнала/количеству операций.
Передача снапшота новым узлам; проверка контрольных сумм.

14.2 Мониторинг

Лидерство: кто лидер, сколько сроков (term/epoch) сменилось.
Лаги: `append_latency`, `commit_index - applied_index`.

Кворум-здоровье: «живы ли большинство/2f+1?»

Размер журнала/скорость компакции, очередь снапшотов.
Для BFT: доля голосов, отвал подписантов, задержки QC.

14.3 Безопасность/согласованность кода

Версионность протокола на проводе, миграции с совместимостью журналов.
Fencing-токены на внешних эффектах (см. «Распределенные блокировки»): лидерский срок (term) передавать в CRON/джобы.

15) Анти-паттерны

Ставить консенсус «ради моды» там, где хватает одной СУБД или кворумных чтений без сериализации.
Смешивать CP и AP без четких границ (CAP) → непредсказуемый UX.
Переоценивать PoW/PoS для корпоративных задач с десятками узлов (сложно/дорого).
Игнорировать ре-конфигурацию и «пересекающиеся кворумы» при изменении состава.
Отсутствие read-barrier (lease/read-index) → «грязные» чтения.
Запускать 2-узловые кластеры (нет большинства).
Недооценка дисков и fsync: «в памяти все летает» — до первой перезагрузки.

16) Чек-лист выбора

1. Модель отказов: CFT (краши) или BFT (злонамеренные)?
2. География: один регион/три зоны или WAN? RTT решает.
3. Семантика чтений: нужны ли линейные чтения? Lease/read-index/фолловер-риды.
4. Нагрузка: ожидания по p50/p99, throughput; нужна ли мульти-лидерность.
5. Операционная сложность: библиотека/готовый движок (etcd/ZK/Consul/Raft-либы) vs собственная реализация.
6. Реконфигурация: частая? Нужен joint consensus и инструменты миграций.
7. Интеграции: внешние побочные эффекты — есть ли fencing по epoch/term?
8. Безопасность: аутентификация узлов, шифрование канала, контроль версий протокола.
9. Тест-плейбуки: partition, GC-стоп, лидера kill, slow disk, clock skew.
10. Наблюдаемость: метрики лидера/лагов/журнала и алерты настроены.

17) Мини-справочник: когда что брать

etcd/Raft-кластер для конфигураций/блокировок/координации внутри DC.
ZooKeeper/ZAB для сервисов, уже завязанных на ZK (старые стеки, очереди, лидерство).
Multi-Paxos через готовый сервис/библиотеку в узкоспециализированных системах.
EPaxos при геораспределении и низкой конфликтности команд.
Tendermint/HotStuff для permissioned сетей/PoS-лейера с десятками-сотнями валидаторов и требованиями к финальности.
Dynamo-подобные/CRDT когда консенсус не нужен, а важна доступность/масштаб с последующим слиянием.

18) Примеры интерфейсов (псевдо)

18.1 Коммит записи (Raft-стиль)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18.2 Read-index для линейного чтения (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18.3 Совместная конфигурация

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18.4 BFT (HotStuff-приближенно)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

Q: Почему бы не использовать два узла и тай-брейкер?
A: Два узла без третьего арбитра не дают кворума при разделении. Нужно ≥3 (CFT) или 3f+1 (BFT).

Q: Чем Raft «проще» Paxos?
A: Четкая декомпозиция, понятные инварианты лога и конфигурации; легче реализовать и сопровождать.

Q: Как читать быстро, не нагружая лидера?
A: Follower-reads (последовательные) для некритичных, либо lease-reads/read-index для линейных; кэшируйте.

Q: Что убивает p99?
A: WAN-RTT, дисковые fsync, GC-стопы, перегретый лидер, большие снапшоты в «час пик».

Q: Нужен ли консенсус для кэша/каталога?
A: Если достаточно eventual consistency — нет. Если требуются транзакционные инварианты — да.

20) Итоги

Консенсус — инструмент для строгой согласованности и упорядочивания. Выбирайте алгоритм, исходя из модели отказов и географии; обеспечьте кворумные пересечения, корректную ре-конфигурацию, линейные чтения там, где это критично, и наблюдаемость. Не забывайте о fencing для внешних эффектов, снапшотах и дисциплине журналов. Тогда репликация состояния будет предсказуемой, а инциденты — редкими и понятными.