Consensus Landscape

Appearance

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

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

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

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

СвойствоОписание
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 — leaderless Paxos с оптимальной задержкой
2014  Raft — «понятный» алгоритм консенсуса
2018  Tendermint — BFT-консенсус для блокчейнов
2019  HotStuff — линейная сложность BFT

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

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

  • Raft — leader-based алгоритм с выборами лидера и репликацией лога. Разработан для простоты понимания.
  • Basic Paxos — leaderless алгоритм, где любой узел может предложить значение. Исторически первый алгоритм консенсуса.
  • Multi-Paxos — оптимизация Basic Paxos со стабильным лидером. Пропускает фазу Prepare после выборов, сокращая латентность с 2 RTT до 1 RTT.
  • Zab — протокол atomic broadcast из Apache ZooKeeper. Три явные фазы: Election → Synchronization → Broadcast.
  • EPaxos — leaderless Paxos с оптимальной латентностью. Коммит за 1 RTT (fast path) без лидера; 2 RTT при конфликтах (slow path).

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

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

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