Распределённый консенсус

Задача согласования одного значения (или последовательности значений) между несколькими независимыми процессами, когда они могут общаться только отправкой сообщений, а сами сообщения могут задерживаться или процессы могут падать.

Почему это сложно

В однопроцессной системе "принять решение" тривиально: один процесс выбирает значение, и на этом всё. Когда процессов несколько, требуется соблюсти три свойства:

Согласие (agreement) - все исправные процессы принимают одно и то же значение
Обоснованность (validity) - принятое значение действительно было предложено одним из процессов (без выдумок на ровном месте)
Завершаемость (termination) - каждый исправный процесс рано или поздно принимает решение

Сложность возникает из-за неопределённости. Если вы отправляете сообщение и не получаете ответа, невозможно понять, упал ли другой процесс или просто медленно отвечает. Именно эта неоднозначность делает консенсус фундаментально сложным в асинхронных системах - см. flp-impossibility.

Где он применяется

Консенсус - это базовый примитив в основе множества систем, которыми пользуются не задумываясь:

Базы данных: реплицируемые базы данных (Postgres с потоковой репликацией, CockroachDB, Spanner) используют консенсус для синхронизации реплик. При записи строки реплики должны договориться, что запись произошла и в каком порядке. Алгоритмы репликации - primary-backup, репликация конечных автоматов (state-machine replication), атомарный broadcast - разбираются глава за главой в replication-theory-and-practice.
Распределённые блокировки: сервисы вроде etcd и ZooKeeper предоставляют блокировки и выбор лидера, а это замаскированные задачи консенсуса. Наличие консенсуса под капотом не делает хранилище CP по умолчанию: в stop-calling-databases-cp-or-ap показано, что чтения в ZooKeeper не линеаризуемы, если перед ними не вызвать sync.
Блокчейны: вся суть блокчейна сводится к тому, чтобы заставить недоверяющие друг другу узлы договориться о журнале транзакций. Bitcoin использует proof-of-work как вероятностный механизм консенсуса.
Многоагентные системы LLM: когда параллельные LLM-агенты должны выдать совместимый код по одному и тому же промпту, они сталкиваются с задачей консенсуса - см. log-distributed-llms.

Классические алгоритмы

Paxos (Lamport, 1989) - первый корректный алгоритм консенсуса для асинхронных систем с отказами вида crash-stop. Печально известен сложностью для понимания и реализации. Большинство реальных систем используют его производные. Исходные статьи с комментариями тех, кому довелось их реализовывать, собраны в concurrency-works-of-leslie-lamport - их стоит почитать, когда пересказы из вторых рук перестанут отвечать на накопившиеся вопросы.

Raft (Ongaro & Ousterhout, 2014) - спроектирован с упором на понятность. Разделяет консенсус на выбор лидера, репликацию лога и безопасность (safety). Используется в etcd, Consul и множестве инструментов вокруг Kubernetes.

PBFT (Castro & Liskov, 1999) - Practical Byzantine Fault Tolerance. Работает, когда до 1/3 узлов проявляют византийское поведение. Обходится намного дороже алгоритмов, рассчитанных только на падения, так как каждому узлу приходится общаться с каждым другим узлом.

QuePaxa (Tennage, Băsescu et al., 2023) - асинхронный консенсус, который отказывается от лидера и подбора таймаутов, от которых зависит Raft, ценой большего числа сообщений на каждое решение. В meerkat-introduction описано, как Cloudflare строит на нём глобальный сервис консенсуса, и это как раз тот случай, где компромисс окупается: в глобальной сети (WAN) обнаружение сбоев по таймаутам - ровно то допущение, на которое нельзя полагаться.

Пространство компромиссов

Результат flp-impossibility доказывает, что в асинхронной системе невозможно одновременно получить safety, liveness и отказоустойчивость. Реальные системы справляются с этим, ослабляя одно из требований:

Ослабить liveness: Paxos/Raft могут зависать во время сетевых разделений, но никогда не примут неверного решения (этот вариант выбирает большинство баз данных)
Ослабить safety: некоторые системы допускают временную несогласованность и сводят данные позже (согласованность в конечном счёте, CRDT)
Добавить допущения о синхронности: использовать таймауты для обнаружения сбоев, смирившись с тем, что система сломается, если временные допущения не подтвердятся