Эта статья содержит 3 содержания: во-первых, она знакомит с тем, что такое линейная непротиворечивость; во-вторых, она анализирует причины, по которым как «запись ведущий-считыватель-подчиненный», так и «запись ведущий-считыватель-ведущий» не могут гарантировать линейную согласованность (Да, правильно, главный писатель и главный читатель не годятся!) и описывает метод обеспечения линейной непротиворечивости при реализации системы на основе Raft; наконец, вводит конкретную стратегию оптимизации производительности чтения Raft без нарушения линейной согласованности.

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

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

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

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

Боевая серия протокола Raft (1) - основные понятия
Боевая серия протокола Raft (2) - основная подборка
Боевая серия протокола Raft (3) - репликация журнала
Протокол боевой серии Raft (4) - безопасность
Боевая серия протокола Raft (5) — изменение члена кластера и сжатие журнала

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Raft Log Read

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

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

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

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

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

3.1 Read Index

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

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

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

3.2 Lease Read

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

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

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

3.3 Follower Read

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

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

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

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

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

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

На этом основная глава нашей серии Raft завершена.

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

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