Paxos: базовый и Multi-Paxos — как устроен протокол консенсуса

Прямой ответ

Paxos — протокол консенсуса, предложенный Лэмпортом: несколько узлов могут прийти к согласию по одному значению, даже если сообщения теряются, дублируются и переупорядочиваются, а часть узлов отказывает. Протокол не требует синхронных часов и не предполагает, что сеть доставляет сообщения вовремя — поэтому он остаётся эталоном корректности, от которого отталкиваются другие алгоритмы, включая Raft.

Роли (один узел может совмещать несколько):

• Proposer — предлагает значение.
• Acceptor — хранит состояние и голосует; множество акцепторов образует кворум.
• Learner — узнаёт принятое значение.

Базовый Paxos идёт в две фазы для одного «слота» (одного значения):

1. Фаза 1 (prepare). Пропозер выбирает уникальный номер предложения n и рассылает prepare(n). Акцептор обещает не принимать предложения с номером меньше n и возвращает уже принятое значение с наибольшим номером, если оно есть.
2. Фаза 2 (accept). Если пропозер получил ответы от кворума, он рассылает accept(n, v), где v — значение из ответа с наибольшим номером (либо своё, если никто ничего не принимал). Кворум ответов означает, что значение принято.

Два свойства обеспечивают безопасность:

• Safety. Никогда не принимается два разных значения; принятое значение нельзя изменить задним числом.
• Quorum intersection. Любые два кворума пересекаются хотя бы в одном акцепторе — именно это делает невозможным одновременное принятие конфликтующих значений.

Multi-Paxos. Запускать две фазы на каждую операцию дорого, поэтому на практике фазу 1 выполняют один раз для лидера, а затем для каждого нового слота сразу отправляют accept. Фактически это «стабильный лидер + последовательность слотов» — та же схема, которую Raft формализовал явно.

Практика: где встречается Paxos

Google Chubby и Spanner. Chubby использовал Paxos для выбора мастера и хранения метаданных; Spanner применяет Paxos внутри каждого сплита для репликации между зонами — это описано в статье о Spanner (см. источник в шапке).

ZooKeeper (ZAB). ZooKeeper формально использует ZAB — протокол атомарного broadcasts, близкий по духу к Multi-Paxos: лидер, эпохи, порядок транзакций.

Что учитывать при проектировании:

1. Кворум — большинство. Для пяти акцепторов кворум равен трём. Формула W + R > N из практики хранилищ родственна, но не тождественна: в Paxos пересечение кворумов нужно для безопасности записи, а в NWR-модели — для «склейки» версий при чтении, см. модель quorum NWR.
2. Уникальность номеров предложений. Номера должны быть глобально уникальны (обычно (уникальный id узла, счётчик)), иначе возможна «гонка» пропозеров и livelock.
3. Livelock. Два пропозера могут перебивать номера друг друга бесконечно. Лечится стабильным лидером — то есть переходом к Multi-Paxos с явными выборами лидера.
4. Логирование состояния акцептора. Обещание по номеру и принятое значение должны переживать перезапуск узла, то есть сбрасываться на диск до ответа. Пропуск fsync — классический способ получить две «принятые» версии значения.

Практический сценарий: сбой лидера во время записи

Контекст: пять акцепторов, стабильный лидер (Multi-Paxos), клиент отправляет команду в слот 1042.

1. Лидер падает после рассылки accept(1042, v) только двум акцепторам. Значение не принято — кворума нет.
2. Смена лидера. Новый лидер выбирается, выполняет фазу 1 для слота 1042 с бо́льшим номером предложения. Два акцептора возвращают (n, v), остальные — пустые ответы.
3. Повтор предложения. Новый лидер обязан предложить именно v, потому что оно уже встречалось в ответах. Команда клиента completes уже при новом лидере.
4. Клиент повторяет запрос. Если клиент не получил ответа, он повторяет операцию; здесь важна идемпотентность — подход описан в статье про идемпотентность API.
5. Проверка наблюдаемости. Метрика смены лидера и длительность фазы 1 должны быть на дашборде — как инструментировать приложение, см. метрики Prometheus.

Результат: значение не потеряно и не задвоено, несмотря на сбой лидера в середине записи. Вывод: безопасность Paxos держится на пересечении кворумов и правиле «предлагать уже встреченное значение», а не на скорости сети.

FAQ

Почему Paxos считается сложным? Сам алгоритм компактен, но в описании Лэмпорта опущены инженерные детали: как выбирать номера, как обрезать лог, как обрабатывать смену состава кластера (reconfiguration), как делать снапшоты. Реализации вынуждены достраивать эти части, и ошибки появляются именно там. Raft снял часть проблемы за счёт жёсткой структуры — см. Raft.

Нужен ли отдельный «мастер» в Paxos? Для базового Paxos — нет, любой узел может быть пропозером. Но без стабильного лидера вероятен livelock, поэтому промышленные реализации используют Multi-Paxos с лидером, который арендует роль на время и продлевает аренду.

Как Paxos связан с CAP-теоремой? Paxos относится к CP-системам: при разделении сети меньшинство отказывается принимать запись, сохраняя согласованность ценой доступности. Разбор компромисса — в статье про теорему CAP.

Можно ли использовать Paxos для репликации больших данных? Обычно нет: консенсус применяют к метаданным и порядку операций, а тяжёлые данные реплицируют отдельно и ссылаются на них из согласованного лога. Такой подход (согласованный лог + внешнее хранилище) позволяет не тащить гигабайты через кворум.

Источники: Lamport «Paxos Made Simple», Wikipedia (Paxos), Spanner paper (Google Research) — ссылки в шапке.