Уточнение протокола Raft

Базовая структура RaftServer

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

Важные переменные для последовательностей журналов

firstLogIndex/lastLogIndex идентифицирует начальную позицию текущей последовательности журнала.Если журнал не сжат, то есть нет модуля моментального снимка, то firstLogIndex равен нулю.
commitIndex указывает журнал, который был отправлен в данный момент, то есть максимальное значение позиции журнала, успешно синхронизированное с большинством
applyIndex — это индекс журнала, который был применен к конечному автомату, и его значение должно быть меньше или равно commitIndex, поскольку к конечному автомату можно применять только отправленные журналы.

Важные переменные состояния сервера

Каждый сервер имеет свою собственную последовательность журналов, а индекс порядкового номера журнала начинается с 1, поскольку 0 имеет особое значение, указывающее на то, что сервер только что был инициализирован и не содержит никаких журналов. Последовательность журнала очень важна, поскольку она определяет состояние конечного автомата.
Каждый сервер должен иметь текущий номер термина, начиная с нуля и постепенно увеличиваясь в одном направлении. После перезапуска сервера ему необходимо знать текущий номер термина, прежде чем он сможет правильно взаимодействовать с другими узлами, поэтому номер термина должен быть постоянным.
Если вы голосуете за узел-кандидат, запишите идентификатор узла-кандидата, за который проголосовали. Если узел внезапно выйдет из строя и перезапустится после голосования за кандидата во время выборов, если это значение не будет записано, он, скорее всего, повторит голосование и проголосует за другой узел. Это приведет к существованию нескольких лидеров в кластере, то есть к расщеплению кластера.
Позиция индекса текущего зафиксированного журнала.При инициализации сервера это значение равно нулю, что указывает на то, что журнал еще не был зафиксирован. Все журналы до этой позиции могут быть безопасно применены к конечному автомату без перезаписи.
Позиция индекса журнала, которая в настоящее время была применена к конечному автомату, что обычно соответствует индексу фиксации. Потому что, как только индекс фиксации продвинулся, новый журнал фиксации немедленно применяется к конечному автомату без каких-либо задержек.
Лидеру необходимо записать совпадающую позицию matchIndex своего собственного журнала и журналов всех последователей. Ведущий журнал и ведомый перед matchIndex согласованы. При этом также необходимо записать следующую позицию лога, которую нужно синхронизировать с Follower. Журналы между matchIndex и nextIndex — это синхронизируемые журналы. Это список журналов, для которых сообщение AppendEntries, отправленное лидером ведомому, еще не получило успешного ответа. Это описано в словаре высокого уровня. как бортовые журналы.

Почему нельзя сохранить commitIndex и applyIndex?

Это связано с механизмом репликации логов. Прежде всего, для выборов условием ПК является не размер двух значений индекса, а номер терма последнего лога и длина лога. Когда лидер выбран и выполняет первую репликацию журнала, он выполнит несколько процессов сопоставления журналов с подписчиками и, наконец, получит значение matchIndex лидера и совпадения журналов подчиненного. Минимальное значение matchIndex в списке основных узлов — это commitIndex текущего лидера. Таким образом, значение commitIndex может быть рассчитано динамически. Если все журналы не усекаются, applyIndex должен быть равен нулю при перезапуске сервера. Затем воспроизведите все представленные дни, чтобы получить текущий конечный автомат. Если в усечении журнала есть моментальный снимок, applyIndex должен точно соответствовать положению начала последовательности журнала.Эта позиция обычно сохраняется в метаданных моментального снимка, которые сохраняются на диске.

Кандидаты просят голосовать за ПКР на этапе выборов

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

Запрос синхронизации журнала лидера на этапе репликации журнала

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

основные правила

Произвольная синхронизация журнала продолжается, и commitIndex продолжает двигаться вперед. Журналы, которые были зафиксированы, должны быть применены к конечному автомату вовремя, а applyIndex должен следовать за commitIndex для продвижения вперед. Чтобы клиент не запрашивал данные из конечного автомата, данные не очень в режиме реального времени.
Если номер термина в любом полученном сообщении RPC больше, чем у текущего узла, текущий номер термина будет немедленно обновлен, а роль будет изменена на «Последователь». Номер термина маленький, а значит устаревший. Причина может заключаться в том, что сеть восстановилась после раздела, такого как серый узел на изображении ниже.

Последователи пассивны и принимают сообщения RPC только от кандидатов и лидеров, а не активно отправляют их.
Если сообщение RPC не будет получено в течение длительного времени, оно будет преобразовано в кандидата и будет участвовать в выборах.
Как только узел становится кандидатом, он сразу же участвует в выборах. Увеличивайте количество терминов, голосуйте за себя и отправляйте RPC-сообщения RequestVote другим узлам для сбора голосов.
После того, как кандидат получает голоса большинства узлов, он сразу же становится Лидером.
Если в течение этого периода будет получен запрос на синхронизацию журнала AppendEntries, отправленный другими узлами, он немедленно станет Подписчиком. Родился новый лидер, и предвыборная пыль осела.
Если время выборов истекло, а большинство не сформировано, избирательный процесс возобновляется.
Как только лидер выбран, он немедленно синхронизирует контрольное сообщение (нет операции) с другими узлами. Это необходимо для того, чтобы журналы, которые в настоящее время не зафиксированы, также были зафиксированы как можно скорее. Лидер только добавит последовательность журнала.Лидер попытается синхронизировать существующую последовательность журнала со всеми узлами, когда он только что был выбран.Если существующий журнал последователя конфликтует с лидером, он будет стерт. В итоге логи Лидера и Последователя будут абсолютно одинаковыми.
После того, как лидер получает запрос клиента, он сначала добавляет его к последовательности локального журнала и отвечает клиенту только после того, как журнал успешно применен к машине состояний.
Если текущая последовательность журнала лидера увеличивается (lastLogIndex > nextIndex), он немедленно отправляет сообщение синхронизации журнала всем подписчикам.
Если Follower отвечает успешно, он будет следовать новым значениям matchIndex и nextIndex во времени.
Если ведомый не отвечает, уменьшите значение nextIndex и выполните повторную синхронизацию. Это сведения о синхронизации журнала лидера с использованием резервного метода повторных попыток.
Если matchIndex большинства расширен, то commitIndex и applyIndex последовательности локальных журналов лидера также должны быть расширены.

Почему лог отсутствия операций должен синхронизироваться сразу после избрания лидера?

На рисунке S1~S5 — это 5 узлов в кластере, а толстая линия указывает, что они в настоящее время являются ведущими. Каждое поле представляет собой журнал, а числа в полях представляют собой термины журнала. Теперь, если предположить, что журнала отсутствия операций нет, что может пойти не так?

(а) Рисунок, S1 является лидером, желтый журнал 2 синхронизируется с узлом S2, и вдруг он падает
(b) Рисунок: S5 выбран, добавляет синий журнал 3 к последовательности локальных журналов и внезапно снова дает сбой.
(c) Рисунок, S1 переизбирается, к локальному добавляется новый красный журнал 4, а затем он начинает синхронизировать предыдущий журнал, а желтый журнал 2 синхронизируется с S3.В это время желтый узел 2 был синхронизирован с большинством, но фиксировать было поздно, и вдруг рухнул.
(d1) Рисунок, S5 переизбирается и начинает синхронизировать предыдущие журналы, синий журнал 3 со всеми узлами. В результате желтый журнал 2 удаляется, хотя он был синхронизирован с большинством узлов.

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

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

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

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

Синхронизация моментальных снимков и сжатие журнала

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

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

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

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

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

Снапшоты — очень ресурсоемкие операции, поэтому руководитель не может делать это слишком часто. Как правило, это выполняется после того, как размер последовательности журнала достигает порогового значения. Снимок аналогичен операции rdb в Redis.После завершения операции rdb журнал aof может быть усечен, поэтому прореживание журнала завершено.

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

Подпишитесь на общедоступную учетную запись «Code Cave» и присоединяйтесь к нам, чтобы изучить протокол Raft.