Откуда заявитель знает, что его предложение не одобрено кворумом акцепторов?

Question

Я читаю "Паксос" на вики, и он читает: «Раунды заканчиваются неудачей, когда несколько Заявителей отправляют противоречивые сообщения Подготовки или когда Заявитель не получает Кворум ответов (Обещание или Принято). В этих случаях необходимо начинать еще один раунд с большим номером предложения». Но я не понимаю, как заявитель сообщает разницу между тем, что его предложение не было одобрено, и просто требуется больше времени для передачи сообщения?

Answer 1

Одна из хитрых частей в понимании Paxos заключается в том, что оригинальная статья и большинство других, включая вики, не описывают полный протокол, пригодный для реального использования.Они сосредоточены только на алгоритмических потребностях.Например, они говорят, что заявитель должен выбрать число «n» больше, чем любое ранее использованное число.Но они ничего не говорят о том, как на самом деле сделать это, о возможных сбоях или о том, как разрешить ситуацию, если два участника одновременно пытаются использовать один и тот же номер предложения (как в обоих, выбирающих n = 2).Это на самом деле полностью нарушает протокол и может привести к неверным результатам, но я не уверен, что когда-либо видел это специально вызванным.Я предполагаю, что это просто должно быть "очевидно".

Конкретно на ваш вопрос, нет идеального способа определить разницу, используя необработанный алгоритм.Практические реализации обычно делают все возможное, отправляя сообщение Nack в Proposer, а не просто игнорируя его.Есть много других приемов, которые можно использовать, но все они, включая Nacks, имеют различные недостатки.Какой подход лучше всего, обычно зависит как от типа приложения, использующего Paxos, так и от среды, в которой он предназначен.

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

Answer 2

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

Часто реализации добавляют сообщения "nack" как отрицательное подтверждение в качестве оптимизации для ускорения восстановления.Предлагающий получает только «откровенные» ответы от достижимых узлов, которые приняли более высокое обещание.«Nack» может показывать как самое высокое обещание, так и самый высокий экземпляр, который, как известно, исправлен.Как это поможет, будет описано ниже.

Я написал реализацию Paxos под названием TRex , в которой некоторые из этих методов максимально приближены к описанию алгоритма в статье Paxos Made Simple .Я написал описание практических соображений о тайм-аутах и ​​нэках в блоге .

Один из интересных методов, которые он использует, заключается в том, что узел с тайм-аутом делает первое предложение с очень низким числом.Это всегда будет получать "Nack" сообщения.Зачем?Рассмотрим кластер из трех узлов, где одно сетевое соединение разрывается между стабильным предложителем и другим узлом.Другой узел прекратит работу и выдаст подготовку.Если он выдает высокую подготовку, он получит обещание от третьего узла.Это прервет стабильного лидера.Тогда у вас будет симметрия, в которой два узла, которые не могут сообщать друг другу, могут бороться с заменой руководства без продвижения вперед.

Чтобы избежать этого, тайм-аут узла может начинаться с низкой подготовки.Затем он может просмотреть сообщения «nack», чтобы узнать от третьего узла, что есть лидер, который делает успехи.Он увидит это, так как самый высокий экземпляр, известный как фиксированный в nack, будет больше, чем локальное значение.Узел тайм-аута не может затем выполнить высокую подготовку и вместо этого попросить третий узел отправить ему последние фиксированные и принятые значения.Благодаря этому усовершенствованию узел времени ожидания теперь может различать стабильный сбой предлагающего или сбой соединения.Такие методы, основанные на «недолговечности», не влияют на правильность реализации, они являются лишь оптимизацией, обеспечивающей быстрое восстановление после отказа и продвижение вперед.