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

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

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

1 Обзор

1.1 Что такое плот?

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.

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

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

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

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

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

Рисунок: Реплицированный конечный автомат

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

1.2 Кто использует Raft

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

Как микросервисная инфраструктура,consulНижний уровень использует Raft для обеспечения согласованности данных между серверами consul. Прочитав главу 6, мы поймем, почему консул предоставляетdefault,consistent,staleТри режима согласованности (режимы согласованности), их соответствующие применимые сценарии и то, как базовый консул поддерживает эти различные режимы согласованности путем изменения модели чтения Raft.

TiKVАлгоритм Raft также используется на нижнем уровне. Хотя все они претендуют на роль «распределенного хранилища kv», сценарии использования TiKV отличаются от etcd. Его целью является поддержка более 100 ТБ данных, одиночный кластер Raft, такой как etcd, определенно не может поддерживать такой объем данных. Поэтому нижний уровень TiKV использует Multi Raft для разделения данных на несколько регионов, каждый регион фактически представляет собой стандартный кластер Raft, что обеспечивает высокую доступность нескольких копий данных в каждом разделе.

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

1.3 Основные понятия плота

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

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

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

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

Во-вторых, какая работа должна нести главный узел? Он будет нести ответственность за получение запроса на эксплуатацию, отправленную клиентом и обертыванием операции какбревноСинхронизируйтесь с другими узлами, гарантируя, чтосамыйПосле того, как узлы синхронизировали эту операцию, они могут безопасно отвечать клиенту. Эта часть работы называется в алгоритме ядра Raftрепликация журнала(Log replication).

Затем, поскольку ответственность главного узла настолько велика, узлы должны быть осторожны при выборе мастера, толькоСоответствовать критериямУзел может быть выбран в качестве главного узла. Кроме того, мастер-узел также должен быть осторожен при обработке журналов операций.Чтобы обеспечить согласованность внешнего отображения кластера, его нельзяперезаписать или удалитьПредыдущий главный узел обработал журнал успешной операции. Так называемая «тщательная обработка» на самом деле заключается в том, чтобы сделать некоторые ограничения при выборе мастера и отправке журнала.Эта часть вызывается в основном алгоритме Raft.безопасность(Safety).

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

В дополнение к основным алгоритмам Raft также предоставляет решения для нескольких проблем, с которыми приходится сталкиваться в инженерной практике.

Первый касается бесконечно растущего бревна. Raft упаковывает операции в журналы. Каждый узел в кластере поддерживает растущую последовательность журналов. Конечный автомат можно получить, только воспроизведя последовательность журналов. Но поскольку эта последовательность журналов может со временем увеличиваться, у нас должен быть какой-то способ избежать бесконечных перегрузок диска и длинных повторов журналов. Эта часть называетсясжатие журнала(Log compaction).

Второй касается изменений членства в кластере. Кластер Raft вряд ли будет иметь фиксированное количество узлов навсегда, всегда есть необходимость в расширении или сжатии, или когда узел выходит из строя и его необходимо заменить. Прямая замена члена кластера может привести к серьезнымрасколотый мозгпроблема. Raft предоставляет способ безопасного изменения членства в кластере. Эта часть называетсяИзменения членства в кластере(Cluster membership change).

Кроме того, мы дополнительно обсудимЛинейная согласованностьопределение, почемуRaft нельзя приравнивать к Linear Consistency,какЛинейная согласованность на основе Raft, и какПрочитайте оптимизацию производительности с точки зрения обеспечения линейной согласованности..

Выше приведен обзор большей части содержания, которое будет обсуждаться в теоретической главе.Здесь у нас есть макро-понимание Raft, и мы знаем, о чем каждая часть и взаимосвязь между ними.

Далее мы подробно обсудим каждую часть алгоритма Raft. Начнем с первой частивыбрать главноеНачинать.

2. Выберите лидера

2.1 Кто такой лидер

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

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

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

2.2 Почему Raft выбирает мастера?

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

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

2.3 Основной процесс выбора плота

2.3.1 Роли узлов

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

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

2.3.2 Срок полномочий

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

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

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

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

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

2.3.3 Переход состояния узла

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

Далее мы подробно обсудим сценарии, в которых происходит каждый переход.

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

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

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

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

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

Рисунок: Первый таймаут S1 истек, он стал кандидатом, срок + 1 и отправил запрос на опрос другим узлам

2.3.3.2 Процесс перехода из состояния-кандидата

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

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

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

Рисунок: "Большинство" узлов дали S1 голосов

Рисунок: S1 становится лидером и начинает отправлять пульсации для поддержания авторитета

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

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

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

Рисунок: S4 и S2 начинают выборы по очереди

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

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

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

Рисунок: S1 ~ S5 все участвуют в выборах

Рисунок: Ни один узел не желает голосовать за других

Рисунок: Если тайм-аут не рандомизирован, все узлы продолжат инициировать выборы одновременно...

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

2.3.3.3 Процесс перехода состояния лидера

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

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

Рисунок: S4 в качестве лидера term2

Рисунок: S4 не работает, S5 будет первым истечет время ожидания

Рисунок: S5 избран лидером срока3

Рисунок: S4 получил контрольный сигнал term3 от S5 после восстановления после простоя

Рисунок: S4 сразу же становится последователем S5

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

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

3. Репликация журнала

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

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

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

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

Этот процесс называетсярепликация журнала(Log replication).

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

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

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

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

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

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

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

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

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

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

3.2.2 Блок-схема копирования журнала

мы проходимАнимация плотаЧтобы смоделировать процесс регулярной репликации журнала:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.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.

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

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

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

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

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

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

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

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

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

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

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

4. Безопасность и правильность

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

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

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

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

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

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

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

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

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

4.2 Ограничения на отправку

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

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

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

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

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

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

этап а: 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.

5. Изменения элементов кластера и сжатие журнала

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

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

В этой статье мы объясним эти два метода отдельно.

5.1 Изменение члена кластера

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

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

5.1.1 Непосредственное переключение конфигурации элемента кластера

Вывод первый:Все сценарии полного переключения кластера со старой конфигурации сразу на новую небезопасны.

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

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

Рисунок 5-1

этап а.В кластере три узла S1 ~ S3.Конфигурацию участника обозначим как C-old, зеленый цвет указывает на то, что текущее представление (конфигурация участника) узла является C-old, а S3 на красной стороне является лидером.

этап б.В кластер добавляются два новых узла, S4 и S5. Изменение записывается от лидера. Обозначим пятиузловую конфигурацию нового члена S1 ~ S5 как C-new, а синий цвет означает, что текущий вид узла C-новый.

этап в.Предположим, что кратковременный сбой S3 инициирует тайм-аут S1 и S5 для выбора ведущего.

стадия д.S1 запрашивает голоса от S2 и S3, а S5 запрашивает голоса от всех остальных четырех узлов. Поскольку журнал S2 не новее журнала S1, S2 может голосовать за S1, а S1 избирается двумя голосами (поскольку S1 считает, что кластер имеет только три узла). И S5 точно получит голоса S3 и S4, потому что S1 не может воспринимать S4, не отправляет ему RPC RequestVote, и лог S1 отстает от S3, S3 точно не проголосует за S1, а S5 избирается тремя голосами . В конце концов в кластере произошла фатальная ошибка с несколькими главными узлами, также известная как «расщепленный мозг».

Рисунок 5-2

Изображение выше взято из статьи и представляет ту же проблему, что и на рис. 5-1, но в другой форме. Значения цветов соответствуют значениям на рис. 5-1, вproblem: two disjoint majoritiesНа данный момент в кластере может быть два лидера.

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

источник:zhuanlan.zhihu.com/p/27207160

Рисунок 5-3

Этот гипотетический сценарий аналогичен этапу d на рис. 5-1, а процесс моделирования выглядит следующим образом:

S1 является исходным лидером кластера, а в кластер добавлены S4 и S5.Эта конфигурация была передана на S3, но S2 еще не получила ее.
В это время S1 отключается на короткое время, а S2 и S3 запускают выборы мастера соответственно.
В итоге S2 получила S1 и свои голоса, S3 получила S4, S5 и свои голоса, и в кластере появилось два лидера.

Процесс на рис. 5-3 вроде бы не сильно отличается от рис. 5-1, за исключением того, что узлы, участвующие в выборах ведущего, другие, но дело в том, чтоСитуация на рис. 5-3 невозможна..

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

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

Здесь, чтобы помочь вам прояснить ситуацию, статья косвенно указывает, чтоЖурнал, сравниваемый при выборе мастера, не требует фиксации, просто сравните последний локальный лог.!

Возвращаясь к рисунку 5-3, причина невозможности заключается в том, что S1, как исходный лидер, уже сохранил журнал новой конфигурации, а S2 не был синхронизирован с этим журналом. предыдущая глава "Безопасность"избирательное ограничение,S1 не может голосовать за S2., поэтому S2 не может стать лидером.

5.1.2 Конфигурация элемента кластера с двухфазным переключением

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

первый этап

Клиент отправляет C-new лидеру, а лидер забирает C-old и C-newсоюзи применимы сразу, обозначим какC-old,new.
Лидер оборачивает C-старый, новый как лог синхронизации с другими нодами.
Последователь применяется сразу после получения C-old, new, когда большинство узлов **C-old, new (то есть большинство узлов C-old и большинство узлов C-new)** переключен, лидер будет фиксировать журнал.

второй этап

Затем Leader оборачивает C-new как синхронизацию журнала с другими узлами.
Подписчики подают заявку сразу после получения C-new.Если они обнаружат, что в это время их нет в списке C-new, они будут активно выходить из кластера.
Лидер подтверждаетБольшинство узлов C-newПосле успешного переключения отправьте клиенту ответ об успешном выполнении.

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

Почему эта схема гарантирует отсутствие нескольких лидеров? Разберем процесс пошагово.

Этап 1. C-старый, новый еще не зафиксирован

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

Если взять в качестве примера сценарий на рис. 5.1, то у S5 вообще нет шансов стать лидером на этапе d, потому что на C-old за него проголосовал только S3, что не удовлетворяет большинство.

Этап 2. C-старый, новый зафиксирован, C-новый не выдан

На этом этапе C-old,new был зафиксирован, что может гарантировать, что большинство узлов, которые были C-old,new (Опять же: большинство узлов для C-старых и большинство узлов для C-новых)копировать.

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

Этап 3. C-new выпущен, но еще не зафиксирован

На данном этапе в кластере может быть три типа узлов C-old, C-old, new и C-new, но так как этап 2 уже пройден, узел C-old уже не может стать лидером. Будь то C-старые, новые или C-новые узлы для инициирования выборов, требуется согласие большинства C-новых узлов, поэтому невозможно иметь двух лидеров.

Стадия 4. C-new зафиксирован

На данном этапе C-new зафиксирован, поэтому только C-new узел может получить большинство голосов, чтобы стать лидером. К этому моменту кластер благополучно завершил этот раунд изменений и может продолжить следующий раунд изменений.

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

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

5.2 Сжатие журнала

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

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

снимок(Snapshot) — это распространенный и простой метод сжатия журналов, который используется такими системами, как ZooKeeper и Chubby. Проще говоря, это дамп состояния системы в определенный момент и сохранение его на земле, чтобы все логи до этого момента можно было отбросить. Так что не поймите неправильно слово «сжатие», у нас нет способа «распаковать» моментальный снимок конечного автомата обратно в последовательность журнала.

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

На изображении выше показан узел со снимками, которые заменяют журналы (term1, index1) ~ (term3, index5).

Снимки обычно содержат следующее:

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

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

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

Синхронизированные моментальные снимки используют новый метод RPC, называемыйInstallSnapshot RPC.

До сих пор мы в основном объясняли содержание статьи Raft.«В поисках понятного алгоритма консенсуса (расширенная версия)»В конце концов, это всего лишь 18 страниц, и в нем больше внимания уделяется теоретическому описанию, чем инженерной практике. Если вы хотите подробно изучить Raft или написать надежную реализацию Raft самостоятельно,Консенсус: соединение теории и практикиЭто лучший выбор для вашей справки.

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

6. Линейная согласованность и оптимизация производительности чтения

6.1 Что такое линейная согласованность?

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

Что такое согласованность? Существует много моделей так называемой непротиворечивости, и разные модели используются для оценки правильности параллельной системы. И то, что мы собираемся обсудить сегодня,сильная консистенция(Strong Consistency), котораяЛинейная согласованность(линеаризуемость), буква C в теории CAP, которую мы часто слышим, относится к ней.

На самом деле мы кратко описали, что такое линейная согласованность в первой статье:

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

"Служить самостоятельным«Оно описывает характеристики, которые должна иметь система линейной согласованности с помощью органов чувств, так как же мы можем судить о том, имеет ли система линейную согласованность? Вообще говоря, это означает, что старые (устаревшие) данные не могут быть прочитаны, но они разделены на две части. случаи. :

Время звонка совпадает (параллелизм) запрос, эффективный порядок может быть определен произвольно.
Существует отношение приоритета для времени вызова (частичный заказ), последний запрос не может нарушить результат, определенный предыдущим запросом.

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

Примеры в этом разделе взяты из книги Мартина Клеппманна «Проектирование приложений, интенсивно использующих данные».

Как показано на рисунке выше, рефери записывает результаты Кубка мира в основную библиотеку, а страницы, просматриваемые Алисой и Бобом, считываются из двух разных ведомых библиотек, однако из-за задержки синхронизации master-slave синхронизация Задержка Последователя 2 задерживается. Она больше, чем у Последователя 1, что в конечном итоге заставляет Боба обновить страницу, услышав восклицание Алисы, и увидеть, что игра все еще продолжается.

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

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

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

В этом случае нельзя сказать, что система удовлетворяет линейной непротиворечивости. Предположим, что первое чтение клиента B возвращает1, если второе чтение Клиента А возвращает0, то этот сценарий не нарушает приведенных выше правил, но система по-прежнему не линейно непротиворечива, потому что клиент видитxЗначение переключается между старым и новым значением, что не соответствует ожидаемому нами требованию «кажется, что это только одна копия данных».

Поэтому нам нужно добавить дополнительное ограничение, как показано на изображении ниже.

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

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

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

Линейная согласованность не ограничивается распределенной средой и может быть просто понята как функция «регистрации» в одноядерной системе с одним компьютером.

Последнее чтение клиента B не удовлетворяет линейной согласованности, потому что оно считывает неправильное значение, если провод перемещается вправо (поскольку клиент A уже прочитал запись, сделанную клиентом C).4). Кроме того, на этой картинке стоит обратить внимание на некоторые детали, которые могут решить многие недоразумения, с которыми мы склонны иметь дело при использовании линейно непротиворечивых систем:

Первый запрос на чтение от клиента B инициируется до первого запроса на запись от клиента D и первого запроса на запись от клиента A, но в конечном итоге считывается результат последней успешной записи от клиента A.
Когда клиент A не получил успешный ответ на первый запрос на запись, клиент B прочитал значение, записанное клиентом A.

Все вышеперечисленные явления разумны в рамках линейно непротиворечивой семантики.

такЛинейная согласованность(линеаризуемость) в дополнение к вызовусильная консистенция(Сильная консистенция), также называемаяатомарная согласованность(Атомная согласованность),Немедленная консистенция(немедленная консистенция) иливнешняя согласованность(Внешняя согласованность), эти названия кажутся более подходящими.

6.2 Чтение линейной согласованности плота

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

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

6.2.1 Анализ дефектов записи ведущего устройства чтения ведомого устройства

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

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

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

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

6.2.2 Анализ дефектов записи мастера чтения мастера

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

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

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

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

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

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

Проблема 2: Грязные чтения, вызванные сетевыми разделами

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

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

6.2.3 Raft Log Read

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

Эта схема чтения называетсяRaft Log Read, который также можно интуитивно назватьRead as Proposal.

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

6.3 Оптимизация производительности чтения Raft

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

6.3.1 Read Index

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

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

Индекс применения на третьем шаге здесьбольше или равночтение индекса является ключевым моментом. Потому что, когда запрос на чтение был инициирован, мы записали индекс фиксации в это время.Пока содержимое, прочитанное клиентом, находится после индекса фиксации, результат будетдолжен быть линейно непротиворечивым(Если вы не понимаете, вы можете просмотреть предыдущий пример линейной согласованности и вопрос 1 в 2.2).

6.3.2 Lease Read

По сравнению с Read Index, Lease Read дополнительно экономит накладные расходы на сетевое взаимодействие, поэтому можетзначительно нижечитатьзадерживать.

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

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

6.3.3 Follower Read

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

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

Эти две гарантии соответствуют двум проблемам, описанным в разделе 2.2 соответственно.

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

Значит, последователь чтения действительно не может удовлетворить линейную согласованность? На самом деле нет, здесь мы даем возможное решение для следящего за чтением:Когда фолловер получает запрос на чтение от клиента, он запрашивает у лидера последний индекс коммита. В любом случае, все записи журнала в конечном итоге будут синхронизированы с ним. конечного автомата, а затем вернуться к конечному автомату.Результат локального конечного автомата клиента может быть. Эта программа называетсяFollower Read.

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

Вышеизложенное является основным содержанием алгоритма Raft и наиболее важным содержанием для инженерной практики.

Если вы продолжите читать, я полагаю, что у вас есть глубокое понимание теории алгоритма Рафта. Конечно, разрыв между теорией и инженерной практикой может быть больше, чем предполагалось, и на практике приходится сталкиваться со многими деталями. В последующих главах, посвященных анализу исходного кода и практических занятиях, мы объединим код, чтобы объяснить многие из этих деталей, не упомянутых в теоретической части, и представим множество примеров проектирования инфраструктуры, так что следите за обновлениями!

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

Спасибо, что нашли время прочитать! Оригинальность не так проста, добро пожаловать, лайкайте, подписывайтесь, комментируйте