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

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

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

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

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

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

Что такое Рафт?

Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems.

--《В поисках понятного алгоритма консенсуса》

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

Так называемая согласованность не означает, что состояние всех узлов в кластере должно быть полностью непротиворечивым в любой момент времени, но относится к цели, то есть к тому, чтобы распределенная система выглядела так, как будто у нее есть только одна копия данных, а чтение а операции записи являются атомарными, поэтому уровень приложения может игнорировать проблему синхронизации между несколькими копиями данных в нижней части системы. Иными словами, мы можем рассматривать сильно непротиворечивую (линейную непротиворечивость) распределенную систему как единое целое.Как только клиент успешно выполнит операцию записи, все клиенты должны иметь возможность прочитать только что записанное значение. Даже в случае сбоя сетевого раздела или небольшого числа узлов кластер в целом может предоставлять услуги, как отдельная машина.

Для этого используется алгоритм консенсуса (Consensus Algorithm), который гарантирует, что даже в случае небольшого количества (≤ (N-1)/2) отказов узлов система все равно сможет предоставлять услуги внешнему миру. Алгоритмы консенсуса обычно основаны на модели Replicated State Machine, то есть все узлы начинают с одного и того же состояния, проходят одни и те же операции журнала и, наконец, достигают согласованного состояния.

Replicated State Machine

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

Основные концепции плота

Подзадачи, связанные с согласованностью плота

Raft использует механизм кворума для достижения консенсуса и отказоустойчивости. Мы называем работу кластера Raft предложением. Всякий раз, когда предложение инициируется, оно должно быть одобрено большинством (> N/2) узлов, прежде чем оно может быть представлено.

Основной алгоритм Raft делит проблему непротиворечивости на три подзадачи и решает их одну за другой, что значительно повышает удобство использования алгоритма:

Leader election
- В кластере должен быть ведущий узел.
Log replication
- Узел Лидер отвечает за получение клиентских запросов и сериализацию операций запросов в синхронизацию журналов.
Safety
- Включая ряд мер, таких как ограничения на выборы лидеров и ограничения на отправку журналов, для обеспечения безопасности конечного автомата.

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

Концепция ролей узлов в кластере

Каждый узел в кластере Raft играет одну из трех ролей:

Leader
- Все обработчики запросов получают запросы на операции, инициированные клиентами, записывают их в локальные журналы и синхронизируют с другими узлами в кластере.
Follower
- Пассивный обновляющий запрос получает запрос на обновление от лидера и записывает его в локальный файл. Если запрос операции клиента отправляется ведомому, он будет перенаправлен ведомым сначала ведущему.
Candidate
- Если ведомый не получает сердцебиение лидера в течение определенного периода времени, считается, что лидер, возможно, вышел из строя.В это время начинается процесс выбора лидера, и узел переключается на кандидата до избрания лидера заканчивается.

Понятия, связанные с выборами

Каждый раз, когда начинаются новые выборы, называемые термином, с каждым термином связано строго возрастающее целое число.

Переключение состояний узла показано на рисунке:

Диаграмма состояния узла

Конкретные инструкции заключаются в следующем:

Starts up
- Узел автоматически переходит в состояние ведомого, когда он только что запущен.
Times out, starts election
- После перехода в состояние ведомого запускается таймер выборов, по истечении которого он переключается на кандидата и инициирует выборы, пульс узла-лидера частично сбрасывает этот таймер.
Times out, new election
- После входа в состояние кандидата запускается таймер тайм-аута.Если новый лидер не был избран по истечении этого срока, состояние кандидата сохраняется и следующие выборы возобновляются.
Receives votes from majority of servers
- Узел состояния кандидата получает более половины голосов и переключается в новое состояние лидера.
Discovers current leader or new term
- Узел состояния-кандидата получает сообщение с лидером или более высоким номером термина (описано далее в этой статье), указывающее, что лидер уже существует, и переключается обратно на ведомого.
Discovers server with higher term
- Узел-лидер получает сообщение с более высоким номером термина, указывающее, что новый лидер уже существует, и переключается обратно на ведомого. Этот тип переключения обычно происходит, когда сетевые разделы, такие как старый лидер, восстанавливаются после простоя.

Понятия, связанные с термином

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

Диаграмма терминов

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

Узлы взаимодействуют через RPC. Существует два основных типа запросов RPC:

RequestVote RPCs:Используется для агитации кандидатов на выборах

AppendEntries RPCs:Используется лидером для репликации журналов на другие узлы и синхронизации тактов.

Это основные понятия Raft, и мы подробно познакомим их в следующей статье.Leader election.

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