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

Задача консенсуса

В распределённой системе несколько процессов (узлов) должны согласовать единое значение, даже если часть узлов выходит из строя или сообщения теряются в сети. Это фундаментальная задача распределённых вычислений, без решения которой невозможно построить надёжные базы данных, системы координации и реплицированные сервисы.

Формально алгоритм консенсуса должен обеспечить три свойства:

Свойство	Описание
Agreement (согласие)	Все корректные узлы принимают одно и то же значение
Validity (валидность)	Принятое значение было предложено одним из узлов
Termination (завершимость)	Каждый корректный узел рано или поздно примет значение

Почему это важно

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

• Реплицированных баз данных — все реплики должны содержать одинаковые данные
• Распределённых блокировок — ZooKeeper, etcd используют консенсус для координации
• Blockchain — каждый блок — результат консенсуса между участниками сети
• Реплицированных автоматов (Replicated State Machine) — если все узлы применяют одни и те же команды в одном порядке, они приходят к одинаковому состоянию

Результат невозможности FLP

В 1985 году Fischer, Lynch и Paterson доказали, что в полностью асинхронной системе (без ограничений на время доставки сообщений) детерминистический консенсус невозможен даже при отказе одного узла (FLP Impossibility).

На практике это ограничение обходят с помощью:

• Рандомизации — случайные таймауты (как в Raft)
• Частичной синхронности — предположение, что сеть «достаточно быстрая» большую часть времени
• Детекторов отказов — механизмы, определяющие, жив ли узел

Краткая история

1988  Viewstamped Replication (Oki, Liskov)
1989  Paxos придуман Лэмпортом (опубликован в 1998)
1999  PBFT — первый практичный BFT-алгоритм (Castro, Liskov)
2001  «Paxos Made Simple» — доступное изложение
2011  Zab — консенсус для ZooKeeper
2013  EPaxos — Paxos без лидера с оптимальной задержкой
2014  Raft — «понятный» алгоритм консенсуса
2018  Tendermint — BFT-консенсус для блокчейнов
2019  HotStuff — линейная сложность BFT

Реализованные в симуляторе

В данном проекте реализованы пять алгоритмов консенсуса:

• Raft — алгоритм с лидером, выборами лидера и репликацией лога. В симуляторе реализован как наиболее строгая учебная модель.
• Basic Paxos — алгоритм без лидера, где любой узел может предложить значение. В симуляторе реализован как slot-based учебная модель классического Paxos.
• Multi-Paxos — оптимизация Basic Paxos со стабильным лидером. В учебной модели использует отдельные слоты и сокращает steady-state латентность с 2 RTT до 1 RTT.
• Zab — протокол atomic broadcast из Apache ZooKeeper. В учебной модели видны три явные фазы: Election → Synchronization → Broadcast.
• EPaxos — Paxos без лидера с низкой латентностью. Это более упрощённая учебная модель: fast path виден как коммит за 1 RTT без лидера; при конфликтах используется slow path на 2 RTT.

Также см. список известных, но не реализованных алгоритмов.

Попробуйте сами

Откройте симулятор и сравните поведение алгоритмов бок о бок — до трёх панелей одновременно.