Gbcast

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

История

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

Термин «репликация конечного автомата» был впервые предложен Лесли Лэмпортом. и получил широкое распространение после публикации обзорной статьи, написанной Фредом Б. Шнайдером . Модель охватывает любую систему, в которой некоторый детерминированный объект (конечный автомат) реплицируется таким образом, что к репликам можно отказоустойчиво применять ряд команд. Реконфигурируемый конечный автомат — это такой автомат, который может изменять свое членство, добавляя новых участников или удаляя старые. Некоторые протоколы конечного автомата также могут выдерживать временную недоступность подмножества текущих участников, не требуя реконфигурации при возникновении таких ситуаций, включая Gbcast, а также Paxos. Широко цитируемый протокол Лампорта для репликации конечного автомата.

Репликация конечного автомата тесно связана с проблемой распределенного консенсуса. в котором набор процессов должен согласовать некоторый результат решения, например, победителя выборов. В частности, можно показать, что любое решение проблемы репликации конечного автомата также способно решить проблему распределенного консенсуса. Как следствие, результаты невозможности для распределенного консенсуса. применяются к решениям проблемы репликации конечного автомата. Последствия этого открытия обсуждаются в разделе «Жизнеспособность» .

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

Протокол Gbcast был впервые описан в публикации 1985 года, в которой обсуждалась инфраструктура, поддерживающая модель виртуальной синхронизации в Isis Toolkit. Дополнительные подробности были предоставлены в более поздней журнальной статье 1987 года: а версия протокола с открытым исходным кодом была выпущена разработчиками Корнелла в ноябре того же года. Isis использовала этот протокол в первую очередь для поддержания членства в группах процессов, но также предлагала API, который конечные пользователи могли вызывать напрямую. Технология стала широко использоваться начиная с 1988 года, когда система Isis была коммерциализирована и стала доступна поддержка. Коммерческая поддержка системы прекратилась в 1998 году, когда Stratus Computer, в то время материнская компания Isis Distributed Systems, переориентировалась исключительно на аппаратные решения для телекоммуникационной отрасли.

Примеры систем, которые использовали Isis в производственных условиях, включают Нью-Йоркскую фондовую биржу, где она использовалась в течение примерно десяти лет для управления настраиваемой, отказоустойчивой и самовосстанавливающейся инфраструктурой отчетности для торгового зала, для передачи котировок и торговых отчетов из системы «бэк-офиса», используемые биржей для отображения накладных расходов. Французская система управления воздушным движением продолжает использовать Isis; с 1996 года система используется для создания отказоустойчивых кластеров рабочих станций для использования авиадиспетчерами и надежной ретрансляции обновлений маршрутизации между центрами управления воздушным движением; со временем французская технология была принята и другими европейскими системами УВД. AEGIS ВМС США использует Isis с 1993 года для поддержки надежной и самовосстанавливающейся коммуникационной инфраструктуры. У Isis также было несколько сотен других производственных пользователей в сферах финансов, телекоммуникаций, управления процессами, SCADA и других критически важных инфраструктурных областях. Более подробную информацию можно найти в.

Постановка задачи

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

Набор членов группы меняется каждый раз, когда участник выходит из строя или присоединяется, а Gbcast также используется для поддержания членства в группе посредством специальных многоадресных рассылок, которые доставляются в приложение как события «нового представления», но которые также корректируют поддерживаемый список членов группы. библиотекой протоколов Gbcast. Таким образом, приложение видит ряд представлений членства, которые начинаются с «начального представления», когда присоединяется конкретный член группы, а затем развиваются с течением времени и упорядочиваются по отношению к другим событиям изменения представления и многоадресным сообщениям. Эти многоадресные рассылки доставляются всем исправным членам, перечисленным в представлении, во время которого запланирована доставка, - свойство, называемое виртуальной синхронизацией.

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

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

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

Процессы

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

Сеть

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

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

Для упрощения изложения мы предполагаем, что используется TCP -подобная схема подтверждения/повторной передачи, создающая иллюзию надежного, упорядоченного, неповторяющегося канала сообщений между каждой парой процессов. Тайм -аут возникает, если эта абстракция канала повторяет повторную попытку и не может получить подтверждение для некоторого сообщения. Используя те же TCP-подобные каналы, мы также можем поддерживать возможность «1 ко всем», при которой один процесс отправляет некоторое сообщение по своим каналам всем остальным членам некоторого представления некоторой группы. Это делается путем сопоставления запроса «1 ко всем» с несколькими сообщениями «1 ко всем». Обратите внимание, что в этих каналах «один ко всем» отсутствует какая-либо гарантия атомарности: если отправитель выйдет из строя во время отправки сообщения, оно может достичь только некоторых пунктов назначения.

Группы процессов и представления

Gbcast определяется относительно «группы процессов»: набора процессов. В развернутой системе такая группа может иметь имя (например, имя файла), способ первоначального обращения к группе и другие атрибуты, такие как параметры управления потоком. Однако подобные подробности здесь опущены для краткости.

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

Первоначальное членство в группе задается внешним агентом и определяет первое представление членства в группе.

Последующие представления членства возникают путем применения команд добавления и удаления и идентифицируются по порядковому номеру.

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

Многоадресные сообщения

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

Протокол Gbcast выполняет эти операции с рядом гарантий, обсуждаемых ниже.

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

Роли

Gbcast лучше всего понимать с точки зрения набора ролей.

Приложение

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

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

Входящие сообщения Gbcast доставляются через upcalls, как и уведомления об изменении просмотра.

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

Лидер

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

Обнаружение сбоев

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

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

Любой процесс, у которого истекло время ожидания, может объявить о сбое конечной точки связанного канала.

Если процесс узнает о сбое в каком-либо кортеже (идентификатор процессора, идентификатор процесса, номер воплощения), он включает эту информацию в следующее исходящее сообщение по всем каналам.

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

Входящее сообщение от нового воплощения отказавшего процесса рассматривается как сообщение от «нового» процесса.

Неудачный процесс

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

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

Новый лидер

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

Чтобы стать лидером, новый лидер должен выполнить протокол, описанный ниже.

Кворумы

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

Учитывая представление i с n членами {A,B,C….}, кворум представления — это любое мажоритарное подмножество членов этого представления. Обратите внимание, что это отличается от того, как этот термин определяется в системах, которые имеют статическое базовое членство: для Gbcast размер кворума будет меняться со временем по мере изменения членства в группе и определения новых представлений.

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

Чтобы гарантировать безопасность, Gbcast определяет три свойства безопасности и обеспечивает их сохранение независимо от характера сбоев:

Нетривиальность

Доставляются только многоадресные рассылки, фактически отправленные каким-либо членом группы. Если процесс получает сообщение от члена группы, которое, по его мнению, не удалось, он отклоняет эти сообщения.

Последовательность

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

Условная живучесть

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

Базовый Gbcast

Этот протокол используется в нормальных условиях.

Напомним, что в Gbcast каждый операционный процесс имеет текущее представление, и каждое представление определяет лидера. Только процесс, который считает себя лидером в текущем представлении, может инициировать новую многоадресную рассылку; другие участники должны ретранслировать многоадресные рассылки, отправляя их лидеру через соединения 1-к-1, а затем ожидая, пока лидер запустит протокол.

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

Шаг подготовки

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

Шаг обещания

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

Зафиксировать шаг

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

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

Обратите внимание, что лидер также мог узнать о неудачах на этапе подготовки или этапа предложения.

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

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

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

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

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

Этап доставки

Если участник получает сообщение Commit, он доставляет связанные сообщения или новые представления в приложение в том порядке, в котором они были предложены лидером. Лидер узнает, что этот шаг удался, когда получены подтверждения, используемые надежным каналом 1-к-1.

Поток сообщений: базовый Gbcast, простейший случай.

(Размер кворума = 2, view1={A,B,C})

Member   Leader        Members      Application Layer
            A          A  B  C       A  B  C
  |         |          |  |  |       |  |  |
  X-------->|          |  |  |       |  |  |  Request that the leader send a multicast M
  |         X--------->|->|->|       |  |  |  Propose(1.1: M) (View 1, sequence 1, message M)
  |         |<---------X--X--X       |  |  |  Promise(1.1)
  |         X--------->|->|->|       |  |  |  Commit(1.1)
  |         |<---------X--X--X------>M->M->M  Committed(1.1); Delivers M
  |         |          |  |  |       |  |  |

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

Простейшими случаями ошибок являются случаи, когда один или несколько участников выходят из строя, но кворум остается активным. В приведенном ниже примере группа состоит из {A,B,C}, где A играет роль лидера. C терпит неудачу на этапе обещания, и в надежном канале от лидера до процесса C происходит тайм-аут . Таким образом, лидер фиксирует доставку M, но одновременно инициирует протокол по удалению C из группы, которая фиксирует, создавая новое представление {A,B}. Если C на самом деле не потерпел неудачу, он теперь может вернуться в группу, но с новым номером воплощения: по сути, C должен вернуться в группу как C'. Любые сообщения от C к A или B будут отклонены с того момента, как каждый из них узнает о явной неудаче: A и B будут избегать C.

Поток сообщений: базовый Gbcast, сбой участника, кроме лидера.

(Размер кворума = 2, view1={A,B,C})

Member   Leader        Members      Application Layer 
            A          A  B  C       A  B  C
  |         |          |  |  |       |  |  |
  X-------->|          |  |  |       |  |  |  Request(M)
  |         X--------->|->|->|       |  |  |  Propose(1.1: M)
  |         |          |  |  *       |  |  *  !! C FAILS !!
  |         |<---------X--X          |  |     Promise(1.1)
  |         X--------->|->|          |  |     Commit(1.1); Propose(1.2: "remove C")
  |         |<---------X--X--------->M->M     Committed(M); Delivers M; Promise(1.2)
  |         X--------->|->|->|       |  |     Commit(1.2);
  |         |<---------X--X--X------>V->V     Committed(1.2); Delivers view2={A,B}
  |         |          |  |          |  |

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

Поток сообщений: базовый Gbcast, добавление участников {D,E,F}, отказ участника, кроме лидера.

В примере, показанном ниже, группе, которая изначально содержит участников {A,B,C}, предлагается добавить {D,E,F}, но член C терпит неудачу во время протокола. Запросы на изменение членства рассматриваются как особый вид многоадресной рассылки, и последовательность событий такая же. Таким образом, пример почти идентичен предыдущему, но теперь в приложение доставляется ряд новых событий представления. (Размер кворума = 2, view1={A,B,C})

Member   Leader        Members               Application Layer 
            A          A  B  C  D  E  F       A  B  C  D  E  F
  |         |          |  |  |                |  |  |  |  |  |
  X-------->|          |  |  |                |  |  |  |  |  |  Request("add D,E,F")
  |         X--------->|->|->|                |  |  |  |  |  |  Propose(1.1: "add D,E,F")
  |         |          |  |  *                |  |  *  |  |  |  !! C FAILS !!
  |         |<---------X--X                   |  |     |  |  |  Promise(1.1)
  |         X--------->|->|                   |  |     |  |  |  Commit(1.1); Propose(2.1: "remove C")
  |         |<---------X--X-----X--X--X------>V->V---->V->V->V  Committed(1.1); Deliver view2={A,B,C,D,E,F}; Promise(2.1)
  |         X--------->|->|---->|->|->|       |  |     |  |  |  Commit(2.1)
  |         |<---------X--X-----X--X--X------>V->V---->V->V->V  Committed(2.1); Deliver view3={A,B,D,E,F}
  |         |          |  |     |  |  |       |  |     |  |  |

В конце протокола новое активное представление — view3={A,B,D,E,F}, а новый размер кворума — 3. Но обратите внимание, что было «промежуточное» представление, view2={A,B. ,C,D,E,F} с размером кворума 4. Если бы лидер не получил 4 обещания на этапе предложения, который удалил C, он не смог бы запустить фазу фиксации для view3. Это иллюстрирует базовую политику: кворум, необходимый для фиксации нового представления, всегда зависит от размера предыдущего представления.

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

Следующий случай неудачи — это когда лидер терпит неудачу, в результате чего появляется новый лидер. Чтобы стать лидером, новый лидер сначала запускает протокол поглощения, а затем новый лидер может запустить базовый Gbcast, как указано выше. Протокол приема выглядит следующим образом:

Шаг запроса

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

Шаг списка обещаний

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

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

Повторите, если необходимо

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

Проверьте наличие кворума

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

Начни как новый лидер

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

Дуэль лидеров

Вполне возможно, что списки обещаний включают два или более различных предложений для одного и того же места. Это происходит (только), если первый лидер A отделился от системы, но, тем не менее, сделал предложение X , которое было замечено только небольшой (не кворумной) группой членов. Затем новый лидер Б успешно вступил во владение, но не узнал о предложении А (которое не могло быть реализовано). Теперь B предлагает Y, опять же при небольшом меньшинстве членов. Теперь считается, что B потерпел неудачу, и C взял на себя управление. C может узнать о предложениях X и Y для одного и того же слота. C должен игнорировать предложение, связанное со старшим лидером A, но сохранить предложение, связанное с новым лидером B: в этой ситуации предложение X не может достичь кворума и, следовательно, не может быть подтверждено, тогда как предложение Y, сделанное более поздний лидер, мог бы взять на себя обязательство (в противном случае, то есть, если бы X мог достичь кворума, B узнал бы о предложении X и, следовательно, повторил бы его; таким образом, поскольку B не узнал о X , X не должно было получить кворума).

Обратите внимание, что протокол поглощения C использует детерминистический порядок среди лидеров A и B, чтобы определить, что предложение X обречено, поскольку лидер B должен был избегать A, чтобы стать лидером. И наоборот, C должен предположить, что предложение Y может быть реализовано, даже если A подозревал, что B потерпел неудачу, потому что предложение Y пересекалось с этапом принятия C. Реализуется правило: путем последовательной нумерации лидеров и включения номера лидера в предложение. На этапе запроса новый лидер может затем использовать предложение лидера с большим номером, если он получает противоречивые предложения для одного и того же слота.

Подозрения на сбой в сочетании с исходящими сообщениями

Обратите внимание: новый лидер считает, что старый лидер потерпел неудачу, а также может полагать, что другие члены потерпели неудачу. Таким образом, фаза запроса и/или новая фаза предложения могут также нести совмещенные сообщения об ошибках для одного или нескольких участников . Это основное требование к протоколу, поскольку оно гарантирует, что эти участники впоследствии будут исключены: если от исключенного участника будет получено дальнейшее сообщение, получатель отклонит эти сообщения. Отсюда следует, что если какой-либо участник выполняет фазу списка обещаний для старого лидера L, никакие дальнейшие сообщения о предложениях или фиксации от L не будут обрабатываться этим участником. Из этого мы видим, что список обещаний, собранный новым лидером, будет полным и будет содержать все обещанные сообщения, которые могли бы достичь кворума в текущем представлении. Он также может содержать некоторые дополнительные обещанные сообщения, которые еще не достигли кворума.

Поток сообщений: базовый Gbcast, провал лидера, TakeOver, базовый Gbcast новым лидером

(Размер кворума = 2, просмотр 1 = {A,B,C})

Member   Leader        Members      Application Layer 
         A  B          A  B  C       A  B  C
  |      |             |  |  |       |  |  |
  X----->|             |  |  |       |  |  |  Request(M)
  |      X------------>|->|  |       |  |  |  Propose(1.1: M) !! Leader fails during send, Propose doesn't reach C !!
  |      *<------------X—-X  |       |  |  |  Promise(1.1) 
  |         |          *  |  |       *  |  |  !! A (THE LEADER) HAS FAILED !! 
  |         |             |  |          |  |  !! NEW LEADER: B !!
  |         ?------------>|->|          |  |  Inquire("B is taking over because A has failed")
  |         |<------------X--X          |  |  PromiseLists(1.1: M)
  |         X------------>|->|          |  |  Propose(1.1: M); Propose(1.2: "remove A")
  |         |<------------X--X--------->|  |  Promise(1.1); Promise(1.2) 
  |         X------------>|->|--------->|  |  Commit(1.1); Commit(1.2); 
  |         |<------------X--X-------->M;V->M;V  Committed(1.1); Committed(1.2); Delivers(M). Delivers view2={B,C}

Поток сообщений: базовый Gbcast, добавление участников {D,E,F}, отказ лидера.

В качестве примера более сложного случая, здесь лидер терпит неудачу в середине фиксации, что увеличивает размер представления.

(Размер кворума = 2, просмотр 1 = {A,B,C})

Member   Leader        Members                Application Layer 
         A  B          A  B  C  D  E  F       A  B  C  D  E  F
  |      |             |  |  |  |  |  |       |  |  |  |  |  |
  X----->|             |  |  |  |  |  |       |  |  |  |  |  |  Request("add D, E, F")
  |      X------------>|->|  |  |  |  |       |  |  |  |  |  |  Propose(1.1) !! Leader fails during send, Propose doesn't reach C !!
  |      *<------------X—-X  |  |  |  |       |  |  |  |  |  |  Promise(1.1) 
  |         |          *  |  |  |  |  |       *  |  |  |  |  |  !! A (THE LEADER) HAS FAILED !! 
  |         |             |  |  |  |  |          |  |  |  |  |  !! NEW LEADER: B !! 
  |         ?------------>|->|  |  |  |          |  |  |  |  |  Inquire("B is taking over because A has failed")
  |         |<------------X--X  |  |  |          |  |  |  |  |  PromiseLists(1.1: "add D, E, F");
  |         ?-------------|--|->|->|->|          |  |  |  |  |  Iterated Inquire("B is taking over because A has failed")
  |         |<------------|--|--X--X--X          |  |  |  |  |  PromiseLists(1.1: "add D, E, F");
  |         X------------>|->|->|->|->|          |  |  |  |  |  Propose(1.1: "add D, E, F"); Propose(2.1: "remove A")
  |         |<------------X--X--X--X--X          |  |  |  |  |  Promise(1.1); Promise(2.1); 
  |         X------------>|->|->|->|->|          |  |  |  |  |  Commit(1.1); Commit(2.1); 
  |         |<------------X--X->X->X->X -------->V->V->V->V->V  Committed(1.1); Committed(2.1); Delivers
                                                                   view2={A,B,C,D,E,F}. Delivers view3={B,C,D,E,F}

В этом примере мы видим итерацию запроса «в действии»: B узнает о протоколе, который добавляет {D,E,F} на первом этапе запроса, поэтому он повторяет запрос, на этот раз связываясь с D, E и F. Нет необходимости повторять запрос в точке C, поскольку это просто вернет ту же информацию, что была получена ранее.

В этом примере окончательная фиксация фактически приводит к последовательной доставке двух представлений членам B и C. Несмотря на то, что два предложения были отправлены одновременно, фиксация для представления 2 требует обещания от кворума представления 1, тогда как фиксация для представления 3 требует ответ кворума от членов view2. Хотя отправка первоначальных представлений явно не показана на диаграмме, присоединяющиеся участники не участвуют в протоколе 1.1, поскольку они не присоединяются к группе до представления2. Обратите внимание, что в элементах B и C возникает эффект конвейеризации: события, связанные с представлением 2, уже предлагаются, хотя события в представлении 1 все еще фиксируются.

Корректность

Чтобы показать, что Gbcast удовлетворяет нетривиальным требованиям, мы начнем с обратного отслеживания от произвольного действия по доставке до точки, в которой клиент запросил соответствующее событие; очевидно, что будут доставлены только те сообщения, которые были отправлены законным образом. Однако нетривиальность этого протокола идет дальше: мы также должны показать, что сообщения от данного участника доставляются только тогда, когда этот участник все еще является активным участником в некотором представлении. Соответственно, мы рассматриваем случай, когда лидер инициирует некоторую многоадресную рассылку, но затем происходит сбой до ее доставки. Здесь новый лидер либо обнаруживает ожидающее предложение и заказывает его до события изменения представления, либо новый лидер не может обнаружить ожидающее предложение, и в этом случае все члены нового представления будут избегать любого входящего сообщения с опозданием. от старого лидера. Таким образом, либо многоадресное сообщение доставляется, пока представление, в котором оно было отправлено, все еще находится в состоянии ожидания, либо оно не будет доставлено вообще.

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

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

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

Логическое разделение группы невозможно из-за правила исключения. Чтобы придерживаться какой-либо новой точки зрения, старый лидер должен получить обещания от кворума, придерживающегося текущей точки зрения. Новый лидер, вступающий во владение, узнает о любой точке зрения, которая могла бы стать приверженной. Таким образом, чтобы принять предложенное им следующее представление, ему потребуется взаимодействовать с кворумом этого промежуточного представления, если таковое имеется. В сценарии, который может привести к разделению, лидер А мог бы истечь по времени на B и продолжить создание последовательности новых взглядов и событий, исключающих B. Но в этом случае большинство старых или промежуточных взглядов члены узнают, что А считает, что Б потерпел неудачу, и будут избегать Б, когда тот спросит об этом. В любом случае B не может получить кворум и, следовательно, не может добиться прогресса. Симметричный аргумент показывает, что если B удастся определить новое представление, исключающее A, то A не сможет получить кворум для любого другого нового представления, которое он может попытаться предложить.

живость

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

Это свойство похоже на <>W, «самый слабый детектор отказов» для достижения консенсуса, но «сильнее», чем это определено Чандрой и Тоуэгом. Чтобы убедиться в этом, рассмотрим прогон, в котором взаимно подозрительный кворум возникает «слишком быстро» для того, чтобы процессы, ошибочно исключенные из представления, могли снова присоединиться к нему. Gbcast не добьется прогресса, и, действительно, группу придется закрыть и перезапустить.

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

Обсуждение: Обнаружение неисправностей

Протокол Gbcast предполагает, что вероятность ошибочного подозрения на сбой будет низкой; схема выходит из строя, если часто возникают подозрения на сбой и операционные процессы часто подозреваются как ошибочные. По аналогии рассмотрим протокол TCP , в котором невозможность получения подтверждения в конечном итоге приведет к разрыву соединения. TCP используется почти повсеместно, и если бы TCP-соединения часто прерывались, когда ни одна конечная точка не вышла из строя, это привело бы к огромным нарушениям в работе Интернета. Таким образом, таймауты устанавливаются консервативно. Аналогичное предположение требуется для систем, использующих Gbcast.

Напротив, существуют другие схемы обнаружения сбоев, такие как та, которую исследовали Чандра и Тоуег, которые могут привести к высокому уровню ошибочных подозрений на сбой. Некоторые протоколы, включая Paxos, способны выдерживать ошибочные подозрения на сбой без каких-либо дорогостоящих последствий. Является ли один подход по своей сути лучше другого, выходит за рамки данного обсуждения. Мы просто подчеркиваем, что подходы различаются, и что Gbcast будет неэффективен, если таймауты будут установлены слишком агрессивно.

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

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

Система Transis исследовала расширения протокола Gbcast, которые позволяют формировать несколько разделов, осуществлять независимый прогресс, а затем снова объединяться. Однако эта тема выходит за рамки настоящего обсуждения.

Обсуждение: Дуэль лидеров

В протоколе Paxos может возникнуть ситуация, когда два или более лидера «сражаются», предлагая разные команды для одного и того же слота. Это также может произойти в Gbcast.

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

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

Механизм избегания разрешает такие дуэли. Когда новый лидер получил кворум на этапе ЗАПРОС, это также лишило старого лидера возможности когда-либо снова достичь кворума для любого нового ПРЕДЛОЖЕНИЯ, которое он мог бы инициировать: большинство членов теперь избегают старого лидера. Таким образом, если какое-либо предложение пропущено новым лидером, это обязательно предложение, которое не достигло кворума членов и не достигнет кворума в будущем. Более того, новый лидер будет избегать членов, знающих о таком предложении, поскольку (когда он перестал ждать ответа на свой ЗАПРОС) он считает, что они потерпели неудачу. Любой член, узнавший о новых предложениях от нового лидера, также будет их избегать.

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

Би-симуляция, эквивалентная Paxos

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

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

1. Начните с базового протокола Paxos . Добавьте номер воплощения процесса, чтобы отличить присоединяющийся процесс от процесса, который постоянно был членом представления. Наведите порядок среди членов группы по возрасту, назначьте лидером самого старшего члена (разрывающего лексикографические связи). Нелидеры подают запросы через лидера.
2. Оба протокола допускают пакетную обработку запросов: базовый Paxos имеет параметр параллелизма альфа: лидер может одновременно запускать максимум альфа-экземпляров протокола. Gbcast позволяет лидеру предлагать несколько событий в одном экземпляре протокола, например доставку сообщений или просмотр событий.
3. Паксос обычно не требует надежной и упорядоченной связи. Измените протокол для работы с надежной абстракцией канала «один-к-одному» (сообщение «один-ко-многим» будет отправлено Paxos по набору каналов «один-к-одному»). Теперь мы можем предположить, что любое отправленное сообщение будет либо получено и доставлено по порядку, либо на стороне отправителя произойдет тайм-аут.
4. Номер слота Paxos станет порядковым номером Gbcast. Номер избирательного бюллетеня Paxos, по сути, преобразуется в номер лидера предложения, используемый для различения конфликтующих предложений на этапе запроса.
5. Определите категорию команд изменения представления, которые действуют путем добавления или удаления процессов из членства в группе. Внедрите механизм обнаружения сбоев, используемый в Gbcast, с просьбой к лидеру удалить всех участников, у которых истекло время ожидания. Участник, удаленный из группы, который восстанавливает соединение с группой, должен воссоединиться с новым номером воплощения. Просмотры отчетов по обращениям в приложение.
6. Базовый Paxos может предлагать многоадресную рассылку только кворуму членов группы, поэтому у типичного участника могут быть пробелы в списке команд. Вот почему в Паксосе учащийся должен прочитать кворум участников и объединить их списки команд. В нашем модифицированном протоколе любая многоадресная рассылка предлагается всем исправным членам, а неработающие элементы исключаются из поля зрения. Таким образом, в отличие от Paxos, наш модифицированный протокол обладает тем свойством, что любой отдельный действующий участник имеет полный список зафиксированных событий. По сути, протокол имеет кворум записи, равный текущему размеру представления членства, и кворум чтения, равный 1. Это может быть удобно при создании приложений, которые поддерживают фактическое состояние базы данных или объекта и для которых неудобно представлять состояние. как серия обновлений в списках команд, которые необходимо объединить, чтобы узнать фактическую последовательность событий.

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

Отсюда следует, что Gbcast и Paxos могут быть преобразованы друг в друга без изменения предположений и с одинаковыми свойствами корректности. Очевидно, что протоколы не очень похожи, но между ними есть глубокая связь. Действительно, можно сделать более сильное утверждение: любая последовательность событий доставки, представленная Gbcast, также может возникнуть в каком-то запуске Paxos, и наоборот: любая последовательность изученных событий из Paxos также может возникнуть в каком-то запуске Gbcast.

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

Краткое описание различий между Paxos и Gbcast

• Gbcast не имеет устойчивого состояния: протокол не ведет журнал событий на диске, а долговечность рассматривается как свойство, специфичное для приложения. Напротив, Paxos гарантирует долговечность: после восстановления после полного отключения системы приложение Paxos все равно сможет изучить полный журнал полученных сообщений.
• На этапе предложения Gbcast должен дождаться ответов от всех участников (или максимального тайм-аута, а затем подозревать остальных), вместо того, чтобы добиваться прогресса с самым быстрым кворумом. В Gbcast цена подозрения на сбой высока, и протокол может перестать работать, если подозревается слишком много сбоев, что вынуждает уровень управления перезапускать всю группу приложений. Таким образом, на практике Gbcast требует консервативных настроек таймаута по сравнению с Paxos.
• При использовании Gbcast в случае возникновения ошибки (например, подозрения на рабочий процесс и его отключение) этот процесс должен завершиться (он может повторно присоединиться под другим именем). В Paxos, если f>0, если процесс не может участвовать в экземпляре протокола, он может продолжать участвовать в последующих экземплярах протокола без ошибок.
• Операционные члены представления никогда не будут иметь пробелов в своих списках команд с помощью Gbcast (каждый член имеет полное состояние). При использовании Paxos у оперативных членов могут возникать пробелы в списках команд (учащиеся объединяют кворум списков в Paxos, чтобы «заполнить» эти пробелы).
• В Paxos для предложения нескольких команд мы используем альфа>1, но в этом случае команды могут выполняться в порядке, отличном от того, в котором они были инициированы (один случай, в котором наблюдается этот проблемный сценарий, включает в себя дуэль лидеров; лидер А предлагает команды a1 и a2, а лидер B предлагает команды b1 и b2, затем они терпят неудачу, и лидер C, вступая во владение, в конечном итоге выполняет b2, а затем a1: результат, который может быть нежелателен для приложений, инициировавших запросы; ). С помощью Gbcast лидер может инициировать несколько команд, выдав одно предложение, описывающее серию действий. Группа будет задействована одновременно, поэтому порядок посвящения будет соблюдаться.
• При использовании Gbcast команда доставляется в том виде, в котором она была инициирована. Реконфигурируемый Paxos может фиксировать команду в слоте, связанном с представлением членства, до активного представления членства в момент фиксации. Таким образом, в Paxos, если приложение каким-либо образом чувствительно к просмотру, команды должны содержать идентификатор представления, чтобы получатели могли определить, является ли команда еще выполнимой.
• Gbcast не требует остановки протокола при изменении конфигурации: частота новых предложений может быть постоянной даже при изменении членства. Для многих реализаций реконфигурируемого Paxos это не так.
• Как в Gbcast, так и в Paxos реконфигурация возможна только в том случае, если кворум предыдущего представления доступен и может подтвердить новое представление. Однако в Paxos требование также распространяется на изучение результатов команд, предложенных для слотов, связанных со старым представлением. На практике это может привести к тому, что вычисление реконфигурации Paxos займет более длительный период, чем для Gbcast, в котором любое состояние хранится в приложении, а не в долгоживущем списке команд: Paxos не может отменить состояние, связанное со старым представлением, до тех пор, пока новое представление активно, и все реплики запомнили старое состояние.
• Gbcast не требует протокола сбора мусора, поскольку, поскольку каждое сообщение или представление фиксируется и сообщается приложению, оно может быть отброшено. Paxos поддерживает состояние, используя схему кворума в журналах команд на своих приемниках, и требует протокола сбора мусора для освобождения этих командных слотов после того, как результат зафиксирован и все учащиеся (реплики) узнали результат.

Сравнение живости

И Paxos, и Gbcast подлежат результату невозможности FLP. Таким образом, ни один из протоколов не может быть гарантированно работоспособным при всех возможных условиях. В лучшем случае мы можем говорить об условиях, при которых гарантируется работоспособность, выраженных в виде предикатов механизма обнаружения сбоев: если условие жизнеспособности выполняется, то протокол будет работоспособным. Условия жизни Basic Paxos и Gbcast схожи, но не идентичны.

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

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

Например, если мы начнем с группы, содержащей {AB,C}, и создадим расширенный сетевой раздел, Paxos возобновит работу после разрешения сетевого раздела, но Gbcast отключится навсегда, и какой-либо форме инфраструктуры управления может потребоваться перезапустить систему. Если необходимо сохранить состояние группы после сбоя, такая инфраструктура определит последнего члена, у которого произошел сбой , и перезапустит группу, используя некоторую форму контрольной точки, сохраненную этим последним участником.

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

Необходимость государственной передачи

Такие системы, как Isis, которые реализуют Gbcast, обычно предоставляют механизм передачи состояния: в момент доставки нового представления, показывающего какого-либо присоединяющегося члена, какой-то существующий член делает контрольную точку своей копии состояния группы. Затем оно копируется новому участнику, который загружает контрольную точку как исходное состояние группы на момент присоединения. (Различные схемы внешнего копирования могут использоваться для предварительной загрузки некоторого состояния перед объединением в случаях, когда состояние слишком велико для передачи таким способом в последний момент). Передача состояния необходима, поскольку в Gbcast, если участник исключен из группы, он больше не будет получать обновления. Gbcast обычно используется приложениями, которые сохраняют свое состояние в памяти и применяют обновления одно за другим по мере их получения, поэтому при возникновении пробела реплика перестает быть полезной.

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

Какой протокол репликации динамически реконфигурируемого конечного автомата появился первым?

Протокол Gbcast был опубликован в начале периода, когда было введено несколько протоколов конечных автоматов, способных управлять собственным членством: Gbcast, репликация со штампом представления (Oki и Liskov). ), Базовый Паксос (Лэмпорт ), протокол частичной синхронизации Дворка, Линча и Стокмейера, и т. д. Среди них Gbcast был опубликован первым в статьях, вышедших в 1985 и 1987 годах; остальные были опубликованы, начиная с 1988 года. Таким образом, можно утверждать, что Gbcast действительно был первым протоколом Paxos. Такое утверждение, однако, рассматривает «Paxos» как довольно широкий термин, охватывающий семейство протоколов, которые реализуют репликацию конечного автомата, поддерживают динамическую реконфигурацию своего членства и имеют одинаковые свойства корректности, но различаются по условиям их работоспособности. Согласно этому определению, Gbcast является протоколом Paxos.

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

Таким образом, на вопрос нет ответа, если его не уточнить, и ответ может быть разным в зависимости от используемого определения эквивалентности.

См. также

• Паксос (информатика)
• Виртуальная синхронизация
• Атомная трансляция
• Консенсус (информатика)
• Надежная многоадресная рассылка
• Свойства безопасности и живучести