Несколько вопросов о Паксосе

Question

Я смущен значением, выбранным предложителем. используйте пример, чтобы объяснить. Если теперь заявитель хочет заблокировать файл, то он отправит, что l1 - это номер_процессора, а v1 - значение "заблокировать файл", и акцепторы принимают его. чем запрашивающий хочет разблокировать файл, и отправляет (l2 > l1), что v2 является значением "unlock the file", после этого акцептор возвращает последнее значение, а предлагающий выбирает его и отправляет снова.

в этом примере v2 потеряно? или каков реальный процесс в этом примере? Кроме того, это два раунда или один раунд? как бороться с туром?

Answer 1

Паксос не атомный регистр; Как только Paxos выберет значение, оно НЕ МОЖЕТ измениться.

Во-первых, обратите внимание, что ваша блокировка является конечным автоматом:

          on_lock
       .-----------.
       |           |
+------+---+    +--v-----+
| UNLOCKED |    | LOCKED |<--- start
+------^---+    +--+-----+
       |           |
       `-----------'
         on_unlock

Paxos можно использовать для определения последовательности переходов; но каждый новый переход должен решаться в новом экземпляре Paxos.

Я предлагаю взглянуть на некоторые другие вопросы о paxos в Stackru:

• выбор значения paxos
• реализация алгоритма Паксоса
• Вопросы по реализации Paxos

Answer 2

Нам нужно описать протокол блокировки, который мы можем использовать для запуска Paox, чтобы понять, когда доступно несколько значений, и увидеть результат выбора значения.

Блокировка - это ячейка, содержащая значение токена блокировки в формате L={T,P}, где P это процесс, удерживающий замок и T время, когда процесс захватил блокировку. Чтобы получить блокировку, которую отправляет клиент V={Lc,Ln} где Lc это то, что он думает, текущий токен блокировки и Ln={T',P'} это новый токен блокировки, который он хочет установить. Специальный токен Nil можно отправить, чтобы разблокировать замок. Новый токен не устанавливается, если в сообщении не указано правильное Lc это соответствует текущему токену. Этот метод сравнения и обмена (CAS) предотвращает ошибочное применение сообщения о отложенной разблокировке. Это также работает для тайм-аута блокировки, когда клиенты могут ее украсть; если два процесса отправляют два гоночных сообщения {L1,L2} а также {L1,L3} только один может добиться успеха. Процесс узнает, успешно ли выполнена его операция, проверяя возвращаемое значение, которое является значением блокировки L, Процесс может запросить значение блокировки, отправив {Nil,Nil} это CAS "ничего не делать", который открывает открытый замок; но который возвращает, кому принадлежит блокировка, если блокировка закрыта.

Пишет должен пройти через лидера. Если узел знает, что это не лидер, он должен перенаправить клиента к лидеру. Если узел не знает, кто является лидером, он должен выдать ошибку, и клиент должен выбрать другой узел случайным образом. Если узел считает себя лидером, он может ответить клиенту только тогда, когда он уверен, что большинство узлов приняли новое значение. Это связано с тем, что Paxos гарантирует, что значение, принятое большинством, станет долговечным для кластера. Если узел был ведущим, то он не слышал большинство подтверждений, он не может ответить клиенту. Он может быть изолирован от других узлов. Другие узлы могут иметь недавно избранного лидера. Это также относится к {Nil,Nil} запросы, которые требуют большинства подтверждений для подтверждения лидера, все еще являются лидером, чтобы сообщить клиенту текущее значение блокировки. В конце концов узел должен услышать, существует ли новый лидер, иначе время ожидания пытается получить значение, принятое большинством. Затем он должен либо перенаправить клиента к новому лидеру, либо вернуть клиенту ошибку.

Теперь мы можем рассмотреть несколько значений при отказе лидера. Клиент A отправляет действительное обновление CAS V1 который должен следовать за лидерным узлом X из трех узлов кластера. Узел X посылает accept(N1,V1) к себе и узлам Y а также Z, Он принимает свою ценность, а также получает признание от Y но сеть сбрасывает сообщение Z, Тогда узел X темнеет и перестает выдавать какие-либо сообщения на некоторое время. Возможно, он мертв или застопорился, но мы пока не знаем. Это видел большинство X,Y но теперь он - таинственный кот Шредингера, мертвый или живой, пока мы не увидим другое сообщение от него, чтобы узнать его судьбу. Именно здесь Paxos решает использовать совместную работу для получения последовательного и правильного результата независимо от того, что произойдет дальше.

Через некоторое время узел Z Тайм-аут, как он не слышал от лидера слишком долго. Это проблемы propose(N2) к себе и другим узлам. Возвращается promise(N2,V1) от узла Y а также promise(N2,empty) от себя. Имеет большинство Y,Z и может привести. Только узел X знает это значение V1 были приняты большинством, и было ли клиенту сказано, что он успешно прошел CAS; но молчит. Узел Z должен сделать консервативный выбор. Если бы это было предположить X мертв, это может быть неправильно: узел X может быть жив и мог сказать клиенту, что операция прошла успешно. Узел Z должны сотрудничать и закончить частичную работу последнего лидера, ведя с V1 как его первое значение. Так что отправляет accept(N2,V1) на все три узла. Теперь не имеет значения, если узел X мертв или жив или сказал клиенту, что операция прошла успешно или нет. Во всех случаях протокол блокировки не будет нарушен, и клиент обнаружит, что у него есть блокировка, если он попытается повторить ошибку; он не видит, и не важно, какое предложение ни какой узел совершил работу.