Вопросы по реализации Paxos

Question

Я внедряю Paxos в приложение кластерного симулятора, используя документацию, доступную в Википедии. К сожалению, он оставляет несколько дверей для интерпретации и не дает много информации по ключевым вопросам реализации. Это неясно и неполно.

• Предположим, кластер разделен на 3 региона, каждый из которых содержит 3 узла (всего = 9 узлов). Что произойдет, если нарушится связь между регионами? Ни один лидер не может достичь кворума (то есть 5).

Не собирается ли Паксос войти в бесконечный цикл? Я думаю, что не следует инициировать Paxos, если вы не можете общаться хотя бы с кворумом узлов.

• На этапе 1b: "Если номер предложения N больше, чем какое-либо предыдущее предложение, то каждый Акцептор обещает не принимать предложения меньше, чем N, и отправляет значение, которое он в последний раз принял для этого экземпляра, Предлагателю".

Что такое "последняя принятая ценность"? Это какой-либо предыдущий номер предложения от заявителя? Что означает "экземпляр" именно в этом случае?

• На Фазе 1a: Включает ли кто-либо значение для согласования с сообщением Подготовка, или оно отложено до Принять! сообщение? Или это имеет значение?

• На Этапе 2a: "Если какой-либо из Акцепторов уже принял значение, лидер должен выбрать значение с максимальным номером предложения N".

В чем здесь ценность? Это номер предложения? Я не верю, но эта фраза неясна.

• На Фазе 2a: "В противном случае, Proposer может выбрать любое значение". Что это значит? Значение для чего? Для номера предложения?

• Паксос, кажется, полагается на возрастающее значение N (номер предложения) для работы? Это правильно?

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

PS: у меня недостаточно репутации, чтобы создать тег "Paxos" (любой волонтер?)

Answer 1

Что такое экземпляр?

Номенклатура в Паксосе немного неинтуитивна.

• Экземпляр - это алгоритм выбора одного значения.
• Раунд относится к единственной попытке предложившего Фазу 1 + Фаза 2. Узел может иметь несколько раундов в экземпляре Paxos. Идентификатор раунда является уникальным для всех экземпляров. Это иногда называют номером предложения.
• Узел может взять на себя несколько ролей; наиболее заметно, Proposer и Acceptor. В своих ответах я предполагаю, что каждый узел выполняет обе роли.
• Этап 1 также известен как подготовительный этап.
  • На Фазе 1a, Proposer отправляет сообщение "Приготовься!" (RoundId) к Акцепторам.
  • На Фазе 1b, Акцепторы отвечают либо Promise!(RoundId, value), либо PrepareNack!()
• Фаза 2 также известна как фаза принятия.
  • На Фазе 2a, Proposer отправляет сообщение Accept!(RoundId, value) акцепторам.
  • На Фазе 2b, Акцепторы отвечают либо Accepted!(...), либо AcceptNack!()

Предположим, кластер разделен на 3 региона, каждый из которых содержит 3 узла (всего = 9 узлов). Что произойдет, если нарушится связь между регионами? Ни один лидер не может достичь кворума (то есть 5).

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

Не собирается ли Паксос войти в бесконечный цикл?

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

На этапе 1b: "Если номер предложения N больше, чем какое-либо предыдущее предложение, то каждый >> Акцептор обещает не принимать предложения меньше N и отправляет значение, которое он в последний раз принял для >> этого экземпляра, Предлагателю".

Что такое "последняя принятая ценность"? Это какой-либо предыдущий номер предложения от заявителя?

Когда узел получает сообщение Accept!(RoundId, value) от Proposer, и он не пообещал не принимать значение (из-за сообщения Prepare!(UpperRoundId)), он сохраняет значение и roundId (я буду позвони им acceptedValue а также acceptedRoundId). Он может перезаписывать их из-за последующих сообщений Accept!(...).

Когда узел получает сообщение Prepare!(RoundId) от Proposer, он сохраняет roundId как promiseRoundId = max(roundId, promiseRoundId), Затем отправляет Promise!(acceptedRoundId, acceptedValue) вернуться к предложителю. Примечание: если узел не получил сообщение Accept!(...), он отвечает Promise!(null, null),

На Фазе 1a: Включает ли кто-либо значение для согласования с сообщением Подготовка, или оно отложено до Принять! сообщение? Или это имеет значение?

Там нет необходимости отправлять его. Я не.

На Этапе 2a: "Если какой-либо из Акцепторов уже принял значение, лидер должен выбрать значение с максимальным номером предложения N".

В чем здесь ценность? Это номер предложения? Я не верю, но эта фраза неясна.

Значение - это фактические данные, по которым алгоритм достиг консенсуса. Я перефразирую это

Чтобы начать фазу принятия, Организатор должен выбрать значение, которое будет принято, в зависимости от результатов фазы Подготовки. Если какой-либо Акцептор ответил с Promise (roundId, value), Proposer должен использовать значение, связанное с самым высоким roundId. В противном случае, Proposer получил только Promise (null, null) и может выбрать любое значение для отправки получателям.

NB: Номер предложения здесь - то же самое, что и roundId.

На Фазе 2a: "В противном случае, Proposer может выбрать любое значение". Что это значит? Значение для чего? Для номера предложения?

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

Паксос, кажется, полагается на возрастающее значение N (номер предложения) для работы? Это правильно?

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

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

1. Скажем, есть M узлов, участвующих в экземпляре Paxos.
2. Сортировать все узлы лексикографически. index[узел] - это индекс узла в этом отсортированном списке.
3. roundId = i*M + index[node] где i - i-й раунд, в котором начинается этот узел (то есть i уникален для каждого узла в экземпляре paxos и монотонно увеличивается).

Или в псевдокоде (которому явно не хватает нескольких основных оптимизаций):

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )

        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue

        acceptResult = doAcceptPhase( roundId, chosenValue )

        if (!acceptResult.shouldContinue?)
            return
    }
}

Answer 2

Я нашел следующий документ, объясняющий Паксос более подробно. Я обновил запись в Википедии соответственно.

Ответы на мой вопрос я мог найти:

Не собирается ли Паксос войти в бесконечный цикл?

Paxos работает только в том случае, если хотя бы кворум узлов может общаться друг с другом (в нашем случае 5). Следовательно, если узел не может обмениваться данными хотя бы с кворумом узлов, он не должен пробовать Paxos.

Что такое "последняя принятая ценность"?

Это последний принятый номер предложения и соответствующее значение.

Что означает "экземпляр" именно в этом случае?

Это относится к акцептору.

Содержит ли значение, которое нужно согласовать с сообщением Подготовить, или оно отложено до Принять! сообщение? Или это имеет значение?

Это значение не включено в сообщение "Подготовка", оно оставляется в сообщении "Запрос на принятие".

В чем здесь ценность? Это номер предложения? Я не верю, но эта фраза неясна.

"В противном случае, Proposer может выбрать любое значение". Что это значит? Значение для чего? Для номера предложения?

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

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

Паксос, кажется, полагается на возрастающее значение N (номер предложения) для работы? Это правильно?

Да. Заявитель р должен все больше пересчитывать свои предложения.

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

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

Answer 3

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

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