Оригинальный адрес:у-у-у-у. xilidu.com/2018/06/04/…

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

Что такое Рафт?

Raft — алгоритм консенсуса для распределенных систем.

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

Paxos был предложен до Raft, но Paxos довольно сложен. Цель Raft — разработать простой для понимания алгоритм распределенного консенсуса.

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

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

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

На практике подобных приложений много.Например master-slave синхронизация mysql синхронизируется через binlog.

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

Давайте поговорим о моем понимании алгоритма Raft.

Базовая гарантия безопасности:

Чтобы обеспечить правильность процесса, Raft должен гарантировать, что следующие свойства всегда истинны:

• Принципы безопасности выборов: В одном и том же сроке может быть не более одного лидера.

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

• Принцип сопоставления логов: Если два журнала имеют один и тот же термин и индекс, то журналы между [0, индекс] точно такие же для двух журналов.

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

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

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

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

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

Для узлов в кластере. В любой момент возможно находиться в одном из трех состояний:

• последователь
• кандидат
• лидер

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

Переключение между ролями:

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

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

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

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

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

синхронизация журналов

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

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

Однажды команда сохраняется большинством последователей. Лидер считает это состояние совершенным. Также сообщите клиенту, что команда отправлена. Если в это время фолловер вылетает или тормозит. Лидер будет пытаться повторить попытку, пока ведомый не примет команду и не сохранит ее в своем журнале. Этот процесс продолжается до тех пор, пока все последователи не сохранят все записи журнала.

В качестве узла Raft должны быть гарантированы следующие свойства.

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

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

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

Анализ безопасности

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

избирательные ограничения

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

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

Чем больше срок и длиннее бревно, тем легче стать лидером.

Зафиксировать записи журнала для предыдущих терминов

На бумаге это понять сложнее. Когда я увидел этот раздел, я перечитал его несколько раз, прежде чем понял смысл статьи. На самом деле автор имеет в виду, что цифра (d) верна, а (e) неверна.

Потому что бревно №2 не зафиксировано, а из-за ряда операций бревно №2 не сдано, а руководитель с большим стажем считает, что бревно №2 зафиксировано.

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

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

Последователи и кандидаты терпят крах

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

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

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

расширение системы

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

Чтобы обеспечить безопасность расширения, Raft использует двухэтапный метод.

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

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

Необходимо решить три вопроса:

• Чтобы не тормозить соответствующую скорость всего кластера, не обязательно давать права голоса вновь добавляемым узлам. Право голоса будет открыто после отслеживания журнала
• Если после расширения старый лидер принадлежит выкинутой ноде, то старый лидер не уйдет в оффлайн сразу, а продолжит работу до C_newпредставлен. В настоящее время лидер отвечает только за управление кластером и не добавляет журналы.
• Узел, который нужно удалить, не получит сердцебиение лидера и будет продолжать думать, что время ожидания истекло, продолжит становиться кандидатом и продолжит голосовать. Заставьте лидера кластера постоянно отрекаться от престола, а затем снова сгенерируйте лидера. Это снижает отзывчивость кластера. Чтобы избежать этой проблемы, сервер игнорирует запрос на голосование, когда подтверждает, что текущий лидер существует. Каждый сервер выжидает как минимум минимальное время ожидания перед началом выборов.

Сжатие журналов:

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

Взаимодействие с клиентами

Во всем протоколе Raft клиент взаимодействует только с лидером.

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

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

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

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

Ссылаться на:

• Дом на плоту
• плот китайский перевод
• Java-реализация плота

Добро пожаловать в мой публичный аккаунт WeChat: