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

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

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

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

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

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

1. Что такое репликация журнала

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

Raft отвечает за то, чтобы все узлы в кластересогласованность журнала.

Кроме того, мы также упоминали: плот дает ведущему узлу более сильное лидерство (Strong Leader). Тогда легко понять способ raft обеспечения согласованности журнала, то есть все операции (лог) должны быть переданы ведущему узлу для обработки (последователь получает операции записи, которые будут переданы ведущему узлу для обработки), а ведущий узел реплицирует его на другие узлы, чтобы обеспечить согласованность всего уровня реализации журнала кластера.

Этот процесс называетсяРепликация журнала, соответствующая модель системы "репликатор состояния журнала".

2. Анализ механизма репликации журналов Raft

2.1 Анализ всего процесса

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

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

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

Логарифмическую модель всего кластера можно макроскопически представить в виде следующего рисунка (x ← 3 означает, что x присваивается значение 3): *Модель журнала кластера Raft

В дополнение к хранению рабочих инструкций конечного автомата (таких как инструкция присваивания x ← 3, которая представляет присваивание x 3), каждый журнал также будет иметьуникальное целочисленное значение индекса(log index), чтобы указать его положение в коллекции журналов. Кроме того, каждый журнал хранитtermчисло (число в верхней части окна записи журнала, номер термина того же цвета), термин представляет собой текущий термин, когда лидер получает эту инструкцию, и журнал с тем же термином отправляется тем же лидером в течение его срока.

Когда журнал считается безопасным для применения к конечному автомату ведущим узлом, журнал вызываетсяcommitted(на картинке вышеcommitted entries). Итак, какие журналы могут быть зафиксированы? ответ:Когда лидер узнает, что этот журнал был успешно реплицирован более чем половиной узлов в кластере. Таким образом, на приведенном выше рисунке мы видим, что (term3, index7) этот журнал и предыдущий журнал зафиксированы, хотя журнал, принадлежащий двум узлам, не является полным.

Raft гарантирует, что все зафиксированные журналы былиУпорство,а также"наконец-то«Его должна применять государственная машина.

Примечание. Слово «окончательный» здесь тонкое и указывает на особенность: то, что Raft гарантирует, — это только согласованность журнала, а согласованность, которую мы действительно ожидаем от конечного автомата, требует от нас выполнения некоторой дополнительной работы, которая описана в последующая статья «Линейность. Согласованность и оптимизация производительности» будет посвящена этому.

2.2 Объяснение процесса репликации журнала Raft

Проходим анимацию плота(raft.github.io/) для имитации регулярной репликации журнала...

*фигура 1

Как показано на рисунке 1, S1 выбран в качестве лидера, и в это время журнал отсутствует. Мы имитируем клиента, делающего запрос к S1.

*фигура 2

Как показано на рисунке 2, S1 добавляет новый журнал (term2, index1) после получения запроса клиента, а затем параллельно инициирует AppendEntries RPC для других узлов.

*изображение 3

Как показано на рисунке 3, S2 и S4 получили запрос первыми, соответственно прикрепили журнал и ответили S1.

*Рисунок 4

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

*Рисунок 5

Как показано на рисунке 5, когда S1 получает2 узлаответ, граница записи в журнале стала сплошной линией, что указывает на то, что журнал былбезопасная копия, потому что в кластере из 5 узлов, 2 узла-последователя плюс сам узел-лидер, количество реплик было обеспечено более чем наполовину, на данный моментS1 ответит на запрос клиента.

*Изображение 6

Как показано на рис. 6, лидер будет продолжать посылать пакеты пульса ведомым, а пакеты пульса будут нести текущуюИндекс журнала, который был безопасно реплицирован (назовем его зафиксированным), здесь (term2, index1).

*Рисунок 7

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

2.3 Гарантия Raft на непротиворечивость журналов

Ранее мы использовали (term2, index1) для представления записи в журнале, почему нам нужно использовать термин, а не просто индекс? Причина в том, что этот термин можно использовать для проверки наличия несоответствий в логах между разными узлами, что будет легче понять после прочтения следующего раздела.

Рафт гарантирует:Если две записи журнала в разных наборах журналов узлов имеют один и тот же термин и индекс, они должны хранить одну и ту же команду.

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

При этом raft также гарантирует:Если две записи журнала в разных наборах журналов узлов имеют один и тот же термин и индекс, то все записи журнала перед ними также будут одинаковыми.

Это связано с тем, что RPC AppendEntries, отправленный лидером, будет дополнительно нестиПредыдущий(термин, индекс) бревна, если фолловер не может найти такой же (терм, индекс) бревна локально, тоОтказаться от получения этого нового журнала.

Следовательно, пока ведомый продолжает нормально получать логи от ведущего, приведенный выше вывод можно проверить по индукции.

2.4 Возможные сценарии несогласованности журналов

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

*График сценария несогласованности журнала

На приведенном выше рисунке показана путаница, которая может возникнуть в журнале кластера, когда лидер term8 только вступает в должность. Например, у последователя может не хватать некоторых журналов (a ~ b), может быть больше незафиксированных журналов (c ~ d) или может быть как отсутствующих журналов, так и большего количества незафиксированных журналов (e ~ f).

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

Давайте сначала попробуем воспроизвести вышеописанный сценарий a~f, а напоследок поговорим о том, как raft решает эту проблему несоответствия.

Сценарий а~б. Журналы последователя отстают от лидера

Этот сценарий на самом деле довольно прост, т.е.подписчик некоторое время недоступен, последователь-а начинает падать после получения (term6, index9), а последователь-b начинает падать после получения (term4, index4). Я не буду здесь вдаваться в подробности.

Сценарий c. Последователь регистрирует больше терминов6, чем лидер

Когда лидер термина 6 синхронизируется (термин 6, индекс 11) с последователем, лидер отключен, и только последователь-c получил RPC AppendEntries этого журнала. Затем, после серии выборов, срок 7 может иметь тайм-аут выборов, или может случиться так, что лидер только что вступил в должность и ушел, наконец, лидер срока 8 вступил в должность, что привело к сцене с, которую мы видели.

Сценарий г. Последователь регистрирует больше терминов7, чем лидер

Когда лидер term6 успешно зафиксировался (term6, index10), произошел простой. В это время лидер term7 вступил в должность и постоянно синхронизировал два лога с фолловером, но перед фиксацией он вышел из строя, и тогда кластер избрал лидера term8.

Сценарий д. В журнале последователей меньше терминов5 ~ 6, чем у лидера, но больше терминов4

Когда лидер термина4 синхронизируется (термин4, индекс7) с последователем и успешно фиксирует (термин4, индекс5) и предыдущий журнал, происходит сбой, за которым следует последователь-е. Таким образом, все синхронизации журналов, происходящие в терминах 5–7, будут пропущены Follower-e. Когда последователь-е восстанавливается, лидер term8 просто вступает в должность.

Сценарий е. Журнал ведомых содержит меньше терминов4 ~ 6, чем лидер, и больше терминов2 ~ 3

Когда лидер термина 2 синхронизировал некоторые журналы (индекс 4 ~ 6) с последователями, произошел сбой перед фиксацией, но он быстро восстановился и был снова избран лидером термина 3, он продолжил синхронизацию некоторых журналов (индекс 7 ~ 11) с последователем. , но время простоя снова произошло в будущем перед фиксацией, за которым последовало время простоя Follower-f.Когда Follower-f проснулся, кластер продвинулся до term8.

2.5 Как справиться с несогласованностью журналов

Из приведенных выше сценариев видно, что ситуация с кластером в реальном мире очень сложна, так как же raft справляется с таким количеством противоречивых сценариев? На самом деле метод очень простой и жестокий, вдумайтесьStrong Leaderэта фраза.

Raft требует, чтобы последователи реплицировали коллекцию журналов лидера для устранения несоответствий.

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

Чтобы журнал последователя оставался точно таким же, как и его собственный, лидер должен сначала найти разницу между двумяпоследний разгде достигнуто соглашение. Поскольку после согласования этого журнала предыдущие журналы также должны быть согласованы (вспомните предыдущую статью). Это подтверждение выполняется на этапе проверки согласованности RPC AppendEntries.

Лидер поддерживает один для каждого последователяnext index, указывающий следующий индекс журнала, который необходимо отправить последователю. Когда лидер только вступает в должность, он инициализирует все следующие значения индекса индексом+1 своего последнего журнала. Если журнал ведомого не соответствует журналу ведущего, проверка согласованности следующего RPC AppendEntries завершится ошибкой. После того, как RPC Append Entries отклонен последователем, лидер уменьшит значение следующего индекса и повторит попытку.

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

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

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

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

Об этом мы подробно поговорим в следующей статье.

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