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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Семейство протоколов Паксос было создано и описано в 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 осуществляется с помощью предложений, которые могут быть приняты или не приняты акцепторами. Каждое предложение уникально пронумеровано для данного заявителя. Значение, соответствующее пронумерованному предложению может быть вычислено в рамках выполнения протокола Паксос, но не обязательно.

Примеры реализации[править | править код]

Простой паксос[править | править код]

Мульти-паксос[править | править код]

Оптимизации[править | править код]

Дешёвый паксос[править | править код]

Сокращённый паксос[править | править код]

Обобщённый паксос[править | править код]

Византийский паксос[править | править код]

Остановимый паксос[править | править код]

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

Промышленное использование[править | править код]

См. также[править | править код]

Примечания[править | править код]

  1. Pease, Marshall; Robert Shostak, Leslie Lamport (April 1980). “Reaching Agreement in the Presence of Faults”. Journal of the Association for Computing Machinery 27 (2). Проверено 2007-02-02.
  2. Lamport, Leslie (July 1978). “Time, Clocks and the Ordering of Events in a Distributed System”. Communications of the ACM 21 (7): 558–565. DOI:10.1145/359545.359563. Проверено 2007-02-02.
  3. Schneider, Fred (1990). “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial”. ACM Computing Surveys 22: 299. DOI:10.1145/98163.98167.

Ссылки[править | править код]

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