Открыть сервис
Главная → Блог → Протокол Paxos

Протокол Paxos

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

История

Протокол Paxos был впервые описан Лесли Лэмпортом в 1989 году в статье «The Part-Time Parliament». Однако из-за необычной метафоры (древнегреческий парламент на острове Паксос) и сложности изложения статья долгое время оставалась малоизвестной. Лэмпорт переработал и упростил описание, и в 1998 году опубликовал более доступную версию под названием «Paxos Made Simple». Именно эта работа получила широкое признание и стала стандартным справочным материалом по протоколу.

Изначально Paxos был разработан для обеспечения отказоустойчивости в распределённых системах, где узлы могут выходить из строя, а сообщения могут теряться или задерживаться. В отличие от более ранних алгоритмов, Paxos обеспечивает корректную работу даже при наличии так называемых «византийских» отказов (злонамеренного поведения узлов), хотя классическая версия протокола не рассчитана на этот тип сбоев.

Основные понятия и роли

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

  • Предлагающий (Proposer) — узел, который инициирует процесс голосования и предлагает значение.
  • Акцептор (Acceptor) — узел, который принимает или отклоняет предложенные значения. Акцепторы хранят состояние голосования.
  • Учащийся (Learner) — узел, который узнаёт о согласованном значении и может его использовать. В реальных системах все узлы часто являются и акцепторами, и учащимися.

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

Алгоритм работы

Протокол Paxos состоит из двух фаз, которые выполняются последовательно для каждого раунда голосования. Раунды нумеруются уникальными возрастающими номерами.

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

  1. Предложение (Prepare): Предлагающий (Proposer) выбирает новый номер раунда n и отправляет сообщение Prepare(n) всем акцепторам (или кворуму).
  2. Ответ (Promise): Каждый акцептор, получивший Prepare(n), проверяет, не получал ли он уже запрос с номером раунда больше или равным n. Если нет, акцептор даёт обещание (promise):
  • Не принимать предложения с номером раунда меньше n.
  • Отправить предлагающему ответ, содержащий:
  • Последнее принятое значение (если такое было) и номер раунда, в котором оно было принято.
  • Если акцептор ещё не принимал никаких значений, ответ будет пустым.

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

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

  1. Предложение (Accept Request): После получения ответов от кворума акцепторов, предлагающий анализирует их. Он выбирает значение, которое будет предлагать:
  • Если среди ответов есть значения, которые были приняты ранее (в более старых раундах), предлагающий выбирает значение с самым высоким номером раунда.
  • Если все ответы пусты (ни один акцептор не принимал значений), предлагающий может предложить своё собственное значение.
  • Затем предлагающий отправляет сообщение Accept(n, value) всем акцепторам (или кворуму).
  1. Принятие (Accepted): Акцептор, получивший Accept(n, value), проверяет, не нарушает ли это его обещание. Он принимает значение, если:
  • Он не дал обещание на раунд с номером больше n.
  • Если обещание дано, акцептор игнорирует запрос.
  • Если условие выполнено, акцептор фиксирует принятое значение и отправляет сообщение Accepted(n, value) всем учащимся (Learners).

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

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

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

Протокол Paxos обеспечивает два ключевых свойства безопасности:

  • Согласованность (Safety): Никогда не будет принято два разных значения. Это гарантируется пересечением кворумов: если одно значение принято кворумом, любой другой кворум, пытающийся принять другое значение, будет содержать хотя бы один акцептор, который уже принял первое значение и сообщит об этом.
  • Жизнеспособность (Liveness): При условии, что большинство узлов работает и может обмениваться сообщениями, протокол в конечном итоге достигнет консенсуса. Однако в условиях нестабильной сети или при одновременной работе нескольких предлагающих протокол может бесконечно долго не завершаться (проблема «livеlock»).

Paxos не гарантирует терминальность (termination) — он не гарантирует, что консенсус будет достигнут за конечное время. Это фундаментальное ограничение для любых распределённых протоколов консенсуса в асинхронных системах.

Варианты и модификации

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

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

Применение

Протокол Paxos и его варианты лежат в основе многих критически важных распределённых систем:

Критика и ограничения

Несмотря на свою теоретическую обоснованность, Paxos часто критикуется за сложность понимания и реализации. Многие разработчики отмечают, что даже после прочтения «Paxos Made Simple» остаются неясными детали, особенно касающиеся обработки граничных случаев и обеспечения жизнеспособности. Альтернативные протоколы, такие как Raft, были разработаны специально для упрощения понимания и реализации, сохраняя при этом те же гарантии безопасности. Raft стал более популярным в индустрии благодаря своей понятной модели и детальной документации.

Источники

  • Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems.
  • Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News.
  • Chandra, T. D., & Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM.
  • Van Renesse, R., & Guerraoui, R. (2010). Replicating for performance: Case studies. Communications of the ACM.
  • Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm. USENIX ATC.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы