Совершить неудачу в Паксосе

Question

Я новичок в распределенной системе и алгоритме консенсуса.Я понимаю, как это работает, но меня смущают некоторые крайние случаи: когда акцепторы получили ПРИНЯТИЕ за экземпляр, но никогда не слышали о том, каков окончательный консенсус или решение, на что отреагируют акцепторы.Например, proposer-сервер запускается или не работает во время коммита или сразу после того, как он отправляет все ACCEPT.Что будет в этом случае?

Спасибо.

Answer 1

когда акцепторы получили ACCEPT для экземпляра, но никогда не слышали о том, каков окончательный консенсус или решение, [как] будут реагировать акцепторы.

Узел, отправляющий значение, обычно узнает, что его значение фиксируется путем подсчета положительных ответов на его сообщения ПРИНЯТЬ до тех пор, пока он не увидит большинство.Если сообщения отбрасываются, их можно отправлять повторно до тех пор, пока не пройдет достаточное количество сообщений для определения результата большинства.Акцепторы не должны ничего делать, но точно следуют алгоритму при отправке повторных сообщений.

Например, запрашивающий объект запускается или сбой во время принятия или сразу после отправки всего ПРИНЯТЬ.Что будет в этом случае?

Действительно, это интересный случай.Значение может быть принято большинством и поэтому зафиксировано, но никто не знает, так как все запланированные сообщения не были доставлены.

Ответы на сообщения PREPARE содержат информацию о уже принятых значениях.Таким образом, любой узел может выдавать сообщения PREPARE и узнавать, зафиксировано ли значение.Это на самом деле гений Паксос.Если значение принято большинством, если оно зафиксировано, потому что любой узел, на котором работает алгоритм, должен продолжать выбирать одно и то же значение при всех сценариях потери и сбоя сообщения.

Обычно Paxos использует стабильного лидера , которыйпотоков принимает сообщения для последовательных раундов с последовательными значениями.В случае сбоя лидера любой узел может сделать тайм-аут и попытаться провести его, отправив сообщения PREPARE.Несколько узлов, выдающих сообщения PREPARE, пытающиеся вести, могут прерывать друг друга, давая живую блокировку.Тем не менее, они никогда не могут не согласиться с тем, какое значение зафиксировано, если оно зафиксировано.Они могут соревноваться только за то, чтобы установить свою ценность, пока не получится достаточно сообщений, чтобы получить победителя.

Еще раз узлы-акцепторы не должны делать ничего, кроме как следовать алгоритму, когда новый лидер вступает во владение от разбитого лидера.Инварианты алгоритма означают, что ни один лидер не будет противоречить любому предыдущему лидеру в отношении фиксированного значения.Новые лидеры сотрудничают со старыми лидерами, и акцепторы могут просто поверить, что это так.Со временем достаточно сообщений, чтобы все узлы узнали результат.

Answer 2

Этот вопрос состоит из двух частей: Как акцепторы реагируют на новые предложения? и Как реагируют акцепторы, если они никогда не узнают результат?

В старых старых paxos акцепторам никогда не требуется знать результат .На самом деле совершенно разумно, что разные акцепторы имеют разные значения в своей памяти, никогда не зная, является ли значение, которое они имеют, фиксированным значением.

Реальная цель paxos - это решить первый вопрос.И, видя, что акцептор фактически никогда не знает, имеет ли он зафиксированное значение, он должен предположить, что он может иметь зафиксированное значение, но может быть открыт для замены его значения, если он не имеетсовершенное значение.Как это узнать?При получении сообщения, предлагающий всегда сравнивает округленное число, и если оно является старым, то приемное устройство сообщает запрашивающему, что он должен сначала «догнать» (a Nack ).В противном случае он верит, что заявитель знает, что он делает.

---

Теперь несколько слов о реальных системах.Некоторые настоящие системы Paxos могут избежать неприятностей с акцепторами, не заботясь о том, какое значение зафиксировано: Paxos просто здесь, чтобы выбрать, каким будет значение.Но многие реальные системы используют Paxos & Friends для создания избыточных копий данных для безопасного хранения.

Некоторые системы paxos будут продолжать пакетирование до тех пор, пока все акцепторы не получат данные.(Обратите внимание, что без вмешательства других авторов предложения, дополнительный пакет paxos копирует везде зафиксированное значение.) Другие системы настороженно относятся к помехам от других авторов и будут использовать другое сообщение Committed , которое обучает акцепторов (и других *).1024 * Учащиеся ) что такое зафиксированное значение.

Но что произойдет, если пропадатель потерпит крах?Последующий заявитель может прийти и предложить значение no-op .Если последующий заявитель готовит (фаза 1А) и может связаться с ЛЮБЫМ акцептором, который предыдущий заявитель успешно отправил Принимает к (фаза 2А), то он будет знать, каким был предыдущий заявительпытается сделать (через ответ в фазе 1B: PrepareAck ).В противном случае принимается безвредное значение no-op .