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

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

Цель этой статьи

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

В этой серии мы объясним алгоритм Raft в трех частях: принцип, исходный код и практика.Эта статья является второй частью серии "Бой на плоту":

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

Ссылки на серию исторических статей:Боевая серия протокола Raft (1) - основные понятия

что такое избиратель

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

Если разрабатываемая нами система сталкивается с необходимостью выбора мастера, то обычно это делается напрямую на основе zookeeper или etcd, а сложность этой части сводится к сторонней системе. Тем не менее, сам raft, который является основой etcd, также имеет концепцию «главного выбора», которая является двухуровневой: основной выбор на основе etcd относится к использованию стороннего etcd для согласования кластера. который является главным узлом.Технически говоря, машина состояний согласованности, аренда и механизм наблюдения etcd используются.Это также может быть сделано с одним узлом MySQL/Redis, но высокая доступность не может быть достигнута; и сам выбор плота относится к сам плот-кластер.Внутренне, посредством голосования, сердцебиения и других механизмов для координации главного узла, признанного большинством узлов в качестве лидера кластера, для координации всех решений.

Когда ваша система использует etcd для записи того, кто является главным узлом, это решение также обрабатывается внутри etcd главным узлом, выбранным его собственным кластером и синхронизированным с другими узлами.

Почему в Рафте первичные выборы?

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

Кроме того, по сравнению с другими алгоритмами консенсуса, плот дает узлу-лидеру более сильное лидерство, что называетсяStrong Leader. Например, записи журнала могут быть отправлены только с узла-лидера на другие узлы, а не наоборот.Этот метод упрощает логику репликации журнала и облегчает понимание raft.

Основной избирательный процесс плота

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

*Название диаграммы: Диаграмма состояния узла

Процесс перехода состояния ведомого

Основной выбор Raft основан на механизме сердцебиения, и каждый узел в кластере является последователем, когда он только запущен (Step: starts up), лидер будет периодически отправлять пакеты пульса всем узлам для поддержания своего авторитета, так как же избирается первый лидер? Метод заключается в том, что если ведомый не получает никакого пульса в течение определенного периода времени, то есть время выборов истекает, то он субъективно считает, что в системе нет доступного лидера, и инициирует новые выборы (Step: times out, starts election).

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

*Иллюстрация: исходное состояние кластера Raft из пяти узлов, все узлы являются последователями, термин равен 1, и каждый узел имеет свой таймер тайм-аута выборов.

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

*Иллюстрация: время ожидания S1 впервые истекло, он стал кандидатом, термин + 1 и отправил запрос на сбор информации другим узлам.

Кандидатный процесс перехода состояния

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

1. Успех выборов (Шаг: получает голоса с большинства серверов)

Когда кандидат от всего кластерасамыйКогда узел (N/2+1) получает голоса за один и тот же срок, он побеждает на выборах, немедленно меняет свою идентичность на лидера и начинает отправлять пульсации другим узлам для поддержания своего авторитета.

*Иллюстрация: «Большинство» узлов дали S1 голосов

*Иллюстрация: S1 становится лидером и начинает посылать сердцебиения для поддержания авторитета.

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

2. Провал на выборах (Шаг: обнаруживает текущего лидера или новый срок)

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

*Иллюстрация: S4 и S2 последовательно начинают выборы

*Иллюстрация: S4 становится лидером.После того, как S2 получит пакет пульса от S4, поскольку срок не меньше, чем его текущий срок, он немедленно переключится на ведомого, чтобы следовать за S4.

3. Шаг: тайм-аут, новые выборы

Третий возможный исход состоит в том, что кандидат не выигрывает и не проигрывает. Если несколько последователей становятся кандидатами одновременно, голоса могут быть разделены.Если ни один кандидат не может получить поддержку большинства узлов, то каждый кандидат будет тайм-аут. На этом этапе кандидату необходимо добавить свой срок, а затем инициировать новый тур выборов. Если здесь не сделать какой-то особый подход, голоса могут все время делиться, в результате чего лидер не будет избран. Под «специальным обращением» здесь понимается вышеупомянутоеРандомизировать тайм-аут выборов.

*Иллюстрация: S1~S5 все участвуют в выборах

*Иллюстрация: Ни один узел не желает голосовать за других

*Иллюстрация: если тайм-аут не рандомизирован, все узлы продолжат инициировать выборы одновременно...

Выше приведены три возможных результата выборов кандидата.

Процесс перехода состояния переключения лидера

Последняя строка на диаграмме состояния узла:discovers server with higher term. Представьте себе сценарий: когда ведущий узел не работает или сеть отключена, другие ведомые не получат сердцебиение ведущего, а первый узел, вызвавший тайм-аут, станет кандидатом и начнет опрос (из-за рандомизации времени тайм-аута каждого ведомого разные), так как срок кандидата больше срока первоначального лидера, все последователи проголосуют за него, и кандидат станет новым лидером. Через некоторое время первоначальный лидер восстановился, получил пакет пульса от нового лидера и обнаружил, что срок в пульсе больше, чем его собственный срок.В это время узел немедленно переключится на последователя и будет следовать за ним. новый лидер.

Анимационная симуляция вышеописанного процесса выглядит следующим образом:

*Иллюстрация: S4 как лидер term2

*Иллюстрация: S4 не работает, S5 будет первым истечет время ожидания

*Иллюстрация: S5 избран лидером срока 3

*Иллюстрация: S4 получил пульс term3 от S5 после восстановления после сбоя

*Иллюстрация: S4 немедленно становится последователем S5

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

Когда за лидера голосуют, лидер также должен брать на себя соответствующую ответственность.Что это за ответственность? Это «репликация журнала», о которой будет рассказано в следующей статье~

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