Алгоритм Paxos¶

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

¶История

Разработка алгоритма Paxos была мотивирована необходимостью создания надёжного протокола для распределённых систем, которые должны работать корректно в присутствии сбоев. В 1980-х годах Лесли Лэмпорт, работая в Xerox PARC, исследовал проблему достижения консенсуса в асинхронных системах. В 1985 году Фишер, Линч и Патерсон доказали теорему FLP, которая утверждает, что в чисто асинхронной системе с возможностью отказа одного узла невозможно гарантировать достижение консенсуса за конечное время. Лэмпорт, однако, показал, что консенсус возможен в практических системах, если допустить, что узлы могут работать в «частично синхронной» модели, где время отклика не предсказуемо, но в конечном итоге стабильно.

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

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

¶Консенсус

Консенсус в распределённой системе означает, что все корректные узлы (те, которые не отказали) соглашаются на одном и том же значении, и это значение было предложено одним из узлов. Алгоритм Paxos решает задачу консенсуса для одного значения (single-decree Paxos). Для принятия последовательности значений (например, записей в журнале операций) используется Multi-Paxos, который запускает несколько экземпляров базового протокола.

¶Роли узлов

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

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

¶Раунды и номера раундов

Протокол работает в раундах (rounds), каждый из которых имеет уникальный номер. Номера раундов строго возрастают и обычно состоят из двух частей: номера узла-прокурора и счётчика. Это гарантирует, что даже если несколько прокуроров одновременно начинают раунды, номера не будут конфликтовать.

¶Описание алгоритма (Single-Decree Paxos)

Алгоритм состоит из двух фаз: фазы подготовки (prepare) и фазы принятия (accept). Каждая фаза включает в себя отправку сообщений и получение ответов от кворума акцепторов.

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

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

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

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

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

• Прокурор выбирает значение для предложения: если среди полученных ответов есть хотя бы один с непустым last_accepted_value, то прокурор выбирает значение с наибольшим last_accepted_round (это гарантирует, что ранее принятое значение не будет перезаписано). Если все ответы пусты, прокурор может выбрать любое значение (например, своё собственное).
• Прокурор отправляет сообщение Accept(n, value) всем акцепторам (или кворуму).

1. Каждый акцептор при получении Accept(n, value):

• Если n больше или равно promised_round, то акцептор принимает предложение, сохраняет (n, value) и отвечает Accepted(n, value).
• Если n меньше promised_round, акцептор игнорирует запрос.

¶Завершение

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

¶Гарантии алгоритма

Алгоритм Paxos гарантирует три свойства:

1. Безопасность (Safety): только одно значение может быть принято, и это значение было предложено. Никогда не будет принято два разных значения.
2. Живучесть (Liveness): если большинство акцепторов корректны и сеть работает достаточно стабильно, то в конечном итоге будет принято значение (при условии, что прокуроры не конфликтуют бесконечно).
3. Отказоустойчивость: алгоритм работает при отказе до (N-1)/2 акцепторов, где N — общее число акцепторов.

¶Multi-Paxos

Для принятия последовательности значений (например, записей в распределённом журнале) используется Multi-Paxos. В этом варианте выбирается лидер (один прокурор), который выполняет фазу подготовки только один раз для первого раунда, а затем для каждого последующего значения использует только фазу принятия. Это значительно повышает производительность, так как фаза подготовки (самая дорогая) выполняется редко. Multi-Paxos является основой для многих систем, таких как Google Chubby и Apache ZooKeeper.

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

• Сложность реализации: несмотря на кажущуюся простоту, реализация Paxos на практике сложна из-за необходимости обработки множества граничных случаев (сбои сети, потеря сообщений, дублирование).
• Производительность: в базовом варианте требуется два раунда обмена сообщениями, что может быть медленным. Multi-Paxos улучшает ситуацию, но всё равно требует лидера.
• Проблема лидера: если несколько прокуроров одновременно пытаются стать лидерами, может возникнуть «конфликт раундов», приводящий к бесконечной серии перевыборов (хотя это редко на практике).
• Альтернативы: существуют более простые или быстрые алгоритмы, такие как Raft, который был разработан как более понятная альтернатива Paxos. Raft использует термин «лидер» и имеет более простую структуру с разделением на этапы выборов, репликации и безопасности.

¶Применение

• Системы управления базами данных: Google Spanner, CockroachDB, TiDB.
• Сервисы координации: Apache ZooKeeper (использует ZAB — вариант Paxos), etcd (использует Raft, но концептуально близок).
• Файловые системы: Google File System (GFS) использует Paxos для координации метаданных.
• Блокчейн: некоторые консенсусные протоколы, такие как Tendermint, используют идеи Paxos.

¶Источники

• Lamport, L. (1998). «The Part-Time Parliament». ACM Transactions on Computer Systems.
• Lamport, L. (2001). «Paxos Made Simple». ACM SIGACT News.
• Chandra, T. D., Griesemer, R., & Redstone, J. (2007). «Paxos Made Live: An Engineering Perspective». ACM Symposium on Principles of Distributed Computing.
• Van Renesse, R., & Altinbuken, D. (2015). «Paxos Made Moderately Complex». ACM Computing Surveys.