Войти
Raft - это алгоритм консенсуса, разработанный как альтернатива алгоритму консенсуса Paxos семейство алгоритмов. Он должен был быть более понятным, чем Paxos, благодаря разделению логики, но он также формально признан безопасным и предлагает некоторые дополнительные функции. Raft предлагает общий способ распределения конечного автомата по кластеру вычислительных систем, гарантируя, что каждый узел в кластере согласовывает одну и ту же серию переходов состояний. Он имеет ряд эталонных реализаций с открытым исходным кодом с реализациями с полной спецификацией на Go, C ++, Java и Scala. Он назван в честь надежного, реплицированного, избыточного и отказоустойчивого.
Raft не является византийским отказоустойчивым алгоритмом: узлы доверяют избранному лидеру.
Raft достигает консенсуса через избранного лидера. Сервер в кластере рафта является либо лидером, либо ведомым, и может быть кандидатом в конкретном случае выборов (лидер недоступен). Лидер отвечает за репликацию журнала для последователей. Он регулярно информирует последователей о своем существовании, отправляя контрольное сообщение. У каждого ведомого есть тайм-аут (обычно от 150 до 300 мс), в течение которого он ожидает тактового сигнала от ведущего. Тайм-аут сбрасывается при получении контрольного сигнала. Если пульс не получен, ведомый меняет свой статус на кандидата и начинает выборы лидера.
Raft реализует консенсус с помощью подхода лидера. В кластере есть один и только один избранный лидер, который полностью отвечает за управление репликацией журналов на других серверах кластера. Это означает, что лидер может принять решение о размещении новых записей и установлении потока данных между ним и другими серверами без консультации с другими серверами. Лидер ведет до тех пор, пока не потерпит неудачу или не отключится, и в этом случае будет избран новый лидер.
Проблема консенсуса разбита в Raft на две относительно независимые подзадачи, перечисленные ниже.
Когда существующий лидер выходит из строя или когда алгоритм инициализируется, необходимо выбрать нового лидера.
В этом случае в кластере начинается новый термин. Срок - это произвольный период времени на сервере, на который необходимо избрать нового лидера. Каждый семестр начинается с выборов лидера. Если выборы завершены успешно (т. Е. Избран один лидер), срок продолжается в обычном режиме, организованном новым лидером. Если выборы не удались, начинается новый срок с новыми выборами.
Выборы лидера запускаются сервером кандидатов. Сервер становится кандидатом, если он не получает сообщения от лидера в течение периода, называемого тайм-аутом выборов, поэтому он предполагает, что действующего лидера больше нет. Он начинает выборы, увеличивая счетчик сроков, голосуя за себя как нового лидера и отправляя сообщение всем другим серверам с просьбой проголосовать. Сервер будет голосовать только один раз за срок, в порядке очереди. Если кандидат получает сообщение от другого сервера с числом терминов, по крайней мере, таким же большим, как текущий срок кандидата, то выборы кандидата проигрывают, и кандидат превращается в последователя и признает лидера легитимным. Если кандидат получает большинство голосов, он становится новым лидером. Если ни то, ни другое не происходит, например, из-за раздельного голосования, начинается новый срок и начинаются новые выборы.
Raft использует случайный тайм-аут выборов, чтобы гарантировать быстрое решение проблем раздельного голосования. Это должно снизить вероятность разделения голосов, потому что серверы не станут кандидатами одновременно: один сервер выйдет из строя, выиграет выборы, затем станет лидером и отправит контрольные сообщения другим серверам, прежде чем кто-либо из последователей сможет стать кандидатом..
Лидер отвечает за репликацию журнала. Он принимает запросы клиентов. Каждый клиентский запрос состоит из команды, которая должна выполняться реплицированными конечными автоматами в кластере. После добавления в журнал лидера в виде новой записи, каждый из запросов пересылается подписчикам в виде сообщений AppendEntries. В случае недоступности подписчиков лидер повторяет сообщения AppendEntries бесконечно, пока запись журнала в конечном итоге не будет сохранена всеми подписчиками.
Как только лидер получает подтверждение от большинства своих последователей, что запись была реплицирована, лидер применяет запись к своему локальному конечному автомату, и запрос считается принятым. Это событие также фиксирует все предыдущие записи в журнале лидера. Как только ведомый узнает, что запись в журнале зафиксирована, он применяет ее к своему локальному конечному автомату. Это обеспечивает согласованность журналов между всеми серверами в кластере, гарантируя соблюдение правила безопасности сопоставления журналов.
В случае отказа лидера журналы могут остаться несогласованными, при этом некоторые журналы старого лидера не будут полностью реплицированы через кластер. Затем новый лидер исправит несоответствие, заставляя последователей дублировать свой собственный журнал. Для этого для каждого из своих последователей лидер сравнит свой журнал с журналом подписчика, найдет последнюю запись, с которой они согласны, затем удалит все записи, следующие за этой важной записью в журнале подписчиков, и заменит ее своей собственные записи журнала. Этот механизм восстановит согласованность журналов в кластере, подверженном сбоям.
Raft гарантирует каждое из этих свойств безопасности:
Первые четыре правила гарантируются детали алгоритма, описанного в предыдущем разделе. Безопасность Государственного аппарата гарантируется ограничением избирательного процесса.
Это правило обеспечивается простым ограничением: кандидат не может выиграть выборы, если его журнал не содержит все зафиксированные записи. Чтобы быть избранным, кандидат должен связаться с большей частью кластера, и, учитывая правила фиксации журналов, это означает, что каждая зафиксированная запись будет присутствовать по крайней мере на одном из серверов, с которыми кандидаты связываются.
Raft определяет, какой из двух журналов (переносимых двумя отдельными серверами) является более актуальным, сравнивая индексный термин последних записей в журналах. Если в журналах есть последняя запись с другими условиями, то журнал с более поздним сроком является более актуальным. Если журналы заканчиваются одним и тем же термином, то тот журнал, который длиннее, является более актуальным.
В Raft запрос кандидата избирателю включает информацию о журнале кандидата. Если его собственный журнал более актуален, чем журнал кандидата, избиратель отказывает в голосовании кандидату. Эта реализация обеспечивает правило безопасности конечного автомата.
Если последователь дает сбой, запросы AppendEntries и голосования, отправленные другими серверами, завершаются ошибкой. Такие сбои обрабатываются серверами, которые бесконечно пытаются добраться до сбитого ведомого. Если последователь перезапустится, ожидающие запросы будут выполнены. Если запрос уже был учтен до сбоя, перезапущенный последователь просто проигнорирует его.
Сроки очень важны для Raft, чтобы выбрать и поддерживать стабильного лидера с течением времени, чтобы иметь идеальную доступность кластера. Стабильность обеспечивается соблюдением временных требований алгоритма:
broadcastTime << electionTimeout << MTBF
Типичное число для этих значений может быть от 0,5 мс до 20 мс для broadcastTime, что означает, что программист устанавливает значение selectionTimeout где-то между 10 и 500 мс. Между сбоями одного сервера может пройти несколько недель или месяцев, что означает, что значения приемлемы для стабильной работы кластера.
