Может ли акцептор в Paxos принять другое значение после того, как он уже принял?
В алгоритме Multi-Paxos рассмотрим этот поток сообщений с точки зрения акцептора:
получить: подготовить (N)
ответ: Обещание (N, ноль)
получить: принять!(N, V1)
ответ: Принято (N, V1)
получить: принять!(N+1, V2)
Ответить:?
Какой должна быть реакция акцептора в этом случае согласно протоколу? Должен ли он ответить с Accepted(N+1, V2), или он должен игнорировать второй Accept!?
Я полагаю, что этот случай может произойти в Multi-Paxos, когда второй заявитель подключается к сети и считает, что он (и всегда был) лидером, поэтому он посылает свое согласие без подготовки. Или если его Prepare просто не дошел до акцептора. Если этот случай может не произойти, вы можете объяснить, почему?
4 ответа
Я не согласен с обоими другими ответами.
Мульти-Паксос не говорит, что Лидер является единственным предложителем; это приведет к тому, что система будет иметь единственную точку отказа. Даже во время сетевых разделов система не сможет прогрессировать. Multi-Paxos - это оптимизация, позволяющая одному узлу (Leader) пропустить некоторые фазы подготовки. Другие узлы, считая, что лидер мертв, могут попытаться продолжить работу экземпляра от ее имени, но все равно должны использовать полный протокол Basic-Paxos.
Отсутствие сообщения о принятии нарушает алгоритм Паксоса. Акцептор должен принять все значения, если он не пообещал его не принимать. (Игнорирование разрешено, но не рекомендуется; это просто потому, что разрешены пропущенные сообщения.)
Существует также элегантное решение для этого. Проблема с круглым числом Лидера (N+1 в вопросе).
Вот некоторые предположения:
- У вас есть такая схема, что круглые идентификаторы не пересекаются во всех узлах (в любом случае, это требуется Paxos).
- У вас есть способ определить, какой узел является экземпляром Leader per Paxos (требуется для Multi-Paxos). Лидер может переключаться с одного экземпляра Paxos на другой.
Кроме того: Парламент, работающий неполный рабочий день, предполагает, что это делается Лидером, выигравшим предыдущий инстанс Paxos (Раздел 3.1), и указывает, что она может оставаться Лидером, пока она жива или самая богатая (Раздел 3.3.1). У меня есть явное значение ELECT_NEW_LEADER: <узел>, которое предлагается через Paxos. - Лидер пропускает только фазу Подготовки в начальном раунде для каждого экземпляра; и использует полный Базовый Паксос в последующих раундах.
С этими допущениями решение очень просто. Лидер просто выбирает действительно низкий круглый идентификатор для своей начальной фазы принятия. Этот идентификатор (который я назову INITIAL_ROUND_ID) может быть любым, если он ниже, чем круглые идентификаторы всех узлов. В зависимости от вашей схемы выбора идентификатора будет работать либо -1, 0, либо Integer.MIN_VALUE.
Это работает, потому что другой узел (я назову его Стюартом) должен пройти через полный протокол Paxos, чтобы предложить что-нибудь, и его круглый идентификатор всегда больше, чем INITIAL_ROUND_ID. Есть два случая, чтобы рассмотреть: достигли ли сообщения Принятия Лидера какой-либо из узлов, которые сообщение Стюарта подготовило.
Когда фаза принятия лидером не достигает ни одного узла, Стюарт не получит никакого значения в любом обещании и может действовать так же, как в обычном Basic-Paxos.
И когда фаза принятия лидером достигает узла, Стюарт вернет значение в обещании, которое он использует для продолжения алгоритма, как в Basic-Paxos.
В любом случае, поскольку идентификатор раунда Стюарта больше, чем INITIAL_ROUND_ID, любые медленные сообщения Accept, которые узел получает от Лидера, всегда приводят к Nack.
Никакой особой логики нет ни у Акцептора, ни у Стюарта. И минимальная специальная логика на Лидере (то есть выберите действительно низкий INITIAL_ROUND_ID).
Обратите внимание, что если мы изменим вопрос ОП на один символ, тогда сам ответ ОП будет правильным: Nack.
- получить: подготовить (N)
- ответ: Обещание (N, ноль)
- получить: принять!(N, V1)
- ответ: Принято (N, V1)
- получить: принять! (N-1, V2)
- ответ: Nack (N, V1)
Но в его нынешнем виде его ответ нарушает алгоритм Паксоса; это должно быть Accept!
- получить: подготовить (N)
- ответ: Обещание (N, ноль)
- получить: принять!(N, V1)
- ответ: Принято (N, V1)
- получить: принять! (N + 1, V2)
- ответ: Принять!(N+1, V2)
Возможно, более простой ответ состоит в том, чтобы заметить, что это тот случай, когда команда Prepare(N+1) была принята большинством, которое не включало рассматриваемый акцептор.
Для уточнения: как только лидер узнает, что какое-то большинство имеет Обещанное (N+1), он отправляет Accept(N+1,x) всем акцепторам, и даже если какое-то другое большинство акцепторов отвечает Accepted(N+1), тогда консенсус был достигнут.
Это не такой уж необычный сценарий.
Правильность Multi-Paxos обусловлена требованием, чтобы лидер (то есть, предлагающий) не менялся между последовательными экземплярами Paxos. Из раздела 3.1 Парламента с частичной занятостью (Протокол парламента с несколькими указами):
Логично, что парламентский протокол [aka Multi-Paxos] использовал отдельный экземпляр полного протокола Синода [aka Paxos] для каждого номера указа. Тем не менее, один президент [aka proposer/ лидер] был выбран для всех этих случаев, и он выполнил первые два шага протокола только один раз.
[Добавленный акцент мой.]
Поэтому Multi-Paxos предполагает, что описанный вами случай - когда второй заявитель выходит в сеть и считает, что он является (и всегда был) лидером - никогда не случится. Если такой случай может произойти, то не следует использовать Multi-Paxos. Что касается второй возможности - когда второй заявитель Prepare не достигло акцептора - тот факт, что второй заявитель уже разослал Accept! означает, что он ранее разослал Prepare это было Promised по кворуму акцепторов. Так как акцепторы уже пообещали первому заявителю на тур Nтогда второй заявитель Prepare должно быть отправлено до раунда N, Поэтому финал Accept!(N+1,V2) должен иметь счетчик меньше, чем N,
Редактировать: Следует также отметить, что эта версия протокола не устойчива к византийскому отказу:
[Протокол Парламента Паксона] не допускает произвольных, злонамеренных сбоев и не гарантирует ограниченный ответ.
-Парламент с частичной занятостью, раздел 4.1
(Отвечая на мой собственный вопрос.)
Мое текущее понимание состоит в том, что я не должен принимать значение в N+1 (то есть не отвечать вообще или отправлять NACK), таким образом, заставляя лидера, возможно, начать еще один раунд с подготовкой (если большинство еще не достигло консенсуса), После того, как я получу Подготовку (N+2), я отвечу Обещанием (N+2, V1) и продолжу как обычно.