В этой статье представлены алгоритмические ограничения Raft на выбор мастера и репликацию журнала для обеспечения его безопасности (исходный текст статьи — «Безопасность», что на самом деле переводится здесь как"правильность"Более уместно, что внутренняя «безопасность» обычно соответствует «Безопасности», но из уважения к автору статьи в этой статье по-прежнему используется «безопасность»).

Примечание: Данная статья является оригинальной, при перепечатке просьба указывать источник.

Автор надеется помочь читателям глубже понять протокол Raft и применить его в инженерной практике, и в то же время интерпретировать ключевые моменты, которые нелегко понять или неправильно понять. Серия начинается сПринцип, исходный код, практикаТри части объясняют принципы и алгоритмы Raft:

• Основная частьВ сочетании с документом Raft, чтобы объяснить принцип алгоритма Raft, следуйте модульной идее Raft, соответственно объясните выбор лидера, репликацию журнала, безопасность, изменение членства в кластере, уплотнение журнала и т. д.
• исходный кодПроанализируйте hashicorp/raft, чтобы изучить промышленную реализацию Raft (hashicorp/raft — низкоуровневая зависимость от Consul).
• Практическая частьРеализуйте простое распределенное хранилище kv на основе hashcorp/raft в качестве последнего штриха.

Ссылки на серию исторических статей:

• Боевая серия протокола Raft (1) - основные понятия
• Боевая серия протокола Raft (2) - основная подборка
• Боевая серия протокола Raft (3) - репликация журнала

---

В предыдущих главах мы описали, как алгоритм Raft выбирает основной и реплицирует журнал, однако до сих пор мы описывалиЭтот механизм еще не гарантирует, что конечный автомат каждого узла применяет журналы в одном и том же порядке.. Представьте себе следующий сценарий:

1. Лидер скопировал некоторые логи на большинство узлов, и после фиксации произошел даунтайм.
2. Фолловер не реплицируется в эти логи, но участвует в выборах и избирается следующим лидером.
3. Новый лидер синхронизирует и фиксирует некоторые журналы, которые перезаписывают предыдущие зафиксированные журналы на других узлах.
4. Конечные автоматы каждого узла могут применять разные последовательности журналов, что приводит к несоответствиям.

Поэтому нам нужно добавить некоторые дополнительные ограничения в механизм «выбор мастера + репликация журнала», чтобы гарантировать, чтоБезопасность конечного автомата, что является корректностью алгоритма Рафта.

1. Ограничения на выборы

Давайте проанализируем сценарий, в котором зафиксированный журнал перезаписывается, как описано выше.Фундаментальная проблема фактически возникает на шаге 2. Кандидат должен обладать достаточной квалификацией, чтобы быть избранным лидером кластера, иначе он принесет в кластер непредсказуемые ошибки. О том, обладает ли кандидат этой квалификацией, можно судить, добавив во время выборов небольшое условие, а именно:

Каждый кандидат должен иметь последнюю версию (термин, индекс) своего локального журнала в RPC RequestVote.Если ведомый обнаружит, что в журнале кандидата нет собственного нового журнала, он откажется голосовать за кандидата.

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

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

Логика сравнения двух (термин, индекс) очень проста: если термин отличается, обновление журнала с большим термином, в противном случае обновление журнала с большим индексом.

2. Ограничения на материалы

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

Вспомним, что такое коммит:

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

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

Однако лидер не может свободно фиксировать журнал, оставленный старым термином, в любое время, даже если он был реплицирован на большинство узлов. В документе Raft приводится классический сценарий:

*фигура 1

Рисунок 1 моделирует сценарии проблемы в хронологическом порядке слева направо.

этап а: S1 является лидером.После получения запроса (term2, index2) копируется только в S2 и не копируется в S3 ~ S5.

этап б: S1 отключен, а S5 избран лидером термина 3 (три голоса S3, S4 и S5).После получения запроса (term3, index2) сохраняется и не копируется ни на один узел.

этап с: S5 отключен, S1 восстановлен, S1 переизбран лидером термина 4 и продолжает копирование (term2, index2) на S3.Большинство узлов были удовлетворены, и мы зафиксируем это.

этап г: S1 снова не работает, S5 восстановлен, S5 переизбран лидером (три голоса S2, S3, S4), копирование (term3, inde2) на все узлы и фиксация. Обратите внимание, что произошла фатальная ошибка, и зафиксированный (term2, index2) был перезаписан (term3, index2).

Чтобы избежать этой ошибки, нам нужно добавить дополнительное ограничение:

Лидер разрешает только коммиты, которые содержат журналы текущего термина.

Для приведенного выше сценария проблема возникает на этапе C. Даже если S1, лидер term4, реплицирует (term2, index2) на большинство узлов, он не может зафиксировать его напрямую, а должен дождаться прибытия журнала term4 и успешно выполнить репликацию. вместе.

этап д: после добавления этого ограничения либо (term2, index2) никогда не фиксируется, поэтому S5 безопасно перезаписывает его на этапе d, либо (term2, index2) фиксируется вместе с (term4, index3), так что S5 не вообще Лидер не может быть избран, т.к. логи большинства нод новее его, так что предыдущей проблемы нет.

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

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

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

Добро пожаловать, чтобы переслать и обратить внимание на публичный аккаунт автора WeChat:Блог Q.Время от времени отправляйте галантерею, практический опыт, сводку системы, интерпретацию исходного кода, технические принципы.