Алгоритм Паксос

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

Протоколы решения задачи консенсуса — базовый элемент автоматного подхода в распределённых вычислениях, предложенного Лесли Лампортом и исследованного далее Ф. Шнайдером.

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

Семейство протоколов Паксос было создано и описано в 1990 г., но было опубликовано в научной литературе только в 1998 г. Однако, исследования на данную тематику начались задолго до реализации протокола. Например, автоматная репликация, подход к программированию на основе модели виртуальной синхронизации, предложенной в 1985 г.

Семейство протоколов Паксос рассматривает варианты решения задачи консенсуса в зависимости от количества вычислителей, количества задержек для получения результата, активности участников, количества отправленных сообщений и типов отказов. Результат отказоустойчивого консенсуса не определён (то есть, при определённых условиях вычислители не смогут прийти к согласию), однако, гарантируется безопасность (консистентность), а условия, при которых консенсус невозможен, очень редки.

О названии

Алгоритм назван в честь вымышленной системы права греческого острова Паксос.

Свойства безопасности и живучести

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

• Нетривиальность — решение может быть принято только из заранее заданного множества исходов;
• Консистентность — принятое решение совпадает у всех вычислителей, в нём участвовавших;
• Живучесть(C,L) — Если было предложено решение C, то рано или поздно вычислитель L примет какое-либо решение (при условии наличия достаточного количества работающих вычислителей).

Предусловия

Для того чтобы упростить представление алгоритма Паксос, опишем следующие определения и предусловия.

Вычислители

• Процессоры работают на произвольной скорости.
• Процессоры могут испытывать сбои.
• Процессоры со стабильным хранилищем могут повторно присоединиться к протоколу после сбоев (в соответствии с моделью сбоя аварийного восстановления).
• Процессоры не вступают в сговор, не лгут или иным образом пытаются подорвать протокол. (То есть византийских провалов не происходит. См. Византийский Паксос для решения, которое допускает сбои, возникающие в результате произвольного/вредоносного поведения процессов.)

Сеть

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

Число процессоров

Как правило, алгоритм консенсуса может добиться прогресса используя 2F+1 процессоров, несмотря на одновременный сбой любых F процессоров. Однако, используя перенастройку, можно использовать протокол, который выдерживает любое количество полных сбоев до тех пор, пока не произойдет сбой не более F процессоров одновременно.

Роли

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

Клиент

Клиент выдает запрос распределенной системе и ожидает ответа. Например, запрос на запись в файл на распределенном файловом сервере.

Акцептор (избиратель)

Акцепторы выступают в качестве отказоустойчивой «памяти» протокола. Они собираются в группы, называемые кворумами. Любое сообщение, отправленное акцептору, должно быть отправлено в кворум акцепторов. Любое сообщение, полученное от акцептора игнорируется до тех пор, пока не будет получена копия от каждого акцептора в кворуме.

Заявитель (предлагающий)

Заявитель защищает запрос клиента, пытаясь убедить акцепторов согласовать этот запрос, и действует в качестве координатора для продвижения протокола в случае возникновения конфликтов.

Ученик

Ученики выступают в качестве фактора репликации протокола. После согласования клиентского запроса акцепторами учащийся может предпринять действия (то есть выполнить запрос и отправить ответ клиенту). Для улучшения доступности обработки можно добавить дополнительных учеников.

Лидер

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

Кворум

Кворумом является большинство из всех членов кластера.

Q = N/2 + 1

К примеру, если в кластере имеется 6 участников, кворумом будет 4.

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

Кворумы определяются как подмножества множества акцепторов таким образом, чтобы любые два подмножества (то есть любые два кворума) имели по крайней мере один общий элемент. Как правило, кворум является любым большинством участвующих акцепторов. Например, рассмотрим множество акцепторов {А,B,С,D}, кворум большинства для которого будут три любых акцептора: {А,B,С}, {А,С,D}, {А,В,D} или {B,С,D}. В более общем плане акцепторам и кворуму могут быть присвоены произвольные положительные веса, определяемым как любое подмножество акцепторов с суммарным весом, превышающим половину общего веса всех акцепторов.

Предложенное число и согласованное значение

Каждая попытка определения согласованного значения v осуществляется с помощью предложений, которые могут быть приняты или не приняты акцепторами. Каждое предложение уникально пронумеровано для данного заявителя. Значение, соответствующее пронумерованному предложению может быть вычислено в рамках выполнения протокола Паксос, но не обязательно.

Остановимый паксос

Остановимый конечный автомат — тот, который может остановить работу по определённой команде. Такие автоматы используются, например, для реализации изменения конфигурации в реплицированном автомате: реконфигурируемый автомат реализуется как последовательность остановимых автоматов, каждый работает в своей конфигурации. Остановимый паксос реализует реплицируемый остановимый конечный автомат.

Промышленное использование

• Данное семейство алгоритмов используется в распределённой службе блокировок Chubby компании Google, используемой, в свою очередь, в BigTable.
• Microsoft использует паксос в своей системе автоматического управления кластерами.

См. также

• Алгоритм Raft
• Алгоритм консенсуса Чандры-Тоэг
• Виртуальная синхронизация
• Конечный автомат

Ссылки

• Leslie Lamport, Dahlia Malkhi, Lidong Zhou. Stoppable Paxos (англ.) (PDF). Microsoft Research (28 апреля 2008). Дата обращения: 26 августа 2012. Архивировано 26 октября 2012 года.