Paxos¶

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

¶История

Протокол Paxos был впервые описан Лэмпортом в 1989 году в технической записке «The Part-Time Parliament», но из-за необычного стиля изложения (с использованием аллегории о парламенте на острове Парос) статья была отклонена редакторами журналов. В 1998 году работа была опубликована в журнале ACM Transactions on Computer Systems. Позднее, в 2001 году, Лэмпорт выпустил более доступное объяснение «Paxos Made Simple», которое стало стандартным введением в алгоритм.

Первоначально Paxos не получил широкого практического применения из-за сложности реализации. Однако в середине 2000-х годов, с ростом популярности крупномасштабных распределённых систем (например, в Google, Amazon, Microsoft), интерес к Paxos возрос. Он лёг в основу таких систем, как Google Chubby (распределённая блокировка), Apache ZooKeeper (использует ZAB — вариант Paxos), а также ряда решений для репликации баз данных.

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

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

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

Ключевые свойства протокола:

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

¶Алгоритм: фазы

Классический Paxos (Basic Paxos) состоит из двух фаз: фазы подготовки (Prepare) и фазы принятия (Accept).

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

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

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

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

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

• Если среди полученных Promise есть хотя бы одно с v_last (то есть акцептор уже принимал какое-то значение), прокурор обязан предложить именно это значение (с наибольшим n_last). Это гарантирует, что если консенсус уже был достигнут, новое предложение не сможет его изменить.
• Если ни один акцептор не сообщил о принятом значении, прокурор может предложить любое своё значение (например, новое).

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

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

Консенсус считается достигнутым, когда большинство акцепторов приняло одно и то же значение.

¶Варианты Paxos

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

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

¶Применение

Paxos и его варианты широко применяются в распределённых системах, где требуется высокая надёжность и согласованность данных:

• Распределённые базы данных: репликация данных между несколькими серверами (например, в Google Spanner, Amazon DynamoDB — частично, CockroachDB).
• Системы координации: Apache ZooKeeper, etcd, Consul — используют Paxos (или его варианты) для выбора лидера и синхронизации конфигурации.
• Распределённые блокировки: Google Chubby — система распределённой блокировки на основе Paxos.
• Блокчейн и криптовалюты: некоторые проекты (например, Stellar, Hyperledger Fabric) используют византийские варианты Paxos для достижения консенсуса между узлами.
• Облачные сервисы: Microsoft Azure, Amazon Web Services (AWS) используют Paxos для обеспечения согласованности в своих распределённых хранилищах (например, Azure Cosmos DB, AWS DynamoDB).

¶Критика и альтернативы

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

• Сложность: даже базовый алгоритм требует тщательного управления номерами предложений и состояниями акцепторов. Ошибки в реализации могут привести к нарушению безопасности.
• Производительность: классический Paxos требует двух сетевых обходов (round trips) для каждого решения, что может быть медленным в высоконагруженных системах.
• Отсутствие гарантий живости: в случае сбоя лидера или сетевых проблем консенсус может быть заблокирован (хотя на практике используются тайм-ауты и механизмы перевыборов).

Основная альтернатива Paxos — алгоритм Raft, разработанный в 2013 году Диего Онгаро и Джоном Остерхаутом. Raft предлагает более понятную декомпозицию на подзадачи (выбор лидера, репликация лога, безопасность) и легче реализуется, сохраняя при те же гарантии безопасности. Raft стал более популярным в индустрии (например, используется в etcd, Consul, TiDB), хотя Paxos остаётся фундаментальным алгоритмом.

¶Интересные факты

• Название «Paxos» было выбрано Лэмпортом из-за аллегории с парламентом на греческом острове, где депутаты могли приходить и уходить в любое время, а сообщения доставлялись с задержками.
• Первоначальная статья «The Part-Time Parliament» была написана в юмористическом стиле, что, по иронии, помешало её публикации в серьёзном журнале.
• В 2012 году Лесли Лэмпорт получил премию Тьюринга, в том числе за вклад в разработку распределённых алгоритмов, включая Paxos.
• Несмотря на широкое использование Paxos в промышленности, многие инженеры признают, что реализация корректного Paxos «с нуля» — сложная задача; поэтому часто используются проверенные библиотеки (например, libpaxos, LogCabin).

¶Источники

• Leslie Lamport. «The Part-Time Parliament». ACM Transactions on Computer Systems, 1998.
• Leslie Lamport. «Paxos Made Simple». ACM SIGACT News, 2001.
• Diego Ongaro, John Ousterhout. «In Search of an Understandable Consensus Algorithm (Extended Version)». USENIX ATC, 2014.
• «Paxos (computer science)» — статья в англоязычной Википедии.
• «Paxos Protocol» — документация Apache ZooKeeper.
• «Consensus Algorithms: Paxos and Raft» — материалы курсов по распределённым системам (MIT 6.824, Stanford CS 244B).