Paxos - это семейство протоколов для решения консенсуса в сети ненадежных или ошибочные процессоры. Консенсус - это процесс согласования одного результата группой участников. Эта проблема становится сложной, когда участники или их коммуникации могут испытывать сбои.
Протоколы консенсуса являются основой для подхода репликации конечного автомата к распределенным вычислениям, как было предложено Лесли Лэмпорт и обследован Фредом Шнайдером. Репликация конечного автомата - это метод преобразования алгоритма в отказоустойчивую распределенную реализацию. Специальные методы могут оставить нерешенными важные случаи сбоев. Принципиальный подход, предложенный Lamport et al. обеспечивает безопасное обращение со всеми случаями.
Протокол Paxos был впервые представлен в 1989 году и назван в честь вымышленной системы законодательного консенсуса, использовавшейся на острове Paxos в Греции, где Лампорт писал, что парламент должен функционировать, «хотя законодатели постоянно бродили по палате парламента и выходили из нее ». Позже он был опубликован в виде журнальной статьи в 1998 году.
Семейство протоколов Paxos включает в себя спектр компромиссов между количеством процессоров, количеством задержек сообщений до получения согласованного значения, уровнем активности человека. участников, количество отправленных сообщений и типы сбоев. Хотя никакой детерминированный отказоустойчивый консенсусный протокол не может гарантировать прогресс в асинхронной сети (результат был подтвержден в статье Фишер, Линч и Патерсон ), Paxos гарантирует безопасность (последовательность) и условия, которые могут помешать ее прогрессу, спровоцировать сложно.
Paxos обычно используется там, где требуется долговечность (например, для репликации файла или базы данных), в которых длительное состояние может быть большим. Протокол пытается добиться прогресса даже в периоды, когда некоторое ограниченное количество реплик не отвечает. Также существует механизм удаления постоянно отказавшей реплики или добавления новой реплики.
Тема предшествует протоколу. В 1988 году Линч, Дворк и Стокмейер продемонстрировали разрешимость консенсуса в широком семействе «частично синхронных» систем. Paxos имеет сильное сходство с протоколом, используемым для согласования при «репликации с отметкой просмотра», впервые опубликованном Oki и Liskov в 1988 году в контексте распределенных транзакций. Несмотря на эту предыдущую работу, Paxos предложил особенно элегантный формализм и включил одно из первых доказательств безопасности отказоустойчивого протокола распределенного консенсуса.
Реконфигурируемые конечные автоматы имеют тесные связи с предыдущей работой над надежными протоколами групповой многоадресной рассылки, которые поддерживают динамическое членство в группах, например, с работой Бирмана в 1985 и 1987 годах над виртуально синхронным протокол gbcast. Однако gbcast необычен с точки зрения поддержки надежности и устранения сбоев разделения. В большинстве надежных протоколов многоадресной рассылки отсутствуют эти свойства, необходимые для реализации модели репликации конечного автомата. Этот момент подробно изложен в статье Лампорта, Малхи и Чжоу.
Протоколы Paxos являются членами теоретического класса решений проблемы, формализованной как единое соглашение с сбои в работе. Нижние оценки для этой задачи были доказаны Кейдаром и Шраером. Derecho, программная библиотека C ++ для репликации конечного автомата в масштабе облака, предлагает протокол Paxos, интегрированный с самоуправляемым виртуально синхронным членством. Этот протокол соответствует границам оптимальности Кейдара и Шраера и эффективно отображается на современное оборудование центра обработки данных удаленного DMA (RDMA) (но использует TCP, если RDMA недоступен).
Чтобы упростить представление Paxos, следующие предположения и определения сделаны явными. Методы расширения области применения известны в литературе и не рассматриваются в этой статье.
В общем, алгоритм консенсуса может развиваться, используя процессоры, несмотря на одновременный отказ любого процессоры: другими словами, количество исправных процессов должно быть строго больше, чем количество ошибочных процессов. Однако, используя реконфигурацию, можно использовать протокол, который выдерживает любое количество полных отказов до тех пор, пока не будет отказано более F одновременно. Для протоколов Paxos эти изменения конфигурации могут выполняться как отдельные конфигурации.
Paxos описывает действия процессоров по их ролям в протоколе: клиент, принимающий, предлагающий, учащийся и лидер. В типичных реализациях один процессор может играть одну или несколько ролей одновременно. Это не влияет на правильность протокола - обычно роли объединяются, чтобы уменьшить время ожидания и / или количество сообщений в протоколе.
Кворумы выражают свойства безопасности (или согласованности) Paxos, гарантируя, что по крайней мере какой-то сохранившийся процессор сохраняет информацию о полученные результаты.
Кворумы определяются как подмножества набора Принимающих, такие, что любые два подмножества (то есть любые два Кворума) имеют как минимум одного члена. Как правило, Кворум составляет любое большинство принимающих участие. Например, учитывая набор Акцепторов {A, B, C, D}, большинство Кворума будут любыми тремя Акцепторами: {A, B, C}, {A, C, D}, {A, B, D}, {B, C, D}. В более общем смысле, акцепторам могут быть присвоены произвольные положительные веса; в этом случае Кворум может быть определен как любое подмножество Акцепторов с суммарным весом, превышающим половину общего веса всех Акцепторов.
Каждая попытка определить согласованное значение v выполняется с предложениями, которые могут быть приняты или не приняты Акцептаторами. Каждое предложение имеет уникальный номер для данного заявителя. Так, например, каждое предложение может иметь форму (n, v), где n - уникальный идентификатор предложения, а v - фактическое предлагаемое значение. Значение, соответствующее пронумерованному предложению, может быть вычислено как часть работы протокола Paxos, но это не обязательно.
Чтобы гарантировать безопасность (также называемую «согласованностью»), Paxos определяет три свойства и гарантирует, что первые два всегда сохраняются, независимо от характера отказов:
Обратите внимание, что завершение работы Paxos не гарантируется, и поэтому он не имеет свойства живучести. Это подтверждается результатом невозможности Fischer Lynch Paterson (FLP), в котором говорится, что протокол согласованности может иметь только два из следующих параметров: безопасность, живучесть и отказоустойчивость. Поскольку цель Paxos - обеспечить отказоустойчивость и безопасность, она также не может гарантировать живучесть.
В большинстве развертываний Paxos каждый участвующий процесс действует в трех ролях; Предлагающий, принимающий и учащийся. Это значительно снижает сложность сообщения без ущерба для правильности:
В Paxos клиенты отправляют команды лидеру. Во время нормальной работы лидер получает команду клиента, присваивает ей новый номер команды i, а затем начинает i-й экземпляр алгоритма консенсуса, отправляя сообщения набору процессов-приемников.
При объединении ролей протокол "разрушается" "в эффективное развертывание в стиле клиент-мастер-реплика, типичное для сообщества баз данных. Преимущество протоколов Paxos (включая реализации с объединенными ролями) - это гарантия их свойств безопасности.
Типичный поток сообщений реализации описан в разделе Multi-Paxos.
Этот протокол является самым основным из семейства Paxos. Каждый «экземпляр» (или «выполнение») основного протокола Paxos определяет единственное выходное значение. Протокол проходит в несколько раундов. Успешный раунд состоит из двух фаз: фазы 1 (которая разделена на части a и b) и фазы 2 (которая разделена на части a и b). См. Ниже описание фаз. Помните, что мы предполагаем асинхронную модель, поэтому, например, процессор может находиться в одной фазе, а другой процессор может находиться в другой.
Это сообщение Accept следует интерпретировать как «запрос», как в «Примите это предложение, пожалуйста!».
Обратите внимание, что Акцептатор может принимать несколько предложений. Это может произойти, когда другой предлагающий, не зная о новом значении, начинает новый раунд с более высоким идентификационным номером n. В этом случае Acceptor может пообещать, а затем принять новое предложенное значение, даже если он принял другое ранее. Эти предложения могут даже иметь разные значения при наличии определенных сбоев. Тем не менее, протокол Paxos гарантирует, что Акцептаторы в конечном итоге согласятся с единым значением.
На следующих диаграммах представлены несколько случаев / ситуаций применения Basic Протокол Paxos. Некоторые случаи показывают, как протокол Basic Paxos справляется с отказом определенных (избыточных) компонентов распределенной системы.
Обратите внимание, что значения, возвращаемые в сообщении Promise, являются «нулевыми» при первом внесении предложения (поскольку ни один акцептор не принял значение ранее в этом раунде).
На схеме ниже есть 1 клиент, 1 предлагающий, 3 принимающих (т.е. размер кворума 3) и 2 учащихся (представлены двумя вертикальными линиями). На этой диаграмме представлен успешный первый раунд (т.е. ни один процесс в сети не завершился ошибкой).
Ученик, предлагающий клиента, принимающий | | | | | | | X -------->| | | | | | Запрос | X --------->| ->| ->| | | Подготовить (1) | | <---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->| ->| ->| | | Принимаю! (1, V) | | <---------X--X--X------>| ->| Принято (1, V) | <---------------------------------X--X Response | | | | | | |
Здесь V - последнее из (Va, Vb, Vc).
Самыми простыми случаями ошибок являются отказ Acceptor (когда кворум Acceptor остается активным) и отказ избыточного Learner. В этих случаях протокол не требует «восстановления» (т. Е. Все равно успешно): никаких дополнительных раундов или сообщений не требуется, как показано ниже (на следующих двух диаграммах / случаях).
На следующей диаграмме один из акцепторов в кворуме выходит из строя, поэтому размер кворума становится равным 2. В этом случае протокол Basic Paxos все еще работает успешно.
Ученик, предлагающий клиента, принимающий | | | | | | | X -------->| | | | | | Запрос | X --------->| ->| ->| | | Подготовить (1) | | | | ! | | !! ПОТЕРПЕТЬ НЕУДАЧУ !! | | <---------X--X | | Promise(1,{Va, Vb, null}) | X--------->| ->| | | Принимаю! (1, V) | | <---------X--X--------->| ->| Принято (1, V) | <---------------------------------X--X Response | | | | | |
В следующем случае один из (избыточных) учащихся не работает, но протокол Basic Paxos все еще работает.
Ученик, предлагающий клиента, принимающий | | | | | | | X -------->| | | | | | Запрос | X --------->| ->| ->| | | Подготовить (1) | | <---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->| ->| ->| | | Принимаю! (1, V) | | <---------X--X--X------>| ->| Принято (1, V) | | | | | | ! !! ПОТЕРПЕТЬ НЕУДАЧУ !! | <---------------------------------X Response | | | | | |
В этом случае предлагающий терпит неудачу после предложения значения, но до достижения соглашения. В частности, он не работает в середине сообщения Accept, поэтому только один Acceptor из кворума получает значение. Тем временем избирается новый Лидер (Предлагающий) (но это подробно не показано). Обратите внимание, что в этом случае есть 2 раунда (раунды идут вертикально, сверху вниз).
Ученик, предлагающий клиента, принимающий | | | | | | | X ----->| | | | | | Запрос | X ------------>| ->| ->| | | Подготовить (1) | | <------------X--X--X | | Promise(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! Leader fails during broadcast !! | X------------>| | | | | Принимаю! (1, V) | ! | | | | | | | | | | | | !! НОВЫЙ ЛИДЕР !! | X --------->| ->| ->| | | Подготовить (2) | | <---------X--X--X | | Promise(2,{V, null, null}) | X--------->| ->| ->| | | Принимаю! (2, V) | | <---------X--X--X------>| ->| Принято (2, V) | <---------------------------------X--X Response | | | | | | |
Самый сложный случай - когда несколько предлагающих считают себя лидерами. Например, текущий лидер может потерпеть неудачу и позже восстановится, но другие предлагающие уже повторно выбрали нового лидера. Выздоровевший лидер этого еще не усвоил и пытается начать один раунд конфликта с нынешним лидером. На диаграмме ниже показано 4 неудачных раунда, но их может быть больше (как показано внизу диаграммы).
Ученик, предлагающий клиента, принимающий | | | | | | | X ----->| | | | | | Запрос | X ------------>| ->| ->| | | Подготовить (1) | | <------------X--X--X | | Promise(1,{null,null,null}) | ! | | | | | !! LEADER FAILS | | | | | | | !! NEW LEADER (knows last number was 1) | X--------->| ->| ->| | | Подготовить (2) | | <---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | | !! OLD LEADER recovers | | | | | | | | !! OLD LEADER tries 2, denied | X------------>| ->| ->| | | Подготовить (2) | | <------------X--X--X | | Nack(2) | | | | | | | | !! OLD LEADER tries 3 | X------------>| ->| ->| | | Подготовить (3) | | <------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | | !! NEW LEADER proposes, denied | | X--------->| ->| ->| | | Принимаю! (2, Ва) | | | <---------X--X--X | | Nack(3) | | | | | | | | !! NEW LEADER tries 4 | | X--------->| ->| ->| | | Подготовить (4) | | | <---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | | !! OLD LEADER proposes, denied | X------------>| ->| ->| | | Принимаю! (3, Vb) | | <------------X--X--X | | Nack(4) | | | | | | | |... and so on...
Типичное развертывание Paxos требует непрерывного потока согласованных значений, действующих как команды для распределенного конечного автомата. Если каждая команда является результатом одного экземпляра протокола Basic Paxos, это приведет к значительным накладным расходам.
Если лидер относительно стабилен, фаза 1 становится ненужной. Таким образом, можно пропустить фазу 1 для будущих экземпляров протокола с тем же лидером.
Для этого число раунда Iвключается вместе с каждым значением, которое увеличивается в каждом раунде одним и тем же лидером. Multi-Paxos сокращает безотказную задержку сообщения (от предложения до обучения) с 4 до 2 задержек.
На следующей диаграмме только один экземпляр (или «выполнение») показан базовый протокол Paxos с начальным лидером (предлагающим). Обратите внимание, что Multi-Paxos состоит из нескольких экземпляров базового протокола Paxos.
Ученик, предлагающий клиента, принимающий | | | | | | | --- Первый запрос --- X -------->| | | | | | Запрос | X --------->| ->| ->| | | Подготовить (N) | | <---------X--X--X | | Promise(N,I,{Va,Vb,Vc}) | X--------->| ->| ->| | | Принимаю! (N, I, V) | | <---------X--X--X------>| ->| Принято (N, I, V) | <---------------------------------X--X Response | | | | | | |
, где V = последний из (Va, Vb, Vc).
В этом случае экземпляры подпоследовательности базового протокола Paxos (представленные I + 1) используют один и тот же лидер, поэтому фаза 1 (из эти последующие экземпляры базового протокола Paxos), которые состоят из подфаз Prepare и Promise, пропускаются. Обратите внимание, что Лидер должен быть стабильным, то есть не должен падать или изменяться.
Ученик, предлагающий клиента, принимающий | | | | | | | --- Следующие запросы --- X -------->| | | | | | Запрос | X --------->| ->| ->| | | Принимаю! (N, I + 1, W) | | <---------X--X--X------>| ->| Принято (N, I + 1, W) | <---------------------------------X--X Response | | | | | | |
Обычное развертывание Multi-Paxos состоит в свертывании ролей Предлагающих, Принимающих и обучающихся в "Серверы". Итак, в итоге остались только «Клиенты» и «Серверы».
На следующей диаграмме представлен первый «экземпляр» базового протокола Paxos, когда роли Предлагающего, Принимающего и Обучающегося сводятся к одной роли, называемой «Сервер».
Клиентские серверы | | | | --- Первый запрос --- X -------->| | | Запрос | X->| ->| Подготовить (N) | | <-X--X Promise(N, I, {Va, Vb}) | X->| ->| Принимаю! (N, I, Vn) | X <>X <>X Accepted (N, I) | <--------X | | Response | | | |
В последующих экземплярах базового протокола Paxos, с тем же лидером, что и в предыдущих примерах базового протокола Paxos, этап 1 можно пропустить.
Клиентские серверы X -------->| | | Запрос | X->| ->| Принимаю! (N, I + 1, W) | X <>X <>X Accepted (N, I + 1) | <--------X | | Response | | | |
Для уменьшения количества передаваемых сообщений и повышения производительности можно выполнить ряд оптимизаций. протокола и т. д. Некоторые из этих оптимизаций описаны ниже.
Cheap Paxos расширяет Basic Paxos, чтобы выдерживать отказы F с помощью F + 1 основных процессоров и F вспомогательных процессоров путем динамического изменения конфигурации после каждого сбоя.
Это снижение требований к процессору происходит за счет живучести; если слишком много основных процессоров выйдет из строя за короткое время, система должна остановиться, пока вспомогательные процессоры не смогут перенастроить систему. В периоды стабильности вспомогательные процессоры занимают не участвует в протоколе.
«Имея только два процессора p и q, один процессор не может отличить отказ другого процессора от отказа среды связи. Требуется третий процессор. Однако этот третий процессор не должен участвовать в выборе последовательности команд. Он должен действовать только в случае отказа p или q, после чего он ничего не делает, пока p или q продолжают управлять системой самостоятельно. Таким образом, третий процессор может быть маленьким / медленным / дешевым или процессором, предназначенным в первую очередь для других задач. "
Пример, включающий три основных приемника, один вспомогательный приемник и размер кворума три, показывая отказ одного главного процессора и последующую реконфигурацию:
{Acceptors} Предлагающий главный вспомогательный обучающийся | | | | | | - Фаза 2 - X -------- --->| ->| ->| | | Принято! (N, I, V) | | |! | | --- FAIL! --- | <-----------X--X--------------->| Принято (N, I, V) | | | | | - Обнаружен сбой (принято только 2) - X ----------->| ->| ------->| | Принять! (N, I, V) (повторно передать, включить Aux) | <-----------X--X--------X------>| Accepted (N, I, V) | | | | | - Перенастроить: Quorum = 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, посылая принятые сообщения лидеру и каждому учащемуся, достигая двух задержек сообщений от клиента к учащемуся.
Если лидер обнаруживает столкновение, он разрешает его, посылая Accept! сообщения для нового раунда, которые принимаются как обычно. Этот метод скоординированного восстановления требует четырех задержек сообщений от клиента к учащемуся.
Окончательная оптимизация происходит, когда лидер заранее определяет метод восстановления, позволяя принимающим сторонам самостоятельно выполнять восстановление после столкновения. Таким образом, нескоординированное восстановление после столкновения может происходить за три задержки сообщения (и только две задержки сообщения, если все учащиеся также являются принимающими).
Client Leader Acceptor Learner | | | | | | | | | X --------->| ->| ->| ->| | | Любой (N, I, Recovery) | | | | | | | | X ------------------->| ->| ->| ->| | | Принять! (N, I, W) | | <---------X--X--X--X------>| ->| Принято (N, I, W) | <------------------------------------X--X Response(W) | | | | | | | |
Конфликтующие предложения при скоординированном восстановлении. Примечание: протокол не определяет, как обрабатывать отброшенный клиентский запрос.
Client Leader Acceptor Learner | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Параллельно противоречивые предложения | | | | | | | | | !! поступили в разном порядке | | | | | | | | | !! акцепторами | X --------------? | -? | -? | -? | | | Принять! (N, I, V) X -----------------? | -? | -? | -? | | | Принять! (N, I, W) | | | | | | | | | | | | | | | | | | !! Акцепторы расходятся во мнениях по поводу стоимости | | | <-------X--X->| ->| ----->| ->| Принято (N, I, V) | | | <-------|<-|<-X--X----->| ->| Принято (N, I, W) | | | | | | | | | | | | | | | | | | !! Обнаружить столкновение и восстановить | | X ------->| ->| ->| ->| | | Принимаю! (N + 1, I, W) | | | <-------X--X--X--X----->| ->| Принято (N + 1, I, W) | <---------------------------------X--X Response(W) | | | | | | | | |
Противоречивые предложения с нескоординированным восстановлением.
Клиент Лидер Приемник Ученик | | | | | | | | | | | X ------->| ->| ->| ->| | | Любой (N, I, Recovery) | | | | | | | | | | | | | | | | | | !! Параллельно противоречивые предложения | | | | | | | | | !! поступили в разном порядке | | | | | | | | | !! акцепторами | X --------------? | -? | -? | -? | | | Принять! (N, I, V) X -----------------? | -? | -? | -? | | | Принять! (N, I, W) | | | | | | | | | | | | | | | | | | !! Акцепторы расходятся во мнениях по поводу стоимости | | | <-------X--X->| ->| ----->| ->| Принято (N, I, V) | | | <-------|<-|<-X--X----->| ->| Принято (N, I, W) | | | | | | | | | | | | | | | | | | !! Обнаружить столкновение и восстановить | | | <-------X--X--X--X----->| ->| Принято (N + 1, I, W) | <---------------------------------X--X Response(W) | | | | | | | | |
(объединенные роли Acceptor / Learner)
Клиентские серверы | | | | | | | | X->| ->| ->| Любой (N, I, Recovery) | | | | | | | | | | | | !! Параллельно противоречивые предложения | | | | | | !! поступили в разном порядке | | | | | | !! серверами | X --------? | -? | -? | -? | Принять! (N, I, V) X -----------? | -? | -? | -? | Принять! (N, I, W) | | | | | | | | | | | | !! Серверы расходятся во мнениях по стоимости | | X <>X->| ->| Принято (N, I, V) | | | <-|<-X<>X принято (N, I, W) | | | | | | | | | | | | !! Обнаружить столкновение и восстановить | | X <>X<>X<>X Accepted (N + 1, I, W) | <-----------X--X--X--X Response(W) | | | | | |
Обобщенный консенсус исследует взаимосвязь между операциями реплицированного конечного автомата и протоколом консенсуса, который его реализует. Главное открытие связано с оптимизацией Paxos, когда конфликтующие предложения могут применяться в любом порядке. т.е. когда предлагаемые операции являются коммутативными операциями для конечного автомата. В таких случаях могут быть приняты обе конфликтующие операции, что позволяет избежать задержек, необходимых для разрешения конфликтов, и повторно предлагать отклоненные операции.
Эта концепция далее обобщается на постоянно растущие последовательности коммутативных операций, некоторые из которых известны как стабильные (и, следовательно, могут выполняться). Протокол отслеживает эти последовательности, гарантируя, что все предложенные операции одной последовательности стабилизируются, прежде чем разрешить любую операцию, не коммутирующую с ними, стать стабильной.
Чтобы проиллюстрировать обобщенный Paxos, в приведенном ниже примере показан поток сообщений между двумя одновременно выполняющимися клиентами и реплицированным конечным автоматом, реализующим операции чтения / записи в двух различных регистрах A и B.
Прочитать(A) | Записать(A) | Прочитать(B) | Записать (B) | |
---|---|---|---|---|
Прочитать (A) | ||||
Запись (A) | ||||
Чтение (B) | ||||
Запись (B) |
Обратите внимание, что в этой таблице обозначает некоммутативные операции.
Возможная последовательность операций:
<1:Read(A), 2:Read(B), 3:Write(B), 4:Read(B), 5:Read(A), 6:Write(A)>
Начиная с 5: Чтение (A)
коммутирует с обоими 3: Запись (B)
и 4: Чтение (B)
, одна возможная перестановка, эквивалентная предыдущему порядку, следующая:
<1:Read(A), 2:Read(B), 5:Read(A), 3:Write(B), 4:Read(B), 6:Write(A)>
На практике коммутация происходит только тогда, когда операции предлагаются одновременно.
Ответы не показаны. Примечание: аббревиатуры сообщений отличаются от предыдущих потоков сообщений из-за специфики протокола, см. Полное обсуждение.
Client Leader Acceptor Learner | | | | | | | | !! Новый лидер начинает раунд | | X ----->| ->| ->| | | Подготовить (N) | | | <-----X- X- X | | Promise(N,null) | | X----->| ->| ->| | | Phase2Start (N, null) | | | | | | | | | | | | | | | | !! Предложения по одновременным поездкам на работу | X -------? | -----? | -? | -? | | | Предложить (ReadA) X -----------? | -----? | -? | -? | | | Предложить (ReadB) | | X ------ X -------------->| ->| Принято (N,) | | | <--------X--X-------->| ->| Принято (N, ) | | | | | | | | | | | | | | | | !! Нет конфликта, оба приняты | | | | | | | | Стабильный = | | | | | | | | | | | | | | | | !! Параллельно конфликтующие предложения X -----------? | -----? | -? | -? | | | Предложить ( ) | X --------? | -----? | -? | -? | | | Предложить (ReadB) | | | | | | | | | | X ------ X -------------->| ->| Принято (N, . ) | | | <--------X--X-------->| ->| Принято (N, . ) | | | | | | | | | | | | | | | | !! Конфликт обнаружен, лидер выбирает | | | | | | | | коммутативный порядок: | | | | | | | | V = | | | | | | | | | | X ----->| ->| ->| | | Phase2Start (N + 1, V) | | | <-----X- X- X-------->| ->| Принято (N + 1, V) | | | | | | | | Стабильный = . | | | | | | | | | | | | | | | | | | | | | | | | !! Более противоречивые предложения X -----------? | -----? | -? | -? | | | Предложить (WriteA) | X --------? | -----? | -? | -? | | | Предложить (ReadA) | | | | | | | | | | X ------ X -------------->| ->| Принято (N + 1, . ) | | | <--------X- X-------->| ->| Принято (N + 1, . ) | | | | | | | | | | | | | | | | !! Лидер выбирает порядок: | | | | | | | | W = | | | | | | | | | | X ----->| ->| ->| | | Phase2Start (N + 2, W) | | | <-----X- X- X-------->| ->| Принято (N + 2, W) | | | | | | | | Стабильный = . | | | | | | | | . | | | | | | | | | | | | | | | |
Приведенный выше поток сообщений показывает нам, что Generalized Paxos может использовать семантику операций, чтобы избежать коллизий при сбое спонтанного упорядочивания сети. Это позволяет протоколу работать быстрее, чем Fast Paxos. Однако при возникновении коллизии Generalized Paxos требуется два дополнительных обхода для восстановления. Эта ситуация проиллюстрирована операциями WriteB и ReadB в приведенной выше схеме.
В общем случае такие обходы неизбежны и происходят из-за того, что в течение одного раунда может быть принято несколько команд. Это делает протокол более дорогим, чем Paxos, когда конфликты часты. Будем надеяться, что возможны два возможных усовершенствования Generalized Paxos для улучшения времени восстановления.
Paxos также может быть расширен для поддержки произвольных отказов участников, включая ложные, фабрикация сообщений, сговор с другими участниками, выборочное неучастие и т. д. Эти типы неудач называются византийскими неудачами в честь решения, популяризированного Лампортом.
Византийский Паксос, представленный Кастро и Liskov добавляет дополнительное сообщение (Verify), которое распространяет информацию и проверяет действия других процессоров:
Клиент, предлагающий акцептор, обучающийся | | | | | | | X -------->| | | | | | Запрос | X --------->| ->| ->| | | Принимаю! (N, I, V) | | X <>X <>X | | Проверить (N, I, V) - ТРАНСЛЯЦИЯ | | <---------X--X--X------>| ->| Accepted (N, V) | <---------------------------------X--X Response(V) | | | | | | |
Fast Byzantine Paxos, представленный Мартином, и Alvisi устраняет эту дополнительную задержку, так как клиент отправляет команды непосредственно приемникам.
Обратите внимание, что сообщение «Принято» в Fast Byzantine Paxos отправляется всем приемникам и всем учащимся, тогда как Fast Paxos отправляет принятые сообщения только учащимся):
Обучающийся клиент-акцептор | | | | | | X ----->| ->| ->| | | Принимаю! (N, I, V) | X <>X <>X ------>| ->| Принято (N, I, V) - РАССЫЛКА | <-------------------X--X Response(V) | | | | | |
Сценарий сбоя одинаков для обоих протоколов; Каждый учащийся ожидает получения F + 1 одинаковых сообщений от разных получателей. Если этого не происходит, сами акцепторы также будут знать об этом (поскольку они обменивались сообщениями друг друга в раунде широковещательной рассылки), и правильные приемники будут ретранслировать согласованное значение:
Client Acceptor Learner | | | ! | | !! Один приемник неисправен X ----->| ->| ->! | | Принимаю! (N, I, V) | X <>X <>X ------>| ->| Принято (N, I, {V, W}) - ТРАНСЛЯЦИЯ | | | ! | | !! Учащиеся получают 2 разные команды | | | ! | | !! Исправьте ошибку уведомления получателя и выберите | X <>X <>X ------>| ->| Принято (N, I, V) - РАССЫЛКА | <-------------------X--X Response(V) | | | ! | |
С появлением высокоскоростных надежных сетей центров обработки данных, поддерживающих удаленный DMA (RDMA ), был проявлен значительный интерес к оптимизации Paxos для использования аппаратной разгрузки, в которой сетевая карта и сетевые маршрутизаторы обеспечивают надежность и контроль перегрузки сетевого уровня, освобождая центральный процессор хоста для других задач. Библиотека Derecho C ++ Paxos - это реализация Paxos с открытым исходным кодом, в которой исследуется этот параметр.
Derecho предлагает как классический Paxos, обеспечивающий надежность данных при полных последовательностях выключения / перезапуска, так и вертикальный Paxos (атомарная многоадресная рассылка) для репликации в памяти и синхронизации с конечным автоматом. Протоколы Paxos, используемые Derecho, необходимо было адаптировать для максимизации асинхронной потоковой передачи данных и устранения других источников задержки на критическом пути лидера. Это позволяет Derecho поддерживать полную скорость двунаправленной передачи данных RDMA. Напротив, хотя традиционные протоколы Paxos можно перенести в сеть RDMA, просто сопоставив операции отправки сообщений с собственными операциями RDMA, при этом на критическом пути остаются задержки туда и обратно. В высокоскоростных сетях RDMA даже небольшие задержки могут быть достаточно большими, чтобы предотвратить использование всей потенциальной полосы пропускания.