Что делать, если лидер терпит неудачу в Multi-Paxos для систем master-slave?

Question

Backgound:

В разделе 3, озаглавленном "Реализация конечного автомата", из бумаги Лампорта " Paxos Made Simple, Multi-Paxos". Multi-Paxos используется в Google Paxos Made Live. (Multi- Paxos используется в Apache ZooKeeper). В Multi-Paxos могут появляться пробелы:

В общем, предположим, что лидер может получить α команды впереди - то есть, он может предлагать команды i + 1 через i + α команды после команд с 1 по i выбраны. Разрыв до α - 1 команды могут возникнуть.

Теперь рассмотрим следующий сценарий:

Вся система использует архитектуру master-slave. Только мастер обслуживает клиентские команды. Ведущий и подчиненные достигают консенсуса относительно последовательности команд через мультипаксо. Мастер является лидером в инстансах Multi-Paxos. Предположим, что теперь ведущий и два его подчиненных имеют состояния (команды были выбраны), показанные на следующем рисунке:

,

Обратите внимание, что в основном состоянии более одного пробела. Из-за асинхронности два раба отстают. В это время мастер терпит неудачу.

Проблема:

1. Что должны делать рабы после обнаружения отказа мастера (например, по механизму сердцебиения)?

2. В частности, как справиться с пробелами и пропущенными командами по отношению к старому мастеру?

Обновление о Заб:

Как указал @sbridges, ZooKeeper использует Zab вместо Paxos. Цитировать,

Zab в первую очередь предназначен для систем первичного резервного копирования (т. Е. Главного-подчиненного), таких как ZooKeeper, а не для репликации конечных автоматов.

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

3. В режиме восстановления Zab также страдает от проблемы гапсов? Если так, что делает Заб?

Answer 1

Разрывом должны быть экземпляры Paxos, которые не достигли соглашения. В статье Paxos Made Simple этот пробел заполняется предложением специальной команды "no-op", которая оставляет состояние неизменным.

Если вам важен порядок выбранных значений для экземпляров Paxos, лучше вместо этого использовать Zab, потому что Paxos не сохраняет причинный порядок. https://cwiki.apache.org/confluence/display/ZOOKEEPER/PaxosRun

Отсутствующей командой должны быть экземпляры Paxos, которые достигли соглашения, но не были изучены учащимся. Значение является неизменным, поскольку было принято кворум акцептора. Когда вы запустите экземпляр paxos с этим идентификатором экземпляра, значение будет выбрано и восстановлено на том же этапе 1b.

Когда рабы / последователи обнаружили сбой в Лидере или Лидер потерял кворум поддержки рабов / последователей, они должны выбрать нового лидера.

В zookeeper не должно быть пробелов, так как последователь связывается с лидером по TCP, который сохраняет FIFO.

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

В режиме широковещания подписчик помещает предложение в очередь в pendingTxns и ожидает выполнения команды COMMIT в том же порядке. Если zxid COMMIT не совпадает с zxid заголовка pendingTxns, последователь завершит работу.

https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab1.0

Answer 2

В частности, в документе ZAB говорится, что новоизбранный лидер предпринимает открытие, чтобы узнать номер следующей эпохи и установить, у кого самая актуальная история коммитов. Последователь пески ACK-E сообщение, в котором указано максимальное смежное zxid это видел. Затем говорится, что он выполняет фазу синхронизации, где передает состояние, пропущенные ими последователи. Он отмечает, что при интересной оптимизации следует выбирать только лидера, который имеет самую актуальную историю коммитов.

С Paxos вам не нужно допускать пробелы. Если вы разрешаете пропуски, то в документе Paxos Made Simple объясняется, как их устранить, на стр. 9. Новый руководитель знает последнее подтвержденное значение, которое он видел, и, возможно, некоторые подтвержденные значения выше. Он проверяет слоты с самого низкого из известных ему промежутков, выполняя фазу 1, чтобы предложить эти слоты. Если в этих слотах есть значения, он выполняет фазу 2, чтобы зафиксировать эти значения, но если он может свободно устанавливать значение, он устанавливает значение no-op. В конце концов он попадает в номер слота, где не было предложено никаких значений, и работает как обычно.

В ответ на ваши вопросы:

1. Что должны делать рабы после обнаружения отказа мастера (например, по механизму сердцебиения)?

Они должны попытаться вести после случайной задержки, чтобы уменьшить риск одновременного предложения двух кандидатов, что приведет к потере сообщений и сбросов диска, так как может привести только один. Рандомизированный тайм-аут лидера хорошо описан в статье о Плоте; такой же подход может быть использован для Paxos.

2. В частности, как справиться с пробелами и пропущенными командами по отношению к старому мастеру?

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

Answer 3

Multi-Paxos используется в Apache ZooKeeper

Zookeeper использует zab, а не paxos. Смотрите эту ссылку для разницы.

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

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

Answer 4

Ответ @Hailin объясняет проблему разрыва следующим образом:

В zookeeper не должно быть пробелов, так как последователь связывается с лидером по TCP, который сохраняет FIFO"

В дополнение:

В статье "Простой полностью упорядоченный протокол вещания" упоминается, что ZooKeeper требует свойство префикса:

Если $ m $ - последнее сообщение, доставленное для лидера $L$, любое сообщение, предложенное до $ m $ на $L$, также должно быть доставлено ".

Это свойство в основном зависит от механизма TCP, используемого в Zab. В Zab Wiki упоминается, что реализация Zab должна следовать следующему предположению (помимо других):

Серверы должны обрабатывать пакеты в порядке их получения. Поскольку TCP поддерживает порядок при отправке пакетов, это означает, что пакеты будут обрабатываться в порядке, определенном отправителем.