Наши партнеры

UnixForum

Библиотека сайта rus-linux.net

Кластеризация согласно консенсусу

Оригинал: Clustering by Consensus
Автор: Dustin J. Mitchell
Дата публикации: July 12, 2016
Перевод: Н.Ромоданов
Дата перевода: январь 2017 г.

Консенсус согласно алгоритму Paxos

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

Алгоритм Paxos был описан Лесли Лампортом (Leslie Lamport) в странной статье, впервые представленной в 1990 году и, в конечном итоге, опубликованной в 1998 году, под названием "The Part-Time Parliament" ("Парламент с частичной занятостью") [1]. В статье Лампорта гораздо больше деталей, чем мы используем здесь, и ее интересно прочитать. По ссылкам, приведенным в конце главы, вы найдете описания некоторых расширений алгоритма, который были адаптированы под нашу реализацию.

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

Простой алгоритм Paxos

Итак, давайте начнем с "простого алгоритма Paxos", также известного как протокол Synod (протокол Синода), который предоставляет способ договориться об одном значение, которое никогда не изменяется. Название Paxos (Паксос) происходит от мифического острова из статьи "The Part-Time Parliament", где законодатели голосовали с использованием процесса, который Лампорт окрестил, как протокол Синода.

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

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

Рис.3.1. Бюллетень

Работа с бюллетенем начинается с того, что предлагающий посылает сообщение Prepare (Подготовить) с номером N всем получающим и ждет, что он услышит от большинства (рис.3.1.).

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

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

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

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

 operation(name='deposit', amount=100.00, destination_account='Mike DiBernardo')

Если другой предлагающий позже инициирует голосование с меньшим номером бюллетеня и другой операцией (скажем, выполнить трансфер на счет 'Dustin J. Mitchell'), то получающие просто не примут его. Если в бюллетене будет больший номер бюллетеня, то сообщение Promise от получающих проинформирует предлагающего о об операции с депозитом Майкла на сумму 100.00 долларов, и предлагающий пошлет это значение в сообщении Accept вместо выполнения трансфера для Дастина. Новый бюллетень будет принят, но с тем же самым значением, как в первом туре голосования.

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

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

Рассмотрим следующую последовательность событий:

  • Предлагающий выполняет фазу Prepare/Promise для номера бюллетеня, равного 1.
  • Прежде, чем предлагающий A получит сообщения о том, что его предложение приняли, предлагающий B выполняет фазу Prepare/Promise для номера бюллетеня, равного 2.
  • Когда предлагающий A наконец пошлет сообщение Accept с номером бюллетеня 1, принимающие не примут его, поскольку они уже послали свои обещания для номера бюллетеня, равного 2.
  • Предлагающий A немедленно на это отреагирует и прежде, чем кандидат B сможет послать свое сообщение о подтверждении Accept, отправит сообщение Prepare с большим номером номером бюллетеня (с номером 3).
  • Сообщение Accept предлагающего B будет отвергнуто и процесс повторится.

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

Алгоритм Multi-Paxos

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

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

Запуск алгоритма Paxos для каждого слота, причем с минимумом в два раунда согласования, был бы слишком медленным. Алгоритм Multi-Paxos оптимизирован за счет использования одного и того же набора номеров бюллетеней для всех слотов и одновременного выполнения для всех слотов фазы Prepare/Promise.

Реализация алгоритма Paxos достаточно сложна

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

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

Фаза Prepare/Promise может функцировать как фаза своеобразного выбора лидера: если член кластера будет владельцем номера бюллетеня с самым последним обещанием, он будет считаться лидером. После этого лидер может непосредственно выполнить фазу Accept/Accepted без повторения первой фазы. Как мы увидим ниже, выбор лидера, на самом деле, является довольно сложными.

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

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

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

Но достаточно рассуждать о теории и алгоритмах - давайте посмотрим на код.

Перейти к следующей части статьи.