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

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

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

Протокол Paxos был впервые представлен в 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, следующие предположения и определения сделаны явными. Методы расширения области применения известны в литературе и не рассматриваются в этой статье.

Процессоры [ править ]

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

Сеть [ править ]

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

Количество процессоров [ править ]

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

Действительность (или нетривиальность )

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

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

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

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

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

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

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

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

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

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

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

Базовый Паксос [ править ]

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

Фаза 1 [ править ]

Этап 1а: подготовка [ править ]

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

Фаза 1b: обещание [ править ]

Любой из принимающих ожидает сообщения о подготовке от любого из предлагающих . Если Acceptor получает сообщение Prepare, Acceptor должен посмотреть на номер идентификатора n только что полученного сообщения Prepare . Есть два случая.

Если n больше, чем все предыдущие номера предложений, полученные от любого из предлагающих, акцептант, то акцептант должен вернуть сообщение, которое мы называем «обещанием», предлагающему, чтобы игнорировать все будущие предложения, имеющие номер меньше чем п . Если Акцептатор принял предложение в какой-то момент в прошлом, он должен включать номер предыдущего предложения, скажем, m , и соответствующее принятое значение, скажем, w , в свой ответ Предлагающему.

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

Фаза 2 [ править ]

Этап 2а: принять [ изменить ]

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

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

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

Этап 2b: принято [ править ]

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

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

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

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

Когда раунды терпят неудачу [ править ]

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

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

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

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

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

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

Базовый Paxos без сбоев [ править ]

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

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

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

Случаи ошибок в базовом Paxos [ править ]

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

Базовый Paxos, когда Acceptor выходит из строя [ править ]

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

Клиент, предлагающий акцептор, обучающийся | | | | | | | X --------> | | | | | | Запрос | X ---------> | -> | -> | | | Подготовить (1) | | | | ! | | !! НЕУДАЧА !! | | <--------- X - X | | Обещание (1, {Va, Vb, null}) | X ---------> | -> | | | Принять! (1, V) | | <---------X--X---------> | -> | Принято (1, V) | <--------------------------------- X - X Ответ | | | | | |

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

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

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

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

В этом случае Претендент терпит неудачу после того, как предложит значение, но до того, как будет достигнуто соглашение. В частности, он терпит неудачу в середине сообщения Accept, поэтому только один Acceptor из кворума получает значение. Тем временем избирается новый Лидер (Предлагающий) (но это не показано подробно). Обратите внимание, что в этом случае есть 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--X------> | -> | Принято (2, V) | <--------------------------------- X - X Ответ | | | | | | |

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

Самый сложный случай - когда несколько предлагающих считают себя лидерами. Например, текущий лидер может потерпеть неудачу и позже восстановиться, но другие предлагающие уже повторно выбрали нового лидера. Выздоровевший лидер еще не усвоил этого и пытается начать один раунд конфликта с нынешним лидером. На диаграмме ниже показано 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, Ва) | | | <--------- X - X - X | | Нак (3) | | | | | | | | !! НОВЫЙ ЛИДЕР пытается 4 | | X ---------> | -> | -> | | | Подготовить (4) | | | <--------- X - X - X | | Обещание (4, {null, null, null}) | | | | | | | | !! СТАРЫЙ ЛИДЕР предлагает, но отказано | X ------------> | -> | -> | | | Принимаю! (3, Vb) | | <------------ X - X - X | | Нак (4) | | | | | | | | ... и так далее ...

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 | | Обещание (N, I, {Va, Vb, Vc}) | X ---------> | -> | -> | | | Принимаю! (N, I, V) | | <---------X--X--X------> | -> | Принято (N, I, V) | <--------------------------------- X - X Ответ | | | | | | |

где 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 Ответ | | | | | | |

Multi-Paxos, когда роли свернуты [ править ]

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

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

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

Multi-Paxos, когда роли свернуты, а лидер устойчив [ править ]

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

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

Оптимизация [ править ]

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

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

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

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

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

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

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

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

Дешевые Паксо [ править ]

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

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

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

Поток сообщений: Cheap Multi-Paxos [ править ]

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

 {Acceptors}Предлагающий Главный Aux Learner| | | | | | -- Фаза 2 --X -----------> | -> | -> | | | Принимаю! (N, I, V)| | | ! | | --- НЕУДАЧА! ---| <-----------X--X---------------> | Принято (N, I, V)| | | | | - Обнаружена неисправность (принято только 2) -X -----------> | -> | -------> | | Accept! (N, I, V) (повторно передать, включить Aux)| <-----------X--X--------X------> | Принято (N, I, V)| | | | | - Перенастроить: кворум = 2 -X -----------> | -> | | | Accept! (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! Сообщения нового раунда , которые Accepted как обычно. Этот метод скоординированного восстановления требует четырех задержек сообщений от клиента к учащемуся.

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

Поток сообщений: Fast Paxos, неконфликтный [ править ]

Клиент Лидер Acceptor Learner | | | | | | | | | X ---------> | -> | -> | -> | | | Любой (N, I, Recovery) | | | | | | | | X -------------------> | -> | -> | -> | | | Принимаю! (N, I, W) | | <---------X--X--X--X------> | -> | Принято (N, I, W) | <------------------------------------ X - X Ответ (Вт) | | | | | | | |

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

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

Клиент Лидер 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 Ответ (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-----> | -> | Принято (N + 1, I, W) | <--------------------------------- X - X Ответ (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 Принято (N + 1, I, W) | <----------- X - X - X - X Ответ (Вт) | | | | | |

Обобщенный Паксос [ править ]

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

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

Пример [ править ]

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

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

	Прочитать)	Написать)	Читать (B)	Написать (B)
Прочитать)
Написать)
Читать (B)
Написать (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)> 

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

Поток сообщений: Generalized Paxos (пример) [ править ]

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

Клиент Лидер Acceptor Learner | | | | | | | | !! Новый лидер начинает раунд | | X -----> | -> | -> | | | Подготовить (N) | | | <----- X- X- X | | Обещание (N, ноль) | | X -----> | -> | -> | | | Phase2Start (N, ноль) | | | | | | | | | | | | | | | | !! Предложения по одновременным поездкам | X -------? | -----? | -? | -? | | | Предложить (ReadA) 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 = <ReadA, WriteB, ReadB> | | | | | | | | | | X -----> | -> | -> | | | Phase2Start (N + 1, В) | | | <----- X- X- X --------> | -> | Принято (N + 1, V) | | | | | | | | Стабильный = <ReadA, ReadB>. | | | | | | | | <ReadA, WriteB, ReadB> | | | | | | | | | | | | | | | | !! Более противоречивые предложения X -----------? | -----? | -? | -? | | | Предложить (WriteA) | X --------? | -----? | -? | -? | | | Предложить (ReadA) | | | | | | | | | | X ------ X --------------> | -> | Принято (N + 1, <WriteA>. <ReadA>) | | | <-------- X- X --------> | -> | Принято (N + 1, <ReadA>. <WriteA>) | | | | | | | | | | | | | | | | !! Лидер выбирает порядок: | | | | | | | | W = <WriteA, ReadA> | | | | | | | | | | X -----> | -> | -> | | | Phase2Start (N + 2; W) | | | <----- X- X- X --------> | -> | Принято (N + 2, W) | | | | | | | | Стабильный = <ReadA, ReadB>. | | | | | | | | <ReadA, WriteB, ReadB>. | | | | | | | | <WriteA, ReadA> | | | | | | | |

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

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

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

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

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

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

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

Поток сообщений: византийский мультипаксос, устойчивое состояние [ править ]

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

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

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

Поток сообщений: Fast Byzantine Multi-Paxos, устойчивое состояние [ править ]

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

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

Поток сообщений: Fast Byzantine Multi-Paxos, сбой [ править ]

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

Адаптация Paxos для сетей RDMA [ править ]

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

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

Использование Paxos в производстве [ править ]

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

См. Также [ править ]

• Алгоритм консенсуса Чандры – Туега
• Государственный аппарат
• Плот

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

Внешние ссылки [ править ]

• Домашняя страница Лесли Лэмпорта
• Paxos Made Simple
• Paxos сделан умеренно сложным
• Возвращаясь к алгоритму Паксоса
• Paxos Commit
• Технический документ Google: Служба распределенной блокировки Chubby
• Технический документ Google: Bigtable - распределенная система хранения структурированных данных
• Обзор алгоритмов Paxos (2007)
• Служба открытой репликации OpenReplica
• FTFile: Библиотека отказоустойчивых файлов
• Библиотека Isis2 (примитив SafeSend - это бесплатная реализация Paxos с открытым исходным кодом)
• Mencius - круговой вращающийся Paxos для геораспределенных систем
• WANdisco - Решения Active-Active Replication для Hadoop, Subversion и GIT
• libpaxos, набор реализаций алгоритма Paxos с открытым исходным кодом
• libpaxos-cpp, реализация алгоритма распределенного консенсуса paxos на C ++
• JBP - Ява Византийский Паксос
• erlpaxos, Paxos от Erlang
• paxos - Прямая реализация paxos на Python и Java
• Manhattan Paxos (mpaxos), Paxos на C, поддержка нескольких групп paxos и эффективных транзакций между ними.
• Кластеризация с Neo4j
• HT-Paxos
• PaxosStore, реализация paxos в WeChat
• LWT в Кассандре
• Google TechTalks: алгоритм Paxos