Паксос (компьютерные науки)

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

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

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

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

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

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

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

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

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

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

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

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

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

Валидность (или нетривиальность )

Только предлагаемые значения могут быть выбраны и изучены. ^[15]

Соглашение (или последовательность , или безопасность )

Никакие два отдельных обучающихся не могут усвоить разные значения (или не может быть более одного принятого значения). ^{[15] [16]}

Прекращение (или жизнеспособность)

Если было предложено значение C, то в конечном итоге обучающийся L узнает некоторое значение (если останется достаточное количество исправных процессоров). ^[16]

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

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

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

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

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

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

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

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

Acceptors ждут сообщения Prepare от любого из Proposers. Когда Acceptor получает сообщение Prepare, он должен проверить номер идентификатора n этого сообщения. Возможны два случая:

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

   В этой статье отсутствует информация об обработке первого сообщения Prepare. Пожалуйста, расширьте статью, чтобы включить эту информацию. Дополнительные сведения могут быть на странице обсуждения . ( Июль 2024 г. )

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

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

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

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

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

Если Acceptor еще не обещал (на этапе 1b) рассматривать только предложения с идентификатором больше n , он должен зарегистрировать значение v (только что полученного сообщения Accept ) как принятое значение (протокола) и отправить сообщение Accepted Proposer и каждому Learner (которые обычно могут быть самими Proposers). Learner узнают принятое значение только после получения сообщений Accepted от большинства Acceptor, т. е. не после получения только первого сообщения Accept.

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

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

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

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

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

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

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

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

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

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | X-------->| | | | | | Запрос | X--------->|->|->| | | Подготовить(1) | | | | ! | | !! ПРОВАЛ !! | |<---------X--X | | Обещание(1,{Va, Vb, null}) | X--------->|->| | | Принять!(1,V) | |<---------X--X--------->|->| Принято(1,V) |<---------------------------------X--X Ответ | | | | | |

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | X-------->| | | | | | Запрос | X--------->|->|->| | | Подготовить(1) | |<---------X--X--X | | Обещание(1,{Va,Vb,Vc}) | X--------->|->|->| | | Принять!(1,V) | |<---------X--X------>|->| Принято(1,V) | | | | | | ! !! ПРОВАЛ!! |<---------------------------------X Ответ | | | | | |

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | X----->| | | | | | Запрос | X------------>|->|->| | | Подготовить(1) | |<------------X--X--X | | Обещание(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! Лидер терпит неудачу во время трансляции !! | X----------->| | | | | Принять!(1,V) | ! | | | | | | | | | | | | !! НОВЫЙ ЛИДЕР !! | X--------->|->|->| | | Подготовить(2) | |<---------X--X--X | | Обещание(2,{V, null, null}) | X--------->|->|->| | | Принять!(2,V) | |<---------X--X------>|->| Принято(2,V) |<---------------------------------X--X Ответ | | | | | | |

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | X----->| | | | | | Запрос | X------------>|->|->| | | Подготовить(1) | |<------------X--X--X | | Обещание(1,{null,null,null}) | ! | | | | | !! ЛИДЕР НЕ СПРАВЛЯЕТСЯ | | | | | | | !! НОВЫЙ ЛИДЕР (знает, что последний номер был 1) | X--------->|->|->| | | Подготовить(2) | |<---------X--X--X | | Обещание(2,{null,null,null}) | | | | | | | | !! СТАРЫЙ ЛИДЕР выздоравливает | | | | | | | | !! СТАРЫЙ ЛИДЕР пытается 2, отказано | X------------>|->|->| | | Подготовить(2) | |<------------X--X--X | | Нак(2) | | | | | | | | !! СТАРЫЙ ЛИДЕР пытается 3 | X------------>|->|->| | | Подготовить(3) | |<------------X--X--X | | Обещание(3,{null,null,null}) | | | | | | | | !! НОВЫЙ ЛИДЕР предлагает, отклонено | | X--------->|->|->| | | Принять!(2,Va) | | |<---------X--X--X | | Нак(3) | | | | | | | | !! НОВЫЙ ЛИДЕР пытается 4 | | X--------->|->|->| | | Подготовить(4) | | |<---------X--X--X | | Обещание(4,{null,null,null}) | | | | | | | | !! СТАРЫЙ ЛИДЕР предлагает, отклоняется | X------------>|->|->| | | Принять!(3,Vb) | |<------------X--X--X | | Нак(4) | | | | | | | | ... и так далее ...

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

Предлагающий Принимающий Учащийся | | | | | | | X--------->|->|->| | | Подготовить(1) |<---------X--X--X | | Обещание(1,{null,null,null}) x--------->| | | | | Принять!(1,V1) | | X------------>|->| Принято(1,V1) ! | | | | | | !! ПРОВАЛ !! | | | | | | X--------->|->| | | Подготовить(2) |<---------X--X | | Обещание(2,{null,null}) X------>|->|->| | | Принять!(2,V2) |<------X--X--X------>|->| Принято(2,V2) | | | | | |

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

 Предлагающий Принимающий Учащийся | | | | | | | | | | | X--------------->|->|->|->|->| | | Подготовить(1) |<--------------X--X--X--X | | Обещание(1,{null,null,null,null,null}) x-------------->| | | | | | Принять!(1,V1) | | | | X------------------>|->| Принято(1,V1) ! | | | | | | | | | | !! ПРОВАЛ !! | | | | | | | | | | X--------------->|->|->|->| | | Подготовить(2) |<--------------X--X--X--X | | Обещание(2,{null,null,null,null}) X-------------->| | | | | | Принять!(2,V2) | | | | X-------------->|->| Принято(2,V2)  ! | | | | | | | | | !! ПРОВАЛ !! | | | | | | | | | X--------->|---->|->|->| | | Подготовить(3) |<---------X-----X--X--X | | Обещание(3,{V1,null,null,null}) X-------------->|->| | | | Принять!(3,V1) | | | | X--X--------->|->| Принято(3,V1)  ! | | | | | | | | !! ПРОВАЛ !! | | | | | | | | X------>|->|------->| | | Подготовить(4) |<------X--X--|--|--X | | Обещание(4,{V1(1),V2(2),null}) X------>|->|->|->|->| | | Принять!(4,V2) | X--X--X--X--X------>|->| Принято(4,V2)

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

Предлагающий Принимающий Учащийся | | | | | | | X--------->|->|->| | | Подготовить(1) |<---------X--X--X | | Обещание(1,{null,null,null}) x--------->|->| | | | Принять!(1,V1) | | X--X--------->|->| Принято(1,V1) ! | | | | | | !! ПРОВАЛ !! | | | | | | X--------->|->| | | Подготовить(2) |<---------X--X | | Обещание(2,{V1,null}) X------>|->|->| | | Принять!(2,V1) |<------X--X--X------>|->| Принято(2,V1) | | | | | |

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

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

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

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | --- Первый запрос --- X-------->| | | | | | Запрос | X--------->|->|->| | | Подготовить(N) | |<---------X--X--X | | Обещание(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | Принять!(N,I,V) | |<---------X--X------>|->| Принято(Н,И,В) |<---------------------------------X--X Ответ | | | | | | |

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

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | --- Последующие запросы --- X-------->| | | | | | Запрос | X--------->|->|->| | | Принять!(N,I+1,W) | |<---------X--X------>|->| Принято(N,I+1,W) |<---------------------------------X--X Ответ | | | | | | |

Обычное развертывание Multi-Paxos заключается в сворачивании ролей Proposers, Acceptors и Learners до «Servers». Таким образом, в конечном итоге остаются только «Clients» и «Servers».

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

Клиент-серверы | | | | --- Первый запрос --- X-------->| | | Запрос | X->|->| Подготовить(N) | |<-X--X Обещание(N, I, {Va, Vb}) | X->|->| Принять!(Н, И, Вн) | X<>X<>X Принято(Н, Я) |<--------X | | Ответ | | | |

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

Клиент-серверы X-------->| | | Запрос | X->|->| Принять!(N,I+1,W) | X<>X<>X Принято(N,I+1) |<--------X | | Ответ | | | |

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

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

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

«Акцепторы не заботятся о том, какое значение выбрано. Они просто отвечают на сообщения Prepare и Accept!, чтобы гарантировать, что, несмотря на сбои, может быть выбрано только одно значение. Однако, если акцептор узнает, какое значение было выбрано, он может сохранить значение в стабильном хранилище и стереть любую другую информацию, которую он там сохранил. Если акцептор позже получит сообщение Prepare или Accept!, вместо выполнения действия Phase1b или Phase2b, он может просто сообщить лидеру о выбранном значении. ^[22]

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

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

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

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

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

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

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

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

 { Акцепторы }Предлагающий Главный Вспомогательный Ученик| | | | | | -- Фаза 2 --X----------->|->|->| | | Принять!(N,I,V)| | | ! | | --- ПРОВАЛ! ---|<----------X--X--------------->| Принято(Н,И,В)| | | | | -- Обнаружен сбой (принято только 2) --X----------->|->|------->| | Принять!(N,I,V) (передать повторно, включить Aux)|<-----------X--X--------X------>| Принято(N,I,V)| | | | | -- Перенастроить: Кворум = 2 --X----------->|->| | | Принять!(N,I+1,W) (Aux не участвует)|<-----------X--X--------------->| Принято(N,I+1,W)| | | | |

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

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

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

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

Клиент Лидер Приемник Ученик | | | | | | | | | X--------->|->|->|->| | | Любой(N,I,Восстановление) | | | | | | | | X------------------->|->|->|->| | | Принять!(Н,И,В) | |<---------X--X--X------>|->| Принято(Н,И,В) |<-----------------------------------X--X Ответ(W) | | | | | | | |

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

Клиент Лидер Приемник Ученик | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Одновременные противоречивые предложения | | | | | | | | | !! получено в разном порядке | | | | | | | | | !! Акцепторами | X-------------?|-?|-?|-?| | | Принять!(N,I,V) X-----------------?|-?|-?|-?|-?| | | Принять!(Н,И,В) | | | | | | | | | | | | | | | | | | !! Акцепторы не согласны с ценностью | | |<-------X--X->|->|----->|->| Принято(Н,И,В) | | |<-------|<-|<-X--X----->|->| Принято(Н,И,В) | | | | | | | | | | | | | | | | | | !! Обнаружение столкновения и восстановление | | X------->|->|->|->| | | Принять!(N+1,I,W) | | |<-------X--X--X----->|->| Принято(N+1,I,W) |<---------------------------------X--X Ответ(W) | | | | | | | | |

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

Клиент Лидер Приемник Ученик | | | | | | | | | | | X------->|->|->|->| | | Любой(N,I,Восстановление) | | | | | | | | | | | | | | | | | | !! Одновременные противоречивые предложения | | | | | | | | | !! получено в разном порядке | | | | | | | | | !! Акцепторами | X-------------?|-?|-?|-?| | | Принять!(N,I,V) X-----------------?|-?|-?|-?|-?| | | Принять!(Н,И,В) | | | | | | | | | | | | | | | | | | !! Акцепторы не согласны с ценностью | | |<-------X--X->|->|----->|->| Принято(Н,И,В) | | |<-------|<-|<-X--X----->|->| Принято(Н,И,В) | | | | | | | | | | | | | | | | | | !! Обнаружение столкновения и восстановление | | |<-------X--X--X----->|->| Принято(N+1,I,W) |<---------------------------------X--X Ответ(W) | | | | | | | | |

(объединенные роли акцептора/ученика)

Клиент-серверы | | | | | | | | X->|->|->| Любой(N,I,Восстановление) | | | | | | | | | | | | !! Одновременные противоречивые предложения | | | | | | !! получено в разном порядке | | | | | | !! Серверами | X--------?|-?|-?|-?| Принять!(N,I,V) X-----------?|-?|-?|-?| Принять!(Н,И,В) | | | | | | | | | | | | !! Серверы не согласны по значению | | X<>X->|->| Принято(N,I,V) | | |<-|<-X<>X Принято(Н,И,З) | | | | | | | | | | | | !! Обнаружение столкновения и восстановление | | X<>X<>X<>X Принято(N+1,I,W) |<-----------X--X--X Ответ(W) | | | | | |

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

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

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

Таблица коммутативности

	Читать(А)	Написать(А)	Читать(Б)	Написать(Б)
Читать(А)
Написать(А)
Читать(Б)
Написать(Б)

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

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

<1:Чтение(A), 2:Чтение(B), 3:Запись(B), 4:Чтение(B), 5:Чтение(A), 6:Запись(A)>

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

<1:Чтение(A), 2:Чтение(B), 5:Чтение(A), 3:Запись(B), 4:Чтение(B), 6:Запись(A)>

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

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

Клиент Лидер Приемник Ученик | | | | | | | | !! Новый лидер начинает раунд | | X----->|->|->| | | Подготовить(N) | | |<-----X- X- X | | Обещание(N,null) | | X----->|->|->| | | Phase2Start(N,null) | | | | | | | | | | | | | | | | !! Предложения по одновременным поездкам | X------- ?|-----?|-?|-?| | | Предложить(ПрочитатьA) X-----------?|-----?|-?|-?| | | Предложить(ReadB) | | X------X-------------->|->| Принято(N,<ReadA,ReadB>) | | |<--------X--X-------->|->| Принято(N,<ReadB,ReadA>) | | | | | | | | | | | | | | | | !! Конфликта нет, оба варианта приняты | | | | | | | | Стабильный = <ReadA, ReadB> | | | | | | | | | | | | | | | | !! Одновременные противоречивые предложения X-----------?|-----?|-?|-?| | | Предложить(<WriteB,ReadA>) | X--------?|-----?|-?|-?| | | Предложить(ReadB) | | | | | | | | | | X------X-------------->|->| Принято(N,<WriteB,ReadA> . <ReadB>) | | |<--------X--X-------->|->| Принято(N,<ReadB> . <WriteB,ReadA>) | | | | | | | | | | | | | | | | !! Конфликт обнаружен, лидер выбирает | | | | | | | | коммутативный порядок: | | | | | | | | V = <ЧтениеA, ЗаписьB, ЧтениеB> | | | | | | | | | | X----->|->|->| | | Фаза2Начало(N+1,V) | | |<-----X- X- X-------->|->| Принято(N+1,V) | | | | | | | | Стабильный = <ReadA, ReadB> . | | | | | | | | <ЧитатьA, ЗаписыватьB, ЧитатьB> | | | | | | | | | | | | | | | | !! Еще больше противоречивых предложений X-----------?|-----?|-?|-?| | | Предложить(WriteA) | X--------?|-----?|-?|-?| | | Предложить(ПрочитатьA) | | | | | | | | | | X------X-------------->|->| Принято(N+1,<WriteA> . <ReadA>) | | |<--------X- X-------->|->| Принято(N+1,<ЧтениеA> . <ЗаписьA>) | | | | | | | | | | | | | | | | !! Лидер выбирает порядок: | | | | | | | | W = <ЗаписьA, ЧтениеA> | | | | | | | | | | X----->|->|->| | | Фаза2Начало(N+2,W) | | |<-----X- X- X-------->|->| Принято(N+2,W) | | | | | | | | Стабильный = <ReadA, ReadB> . | | | | | | | | <ЧтениеA, ЗаписьB, ЧтениеB> . | | | | | | | | <ЗаписьA, ЧтениеA> | | | | | | | |

Вышеприведенный поток сообщений показывает нам, что обобщенный Paxos может использовать семантику операций, чтобы избегать коллизий, когда спонтанное упорядочение сети дает сбой. Это позволяет протоколу быть на практике быстрее, чем Fast Paxos. Однако, когда происходит коллизия, обобщенному 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]

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

Клиент Предлагающий Принимающий Учащийся | | | | | | | X-------->| | | | | | Запрос | X--------->|->|->| | | Принять!(N,I,V) | | X<>X<>X | | Проверить(N,I,V) - ТРАНСЛЯЦИЯ | |<---------X--X------>|->| Принято(Н,В) |<---------------------------------X--X Ответ(V) | | | | | | |

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

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

Клиент-акцептор, обучающийся | | | | | | X----->|->|->| | | Принять!(N,I,V) | X<>X<>X------>|->| Принято(N,I,V) - ТРАНСЛЯЦИЯ |<-------------------X--X Ответ(V) | | | | | |

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

Клиент-акцептор, обучающийся | | | ! | | !! Один акцептор неисправен X----->|->|->! | | Принять!(N,I,V) | X<>X<>X------>|->| Принято(N,I,{V,W}) - ТРАНСЛЯЦИЯ | | | ! | | !! Учащиеся получают 2 разные команды | | | ! | | !! Правильные акцепторы замечают ошибку и выбирают | X<>X<>X------>|->| Принято(N,I,V) - ТРАНСЛЯЦИЯ |<-------------------X--X Ответ(V) | | | ! | |

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

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

Этот раздел нуждается в дополнительных цитатах для проверки . Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники в этом разделе. Неподтвержденный материал может быть оспорен и удален. Найти источники:  "Paxos" computer science – новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2018 г. ) ( Узнайте, как и когда удалять это сообщение )

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

• Задача о двух генералах
• Алгоритм консенсуса Чандра-Тоуэга
• Государственная машина
• Плот