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