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

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

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

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

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

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

В Фазе 1a: Включает ли это значение, которое нужно согласовать с сообщением Prepare, или это отложено на Accept! сообщение? Или это имеет значение?
В Фазе 2a: "Если какой-либо из Акцепторов уже принял значение, лидер должен Выбрать значение с максимальным номером предложения N '.

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

В Фазе 2a: "В противном случае, Proposer может выбрать любое значение". Что это значит? Значение для чего? Номер предложения?
Paxos, похоже, полагается на увеличение стоимости N (номер предложения) для работы? Правильно ли это?
В записи wikipedia не обсуждаются начальные значения, которые должен быть установлен node, прежде чем приступать к участию в Paxos. Что это?

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

Ответ 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
    }
}

Ответ 2

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

Ответы на мой вопрос, который я мог найти, следующие:

Разве Паксо не войдет в бесконечное цикл?

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

Что такое "последнее значение, которое он принял"?

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

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

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

Включает ли это значение для согласования с сообщением "Подготовить" или это отложенный до принятия! сообщение? Или это имеет значение?

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

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

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

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

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

Paxos, похоже, полагается на увеличение стоимости N (номер предложения) для работы? Правильно ли это?

Да. Поставщик p должен все чаще указывать свои предложения.

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

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

Ответ 3

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

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