Выбор значения paxos
Я читал о Паксосе на вики-странице и газете (Паксос сделан просто). Тем не менее, я все еще смущен некоторыми деталями:
На этапе 1а включает ли заявитель значение, которое он намеревается выбрать в предложении для акцепторов?
На этапе 1b акцептор должен вернуть значение, которое он принял ранее, если таковой имеется. каков срок службы стоимости? IOW, когда он считается принятым и когда он перезаписывается / отбрасывается?
Некоторые обновления о пожизненном вопросе. IIUC, после первого принятия, акцептор должен всегда иметь под рукой ранее принятое значение. Как он решает, должен ли он вернуть его в следующей фазе обещания (1b)? Или когда он решает забыть ценность?
Обновления 2, чтобы лучше обсудить с @MichealDeardeuff:
У меня есть ниже понимание Паксос:
Обычно в рабочем процессе Paxos акцептор всегда должен иметь под рукой ранее принятое значение. А при ответе на запрос на подготовку он отправит значение обратно в ответ на обещание. И заявитель должен проверить, является ли значение таким же, как само предложенное в последнем раунде. Если это не так, заявитель переходит к отправке запроса на принятие со значением, возвращенным получателем. Если это так, то предлагающий затем переходит к отправке запроса Accept со значением, которое он намеревался отправить в текущем раунде.
Верно ли понимание выше?
Если это не правильно, объясните, пожалуйста, почему?
Если это правильно, я запутался, потому что протокол Paxos явно не говорит об этом. Это только заявляет:
где v - значение предложения с наибольшим номером среди ответов или любое значение, если в ответах не было предложений.
Тем не менее, насколько я понимаю, заявитель должен проверить и посмотреть, является ли значение, возвращаемое акцептором, тем же значением, что и тот же заявитель, предложенный в последнем раунде. Если это так, даже если среди ответов на обещание есть значение с предложением с наибольшим номером, заявитель все равно может выбрать любое значение, которое он хочет, как если бы не было значений, возвращаемых получателями.
И это причина, по которой я хочу посмотреть, есть ли какая-либо ссылка, чтобы поддержать понимание.
Спасибо большое!
1 ответ
На этапе 1а включает ли заявитель значение, которое он намеревается выбрать в предложении для акцепторов?
Заявителю не нужно отправлять значение, которое он намерен выбрать, до фазы 2а. Смотрите также мой ответ на предыдущий вопрос.
На этапе 1b акцептор должен вернуть значение, которое он принял ранее, если таковой имеется. каков срок службы стоимости? IOW, когда он считается принятым и когда он перезаписывается / отбрасывается?
Из моего ответа на другой вопрос: "Акцептор должен принимать все значения, если он не обещал не принимать его". То есть он должен принимать любое значение с идентификатором раунда, большим или равным идентификатору раунда в последнем отправленном им ответе.
Причина, по которой он должен принимать любое другое значение, заключается в том, что заявитель может обнаружить (в результате этапа 1), что другое значение должно быть выбрано или уже было выбрано; Затем он передает это значение всем получателям. Это несоответствие может произойти, когда есть несколько авторов и / или во время сетевого раздела.
Обновление, чтобы ответить на комментарий.
Когда акцептор принимает значение, он сохраняет это значение до тех пор, пока не примет другое значение. (наряду с этим он сохраняет раунд значения).
На Фазе 1b, Акцептор всегда отправляет свое значение, позволяя Предлагателю разобраться, каково фактически выбранное значение. Он никогда не забывает свою текущую стоимость. Когда-либо.
После получения обещаний от акцепторов, у автора предложения открывается прекрасный вид на систему. (Примечание: это не обязательно полный или актуальный вид.)
Может случиться так, что разные акцепторы приняли разные значения из-за разногласий с другим предложителем. Таким образом, предлагающий выбирает значение с наибольшим круглым идентификатором и отправляет это значение всем получателям. Вот почему значения акцепторов могут изменяться.
Озабоченность в комментариях заключается в том, что это нарушает Паксос. Не так.
Но прежде чем перейти к примеру, позвольте мне подчеркнуть, что гораздо проще думать о Paxos с именованными фазами и сообщениями вместо 1a, 1b, 2a, 2b. Обычно я называю фазы подготовительной и принимающей. С сообщением 1a как Подготовить, 1b как Обещание, 2a как Принятие и 2b как Принято.
Теперь давайте возьмем гипотетический пример, который люди часто приводят и который, по их мнению, разрушает Паксос. Предположим, у нас есть три акцептора A1, A2 и A3. А1 и А2 имеют принятое значение ABC в 1 раунде, а А3 выбрало XYZ в 2 раунде (т.е. от другого заявителя). Мы можем видеть, что А1 и А2 составляют большинство и что ABC был "выбран".
Продолжая этот гипотетический пример, заявитель отправляет Prepare(3) и получает ответные ответы от A2 и A3, а именно Promise(ABC @ 1) и Promise(XYZ @ 2). Proposer видит, что XYZ имеет самый высокий раунд, и отправляет его на этапе принятия, перезаписывая ABC на других хостах. И альт, Паксос сломан, верно?
Нет. Проблема в начальном состоянии, что невозможно. Позвольте мне показать вам, почему.
Во-первых, некоторые предложения, которые являются ключевыми для правильной работы Paxos:
Предложение A: чтобы A1 и A2 имели значение ABC @ 1, заявитель должен был отправить Accept(ABC @ 1), что означает, что он должен получить большинство обещаний в ответ на отправку Prepare(1).
Предложение B: Чтобы A3 имел значение XYZ @ 2, заявитель должен был отправить Accept(XYZ @ 2), что означает, что он должен получить большинство Обещаний в ответ на отправку Prepare(2).
А теперь доказательство:
Случай 1: у A1 и A2 уже есть значения ABC @ 1. Согласно предложению B, чтобы A3 имел значение XYZ @ 2, он должен был получить большинство обещаний от акцепторов. Так как значение ABC находится на большинстве акцепторов, то по крайней мере один из них должен был отправить Promise(ABC @ 1). Если 1 является наибольшим круглым идентификатором, то заявитель должен выбрать значение ABC и отправить сообщение Accept(ABC @ 2). Но это не так, он послал Принять (XYZ @ 2). Противоречие.
Случай 2: A3 уже имеет значение XYZ @ 2. (Помните, раунд 2 может предшествовать раунду 1: идентификаторы раунда монотонно растут только для каждого заявителя.) Согласно предложению A, для A1 и A2 значение ABC @ 1, a Заявитель должен был получить большинство Обещаний от акцепторов. Точно так же, согласно предложению B, для того, чтобы A3 имел его, он также должен был получить большинство Обещаний. Это означает, что должен быть хотя бы один акцептор в наборе {A1, A2}, который Обещан дважды.
Случай 2a: получатель отправил сначала Promise(1), затем Promise(2). Затем, когда он получил сообщение Accept(ABC @ 1), он, должно быть, отклонил его, потому что он пообещал принять значение не ранее 2. Но он не отклонил его, потому что он имеет значение ABC @ 1. Противоречие.
Случай 2b: акцептор отправил Promise (2) первым. Затем, когда он получил сообщение Prepare(1), он, должно быть, отклонил его, потому что он уже обещал более высокий раунд. Но это явно не так, потому что, по предложению A, он отправил Promise(1). Противоречие.
Вот Это Да!
Я надеюсь, что это помогает вам.
Обновление 2: Вот псевдопифонная реализация Paxos
from itertools import count
from concurrent import futures
class Acceptor():
def __init__(self):
self.acceptedValue = None
self.acceptedRound = None
self.promisedRound = None
def onPrepare(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.promisedRound = message.round
response = new Promise(round=self.acceptedRound, value=self.acceptedValue)
send(message.source, response)
def onAccept(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.acceptedValue = message.value
self.acceptedRound = message.round
send(message.source, new Accepted())
class Proposer():
def __init__(self, selfId, quorum):
self.quorum = quorum
self.id = selfId
# get a unique starting round,
# assumes acceptors and proposers are on same hosts
self.initialRound = sorted(quorum).index(selfId)
def propose(self, value):
"Propose a value to be chosen; returns actual value chosen"
# round is always unique to a proposer
# count(start, step) returns an infinite sequence
for round in count(self.initialRound, len(self.quorum))
promises = self.prepare(round)
if not promises: continue
# interpret the prepare phase results, may be None
selectedValue = max(promises, key=lambda p: p.round or -1)
accepted = self.accept(round, selectedValue or value)
if accepted: return value
def prepare(self, round):
"Drive the Prepare phase. returns the promises from the acceptors or None"
message = new Prepare(round, source=self.id)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)))
# wait for the results
promises = []
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Promise):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return None
promises.append(message)
if (len(promises) > len(self.quorum) / 2:
return promises
# No majority of responses
return None
def accept(self, round, value):
"Drive the Accept phase. returns True iff the value was accepted"
message = new Accept(round, value)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)
# wait for the results
accepts = 0
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Accepted):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return False
accepts = accepts + 1
if accepts > len(self.quorum) / 2:
return True
# No majority of responses
return False
Обновление 3 Чтобы ответить на дополнительные вопросы из комментариев.
… Если это то же значение, которое proposer послал в последнем раунде, мы хотим, чтобы proposer проигнорировал его (в противном случае мы попадем в тупик, верно?)
(Я предполагаю, что "игнорирование" значения означает преждевременный выход из цикла.)
Во-первых, обратите внимание, что цикл заканчивается, когда предлагающий получает подтверждение от большинства акцепторов, что значение было выбрано. Таким образом, если заявитель обнаруживает, что выполняет последующую фазу подготовки, вы можете быть уверены, что он конкурирует с другим заявителем ИЛИ произошел какой-то сетевой раздел. Во-вторых, обратите внимание, что этап подготовки возвращает значение, даже если только один акцептор принял значение (то есть значение, возможно, не было принято большинством).
Если фаза "Подготовка" приводит к значению , равному значению, которое она видела в предыдущем раунде, она все равно должна перейти к фазе "Принять" по нескольким причинам.
- Если предложивший рано выходит из цикла, возможно, произошел сбой другого предложившего. Это может привести к тому, что значение не будет выбрано.
- Если он выходит из цикла рано, то разумно, чтобы другой заявитель следовал тому же алгоритму, который также вышел из цикла; снова в результате, возможно, не будет выбрано значение.
- Если так получилось, что значение действительно было выбрано, возможно, что не все узлы получили значение (из-за сетевого раздела) или имеют другое значение (из-за этого сражения с другим предложителем). Это хорошо, тогда, чтобы продвинуть значение к узлам ради долговечности.
С другой стороны, Paxos может зайти в бесконечный цикл, когда между двумя или более претендентами возникает спор, а некоторые испытывают неудачу. (Это справедливо для любого алгоритма консенсуса и было доказано Лисковым и др. До того, как какой-либо алгоритм консенсуса был фактически обнаружен.) Так говорит теория, но в практических системах это легко обойти: в каждом последующем раунде пауза для случайного количества времени, чтобы дать другому участнику возможность выиграть гонку. Конечно, все еще возможно иметь бесконечный цикл, но вряд ли это когда-либо случится при жизни вселенной.
У вас есть какие-либо ссылки в поддержку аргумента?
Я говорю в основном из моего собственного обучения и опыта. Я работаю в команде, которая разрабатывает и поддерживает систему, основанную на ядре Paxos. Я также сделал обширное исследование по этому вопросу.
Вот несколько хороших работ на эту тему:
- Paxos Made Simple (о котором вы уже говорили, что уже читали)
- Парламент Паксона (оригинал статьи)
- Деконструкция Paxos (модулирует Paxos на несколько компонентов, которые затем настраиваются для различных сценариев)
- ABCDs Paxos (Батлер Лэмпсон популяризировал Paxos, но иногда он может сбить с толку.)
Обновление 4 Ответы на обновления в вопросе.
Обычно в рабочем процессе Paxos акцептор всегда должен иметь под рукой ранее принятое значение. А при ответе на запрос на подготовку он отправит значение обратно в ответ на обещание. И заявитель должен проверить, является ли значение таким же, как само предложенное в последнем раунде. Если это не так, заявитель переходит к отправке запроса на принятие со значением, возвращенным получателем.
Хорошо, пока. Но заявитель не должен поддерживать состояние между раундами. Мы скоро узнаем почему.
Если это [то же значение], то предложивший затем отправляет запрос Accept со значением, которое он намеревался отправить в текущем раунде.
Если какое-либо значение возвращается акцептором, то на этапе принятия необходимо использовать значение с наибольшим круглым идентификатором. Если никакое значение не возвращается акцептором, тогда может использоваться любое значение: моя логика предполагает, что это будет значение, которое клиент передал предложившему.
Сравните это с Paxos Made Simple (стр. 6):
... где v - значение предложения с наибольшим номером среди ответов или любое значение, если в ответах не было предложений.
(Довольно трудно, чтобы терминология переключалась между бумагами. Здесь Лэмпорт использует термин " пронумерованные предложения", в других местах он использует термин round-id. Есть одно и то же.)
Предположим, что предложитель запускает фазу подготовки и видит это состояние среди акцепторов.
A1 A2 A3
promise: 3 ? 4
value@round: x@3 ? y@4
где фактическое состояние
A1 A2 A3
promise: 3 4 4
value@round: x@3 y@4 y@4
Теперь предположим, что он провел предыдущий раунд со значением y. Если в этой точке разрешено выбирать любое значение, оно может вызвать это состояние:
A1 A2 A3
value@round: z@5 z@5 z@5
Это перезаписывает выбранное значение, нарушая свойство согласованности консенсуса (а именно, может быть выбрано самое большее одно значение.).
Если вы хотите такого рода поведение, вы не можете использовать согласованный протокол как есть. Вы можете использовать протоколы, такие как ABD, или другой круговой регистр. Или вы можете думать о Паксосе как о выборе перехода в конечном автомате. Другими словами, каждый раз, когда вы хотите изменить переменную, вы запускаете новый алгоритм Paxos, чтобы выбрать переход. Это то, что делает моя система (и я осмелюсь сказать, что большинство практичных систем Paxos).
Обратите внимание, что регистры ABD и циклические регистры действуют аналогично Paxos, но немного проще, потому что они не должны гарантировать вышеуказанное свойство согласованности (после выбора всегда выбирается). Но конечный автомат на основе Paxos допускает операции CAS с переменными.