Паксос (информатика)

Paxos — это семейство протоколов для достижения консенсуса в сети ненадежных или ошибочных процессоров. Консенсус – это процесс согласования одного результата среди группы участников. Эта проблема усложняется, когда участники или их коммуникации могут испытывать сбои. ^[1]

Протоколы консенсуса являются основой подхода репликации конечных автоматов к распределенным вычислениям , как предложил Лесли Лэмпорт. ^[2] и исследован Фредом Шнайдером . ^[3] Репликация конечного автомата — это метод преобразования алгоритма в отказоустойчивую распределенную реализацию. Специальные методы могут оставить нерешенными важные случаи сбоев. Принципиальный подход, предложенный Lamport et al. обеспечивает безопасное рассмотрение всех дел.

Протокол Паксоса был впервые представлен в 1989 году и назван в честь вымышленной системы законодательного консенсуса, используемой на острове Паксос в Греции, где Лэмпорт писал, что парламент должен функционировать, «хотя законодатели постоянно входили и выходили из парламентской палаты». ^[4] Позже она была опубликована в виде журнальной статьи в 1998 году. ^[5]

Семейство протоколов Paxos включает в себя спектр компромиссов между количеством процессоров, количеством задержек сообщений до получения согласованного значения, уровнем активности отдельных участников, количеством отправленных сообщений и типами сбоев. Хотя ни один детерминированный отказоустойчивый протокол консенсуса не может гарантировать прогресс в асинхронной сети ( результат доказан в статье Фишера , Линча и Патерсона) . ^[6]), Паксос гарантирует безопасность (последовательность), и трудно спровоцировать условия, которые могли бы помешать ему добиться прогресса.

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

История

Эта тема предшествует протоколу. В 1988 году Линч , Дворк и Стокмейер продемонстрировали ^[7] разрешимость консенсуса в широком семействе «частично синхронных» систем. Paxos имеет большое сходство с протоколом, используемым для согласования в «репликации с метками просмотра», впервые опубликованным Оки и Лисковым в 1988 году, в контексте распределенных транзакций. ^[8] Несмотря на эту предыдущую работу, Paxos предложил особенно элегантный формализм и включил одно из первых доказательств безопасности отказоустойчивого протокола распределенного консенсуса.

Реконфигурируемые конечные автоматы тесно связаны с предыдущими работами над надежными протоколами групповой многоадресной рассылки, которые поддерживают динамическое членство в группах, например, виртуально с работой Бирмана в 1985 и 1987 годах над синхронным gbcast. ^[9] протокол. Однако gbcast необычно обеспечивает надежность и устраняет сбои разделения. Большинству надежных протоколов многоадресной рассылки не хватает этих свойств, которые необходимы для реализации модели репликации конечного автомата. Этот момент развит в статье Лампорта , Малхи и Чжоу. ^[10]

Протоколы Paxos являются членами теоретического класса решений проблемы, формализованных как единое соглашение с аварийными сбоями. Нижние оценки этой задачи были доказаны Кейдаром и Шраером. ^[11] Верно, ^[12] Программная библиотека C++ для репликации конечных автоматов в облачном масштабе предлагает протокол Paxos, интегрированный с самоуправляемым виртуально синхронным членством. Этот протокол соответствует границам оптимальности Кейдара и Шраера и эффективно сопоставляется с оборудованием современного удаленного центра обработки данных DMA (RDMA) (но использует TCP, если RDMA недоступен).

Предположения

Чтобы упростить представление Paxos, следующие предположения и определения сделаны явными. Методы расширения области применения известны в литературе и не рассматриваются в данной статье.

Процессоры

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

Сеть

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

Количество процессоров

В общем, алгоритм консенсуса может добиться прогресса, используя $n=2F+1$ процессоров, несмотря на одновременный выход из строя любого $F$ процессоры: ^[13] другими словами, количество исправных процессов должно быть строго больше числа неисправных процессов. Однако, используя реконфигурацию, можно использовать протокол, который выдерживает любое количество общих отказов, если одновременно происходит не более F сбоев. Для протоколов Paxos эти реконфигурации можно обрабатывать как отдельные конфигурации . ^[14]

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

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

Валидность (или нетривиальность ): Только предложенные значения могут быть выбраны и изучены. ^[15]
Согласие (или последовательность , или безопасность ): Никакие два разных ученика не могут усвоить разные ценности (или не может быть более одной определенной ценности). ^[15]^[16]
Прекращение (или жизнеспособность): Если было предложено значение C, то в конечном итоге учащийся L выучит какое-то значение (если достаточное количество процессоров останется исправным). ^[16]

Обратите внимание, что Paxos не гарантированно завершает работу и, следовательно, не имеет свойства жизнеспособности. Это подтверждается результатом невозможности Фишера-Линча-Патерсона (FLP). ^[6] в котором говорится, что протокол согласованности может иметь только два параметра: безопасность , живучесть и отказоустойчивость . Поскольку целью Paxos является обеспечение отказоустойчивости и гарантия безопасности, он не может также гарантировать работоспособность.

Типичное развертывание

В большинстве развертываний Paxos каждый участвующий процесс выполняет три роли; Предлагающий, Принимающий и Учащийся. ^[17] Это значительно снижает сложность сообщения, не жертвуя при этом корректностью:

В Paxos клиенты отправляют команды лидеру. При нормальной работе лидер получает команду клиента, присваивает ей новый номер команды. $i$ , а затем начинается $i$ ^й экземпляр алгоритма консенсуса путем отправки сообщений набору принимающих процессов. ^[16]

При слиянии ролей протокол «сворачивается» в эффективное развертывание в стиле клиент-мастер-реплика, типичное для сообщества баз данных. ^[18] Преимущество протоколов Paxos (в том числе реализаций со слитыми ролями) — гарантия его свойств безопасности .

Поток сообщений типичной реализации описан в разделе Multi-Paxos .

Базовый Паксос

Этот протокол является самым простым из семейства Paxos. Каждый «экземпляр» (или «выполнение») базового протокола Paxos определяет одно выходное значение. Протокол продолжается в несколько раундов. Успешный раунд состоит из двух фаз: фаза 1 (которая разделена на части a и b ) и фаза 2 (которая разделена на части a и b ). Ниже смотрите описание этапов. Помните, что мы предполагаем асинхронную модель, поэтому, например, процессор может находиться в одной фазе, а другой процессор — в другой.

Этап 1

Этап 1а: Подготовка

Предлагающий создает сообщение , которое мы называем Подготовка . Сообщение идентифицируется уникальным номером n , который должен быть больше любого числа, ранее использованного в сообщении «Подготовка» этим Предлагающим. Обратите внимание, что n — это не то значение, которое следует предложить; это просто уникальный идентификатор исходного сообщения Предлагающего. Фактически, сообщение «Подготовка» не обязательно должно содержать предлагаемое значение (часто обозначаемое v ).

Предлагающий выбирает как минимум кворум принимающих . ^{[ как? ]} сообщение «Подготовка», содержащее n и отправляет им . Предлагающий не должен инициировать Paxos, если он не может связаться с достаточным количеством Принимающих, чтобы составить Кворум.

Фаза 1б: Обещание

Принимающие ждут сообщения о подготовке от любого из предлагающих. Когда Получатель получает сообщение «Подготовка», он должен проверить идентификационный номер n этого сообщения. Есть два случая:

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

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

Этап 2

Этап 2а: принять

Если предлагающий получает обещания от кворума принимающих, ему необходимо установить значение v для своего предложения. Если какие-либо акцепторы ранее приняли какое-либо предложение, то они отправят свои значения предлагающему, который теперь должен установить значение своего предложения v равным значению, связанному с наибольшим номером предложения, сообщенным акцепторами, назовем это з . Если ни один из Принимающих не принял предложение до этого момента, Предлагающий может выбрать значение, которое он изначально хотел предложить, скажем, x . ^[19]

Предлагающий отправляет «Принять» сообщение (n, v) кворуму принимающих с выбранным значением для его предложения v и номером предложения n (который совпадает с номером, содержащимся в сообщении «Подготовка» , ранее отправленном Акцепторы). Таким образом, сообщение Accept имеет вид либо (n, v=z), либо, в случае, если ни один из Acceptors ранее не принял значение, (n, v=x) .

Это сообщение «Принять » следует интерпретировать как «запрос», например «Примите это предложение, пожалуйста!».

Этап 2б: принято

Если Акцептор получает сообщение Принять (n, v) от Предлагающего, он должен принять его тогда и только тогда, когда он еще не пообещал (на этапе 1b протокола Paxos) рассматривать только предложения, имеющие идентификатор больше n. .

Если Принимающая сторона еще не пообещала (на этапе 1b) рассматривать только предложения, имеющие идентификатор больше n , он должен зарегистрировать значение v (только что полученного сообщения Принять ) как принятое значение (Протокола) и отправить сообщение Принято сообщение для Предлагающего и каждого Учащегося (которым обычно могут быть сами Предлагающие. Учащиеся узнают решенное значение ТОЛЬКО ПОСЛЕ получения Принятых сообщений от большинства принимающих, что означает, НЕ после получения только ПЕРВОГО сообщения о принятии).

В противном случае он может игнорировать сообщение или запрос Accept.

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

Когда раунды терпят неудачу

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

Paxos можно использовать для выбора лидера

Обратите внимание, что Предлагающий на Паксосе может предложить «Я лидер» (или, например, «Предлагающий X является лидером»). ^[20] Благодаря согласию и гарантиям действительности Paxos, в случае принятия Кворумом, предлагающий теперь считается лидером для всех остальных узлов. Это удовлетворяет потребности выборов лидера. ^[21] потому что есть один узел, считающий, что он является лидером, и один узел, который всегда известен как лидер.

Графическое представление потока сообщений в базовом Paxos

На следующих диаграммах представлены несколько случаев/ситуаций применения протокола Basic Paxos. Некоторые случаи показывают, как протокол Basic Paxos справляется с выходом из строя определенных (избыточных) компонентов распределенной системы.

Обратите внимание, что значения, возвращаемые в сообщении Promise , являются «нулевыми» при первом предложении (поскольку ни один акцептор не принял значение ранее в этом раунде).

Базовый Паксос без сбоев

На диаграмме ниже присутствует 1 клиент, 1 предлагающий, 3 принимающих (т. е. размер кворума равен 3) и 2 обучающихся (представлены двумя вертикальными линиями). На этой диаграмме представлен случай успешного первого раунда (т. е. ни один процесс в сети не завершился сбоем).

Здесь V — последний из (Va, Vb, Vc).

Случаи ошибок в базовом Paxos

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

Базовый Paxos, когда акцептор терпит неудачу

На следующей диаграмме один из акцепторов в кворуме выходит из строя, поэтому размер кворума становится равным 2. В этом случае базовый протокол Paxos по-прежнему работает успешно.

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

Базовый Paxos, когда резервный ученик терпит неудачу

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

Client Proposer         Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |

Базовый Paxos, когда предлагающий терпит неудачу

В этом случае Предлагающий терпит неудачу после предложения значения, но до достижения соглашения. В частности, происходит сбой в середине сообщения Accept, поэтому значение получает только один Acceptor из кворума. Тем временем избирается новый лидер (предложитель) (но это не показано подробно). Обратите внимание, что в данном случае раундов 2 (раунды идут вертикально, сверху вниз).

Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{V, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Базовый Паксос, когда конфликтуют несколько предлагающих

Самый сложный случай — это когда несколько Предлагающих считают себя Лидерами. Например, текущий лидер может потерпеть неудачу и позже восстановиться, но другие Предлагающие уже повторно выбрали нового лидера. Выздоровевший лидер еще этого не усвоил и пытается начать один раунд в конфликте с нынешним лидером. На схеме ниже показаны 4 неудачных раунда, но их может быть больше (как подсказано внизу схемы).

Client   Proposer       Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null,null,null})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows last number was 1)
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 2, denied
   |      X------------>|->|->|       |  |  Prepare(2)
   |      |<------------X--X--X       |  |  Nack(2)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 3
   |      X------------>|->|->|       |  |  Prepare(3)
   |      |<------------X--X--X       |  |  Promise(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(2,Va)
   |      |  |<---------X--X--X       |  |  Nack(3)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries 4
   |      |  X--------->|->|->|       |  |  Prepare(4)
   |      |  |<---------X--X--X       |  |  Promise(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(3,Vb)
   |      |<------------X--X--X       |  |  Nack(4)
   |      |  |          |  |  |       |  |  ... and so on ...

Базовый Paxos, где акцептор принимает два разных значения

В следующем случае один Предлагающий достигает принятия значения V1 одним Принимающим, прежде чем потерпит неудачу. Новый Предлагающий подготавливает Принимающих, которые никогда не принимали V1, что позволяет ему предложить V2. Затем V2 принимается всеми Акцепторами, включая того, который первоначально принял V1.

Proposer    Acceptor     Learner
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Prepare(1)
 |<---------X--X--X       |  |  Promise(1,{null,null,null})
 x--------->|  |  |       |  |  Accept!(1,V1)
 |  |       X------------>|->|  Accepted(1,V1)
 !  |       |  |  |       |  |  !! FAIL !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Prepare(2)
    |<---------X--X       |  |  Promise(2,{null,null})
    X------>|->|->|       |  |  Accept!(2,V2)
    |<------X--X--X------>|->|  Accepted(2,V2)
    |       |  |  |       |  |

Базовый Paxos, где большинства с несколькими идентификаторами недостаточно.

В следующем случае один Предлагающий достигает принятия значения V1 одного Принимателя, прежде чем потерпит неудачу. Новый Предлагающий подготавливает Принимающих, которые никогда не принимали V1, что позволяет ему предложить V2. Этот Предлагающий может заставить одного Принимателя принять V2, прежде чем он потерпит неудачу. Новый Предлагающий находит большинство, включающее Принимающего, принявшего V1, и должен предложить его. Предлагающему удается убедить двух акцепторов принять его, прежде чем он потерпит неудачу. На данный момент три акцептора приняли версию V1, но с разными идентификаторами. Наконец, новый предлагающий подготавливает большинство, которое не увидело самый большой принятый идентификатор. Значение, связанное с самым большим идентификатором в этом большинстве, — это V2, поэтому оно должно предлагаться. Затем этот Предлагающий заставляет всех Принимающих принять V2, достигая консенсуса.

  Proposer           Acceptor        Learner
 |  |  |  |       |  |  |  |  |       |  |
 X--------------->|->|->|->|->|       |  |  Prepare(1)
 |<---------------X--X--X--X--X       |  |  Promise(1,{null,null,null,null,null})
 x--------------->|  |  |  |  |       |  |  Accept!(1,V1)
 |  |  |  |       X------------------>|->|  Accepted(1,V1)
 !  |  |  |       |  |  |  |  |       |  |  !! FAIL !!
    |  |  |       |  |  |  |  |       |  |
    X--------------->|->|->|->|       |  |  Prepare(2)
    |<---------------X--X--X--X       |  |  Promise(2,{null,null,null,null})
    X--------------->|  |  |  |       |  |  Accept!(2,V2)
    |  |  |       |  X--------------->|->|  Accepted(2,V2)
    !  |  |       |  |  |  |  |       |  |  !! FAIL !!
       |  |       |  |  |  |  |       |  | 
       X--------->|---->|->|->|       |  |  Prepare(3)
       |<---------X-----X--X--X       |  |  Promise(3,{V1,null,null,null})
       X--------------->|->|  |       |  |  Accept!(3,V1)
       |  |       |  |  X--X--------->|->|  Accepted(3,V1)
       !  |       |  |  |  |  |       |  |  !! FAIL !!
          |       |  |  |  |  |       |  |
          X------>|->|------->|       |  |  Prepare(4)
          |<------X--X--|--|--X       |  |  Promise(4,{V1(1),V2(2),null})
          X------>|->|->|->|->|       |  |  Accept!(4,V2)
          |       X--X--X--X--X------>|->|  Accepted(4,V2)

Базовый Паксос, где новые предложения не могут изменить существующий консенсус

В следующем случае один Предлагающий достигает принятия значения V1 двух Принимающих, прежде чем потерпит неудачу. Новый предлагающий может начать новый раунд, но теперь он не может подготовить большинство, не включающее хотя бы одного акцептанта, принявшего версию V1. Таким образом, даже если Предлагающий не видит существующего консенсуса, единственный вариант Предлагающего — предложить уже согласованную ценность. Новые предлагающие могут постоянно увеличивать идентификатор, чтобы перезапустить процесс, но консенсус никогда не может быть изменен.

Proposer    Acceptor     Learner
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Prepare(1)
 |<---------X--X--X       |  |  Promise(1,{null,null,null})
 x--------->|->|  |       |  |  Accept!(1,V1)
 |  |       X--X--------->|->|  Accepted(1,V1)
 !  |       |  |  |       |  |  !! FAIL !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Prepare(2)
    |<---------X--X       |  |  Promise(2,{V1,null})
    X------>|->|->|       |  |  Accept!(2,V1)
    |<------X--X--X------>|->|  Accepted(2,V1)
    |       |  |  |       |  |

Мультиупаковки

Типичное развертывание Paxos требует непрерывного потока согласованных значений, действующих как команды для распределенного конечного автомата. Если каждая команда является результатом одного экземпляра протокола Basic Paxos , это приведет к значительным накладным расходам.

Если лидер относительно стабилен, фаза 1 становится ненужной. Таким образом, можно пропустить фазу 1 для будущих экземпляров протокола с тем же лидером.

Для этого круглое число I включается вместе с каждым значением, которое увеличивается в каждом раунде одним и тем же Лидером. Multi-Paxos сокращает задержку безотказного сообщения (предложение к обучению) с 4 задержек до 2 задержек.

Графическое представление потока сообщений в Multi-Paxos

Мульти-Паксос без сбоев

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

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

где V = последний из (Va, Vb, Vc).

Мульти-Паксос, когда фазу 1 можно пропустить

В этом случае последующие экземпляры базового протокола Paxos (представленные I+1 ) используют одного и того же лидера, поэтому фаза 1 (этих последующих экземпляров базового протокола Paxos), состоящая из подфаз подготовки и обещания, пропускается. Обратите внимание, что Лидер должен быть стабильным, т.е. не должен падать или меняться.

Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Мульти-Паксос, когда роли свернуты

Обычное развертывание Multi-Paxos заключается в сведении роли предлагающих, принимающих и обучающихся к «серверам». Итак, в конце концов есть только «Клиенты» и «Серверы».

На следующей диаграмме представлен первый «экземпляр» базового протокола Paxos, когда роли Предлагающего, Принимающего и Учащегося сведены в одну роль, называемую «Сервер».

Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         X->|->|  Accept!(N, I, Vn)
   |         X<>X<>X  Accepted(N, I)
   |<--------X  |  |  Response
   |         |  |  |

Мульти-Паксос, когда роли разрознены, а лидер устойчив

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

Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |

Оптимизации

Можно выполнить ряд оптимизаций, чтобы уменьшить количество обмениваемых сообщений, улучшить производительность протокола и т. д. Некоторые из этих оптимизаций описаны ниже.

«Мы можем сохранять сообщения ценой дополнительной задержки сообщения, имея одного выделенного учащегося, который информирует других учащихся, когда узнает, что значение было выбрано. Затем принимающие сообщения отправляют принятые сообщения только выделенному учащемуся. В большинстве приложений Роли лидера и выдающегося ученика выполняются одним и тем же процессором. ^[22]

«Лидер может отправлять сообщения « Подготовьтесь и принять!» только кворуму принимающих. Пока все принимающие в этом кворуме работают и могут общаться с лидером и учащимися, нет необходимости, чтобы принимающие, не входящие в кворум, делали что-либо. ^[22]

«Принимающим сторонам все равно, какое значение выбрано. Они просто отвечают на сообщения «Подготовка» и «Принять!» , чтобы гарантировать, что, несмотря на сбои, можно выбрать только одно значение. Однако, если получатель узнает, какое значение было выбрано, он может сохранить значение в стабильном хранилище и стереть любую другую информацию, которую он там сохранил. Если получатель позже получит сообщение «Подготовить» или «Принять!» , вместо выполнения действия «Фаза 1b» или «Фаза 2b» он может просто сообщить лидеру о выбранном значении. ^[22]

«Вместо того, чтобы отправлять значение v, лидер может отправить хеш v некоторым акцепторам в своих сообщениях Accept!. Учащийся узнает, что v выбран, если он получает сообщения Accepted для v или его хэша от кворума акцепторов, и по крайней мере одно из этих сообщений содержит v, а не его хеш. Однако лидер может получать сообщения Promise , в которых сообщается хеш значения v, которое он должен использовать в своем действии Phase2a, не сообщая ему фактическое значение v. Если это так. случается, лидер не может выполнить действие фазы 2а, пока не свяжется с каким-либо процессом, который знает v." ^[22]

«Представитель может отправить свое предложение только лидеру, а не всем координаторам. Однако для этого необходимо, чтобы результат алгоритма выбора лидера был передан предлагающим, что может быть дорогостоящим. Поэтому, возможно, было бы лучше позволить предлагающий отправляет свое предложение всем координаторам (в этом случае только сами координаторы должны знать, кто является лидером). ^[15]

«Вместо того, чтобы каждый принимающий отправлял сообщения «Принято» каждому учащемуся, принимающие могут отправлять свои сообщения «Принято» лидеру, а лидер может информировать учащихся о выборе значения. Однако это добавляет дополнительную задержку сообщения. ^[15]

«Наконец, заметьте, что фаза 1 не нужна для раунда 1… Лидер раунда 1 может начать раунд, отправив сообщение Accept! с любым предложенным значением». ^[15]

Дешевый Паксос

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

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

«При наличии только двух процессоров p и q один процессор не может отличить отказ другого процессора от отказа среды связи. Необходим третий процессор. Однако этот третий процессор не обязан участвовать в выборе последовательности команд. Он должен предпринимать действия только в случае сбоя p или q, после чего он ничего не делает, в то время как p или q продолжают управлять системой самостоятельно. Таким образом, третий процессор может быть небольшим/медленным/дешевым или процессором, в первую очередь предназначенным для других задач. ." ^[22]

Поток сообщений: дешевые мульти-паксосы

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

            {  Acceptors  }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |

Фаст Паксос

Fast Paxos обобщает базовый Paxos , чтобы уменьшить сквозные задержки сообщений. В Basic Paxos задержка сообщения от запроса клиента до обучения составляет 3 задержки сообщения. Fast Paxos допускает 2 задержки сообщений, но требует, чтобы (1) система состояла из 3f+1 приемников, допускающих до f ошибок (вместо классических 2f+1), и (2) клиент отправлял свой запрос нескольким адресатам. .

Интуитивно понятно, что если лидеру нечего предложить, клиент может отправить сообщение Accept! сообщение непосредственно Принимателям. Принимающие будут реагировать, как в Basic Paxos, отправляя сообщения «Принято» лидеру и каждому Учащемуся, достигая двух задержек сообщений от Клиента к Учащемуся.

Если лидер обнаруживает столкновение, он разрешает его, отправляя Accept! сообщения для нового раунда, которые принимаются как обычно. Этот метод скоординированного восстановления требует четырех задержек сообщений от клиента к учащемуся.

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

Поток сообщений: быстрый Paxos, неконфликтный

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

Поток сообщений: Fast Paxos, противоречивые предложения

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

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Противоречивые предложения с нескоординированным восстановлением.

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Поток сообщений: Fast Paxos с нескоординированным восстановлением, свернутыми ролями

(объединенные роли принимающего/учащегося)

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

Обобщенный Паксос

Обобщенный консенсус исследует взаимосвязь между операциями реплицируемого конечного автомата и протоколом консенсуса, который его реализует. ^[16] Основное открытие связано с оптимизацией Paxos, когда противоречивые предложения могут применяться в любом порядке. т.е. когда предлагаемые операции являются коммутативными операциями для конечного автомата. В таких случаях конфликтующие операции могут быть как приняты, избегая задержек, необходимых для разрешения конфликтов, так и повторного предложения отклоненных операций.

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

Пример

Чтобы проиллюстрировать обобщенный Paxos, в примере ниже показан поток сообщений между двумя одновременно работающими клиентами и реплицируемым конечным автоматом, реализующим операции чтения/записи над двумя отдельными регистрами A и B.

Таблица коммутативности
	Читать(А)	Написать (А)	Читать(Б)	Написать(Б)
Читать(А)
Написать (А)
Читать(Б)
Написать(Б)

Обратите внимание, что в этой таблице указаны операции, которые не являются коммутативными.

Возможная последовательность действий:

 <1:Read(A), 2:Read(B), 3:Write(B), 4:Read(B), 5:Read(A), 6:Write(A)>

С 5:Read(A) ездит с обоими 3:Write(B) и 4:Read(B), одна из возможных перестановок, эквивалентных предыдущему порядку, следующая:

 <1:Read(A), 2:Read(B), 5:Read(A), 3:Write(B), 4:Read(B), 6:Write(A)>

На практике поездка на работу происходит только тогда, когда операции предлагаются одновременно.

Поток сообщений: обобщенный Paxos (пример)

Ответы не показаны. Примечание: сокращения сообщений отличаются от предыдущих потоков сообщений из-за особенностей протокола, см. ^[23] для полноценного обсуждения.

Client      Leader  Acceptor       Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X- X- X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X------- ?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |  commutative order:
 |  |         |      |  |  |         |  |  V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+1,<WriteA> . <ReadA>)
 |  |         |<--------X- X-------->|->|  Accepted(N+1,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order:
 |  |         |      |  |  |         |  |  W = <WriteA, ReadA>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |

Производительность

Приведенный выше поток сообщений показывает нам, что Generalized Paxos может использовать семантику операций, чтобы избежать коллизий, когда спонтанное упорядочение сети не удается. Это позволяет протоколу работать быстрее, чем Fast Paxos. Однако в случае столкновения Generalized Paxos потребуется еще два рейса туда и обратно, чтобы восстановиться. Эта ситуация иллюстрируется операциями WriteB и ReadB в приведенной выше схеме.

В общем случае такие обходы неизбежны и связаны с тем, что в течение раунда может быть принято несколько команд. Это делает протокол более дорогим, чем Paxos, когда конфликты часты. Будем надеяться, что возможны две возможные модификации Generalized Paxos для сокращения времени восстановления. ^[24]

Во-первых, если координатор входит в каждый кворум акцепторов (раунд N называется центрированным ), то для восстановления в раунде N+1 после коллизии в раунде N координатор пропускает фазу 1 и предлагает на фазе 2 последовательность, которую он принял последней. во время раунда N. Это снижает стоимость восстановления до одной поездки туда и обратно.
Во-вторых, если в обоих раундах N и N+1 используется уникальный и идентичный центрированный кворум, когда акцептор обнаруживает коллизию в раунде N, он спонтанно предлагает в раунде N+1 последовательность, суффиксирующую оба (i) последовательность, принятую в раунде N, на координатор и (ii) наибольший неконфликтный префикс, который он принял в раунде N. Например, если координатор и акцептор приняли соответственно в раунде N <WriteB, ReadB> и <ReadB, ReadA> , акцептор спонтанно примет < WriteB, ReadB, ReadA> на этапе N+1. При таком варианте стоимость восстановления равна задержке одного сообщения, что, очевидно, является оптимальным. Обратите внимание, что использование уникального кворума в раунде не вредит жизнеспособности. Это связано с тем, что любой процесс в этом кворуме является кворумом чтения для фазы подготовки следующих раундов. ^[25]

Византийский Паксос

Paxos также может быть расширен для поддержки произвольных неудач участников, включая ложь, фабрикацию сообщений, сговор с другими участниками, выборочное неучастие и т. д. Эти типы неудач называются византийскими неудачами , по названию решения, популяризированного Лэмпортом. ^[26]

Византийский Паксос ^[27] введенное Кастро и Лисковым, добавляет дополнительное сообщение (Verify), которое служит для распространения знаний и проверки действий других процессоров:

Поток сообщений: византийский Multi-Paxos, устойчивое состояние

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |

Быстрый византийский Паксос ^[28] представленный Мартином и Алвиси, устраняет эту дополнительную задержку, поскольку клиент отправляет команды непосредственно акцепторам.

Обратите внимание, что сообщение «Принято» в Fast Byzantine Paxos отправляется всем принимающим и всем учащимся, тогда как Fast Paxos отправляет сообщения «Принято» только учащимся):

Поток сообщений: Fast Byzantine Multi-Paxos, устойчивое состояние.

Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |

Сценарий сбоя одинаков для обоих протоколов; Каждый Учащийся ожидает получения идентичных сообщений F+1 от разных Принимающих. Если этого не произойдет, об этом будут знать и сами Акцепторы (поскольку они обменивались сообщениями друг друга в широковещательном раунде), и правильные Акцепторы будут ретранслировать согласованное значение:

Поток сообщений: Fast Byzantine Multi-Paxos, сбой

Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |

Адаптация Paxos для сетей RDMA

С появлением очень высокоскоростных надежных сетей центров обработки данных, поддерживающих удаленный DMA ( RDMA ), возник значительный интерес к оптимизации Paxos для использования аппаратной разгрузки, при которой сетевая карта и сетевые маршрутизаторы обеспечивают надежность и контроль перегрузки на сетевом уровне, освобождая главный процессор для других задач. Библиотека Derecho C++ Paxos — это реализация Paxos с открытым исходным кодом, в которой рассматривается этот вариант. ^[12]

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

Производственное использование Паксоса

Google использует алгоритм Paxos в своей службе распределенной блокировки Chubby , чтобы обеспечить согласованность реплик в случае сбоя. ^[29] Chubby используется Bigtable , который сейчас находится в разработке в Google Analytics и других продуктах.
Google Spanner и Megastore используют внутренний алгоритм Paxos.
Служба репликации OpenReplica использует Paxos для поддержки реплик для системы открытого доступа, которая позволяет пользователям создавать отказоустойчивые объекты. Он обеспечивает высокую производительность за счет параллельных раундов и гибкость за счет динамического изменения членства.
IBM предположительно использует алгоритм Paxos в своем продукте IBM SAN Volume Controller для реализации отказоустойчивой виртуальной машины общего назначения, используемой для запуска компонентов конфигурации и управления службами виртуализации хранения, предлагаемыми кластером. ( Оригинальный исследовательский документ MIT и IBM )
Microsoft использует Paxos в службе управления кластерами Autopilot от Bing и в отказоустойчивой кластеризации Windows Server.
WANdisco внедрила Paxos в свою технологию активно-активной репликации DConE. ^[30]
XtreemFS на основе Paxos использует алгоритм согласования аренды для отказоустойчивой и последовательной репликации файловых данных и метаданных. ^[31]
Heroku использует Doozerd , который реализует Paxos для своего согласованного распределенного хранилища данных.
Ceph использует Paxos как часть процессов мониторинга, чтобы согласовать, какие OSD работают и находятся в кластере.
Распределенная база данных SQL MariaDB Xpand использует Paxos для разрешения распределенных транзакций .
Графическая база данных Neo4j HA реализует Paxos, заменяя Apache ZooKeeper из версии 1.9.
База данных Apache Cassandra NoSQL использует Paxos только для функции облегченных транзакций.
База данных ScyllaDB NoSQL использует Paxos для облегченных транзакций
Amazon Elastic Container Services использует Paxos для обеспечения единообразного представления состояния кластера.
Amazon DynamoDB использует алгоритм Paxos для выборов лидеров и достижения консенсуса .

См. также

Ссылки

^ Пиз, Маршалл; Шостак, Роберт; Лэмпорт, Лесли (апрель 1980 г.). «Достижение соглашения при наличии разногласий» . Журнал Ассоциации вычислительной техники . 27 (2): 228–234. дои : 10.1145/322186.322188 . S2CID 6429068 . Проверено 2 февраля 2007 г.
^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 . Проверено 2 февраля 2007 г.
^ Шнайдер, Фред (1990). «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие» (PDF) . Обзоры вычислительной техники ACM . 22 (4): 299–319. CiteSeerX 10.1.1.69.1536 . дои : 10.1145/98163.98167 . S2CID 678818 .
^ История газеты Лесли Лэмпорт
^ Лэмпорт, Лесли (май 1998 г.). «Неполный парламент» . Транзакции ACM в компьютерных системах . 16 (2): 133–169. дои : 10.1145/279227.279229 . S2CID 421028 . Проверено 2 февраля 2007 г.
^ Jump up to: ^а ^б Фишер, М. (апрель 1985 г.). «Невозможность распределенного консенсуса при одном неисправном процессе» . Журнал АКМ . 32 (2): 374–382. дои : 10.1145/3149.214121 . S2CID 207660233 .
^ Дворк, Синтия; Линч, Нэнси; Стокмейер, Ларри (апрель 1988 г.). «Консенсус при наличии частичной синхронности» (PDF) . Журнал АКМ . 35 (2): 288–323. CiteSeerX 10.1.1.13.3423 . дои : 10.1145/42282.42283 . S2CID 17007235 .
^ Оки, Брайан; Лисков, Барбара (1988). «Репликация с отметкой просмотра: новый метод первичного копирования для поддержки высокодоступных распределенных систем» . PODC '88: Материалы седьмого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 8–17. дои : 10.1145/62546.62549 .
^ Бирман, Кеннет; Джозеф, Томас (февраль 1987 г.). «Надежная связь при наличии сбоев». Транзакции ACM в компьютерных системах . 5 : 47–76. дои : 10.1145/7351.7478 . hdl : 1813/6534 . S2CID 11224827 .
^ Лэмпорт, Лесли; Малхи, Георгин; Чжоу, Лидун (март 2010 г.). «Реконфигурация конечного автомата». Новости СИГАКТ . 41 (1): 63–73. CiteSeerX 10.1.1.212.2168 . дои : 10.1145/1753171.1753191 . S2CID 15189602 .
^ Кейдар, Идит ; Шраер, Александр (2006). «Своевременность, обнаружение сбоев и согласованная производительность». PODC '06: Материалы 25-го ежегодного симпозиума ACM по принципам распределенных вычислений . дои : 10.1145/1146381.1146408 .
^ Jump up to: ^а ^б Джа, Сагар; Беренс, Джонатан; Гкунтувас, Тео; Милано, Мэтью; Сун, Вейцзя; Тремель, Эдвард; ван Ренесс, Робберт; Цинк, Сидней; Бирман, Кен (апрель 2019 г.). «Derecho: быстрая репликация конечного автомата для облачных сервисов». Транзакции ACM в компьютерных системах . 36 (2). дои : 10.1145/3302258 . S2CID 218482757 .
^ Лэмпорт, Лесли (2004). «Нижние границы асинхронного консенсуса» .
^ Ван Ренесс, Робберт; Алтинбукен, Дениз (17 февраля 2015 г.). «Паксос стал умеренно сложным» . Обзоры вычислительной техники ACM . 47 (3): 42:1–42:36. дои : 10.1145/2673577 . ISSN 0360-0300 .
^ Jump up to: ^а ^б ^с ^д ^и Лэмпорт, Лесли (2005). «Быстрый Паксос» .
^ Jump up to: ^а ^б ^с ^д Лэмпорт, Лесли (2005). «Общий консенсус и Паксос» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Чандра, Тушар; Гриземер, Роберт; Редстоун, Джошуа (2007). «Паксос ожил». Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 398–407. дои : 10.1145/1281100.1281103 . ISBN 9781595936165 . S2CID 207164635 . {{cite book}}: CS1 maint: дата и год ( ссылка )
^ Кесада Торрес, Луис (2018). Алгоритм Паксоса . Google TechTalks.
^ Лэмпорт, Лесли (2001). Paxos Made Simple Новости ACM SIGACT (колонка распределенных вычислений) 32 , 4 (целый номер 121, декабрь 2001 г.) 51-58.
^ «Выборы лидера, почему меня это должно волновать?» . Эластичный блог . 13 сентября 2013 года . Проверено 27 февраля 2021 г.
^ И. Гупта, Р. ван Ренесс и К.П. Бирман, 2000, Вероятностно правильный протокол выборов лидера для больших групп, Технический отчет , Корнельский университет
^ Jump up to: ^а ^б ^с ^д ^и Лэмпорт, Лесли; Масса, Майк (2004). «Дешевый Паксос» . Материалы Международной конференции по надежным системам и сетям (DSN 2004) .
^ Тернер, Брайан (2007). «Семейство протоколов консенсуса Паксос» .
^ Пьер, Сутра; Марк, Шапиро (2011). «Быстрый подлинный обобщенный консенсус» (PDF) . SRDS'11: 30-й симпозиум IEEE по надежным распределенным системам .
^ Лэмпорт, Лесли; Малхи, Георгин; Чжоу, Лидун (2009). «Вертикальные паксосы и репликация первичного резервного копирования». Материалы 28-го симпозиума ACM по принципам распределенных вычислений . ПОДК '09. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 312–313. CiteSeerX 10.1.1.150.1791 . дои : 10.1145/1582716.1582783 . ISBN 9781605583969 . S2CID 2763624 .
^ Лэмпорт, Лесли; Шостак, Роберт; Пиз, Маршалл (июль 1982 г.). «Проблема византийских генералов» . Транзакции ACM в языках и системах программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . дои : 10.1145/357172.357176 . S2CID 55899582 . Проверено 2 февраля 2007 г.
^ Кастро, Мигель; Лисков, Барбара (февраль 1999 г.). «Практическая византийская отказоустойчивость» (PDF) . Материалы третьего симпозиума по проектированию и внедрению операционных систем : 173–186 . Проверено 5 марта 2018 г.
^ Мартин, Жан-Филипп; Альвизи, Лоренцо (июль 2006 г.). «Быстрый византийский консенсус» (PDF) . Транзакции IEEE для надежных и безопасных вычислений . 3 (3): 202–215. дои : 10.1109/TDSC.2006.35 . Проверено 5 марта 2018 г.
^ Берроуз, Майк. «Служба блокировки Chubby для слабосвязанных распределенных систем» (PDF) . ОСДИ.
^ Ахлад и др. (2011). «Механизм распределенной координации (DConE)». Архивировано 15 апреля 2016 г. в Wayback Machine . Технический документ WANdisco.
^ Кольбек, Бьёрн; Хёгквист, Микаэль; Стендер, Ян; Хупфельд, Феликс (2011). «Аренда – Согласование аренды без сервера блокировки» . 25-й Международный симпозиум IEEE по параллельной и распределенной обработке (IPDPS 2011).

Внешние ссылки

[agree-1] Пиз, Маршалл; Шостак, Роберт; Лэмпорт, Лесли (апрель 1980 г.). «Достижение соглашения при наличии разногласий» . Журнал Ассоциации вычислительной техники . 27 (2): 228–234. дои : 10.1145/322186.322188 . S2CID 6429068 . Проверено 2 февраля 2007 г.

[clocks-2] Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 . Проверено 2 февраля 2007 г.

[schneider-3] Шнайдер, Фред (1990). «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие» (PDF) . Обзоры вычислительной техники ACM . 22 (4): 299–319. CiteSeerX 10.1.1.69.1536 . дои : 10.1145/98163.98167 . S2CID 678818 .

[Lamport-4] История газеты Лесли Лэмпорт

[paxos-5] Лэмпорт, Лесли (май 1998 г.). «Неполный парламент» . Транзакции ACM в компьютерных системах . 16 (2): 133–169. дои : 10.1145/279227.279229 . S2CID 421028 . Проверено 2 февраля 2007 г.

[flp-6] Jump up to: ^а ^б Фишер, М. (апрель 1985 г.). «Невозможность распределенного консенсуса при одном неисправном процессе» . Журнал АКМ . 32 (2): 374–382. дои : 10.1145/3149.214121 . S2CID 207660233 .

[LDS88-7] Дворк, Синтия; Линч, Нэнси; Стокмейер, Ларри (апрель 1988 г.). «Консенсус при наличии частичной синхронности» (PDF) . Журнал АКМ . 35 (2): 288–323. CiteSeerX 10.1.1.13.3423 . дои : 10.1145/42282.42283 . S2CID 17007235 .

[vr-8] Оки, Брайан; Лисков, Барбара (1988). «Репликация с отметкой просмотра: новый метод первичного копирования для поддержки высокодоступных распределенных систем» . PODC '88: Материалы седьмого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 8–17. дои : 10.1145/62546.62549 .

[BJ87-9] Бирман, Кеннет; Джозеф, Томас (февраль 1987 г.). «Надежная связь при наличии сбоев». Транзакции ACM в компьютерных системах . 5 : 47–76. дои : 10.1145/7351.7478 . hdl : 1813/6534 . S2CID 11224827 .

[LMZ10-10] Лэмпорт, Лесли; Малхи, Георгин; Чжоу, Лидун (март 2010 г.). «Реконфигурация конечного автомата». Новости СИГАКТ . 41 (1): 63–73. CiteSeerX 10.1.1.212.2168 . дои : 10.1145/1753171.1753191 . S2CID 15189602 .

[optimality-11] Кейдар, Идит ; Шраер, Александр (2006). «Своевременность, обнаружение сбоев и согласованная производительность». PODC '06: Материалы 25-го ежегодного симпозиума ACM по принципам распределенных вычислений . дои : 10.1145/1146381.1146408 .

[Derecho-12] Jump up to: ^а ^б Джа, Сагар; Беренс, Джонатан; Гкунтувас, Тео; Милано, Мэтью; Сун, Вейцзя; Тремель, Эдвард; ван Ренесс, Робберт; Цинк, Сидней; Бирман, Кен (апрель 2019 г.). «Derecho: быстрая репликация конечного автомата для облачных сервисов». Транзакции ACM в компьютерных системах . 36 (2). дои : 10.1145/3302258 . S2CID 218482757 .

[consensus-13] Лэмпорт, Лесли (2004). «Нижние границы асинхронного консенсуса» .

[14] Ван Ренесс, Робберт; Алтинбукен, Дениз (17 февраля 2015 г.). «Паксос стал умеренно сложным» . Обзоры вычислительной техники ACM . 47 (3): 42:1–42:36. дои : 10.1145/2673577 . ISSN 0360-0300 .

[fast-15] Jump up to: ^а ^б ^с ^д ^и Лэмпорт, Лесли (2005). «Быстрый Паксос» .

[general-16] Jump up to: ^а ^б ^с ^д Лэмпорт, Лесли (2005). «Общий консенсус и Паксос» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[live-17] Чандра, Тушар; Гриземер, Роберт; Редстоун, Джошуа (2007). «Паксос ожил». Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 398–407. дои : 10.1145/1281100.1281103 . ISBN 9781595936165 . S2CID 207164635 . {{cite book}}: CS1 maint: дата и год ( ссылка )

[techtalk-18] Кесада Торрес, Луис (2018). Алгоритм Паксоса . Google TechTalks.

[paxos-simple-19] Лэмпорт, Лесли (2001). Paxos Made Simple Новости ACM SIGACT (колонка распределенных вычислений) 32 , 4 (целый номер 121, декабрь 2001 г.) 51-58.

[elas_Lead-20] «Выборы лидера, почему меня это должно волновать?» . Эластичный блог . 13 сентября 2013 года . Проверено 27 февраля 2021 г.

[21] И. Гупта, Р. ван Ренесс и К.П. Бирман, 2000, Вероятностно правильный протокол выборов лидера для больших групп, Технический отчет , Корнельский университет

[cheap-22] Jump up to: ^а ^б ^с ^д ^и Лэмпорт, Лесли; Масса, Майк (2004). «Дешевый Паксос» . Материалы Международной конференции по надежным системам и сетям (DSN 2004) .

[paxos-family-23] Тернер, Брайан (2007). «Семейство протоколов консенсуса Паксос» .

[fggc-24] Пьер, Сутра; Марк, Шапиро (2011). «Быстрый подлинный обобщенный консенсус» (PDF) . SRDS'11: 30-й симпозиум IEEE по надежным распределенным системам .

[25] Лэмпорт, Лесли; Малхи, Георгин; Чжоу, Лидун (2009). «Вертикальные паксосы и репликация первичного резервного копирования». Материалы 28-го симпозиума ACM по принципам распределенных вычислений . ПОДК '09. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 312–313. CiteSeerX 10.1.1.150.1791 . дои : 10.1145/1582716.1582783 . ISBN 9781605583969 . S2CID 2763624 .

[byzgen-26] Лэмпорт, Лесли; Шостак, Роберт; Пиз, Маршалл (июль 1982 г.). «Проблема византийских генералов» . Транзакции ACM в языках и системах программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . дои : 10.1145/357172.357176 . S2CID 55899582 . Проверено 2 февраля 2007 г.

[27] Кастро, Мигель; Лисков, Барбара (февраль 1999 г.). «Практическая византийская отказоустойчивость» (PDF) . Материалы третьего симпозиума по проектированию и внедрению операционных систем : 173–186 . Проверено 5 марта 2018 г.

[28] Мартин, Жан-Филипп; Альвизи, Лоренцо (июль 2006 г.). «Быстрый византийский консенсус» (PDF) . Транзакции IEEE для надежных и безопасных вычислений . 3 (3): 202–215. дои : 10.1109/TDSC.2006.35 . Проверено 5 марта 2018 г.

[29] Берроуз, Майк. «Служба блокировки Chubby для слабосвязанных распределенных систем» (PDF) . ОСДИ.

[WANdisco-30] Ахлад и др. (2011). «Механизм распределенной координации (DConE)». Архивировано 15 апреля 2016 г. в Wayback Machine . Технический документ WANdisco.

[flease-31] Кольбек, Бьёрн; Хёгквист, Микаэль; Стендер, Ян; Хупфельд, Феликс (2011). «Аренда – Согласование аренды без сервера блокировки» . 25-й Международный симпозиум IEEE по параллельной и распределенной обработке (IPDPS 2011).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]