Глава 14. Консенсус

Некое широковещание это абстракция взаимодействия, часто применяемая в распределённых системах. Алгоритмы широковещания используются для рассеивания сведений по некому набору процессов. Существует много алгоритмов широковещания, делающих различные предположения и предоставляющих различные гарантии. Широковещание является неким важным примитивом и применяется во множестве мест, включая и алгоритмы консенсуса. Мы уже обсуждали одну из форм широковещания - рассеяние gossip (см. раздел Рассеивание Gossip).

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

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

Для надёжности широкого вещания необходимо обеспечивать кто все Корректные процессы получили одни и те же сообщения, даже если сам отправитель испытывает крушение в процессе передачи.

Для реализации некой наивной версии некого надёжного широковещания, мы можем пользоваться неким определителем отказов и какой- то механизм отхода. Наиболее прямолинейный механизм отхода состоит в разрешении каждому принимающему данное сообщение процессу переправления его всем прочим процессам, о которых он осведомлён. Когда соответствующий процесс источника отказывает, прочие процессы выявляют это падение и продолжают широковещательно распространять это сообщение, действенно заполняя данную сетевую среду N2 сообщениями (как это показано на Рисунке 14-1). Даже если такой отправитель претерпел крушение, сообщения всё ещё подбираются и доставляются всей оставшейся системой, улучшая её надёжность и позволяя всем получателям видеть те же самые сообщения [CACHIN11].

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

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

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

В сумме некое атомарное широковещание обязано гарантировать два существенных свойства:

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

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

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

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

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

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

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

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

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

Одной из самых популярных и широко известных реализаций обсуждаемого атомарного широковещания является ZAB, применяемый Apache Zookeeper [HUNT10] [JUNQUEIRA11], иерархическое распределённое хранилище ключ- значение, в котором оно используется для обеспечения необходимого тотального порядка событий и атомарной доставки, требующейся для сопровождения согласованности между установленными состояниями реплик.

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

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

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

Рисунок 14-2 отображает все три фазы данного алгоритма ZAB и обмен сообщений на каждом из этапов.

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

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

Сообщения тотально упорядочены и установленный Лидер не предпринимает попыток отправить своё следующее сообщение пока не было подтверждено предыдущее сообщение. Даже когда некоторые сообщения получаются Последователями более одного раза, их повторное приложение не производит дополнительных сторонних эффектов при следовании порядку доставки. ZAB способен обрабатывать множество нерешённых одновременных изменений состояний клиентов, так как некий уникальный лидер будет получать запросы на запись, устанавливать необходимый порядок событий и широковещательно распространять эти изменения.

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

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

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

Вероятно наиболее широко известным алгоритмам консенсуса является Paxos. Он впервые был предложен Лесли Дампортом в его статье "The Part-Time Parliament" [LAMPORT98]. В этой статье консенсус описывается в выражениях терминологии, вдохновлённой законодательным и избирательным процессом на Эгейском острове Паксос. В 2001 этот автор выпустил следующую статью, озаглавленную "Paxos Made Simple" [LAMPORT01], которая вводила более простую терминологию, которая теперь и применяется для объяснения данного алгоритма.

Участники Paxos способны выполнять одну из трёх ролей: Заявителей, Получателей или Обучаемых.

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

Всякое предложение состоит из некого значения, предлагаемого соответствующим клиентом, а также монотонно возрастающим номером предложения. Этот номер затем используется для обеспечения общего порядка исполняемых операций и устанавливает взаимосвязи происхождения -до/ -после между ними. Номера предложений также часто реализуются при помощи неких пар (id, timestamp), где также сопоставляется и идентификатор узла, который может применяться в качестве разрывающих связей (break ties) для временных отметок.

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

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

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

На протяжении этапа предложения установленный Вносящий предложение отправляет некое сообщение Prepare(n) (где n это номер предложения) некому большинству Получателей и предпринимает попытку сбора их голосов.

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

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

Соответствующий Получатель принимает это предложение с номером n, если только на протяжении этапа предложения он уже не ответил Prepare(m), где m больше чем n. Когда Получатель отвергает данное предложение, он уведомляет об этом своего Заявителя, отправляя самое большое последовательное число, которое он наблюдал в своём запросе содействуя своему Заявителю поймать его [LAMPORT01].

Вы можете рассмотреть обобщённое отображение некого раунда Paxos на Рисунке 14-3.

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

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

Итак, основная цель самого первого этапа алгоритма состоит в установлении некого лидера для данного раунда и понимания каое значение подлежит принятию, что делает возможным такому лидеру продолжить вторым этапом: широковещательным распространением этого значения. На практике, мы бы желали снизить общее число этапов в данном алгоритме, потому мы позволяем своему Заявителю предлагать более одного значения. Мы обсудим это более подробно в разделе Multi-Paxos.

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

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

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

Жизнеспособность гарантируется при наличии f отказавших процессов. Для этого данный протокол требует в общей сложности 2f + 1 процессов с тем, чтобы когда произойдёт f отказов, всё ещё будет иметься f + 1 процессов, способных продолжать работу. Применяя кворумы, вместо того чтобы требовать присутствия всех процессов, Paxos (и прочие алгоритмы консенсуса) обеспечивают результаты даже в сучае возникновения f отказов. В разделе Гибкий Paxos мы обсудим кворумы слегка в иной терминологии и опишем как строит протоколы, требующие лишь пересечения кворумов между этапами алгоритма.

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

Рисунок 14-4 отображает такую ситуацию:

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

В неком приложении клиент/ сервер, в котором определённый клиент соединяется лишь с первоначальным Заявителем, это может повлечь за собой ситуации, при которых данный клиент не знает об окончательном результате исполнения данного раунда Paxos (к примеру, такое положение вещей описывается в https://databass.dev/links/68).

Тем не менее, также возможны и иные сценарии, как это отображено на Рисунке 14-5. Например:

В данных обстоятельствах имеется ещё одна возможность, отображаемая на Рисунке 14-6:

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

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

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

До сиз пор мы обсуждали классический алгоритм Paxos, в котором мы придерживаемся некого произвольного Заявителя и пытаемся запустить некий раунд Paxos. Одной из основных проблем данного подхода состоит в том, что для всякого раунда происходящего в данной системе репликации необходим некий раунд предложения. Лишь после того как соответствующий Заявитель установлен для данного раунда, что происходит после отклика большинства Получателей неким Promise на соответствующий Prepare, он способен запустить данную репликацию. Чтобы избежать соответствующего этапа предложения и позволить установленному Заявителю повторно применять его общепризнанное положение, мы можем применять Множественный Paxos (Multi-Paxos), который вводит некое понятие Лидера: некого Высокопоставленного Заявителя (distinguished proposer) [LAMPORT01]. Именно это является критическим добавлением, которое значительно улучшает действенность алгоритма.

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

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

Аналогичная ситуация может происходить и в Множественном Paxos: мы пытаемся выполнить некое чтение из известного Лидера после того как уже избран другой Лидер, возвращая устаревшие сведения, что входит в противоречие с необходимостью для консенсуса обеспечения линеаризуемости. Во избежание этого и дабы гарантировать что никакой иной процесс не способен успешно представить значения, некоторые реализации Множественного Paxos применяют аренду (leases). Установленный Лидер периодически взаимодействует с имеющимися участниками, уведомляя их что он всё ещё работает, действенно продлевая свою аренду. Участники должны откликаться и позволять этому Лидеру продолжать свои операции, обещая что они не будут принимать предложения от прочих лидеров на данный период аренды [CHANDRA07].

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

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

Для предотвращения роста журнала до неопределённо большого размера, к его содержимому следует применять обсуждавшуюся ранее структуру. После того как данный журнал синхронизирует содержимое со своей первичной структурой, создаётся некий моментальный снимок, а сам журнал может быть усечён. Журнал и состояние моментальных снимков обязаны быть взаимно согласованными, причём изменения моментального снимка должны применяться атомарно с усечением откидываемого сегмента журнала [CHANDRA07].

Мы можем представлять себе отдельное постановление Paxos как некий однократно- записываемый регистр: у нас есть некий разъём, в который мы имеем возможность помещать некое значение и как только мы записали туда своё значение, невозможны никакие последующие изменения. На протяжении самого первого этапа предложения состязаются за обладание данным регистром,а на втором этапе один из них записывает своё значение. В то же самое время, Множественный Paxos может представляться нам как некий дописываемый исключительно в конец журнал, состоящий из некой последовательности таких значений: за раз мы можем записывать единственное значение, все значения строго упорядочены и мы не имеем возможности изменять уже записанные значения [RYSTSOV16]. Имеются примеры алгоритмов консенсуса, которые предлагают наборы регистров считывания- изменения- записи и используют разделение состояния вместо того чтобы реплицировать конечные автоматы, например, Active Disk Paxos [CHOCKLER15] и CASPaxos [RYSTSOV18].

Мы можем снизить общее число проходов туда и обратно на один по сравнению со своим классическим алгоритмом Paxos, позволив любому Заявителю взаимодействовать с Получателями напрямую вместо того чтобы полагаться на установленного Лидера. Для этого нам требуется увеличить размер своего кворума до 2f + 1 (где f это общее число процессов, для которых допустим отказ), в сравнении с f + 1 для классического Paxos, а общее число Получателей до 3f + 1 [JUNQUEIRA07]. Такая организация носит название Быстрого Paxos [LAMPORT06].

Наш алгоритм классического Paxos обладает неким условием, когда на протяжении выполняемого этапа репликации установленный Заявитель может выцеплять любое значение, которое он собирал на своём этапе предложения. Быстрый Paxos обладает двумя типами раундов: классическим, при котором данный алгоритм продолжается тем же самым способом , что и в своей классической версии и быстрым, когда он разрешает Получателям принимать прочие значения.

При определении данного алгоритма мы будем именовать своего Заявителя, который должен собрать достаточное число откликов на этапе предложения Координатором и зарезервировать термин Заявителя для всех прочих Заявителей. некоторые описания Быстрого Paxos сообщают, что клиенты могут вступать в контакт с Получателями напрямую [ZHAO15].

В неком быстром раунде, когда установленному Координатору дозволено выцеплять своё собственное значение на протяжении выполняемого этапа репликации, он имеет возможность этого вместо вызова для Получателей какого- то специального сообщения Any. Получателям в таком случае позволяется воспринимать значение любого Заявителя как если бы это был классический раунд и они получили некое сообщение с данным значением от своего Координатора. Иначе говоря, Получатели независимо принимают решение по получаемым ими от различных Заявителей значениям.

Рисунок 14-7 отображает некий образец классического и быстрого раундов в Быстром Paxos. Исходя из этого рисунка может показаться, что отображённый быстрый раунд имеет больше шагов исполнения, но имейте в виду, что в классическом раунде для представления своего значения установленному Заявителю необходимо пройти через своего Координатора для получения фиксации своего значения.

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

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

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

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

Вместо применения Лидера и предлагаемых номеров для последовательных команд мы можем пользоваться Лидером для конкретной фиксации этой определённой команды и установления порядка просмотра и установки зависимостей. Такой подход обычно именуется Уравнивающим Paxos (Egalitarian Paxos) или EPaxos [MORARU11]. Основная мысль допуска независимой фиксации не конфликтующих записей в имеющемся реплицируемом конечном автомате впервые была предложена в [LAMPORT05] и носила название Обобщённого Paxos. EPaxos это первая реализация Обобщённого Paxos.

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

EPaxos запускается фазой Предварительного приёма, в процессе которого некий процесс превращается в Лидера для данной определённой цели. Каждое предложение содержит:

После сбора этих сведений, он направляет сообщение Pre-Accept быстрому кворуму реплик. Быстрый кворум это ⌈3f/4⌉ реплик, где f это значение числа возможных отказов.

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

Когда установленный Лидер не получает достаточного числа откликов или если его получаемый от своих реплик список команд отличен и содержит пересекающиеся команды, он обновляет свои зависимости неким новым перечнем зависимостей и последовательным номером. Этот новый список зависимостей основывается на отклика предыдущих реплик и сочетает все собранные зависимости. Установленный новый последовательный номер обязан быть больше чем самый наивысший наблюдавшийся в репликах последовательный номер. После этого, данный Лидер отправляет свою новую, изменённую команду в ⌊f/2⌋ + 1 реплик. После осуществления этого, данный Лидер может окончательно зафиксировать данное предложение.

На самом деле у нас имеются два сценария:

Рисунок 14-8 отображает эти сценарии - P1 инициирует запуск быстрого пути, а P5 инициирует запуск медленного пути:

Две команды, A и B, пересекаются только если имеет значение их порядок; иначе говоря, когда исполнение A перед B и выполнение B до A приводит к различным результатам.

Фиксация выполняется откликом клиенту и асинхронным уведомлением реплик сообщением Commit. Команды выполняются после их фиксации.

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

Для выполнения команды реплики строят некий граф зависимостей и исполняют все команды в порядке, обратном зависимостям. Говоря иначе, прежде чем какая- то команда может быть выполнена, необходимо выполнить все её зависимости (и, затем и все их зависимости). Так как только пересекающиеся команды обязаны зависеть друг от друга, подобная ситуация должна быть достаточно редкой для большей части рабочих нагрузок [MORARU13].

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

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

Нам требуется ответить на два важных вопроса:

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

Во Множественном Paxos собственно фаза выбора Лидера не является частой и нашему Высокопоставленному Лидеру позволено фиксировать различные значения без возврата к соответствующему этапу выборов, потенциально оставаясь установленным Лидером длительное время. В разделе Настраиваемая согласованность мы обсудили формулу, способствующую нам в поиске конфигурации в которой мы обладаем пересечениями между своими наборами узлов. Одним из примеров было простое ожидание того что один узел подтвердит соответствующую запись (и позволит имеющимся запросам во всех остальных узлах завершаться асинхронно) и чтение со всех доступных узлов. Иными словами, пока мы имеем R + W > N, существует по крайней мере один общий узел между наборами чтения и записи.

Можем ли мы воспользоваться этой же логикой для консенсуса? Оказывается, да, причём в Paxos нам всего лишь требуется чтобы группа узлов из нашего первого этапа (которая выбирает Лидера) перекрывалась с группой второго этапа (участвующей в принятии предложений).

Говоря другими словами, некий кворум не обязательно должен определяться как некое большинство, а всего лишь как какая- то не пустая группа узлов. Если мы определим общее число участников как N, N, общее число узлов, требуемых для успешности этапа предложения как Q1, а общее число узлов для успешности этапа приёма как Q2, нам всего лишь требуется чтобы Q1 + Q2 > N. Так как наш второй этап как правило более распространён чем первый, Q2 может содержать лишь N/2 Получателей, в то время как Q1 настраивается на соответствующее большее значение (Q1 = N - Q2 + 1). Эта находка является важным наблюдением, критически важным для понимания консенсуса. Тот алгоритм, который мы применяем в данном подходе носит название Гибкого Paxos [HOWARD16].

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

Гибкий Paxos делает возможным компромисс с доступностью в пользу задержек: мы снижаем общее число узлов, участвующих во втором этапе, но нам приходится собирать больше голосов, что требует большего числа участников доступными на этапе выборов своего Лидера. Хорошая новость состоит в том, что данная конфигурация может продолжать соответствующий этап репликации и быть безразличной вплоть до отказа N - Q2 + 1 узлов, пока установленный Лидер стабилен и не требуется новый раунд выборов.

Другим вариантом Paxos, использующим ту же идею пересечения кворумов является Вертикальный Paxos. Вертикальный Paxos делает различия между кворумами чтения и записи. Эти кворумы обязаны пересекаться. Некий Лидер должен собирать кворум меньшего размера чтений для одного или более предложений с меньшими номерами и кворум большего размера записи для своего собственного предложения [LAMPORT09]. [LAMPSON01] также проводит различие между кворумами выдачи и решения, что транслируется в этапы подготовки и принятия и снабжает нас определением кворума, аналогичным Гибкому Paxos.

Обобщённое решение для консенсуса

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

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

Регистры с одним и тем же значением, расположенные в различных серверах образуют некий набор регистров. Всякий набор регистров может обладать одним или более кворумами. В зависимости от значения состояния регистров в нём, кворум может быть в одном из состояний без решения (undecided, Any и Maybe v), либо с решением (None и Decided v):

Any

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

Maybe v

Когда этот кворум принимает решение, его решением может быть только v.

None

Этот кворум не способен принимать решение по конкретному значению.

Decided v

Данный кворум принял решение со значением v.

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

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

Правила записи слегка сложнее, так как для обеспечения безопасности алгоритма нам необходимо сохранять ряд инвариантов. Прежде всего, нам требуется быть уверенными что наш клиент не просто предлагает новые значения: ему разрешается записывать в регистр некое определённое значение только когда он получил его в качестве входных данных или считал его из некого регистра. Клиенты не способны записывать значения, которые допускают различные кворумы в одном и том же регистре для принятия решения по различным значениям. И, наконец, клиенты не могут записывать значения, которые отменяют предыдущие решения, принятые в более ранних наборах регистров (принятые в наборе регистров вплоть до r - 1 решения обязаны быть None, Maybe v или Decided v.)

 

Обобщённый алгоритм Paxos

Совмещая эти три правила воедино, мы можем реализовать некий обобщённый алгоритм Paxos, который достигает согласия относительно некого отдельного значения при помощи регистров с единственной записью [HOWARD19]. Допустим, у нас имеются три сервера [S0, S1, S2], регистры [R0, R1, …] и клиенты [C0, C1, …], причём эти клиенты способны записывать лишь в соответствующие назначенные подмножества регистров. Для всех регистров мы применяем кворумы простого большинства ({S0, S1}, {S0, S2}, {S1, S2}).

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

В процессе фазы 1

Наш клиент проверяет что тот регистр, в который он намерен выполнить запись не записан через отправку команды P1A(register) в его сервер. Когда этот регистр не записан, все регистры вплоть до register - 1 установлены в значение nil, что препятствует клиентам запись в предыдущие регистры. Соответствующий сервер откликается неким набором регистров, записанных до сих пор. Если клиент получает отклики от большинства серверов, он выбирает либо соответствующее значение из полученного регистра с наибольшим индексом, либо своё собственное значение в случае когда нет представленного значения. В противном случае он перезапускает этот первый этап.

В процессе фазы 2

Наш клиент уведомляет все серверы относительно того значения, которое он выбрал на протяжении своего первого этапа, отправляя им P2A(register, value). Если большинство серверов откликаются на это сообщение, он может выдать своё выбранное значение. В противном случае он вновь начинает с фазы 1.

Рисунок 14-9 отображает обобщённый Paxos (адаптировано из [HOWARD19]). Клиент C0 предпринимает попытку фиксации значения V. В процессе своего первого этапа его таблица состояний пуста, а серверы S0 и S1 откликаются с пустыми значениями набора регистров, что указывает на то, что до сих пор не записан ни один из регистров. На протяжении второго этапа он может представить своё значение V, так как никакое иное значение не было записано.

 

Рисунок 14-9

Обобщённый Paxos

В этот момент, какой- то иной клиент может сделать серверам запрос поиска значения текущего состояния. Кворум {S0, S1} достиг состояния Decided A, а кворумы {S0, S2} и {S1, S2} достигли значения состояния Maybe V для R0, а потому C1 выбирает значение V. В этот момент никакой из клиентов не способен принять решения отличного от V.

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

Мы также можем провести параллели с оригинальным Paxos. Например, в неком сценарии, в котором наш клиент определяет что один из имеющихся предыдущих наборов регистров обладает соответствующим решением Maybe V, он выбирает V и пробует зафиксировать его снова, что схоже с тем, как некий Заявитель в Paxos может предлагать своё значение после произошедшего отказа имевшегося ранее Заявителя, и который мог зафиксировать это значение по крайней мере у одного Получателя. Точно так же, когда конфликты в Лидерах Paxos разрешаются перезапуском данного голосования с большим номером предложения, в нашем обобщённом алгоритме все незаписанные регистры с низшими рангами установлены в значение nil.