Интерпретация алгоритма Raft

предисловие

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

Автор алгоритма Raft жаловался в статье, что алгоритм Paxos сложен для понимания и реализации, поэтому он предложилЛегко понять и легко построитьалгоритм распределенного консенсуса, а алгоритм Raft обеспечиваетТа же безопасность и производительность, что и у алгоритма Paxos.. Можно сказать, что внедрение алгоритма Рафта принесло пользу людям с обычным IQ.

Лично я считаю, что наиболее ценной частью алгоритма Raft является то, что он использует инженерное мышление для разработки алгоритма, так что алгоритм Raft можно широко использовать в распределенной области. (и т.д., СОФАЙРафт, ТиКВ...)

Хотя алгоритм Raft легче понять, чем алгоритм Paxos, когда я читал оригинальную статью, я все же наступил на яму во многих местах.Эта статья предназначена для того, чтобы разобраться и поделиться своими сомнениями и личным мнением по этим ключевым моментам. (Объем этой статьи касается только алгоритма Basic Raft)

Китайские переводы плот
Анимация алгоритма RAFT

1. Суть алгоритма Raft

Будь то алгоритм Raft или алгоритм Paxos, это зависит откопировать конечный автоматМодель конечного автомата копирования показана на следующем рисунке:

Описание Простая модель: иметь одинаковое начальное состояние (состояние) на множестве узлов в кластере, и выполняя серию операционного журнала (журнал),В конечном итоге быть в состоянии создать согласованное состояние. Модуль консенсуса на рисунке — это модуль, в котором работает алгоритм Raft, так что в сложной распределенной среде все еще может быть достигнута согласованность реплицированного конечного автомата. Четыре операции на рисунке следующие:

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

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

Алгоритм RAFT аналогичен алгоритму PaxOS.Характеристики распределенных алгоритмов:

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

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

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

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

Во-вторых, почему RAFT выбирает механизм случайного выбора тайм-аута?

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

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

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

Случайный тайм-аут выборов — это поведение ведомого, и лидер понимает, что он потерял лидерство, только когда получает пакет сердцебиения от лидера с более высоким сроком пребывания в должности. Таким образом, это приведет к тому, что старый лидер будет общаться с клиентом, в результате чего клиент будет читать устаревшие данные. Для решения этой проблемы. Автор алгоритма Raft указал, что хотя данные считываются, лидеру все равно нужноСоздайте специальный журнал (индекс чтения) и отправьте пакеты сердцебиения всем подписчикам., если большинство фолловеров возвращают нормальный ответ, то пока этот лог применяется конечным автоматом, это означает, что в этот момент у лидера все еще есть лидерская позиция, и в этот момент клиенту возвращаются последние данные время . Таким образом, хотя безопасность алгоритма гарантируется, производительность операции чтения не сильно отличается от производительности операции записи, что является фатальным в сценарии с большим количеством операций чтения и меньшим количеством записей.
Вышеупомянутая статья говорит о некоторых проблемах, которые может создать старый лидер, напротив, последователи могут также выступать в роли демонов. В следующих двух сценариях последователи будут влиять на стабильность кластера.
① Последователь принимает неверный файл конфигурации и продолжает отправлять запросы на сбор голосов другим узлам в кластере, но фактически не включен в кластер.
②Фолловеры только потеряли связь с лидером в одностороннем порядке, но хорошо общались с другими узлами в кластере, поэтому ведомые продолжали отправлять запросы на сбор голосов другим узлам в кластере, но фактически лидер не рухнул.
Вышеупомянутые две ситуации вызовут колебания в сети кластера, поэтому какие есть решения, чтобы этого избежать?
Как правило, эту проблему можно решить, добавив уровень проверки, прежде чем стать кандидатом.Когда кандидат хочет инициировать запрос на выборы, сначала отправьтеpre-vote, после получения согласия большинства узлов он автоматически увеличит срок и инициирует запрос на выборы. Когда узел получает запрос на предварительное голосование, если он недавно общался с лидером, он будет напрямую игнорировать запрос на предварительное голосование, тем самым избегая бесконечного количества запросов на выборы от кандидатов.

3. Каково использование prevLogIndex, prevLogIndex, lastLogIndex и lastLogTerm?

В базовом алгоритме Raft есть только два типа запросов RPC: RPC с дополнительным журналом и RPC с голосованием по запросу. Конкретные параметры показаны в следующей таблице:

Дополнительный журнал RPC:

параметр	объяснять
term	лидерский срок
leaderId	Идентификатор лидера, чтобы подписчики могли перенаправлять запросы
prevLogIndex	Новая запись журнала следует за предыдущим значением индекса.
prevLogTerm	номер термина записи prevLogIndex
entries[]	записи журнала для хранения (пусто для сердцебиения; для эффективности отправляйте несколько сразу)
leaderCommit	Значение индекса журнала, который лидер зафиксировал

Другие параметры легко понять, но очень трудно понять два параметра prevLogIndex и prevLogIndex в первый раз. Подробно описаны следующие два параметра.
Эти два параметра в основном дляГарантия непротиворечивости алгоритмаи существуют.(Подробные инструкции по проверке согласованности см. в Разделе 4 ниже)
Описание этого параметра выглядит следующим образом:

Возвращает false, если номер термина записи журнала в prevLogIndex не совпадает с prevLogTerm.

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

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

Запросить голосование RPC

параметр	объяснять
term	Номер срока кандидата
candidateId	Идентификатор кандидата, запросившего бюллетень
lastLogIndex	значение индекса последней записи журнала кандидата
lastLogTerm	Номер термина последней записи в журнале кандидата

Опишем подробно два параметра lastLogIndex и lastLogTerm. Прежде всего, эти два параметра относятся к службе выборов лидера, к выбору лидера.Исключить узлы, которые не содержат последних журналов, чтобы избежать перезаписи зафиксированного журнала. (Но полностью избежать этого не получится, в пятом разделе ниже все же будет небольшая лазейка.)

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

Текущее значение термина последователя меньше, чем термин в запросе-голосовании RPC (то есть самоинкрементный термин кандидата).
Когда терм равен, сравнивается размер lastLogTerm.Когда lastLogTerm кандидата меньше, чем у фолловера, фолловер не отвечает кандидату

В сочетании с рабочим механизмом алгоритма Raft:

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

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

4. Как алгоритм Raft обеспечивает согласованность всех конечных автоматов

Далее поговорим о том, как алгоритм Raft обеспечивает согласованность.

Критерии оценки несоответствия данных

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

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

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

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

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

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

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

С помощью приведенных выше четырех правил мы видим, что лидер может управлять согласованностью всех узлов, не потребляя много ресурсов.Постоянно отправляя дополнительные журнальные RPC (или пакеты пульса), узлы кластера будут автоматически сходиться. Конечно, с точки зрения клиента, алгоритм Raft обеспечивает высокую согласованность.

5. Правильный способ для Raft отправлять записи журнала из предыдущих условий.

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

Временной ряд, показанный на рисунке, показывает, почему руководитель не может решить зафиксировать запись в журнале для старого номера термина. В (а) S1 является лидером, частично повторяющим запись журнала в позиции индекса 2. В (b) происходит сбой S1, затем S5 побеждает на выборах с S3, S4 и собственными голосами в термине 3, а затем получает другую запись журнала от клиента и помещает ее в индекс 2. Затем в (c) S5 снова дает сбой, S1 перезапускается, выборы проходят успешно, и журнал копируется. На данный момент журнал из термина 2 реплицирован на большинство машин в кластере, но еще не зафиксирован. Если S1 снова выйдет из строя в (d), S5 может быть успешно переизбран (голосами от S2, S3 и S4), а затем перезапишет их журнал с индексом 2. И наоборот, если перед сбоем S1 реплицировал записи журнала, созданные в новом термине, в котором он доминировал, на большинство машин, как в (e), то эти новые записи журнала будут зафиксированы в более поздних терминах (поскольку S5 не может быть выбран успешно). . Это гарантирует, что все предыдущие старые записи журнала будут зафиксированы одновременно.

Во избежание описанной выше ситуации вот еще один патч алгоритма Raft:Raft никогда не будет фиксировать запись журнала из предыдущего термина, подсчитывая реплики.. Что означает этот патч? Обратите внимание, что на отметке времени (c), когда S1 является лидером, S1 обнаруживает, что журнал, представленный в его последнем термине (т. е. первый журнал с термином 2), не использовался большинством копий последователей. Итак, S1 отправляет журнал на S3, а S3 проверяет журнал и обнаруживает, что условия выполнены:

S3 currentTerm = 1
Индекс журнала S3 пуст, что можно принять.

Итак, S3 копирует лог в локальный лог, модифицирует S3 currentTerm = 2, а затем возвращает его лидеру S1.Лидер считает, что количество скопированных фолловеров превышает половину, затем инициирует коммит, после чего возвращает клиенту (клиенту ): «Я сохранил журнал и могу уверенно им пользоваться». Однако в момент отметки времени (d) S1 рушится, а S5 становится кандидатом и начинает собирать голоса.В это время давайте проанализируем отношения между S5 и ключевой фигурой S3:

Срок S5 = 5 > Срок S3 = 2

Тогда если S5 соберет голоса от S3, хотя на S5 нет лога с номером терма 2, а у S1 на S3 есть лог предыдущего терма, когда номер терма равен 4, то по правилам выборов Raft, S3 все равно даст S5 Голосование. А потому что в алгоритме Raft:

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

Следовательно, по этой причине будет перезаписан первый журнал со сроком 2. Если клиент получит к нему доступ, он обнаружит, что данные до и после доступа несовместимы, что недопустимо. Так что, если лидер хочет зафиксировать журналы с предыдущих сроков? Ключевым моментом является то, что на момент временной метки (d) S5, у которого отсутствует ключевой журнал, не может быть лидером. Тогда, пока отметка времени (c),Журнал с номером триместра можно подать в систему, а журнал предыдущего триместра можно подать вместе с этим журналом с номером триместра 4, как показано на метке времени (d), даже сразу после сбоя лидера S1 из-за ограничений выбора алгоритма Raft:

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

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

6. Как Raft не прекращает обработку клиентских запросов при изменении членства в кластере

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

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

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

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

7. Влияние нового узла на кластер

Когда новый узел присоединяется к кластеру, остается небольшой патч. Давайте посмотрим на сцену на рисунке 4 выше. Здесь мы сначала исключим ситуацию, когда будет избрано несколько лидеров. Мы предполагаем, что есть клиент службы поддержки который инициирует запись в журнал в это время.Получив запрос, лидер отправляет его на каждый узел через RPC дополнительного журнала.Поскольку узлы 4 и 5 являются вновь добавленными узлами в это время, он обязательно вернет отказ дополнительного log лидеру, то, если журнал успешно отправлен в это время, все исходные узлы 1, 2 и 3 должны быть успешно реплицированы, что эквивалентно снижению доступности системы без простоя машины или сетевых аномалий.

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

Восемь, роль моментальных снимков журнала Raft

У моментальных снимков журнала Raft есть две основные цели:

сжатый журнал

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

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

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

9. Идемпотентные операции между Raft-клиентом и сервером

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

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

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

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

10. Резюме

Эта статья является моим личным пониманием алгоритма Raft.В процессе написания статьи я нашел несколько замечательных статей.我做分布式系统, ТиКВ唐刘....) действительно сильны, они прошли долгий путь в оптимизации алгоритма Raft, когда я еще работал над Basic Raft. Прочитав столько информации, чем больше я чувствую себя блюдом, тем сложнее мне писать. Если есть какие-либо недостатки в моем понимании, пожалуйста, дайте мне знать.

Пригласительная открытка:Кодовая записка Ван Лаомо