Протокол консенсуса Paxos¶

Протокол консенсуса Paxos — это семейство алгоритмов, предназначенных для достижения консенсуса в распределённых системах, работающих в условиях ненадёжной сети и возможных сбоев узлов. Paxos гарантирует, что даже при наличии отказов (вплоть до определённого порога) все корректно работающие узлы системы согласуют единое значение, что является фундаментальной задачей для построения отказоустойчивых систем, таких как базы данных, блокчейн-платформы и системы управления конфигурациями. Алгоритм был впервые описан Лесли Лэмпортом в 1989 году и формально опубликован в 1998 году, а его название происходит от вымышленного греческого острова, на котором, по замыслу автора, действовала гипотетическая законодательная система, иллюстрирующая принципы работы протокола.

¶История

Протокол Paxos был разработан американским учёным в области информатики Лесли Лэмпортом (Leslie Lamport). В 1989 году он написал статью «The Part-Time Parliament», в которой описал алгоритм, используя метафору парламента на вымышленном острове Paxos. Однако из-за необычного стиля изложения и сложности для восприятия статья была первоначально отвергнута научным сообществом. Лэмпорт переписал её в более традиционном академическом стиле, и в 1998 году она была опубликована в журнале ACM Transactions on Computer Systems. С тех пор Paxos стал одним из наиболее влиятельных и широко используемых алгоритмов консенсуса, хотя его практическая реализация часто считается сложной.

¶Основные понятия

¶Участники (Roles)

В классическом Paxos выделяются три типа участников, хотя один и тот же узел может выполнять несколько ролей:

• Прокуроры (Proposers) — узлы, которые инициируют предложение значения (например, новое состояние системы). Они отправляют запросы на согласование.
• Акцепторы (Acceptors) — узлы, которые принимают или отклоняют предложения. Акцепторы хранят состояние и голосуют за предложения. Для достижения консенсуса требуется, чтобы большинство (кворум) акцепторов приняло одно и то же значение.
• Ученики (Learners) — узлы, которые не участвуют в голосовании, но получают информацию о том, какое значение было согласовано. Они могут быть клиентами или репликами, которым нужно знать результат.

¶Условия работы

Paxos предполагает, что система может сталкиваться со следующими типами сбоев:

• Отказ узла (crash failure) — узел может внезапно прекратить работу, но не может вести себя злонамеренно (византийские сбои не рассматриваются).
• Потеря сообщений — сообщения могут задерживаться, теряться или дублироваться, но не могут быть искажены.
• Асинхронность — нет предположений о времени доставки сообщений, хотя для обеспечения прогресса алгоритм полагается на частичную синхронность (например, тайм-ауты).

¶Алгоритм

Paxos работает в несколько фаз, каждая из которых состоит из двух этапов. Основная идея заключается в том, что прокурор сначала пытается получить от акцепторов обещание не принимать предложения с меньшим номером, а затем отправляет значение, которое должно быть принято.

¶Фаза 1: Подготовка (Prepare)

1. Прокурор выбирает уникальный номер предложения n (обычно увеличивающийся с каждым новым предложением) и отправляет сообщение Prepare(n) всем акцепторам (или их большинству).
2. Акцептор при получении Prepare(n):

• Если n больше, чем номер любого предыдущего обещания, которое он дал, он обещает не принимать никаких предложений с номером меньше n.
• Он отправляет прокурору ответ Promise(n, v), где v — это значение, которое он ранее принял для самого высокого номера предложения (если такое есть). Если акцептор ещё не принимал никаких предложений, он отправляет Promise(n, null).

¶Фаза 2: Принятие (Accept)

1. Прокурор после получения ответов от большинства акцепторов (кворума) анализирует их:

• Если хотя бы один акцептор вернул значение v (с каким-то номером), прокурор выбирает значение с самым высоким номером из всех полученных.
• Если все ответы содержат null, прокурор может выбрать любое значение (например, своё собственное).

1. Прокурор отправляет сообщение Accept(n, v) всем акцепторам, где n — тот же номер, а v — выбранное значение.
2. Акцептор при получении Accept(n, v):

• Если он не дал обещания на более высокий номер (т.е. n не меньше его текущего обещания), он принимает значение v и отправляет сообщение Accepted(n, v) всем ученикам (или прокурору, который затем распространяет информацию).
• В противном случае он игнорирует запрос.

¶Фаза 3: Обучение (Learn)

Ученики собирают сообщения Accepted от акцепторов. Как только они получают такие сообщения от большинства акцепторов, они узнают, что консенсус достигнут, и могут применять значение v. В некоторых реализациях прокурор сам сообщает ученикам о результате.

¶Гарантии и свойства

Paxos гарантирует два ключевых свойства:

• Безопасность (Safety) — согласованное значение никогда не будет отменено или изменено; все корректные узлы в конечном итоге согласуют одно и то же значение.
• Живучесть (Liveness) — при условии, что большинство узлов работают и могут общаться, консенсус будет достигнут за конечное время (хотя в асинхронных системах это не гарантируется без дополнительных предположений).

¶Разновидности и модификации

Существует несколько модификаций Paxos, адаптированных под разные сценарии:

• Multi-Paxos — расширение для последовательного согласования нескольких значений (например, записей в логе). В этом режиме после выбора лидера (прокурора) фаза 1 выполняется только один раз, а затем все последующие предложения обрабатываются только через фазу 2, что значительно повышает производительность.
• Fast Paxos — вариант, в котором прокурор может отправлять значение напрямую акцепторам без предварительной фазы подготовки, что сокращает задержки, но требует большего кворума.
• Cheap Paxos — оптимизация, при которой часть акцепторов может быть временно отключена для экономии ресурсов.
• Byzantine Paxos — модификация, устойчивая к византийским сбоям (злонамеренным узлам), но требующая более сложных протоколов.

¶Применение

Протокол Paxos лежит в основе многих промышленных систем, требующих отказоустойчивости и согласованности:

• Google Chubby — система распределённых блокировок, использующая Paxos для выбора лидера и хранения конфигураций.
• Apache ZooKeeper — хотя официально использует протокол Zab, его архитектура во многом схожа с Paxos.
• Microsoft Azure — некоторые сервисы, такие как Azure Storage, используют Paxos для обеспечения согласованности данных.
• CockroachDB — распределённая база данных, использующая Multi-Paxos для репликации.
• Blockchain-платформы — некоторые частные блокчейны (например, Hyperledger Fabric) используют Paxos для достижения консенсуса среди доверенных узлов.

¶Критика и сложность

Несмотря на теоретическую элегантность, Paxos часто критикуют за сложность практической реализации. Основные трудности:

• Сложность понимания — алгоритм труден для восприятия даже опытными разработчиками, что приводит к ошибкам при реализации.
• Проблема лидера — в Multi-Paxos требуется выбор лидера, что может быть узким местом и приводить к задержкам при сбоях.
• Производительность — в классическом варианте Paxos требует 3-4 сетевых обмена на одно предложение, что может быть медленным для высоконагруженных систем.

В ответ на эти сложности были разработаны альтернативные алгоритмы, такие как Raft, который ставит своей целью упрощение понимания и реализации, сохраняя при этом те же гарантии безопасности.

¶Источники

1. Lamport, L. «The Part-Time Parliament». ACM Transactions on Computer Systems, 1998.
2. Lamport, L. «Paxos Made Simple». ACM SIGACT News, 2001.
3. Chandra, T. D., Griesemer, R., & Redstone, J. «Paxos Made Live: An Engineering Perspective». Proceedings of the 26th ACM Symposium on Principles of Distributed Computing, 2007.
4. Ongaro, D., & Ousterhout, J. «In Search of an Understandable Consensus Algorithm». USENIX Annual Technical Conference, 2014.