Что такое экземпляр?
Номенклатура в Паксосе немного неинтуитивна.
- экземпляр - алгоритм длявыбор значения one .
- A round относится к единственной попытке заявителя на этапе 1 + этап 2. Узел может иметь несколько этапов в случае в Паксосе.Идентификатор раунда является глобально уникальным для каждого экземпляра всех узлов.Это иногда называют номером предложения .
- Узел может выполнять несколько ролей;наиболее заметно, Proposer и Acceptor.В своих ответах я предполагаю, что каждый узел выполняет обе роли.
- Этап 1 также известен как этап подготовки.
- На Фазе 1a, Proposer отправляет акцепторам сообщение Prepare! (RoundId)
- На Фазе 1b акцепторы отвечают либо Promise! (RoundId, value), либо PrepareNack! ()
- Фаза 2 также известна как фаза принятия.
- На Фазе 2a, Proposer отправляет сообщение Accept! (RoundId, value) акцепторам
- На Фазе 2b, Acceptors отвечает либо Accepted! (...), либо AcceptNack!()
Предполагается, что кластер разделен на 3 области, каждая из которых содержит 3 узла (всего = 9 узлов).Что произойдет, если нарушится связь между регионами?Ни один лидер не может достичь кворума (а это 5).
Паксос требует, чтобы у вас был хотя бы кворум (5 узлов в вашем случае).Перейти с вашим решением трех регионов;наличие двух сетевых разделов между тремя регионами - очень плохая новость.Я также использую версию Paxos, которая может изменять принадлежность узла от одного экземпляра к другому.Это полезно для разделов и сбоя узла.
Не собирается ли 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) обратно Proposer.Примечание: если узел не получил сообщение Accept! (...), он отвечает Promise!(null, null).
На этапе 1a: Включает ли одно значение для согласования с Prepare?сообщение или это отложено до принятия!сообщение?Или это имеет значение?
Не нужно его отправлять.Не знаю.
На Фазе 2a: «Если кто-либо из Акцепторов уже принял значение, лидер должен выбрать значение с максимальным номером предложения N».
В чем здесь ценность?Это номер предложения?Я не верю, но эта фраза неясна.
Значение - это фактические данные, по которым алгоритм достиг консенсуса.Я перефразирую это к
Чтобы начать фазу принятия, Организатор должен выбрать значение, которое будет принято, в зависимости от результатов фазы Подготовки. Если какой-либо Акцептор ответил с Promise (roundId, value), Proposer должен использовать значение, связанное с самым высоким roundId. В противном случае, Proposer получил только Promise (null, null) и может выбрать любое значение для отправки получателям.
Примечание: номер предложения здесь совпадает с номером раунда.
На Фазе 2a: «В противном случае, Proposer может выбрать любое значение». Что это значит? Значение для чего? Для предложения номер?
Это значение, по которому вы хотите достичь консенсуса. Обычно это изменение состояния распределенной системы, которое может быть вызвано запросом клиента.
Паксос, кажется, полагается на возрастающее значение N (номер предложения) для работы? Это правильно?
В записи в Википедии не обсуждаются начальные значения, которые узел должен установить перед началом участия в Paxos. Что это?
Идентификаторы раунда (иначе номера предложений) должно увеличиваться, а должно быть уникальным для каждого экземпляра во всех узлах. В документе Paxos предполагается, что вы можете сделать это, потому что это тривиально. Вот одна схема, которая дает одинаковые результаты на всех узлах:
- Скажем, есть M узлов, участвующих в экземпляре Paxos.
- Сортировка всех узлов лексикографически. index [узел] - это индекс узла в этом отсортированном списке.
roundId = i*M + index[node] где 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
}
}