Paxos (информатика)

редактировать

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

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

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

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

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

Содержание

  • 1 История
  • 2 Предположения
    • 2.1 Процессоры
    • 2.2 Сеть
    • 2.3 Количество процессоров
  • 3 Роли
    • 3.1 Кворумы
    • 3.2 Номер предложения и согласованное значение
  • 4 Свойства безопасности и живучести
  • 5 Типичное развертывание
  • 6 Базовый Paxos
    • 6.1 Этап 1
      • 6.1.1 Этап 1a: подготовка
      • 6.1.2 Этап 1b: Promise
    • 6.2 Фаза 2
      • 6.2.1 Фаза 2a: Принято
      • 6.2.2 Фаза 2b: Принято
    • 6.3 Когда раунды терпят неудачу
    • 6.4 Paxos можно использовать для выбора лидера
    • 6.5 Графическое представление потока сообщений в базовом Paxos
      • 6.5.1 Базовый Paxos без сбоев
      • 6.5.2 Случаи ошибок в базовом Paxos
      • 6.5.3 Базовый Paxos при отказе приемника
      • 6.5.4 Базовый Paxos при резервном учащийся терпит неудачу
      • 6.5.5 Basic Paxos, когда Proposer терпит неудачу
      • 6.5.6 Basic Paxos при конфликте нескольких предлагающих
  • 7 Multi-Paxos
    • 7.1 Графическое представление потока сообщений в Multi-Paxos
      • 7.1.1 Multi-Paxos без сбоев
      • 7.1.2 Multi-Paxos, когда этап 1 можно пропустить
      • 7.1.3 Multi-Paxos, когда роли свернуты
      • 7.1.4 Multi-Paxos, когда роли свернуты, а лидер остается стабильным
  • 8 Оптимизация
  • 9 Cheap Paxos
    • 9.1 Поток сообщений: дешевый Multi-Paxos
  • 10 Fast Paxos
    • 10.1 Поток сообщений: Fast Paxos, неконфликтный
    • 10.2 Поток сообщений: Fast Paxos, конфликтующие предложения
    • 10.3 Поток сообщений: Fast Paxos с нескоординированным восстановлением, свернутые роли
  • 11 Обобщенный Paxos
    • 11.1 Пример
    • 11.2 Поток сообщений: Обобщенный Paxos (пример)
    • 11.3 Производительность
  • 12 Византийский Paxos
    • 12.1 Поток сообщений: Византийский Multi-Paxos, устойчивое состояние
    • 12.2 Поток сообщений: Fast Byzantine Multi-Paxos, устойчивое состояние
    • 12.3 Поток сообщений: Fast Byzantine Multi-Paxos, сбой
  • 13 Адаптация Paxos для сетей RDMA
  • 14 Использование Paxos в производстве
  • 15 См. Также
  • 16 Ссылки
  • 17 Внешние ссылки

История

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

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

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

Допущения

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

Процессоры

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

Сеть

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

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

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

Роли

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

Клиент
Клиент отправляет запрос в распределенную систему и ждет ответа. Например, запрос записи в файл на распределенном файловом сервере.
Acceptor (Voters)
Acceptors действуют как отказоустойчивая «память» протокола. Акцептаторы собираются в группы, называемые кворумами. Любое сообщение, отправленное Получателю, должно быть отправлено в Кворум Получателей. Любое сообщение, полученное от Акцептора, игнорируется, если только копия не получена от каждого Акцептора в Кворуме.
Предлагающий
Предлагающий защищает запрос клиента, пытаясь убедить Акцептирующих согласиться с ним, и действует как координатор для продвижения протокола вперед при возникновении конфликтов.
Учащийся
Учащиеся действуют как фактор репликации для протокола. После того, как запрос клиента был согласован с принимающими сторонами, учащийся может предпринять действия (то есть: выполнить запрос и отправить ответ клиенту). Чтобы повысить доступность обработки, можно добавить дополнительных учащихся.
Лидер
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 определяет три свойства и гарантирует, что первые два всегда сохраняются, независимо от характера отказов:

Валидность (или нетривиальность)
Можно выбрать и изучить только предложенные значения.
Согласие (или последовательность, или безопасность)
Никакие два разных ученика не могут учиться разные значения (или не может быть более одного определенного значения)
Прекращение (или жизнеспособность)
Если значение C было предложено, то в конечном итоге учащийся L узнает некоторое значение (если достаточно процессоры остаются исправными).

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

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

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

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

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

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

Basic Paxos

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

Этап 1

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

A Предлагающий создает сообщение, которое мы называем «Подготовить» и обозначается номером n. Обратите внимание, что n - это не значение, которое должно быть предложено и, возможно, согласовано, а просто число, которое однозначно идентифицирует это начальное сообщение предлагающим (для отправки принимающим). Число n должно быть больше любого числа, использованного этим Предлагающим в любом из предыдущих сообщений о подготовке. Затем он отправляет сообщение Prepare, содержащее n, в кворум из Acceptors. Обратите внимание, что сообщение Prepare содержит только число n (то есть, оно не обязательно должно содержать, например, предлагаемое значение, часто обозначаемое v). Претендент решает, кто входит в Кворум. Предлагающий не должен инициировать Paxos, если он не может связаться, по крайней мере, с кворумом принимающих.

Фаза 1b: обещание

Любой из принимающих ожидает сообщения о подготовке от любого из предлагающих. Если Acceptor получает сообщение Prepare, Acceptor должен посмотреть на номер идентификатора n только что полученного сообщения Prepare. Есть два случая.
Если n больше, чем каждый предыдущий номер предложения, полученный Акцептатором от любого из Претендентов, то Акцептатор должен вернуть сообщение, которое мы называем «Обещанием», Претенденту, чтобы игнорируйте все будущие предложения с номером меньше n. Если Акцептатор принял предложение в какой-то момент в прошлом, он должен включить номер предыдущего предложения, скажем m, и соответствующее принятое значение, скажем, w, в свой ответ Предлагающему.
В противном случае (то есть n равно меньше или равно любому предыдущему номеру предложения, полученному от любого Предлагающего Акцептатором) Акцептатор может проигнорировать полученное предложение. В этом случае для работы Paxos не нужно отвечать. Однако в целях оптимизации отправка ответа с отказом (Nack ) сообщит Предлагающему, что он может остановить свою попытку достичь консенсуса с предложением n.

Фаза 2

Фаза 2a: Accept

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

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

Фаза 2b: Принято

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

Обратите внимание, что Акцептатор может принимать несколько предложений. Это может произойти, когда другой предлагающий, не зная о новом значении, начинает новый раунд с более высоким идентификационным номером n. В этом случае Acceptor может пообещать, а затем принять новое предложенное значение, даже если он принял другое ранее. Эти предложения могут даже иметь разные значения при наличии определенных сбоев. Тем не менее, протокол Paxos гарантирует, что Акцептаторы в конечном итоге согласятся с единым значением.

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

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

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

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

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

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

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

Базовый Paxos без сбоев

На схеме ниже есть 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).

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

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

Базовый Paxos при отказе акцептора

На следующей диаграмме один из акцепторов в кворуме выходит из строя, поэтому размер кворума становится равным 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 при отказе избыточного учащегося

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

Ученик, предлагающий клиента, принимающий | | | | | | | X -------->| | | | | | Запрос | X --------->| ->| ->| | | Подготовить (1) | | <---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->| ->| ->| | | Принимаю! (1, V) | | <---------X--X--X------>| ->| Принято (1, V) | | | | | | ! !! ПОТЕРПЕТЬ НЕУДАЧУ !! | <---------------------------------X Response | | | | | |

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

В этом случае предлагающий терпит неудачу после предложения значения, но до достижения соглашения. В частности, он не работает в середине сообщения 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 | | | | | | |

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

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

Multi-Paxos

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

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

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

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

Multi-Paxos без сбоев

На следующей диаграмме только один экземпляр (или «выполнение») показан базовый протокол 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).

Multi-Paxos, когда фаза 1 может быть пропущена

В этом случае экземпляры подпоследовательности базового протокола 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, когда роли свернуты

Обычное развертывание 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 | | | |

Multi-Paxos, когда роли свернуты, а лидер остается неизменным

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

Клиентские серверы X -------->| | | Запрос | X->| ->| Принимаю! (N, I + 1, W) | X <>X <>X Accepted (N, I + 1) | <--------X | | Response | | | |

Оптимизация

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

«Мы можем сохранять сообщения за счет дополнительной задержки сообщения, имея одного выдающегося учащегося, который информирует других учащихся, когда узнает, что значение было выбрано. Принимающие затем отправляют принятые сообщения только выдающемуся учащемуся. в большинстве приложений роли лидера и выдающегося ученика выполняет один и тот же процессор.
«Лидер может послать свои Prepare и Accept! сообщения только кворуму принимающих. Пока все принимающие в этом кворуме работают и могут общаться с лидером и учениками, у принимающих, не входящих в кворум, нет необходимости что-либо делать.
«Принимающим безразлично, какое значение выбрано. Они просто отвечают на сообщения« Подготовить »и« Принять! », Чтобы гарантировать, что, несмотря на сбои, можно выбрать только одно значение. Однако, если акцептор действительно узнает, какое значение было выбрано, он может сохранить значение в стабильном хранилище и стереть любую другую информацию, которую он там сохранил. Если принимающий позже получит сообщение Prepare или Accept !, вместо выполнения своего действия Phase1b или Phase2b он может просто проинформировать лидера о выбранном значении.
«Вместо того, чтобы посылать значение v, лидер может послать хеш v некоторым получателям в своем Accept! Сообщения. Обучающийся узнает, что v выбрано, если он получает сообщения Accepted для v или его хэш от кворума принимающих, и по крайней мере одно из этих сообщений содержит v, а не его хэш. Однако лидер может получать сообщения Promise, которые сообщают ему хэш значения v, которое он должен использовать в своем действии Phase2a, не сообщая ему фактическое значение v. Если это произойдет, лидер не сможет выполнить свое действие Phase2a, пока не свяжется с некоторыми процесс, который знает v. "
" Предлагающий может отправить свое предложение только лидеру, а не всем координаторам. Однако для этого требуется, чтобы результат алгоритма выбора лидера передавался предлагающим, что может быть дорогостоящим. Так что, возможно, лучше было бы позволить предлагающему отправить свое предложение всем координаторам. (В этом случае только сами координаторы должны знать, кто является лидером.)
«Вместо того, чтобы каждый принимающий отправлял принятые сообщения каждому учащемуся, принимающие могут отправлять свои принятые сообщения лидеру, а лидер может информировать учащихся, когда значение было выбрано. Однако это добавляет дополнительную задержку сообщения.
«Наконец, обратите внимание, что фаза 1 не нужна для раунда 1.. Лидер раунда 1 может начать раунд, отправив Accept! сообщение с любым предложенным значением. "

Cheap Paxos

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

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

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

Поток сообщений: дешевый Multi-Paxos

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

{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

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

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

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

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

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

Client Leader Acceptor Learner | | | | | | | | | X --------->| ->| ->| ->| | | Любой (N, I, Recovery) | | | | | | | | X ------------------->| ->| ->| ->| | | Принять! (N, I, W) | | <---------X--X--X--X------>| ->| Принято (N, I, W) | <------------------------------------X--X Response(W) | | | | | | | |

Поток сообщений: Fast Paxos, конфликтующие предложения

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

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) | | | | | | | | |

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

(объединенные роли 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, когда конфликтующие предложения могут применяться в любом порядке. т.е. когда предлагаемые операции являются коммутативными операциями для конечного автомата. В таких случаях могут быть приняты обе конфликтующие операции, что позволяет избежать задержек, необходимых для разрешения конфликтов, и повторно предлагать отклоненные операции.

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

Пример

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

Таблица коммутативности
Прочитать(A)Записать(A)Прочитать(B)Записать (B)
Прочитать (A)Нет
Запись (A)Нет Нет
Чтение (B)Нет
Запись (B)Нет Нет

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

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

<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)>

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

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

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

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 для улучшения времени восстановления.

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

Византийский Paxos

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

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

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

Клиент, предлагающий акцептор, обучающийся | | | | | | | 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 отправляет принятые сообщения только учащимся):

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

Обучающийся клиент-акцептор | | | | | | X ----->| ->| ->| | | Принимаю! (N, I, V) | X <>X <>X ------>| ->| Принято (N, I, V) - РАССЫЛКА | <-------------------X--X Response(V) | | | | | |

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

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

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) | | | ! | |

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

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

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

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

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

См. также

Ссылки

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

Последняя правка сделана 2021-06-01 06:43:24
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте