Raft — это алгоритм консенсуса , разработанный как альтернатива семейству алгоритмов Paxos . Он должен был быть более понятным, чем Paxos, за счет разделения логики, но он также формально доказано безопасен и предлагает некоторые дополнительные функции. [1] Raft предлагает общий способ распределения конечного автомата по кластеру вычислительных систем, гарантируя, что каждый узел в кластере согласует одну и ту же серию переходов состояний. Он имеет ряд реализаций с открытым исходным кодом, с реализациями полной спецификации на Go , C++ , Java и Scala . [2] Он назван в честь Reliable, Replicated, Redundant, And Fault-Tolerant. [3]
Raft не является алгоритмом византийской отказоустойчивости (BFT); узлы доверяют избранному лидеру. [1]
Raft достигает консенсуса через избранного лидера. Сервер в кластере raft является либо лидером , либо последователем и может быть кандидатом в конкретном случае выборов (лидер недоступен). Лидер отвечает за репликацию журнала последователям. Он регулярно информирует последователей о своем существовании, отправляя сообщение heartbeat. У каждого последователя есть тайм-аут (обычно от 150 до 300 мс), в течение которого он ожидает heartbeat от лидера. Тайм-аут сбрасывается при получении heartbeat. Если heartbeat не получен, последователь меняет свой статус на кандидата и начинает выборы лидера. [1] [4]
Raft реализует консенсус с помощью подхода лидера. Кластер имеет одного и только одного избранного лидера, который полностью отвечает за управление репликацией журналов на других серверах кластера. Это означает, что лидер может принимать решения о размещении новых записей и установлении потока данных между ним и другими серверами, не консультируясь с другими серверами. Лидер лидирует до тех пор, пока не выйдет из строя или не отключится, в этом случае выжившие серверы выбирают нового лидера.
Проблема консенсуса разлагается в Raft на две относительно независимые подзадачи, перечисленные ниже.
В случае отказа действующего лидера или при инициализации алгоритма необходимо выбрать нового лидера.
В этом случае в кластере начинается новый срок . Срок — это произвольный период времени на сервере, на который необходимо выбрать нового лидера. Каждый срок начинается с выборов лидера. Если выборы завершены успешно (т. е. избран один лидер), срок продолжается с обычными операциями, организованными новым лидером. Если выборы не увенчались успехом, начинается новый срок с новых выборов.
Выборы лидера начинаются сервером- кандидатом . Сервер становится кандидатом, если он не получает сообщения от лидера в течение периода, называемого тайм-аутом выборов , поэтому он предполагает, что действующего лидера больше нет. Он начинает выборы, увеличивая счетчик сроков, голосуя за себя как за нового лидера и отправляя сообщение всем другим серверам с просьбой проголосовать за них. Сервер будет голосовать только один раз за срок, по принципу «первым пришел — первым обслужен». Если кандидат получает сообщение от другого сервера с номером срока, большим, чем текущий срок кандидата, то выборы кандидата считаются недействительными, и кандидат становится последователем и признает лидера законным. Если кандидат получает большинство голосов, то он становится новым лидером. Если ни то, ни другое не происходит, например, из-за разделения голосов, то начинается новый срок и новые выборы. [1]
Raft использует рандомизированный тайм-аут выборов, чтобы гарантировать быстрое решение проблем с разделением голосов. Это должно снизить вероятность разделения голосов, поскольку серверы не станут кандидатами одновременно: один сервер выйдет из строя, выиграет выборы, затем станет лидером и отправит сообщения heartbeat другим серверам, прежде чем кто-либо из последователей сможет стать кандидатами. [1]
Лидер отвечает за репликацию журнала. Он принимает клиентские запросы. Каждый клиентский запрос состоит из команды, которая должна быть выполнена реплицированными конечными автоматами в кластере. После добавления в журнал лидера в качестве новой записи каждый из запросов пересылается последователям в виде сообщений AppendEntries. В случае недоступности последователей лидер повторяет сообщения AppendEntries неограниченное количество раз, пока запись журнала в конечном итоге не будет сохранена всеми последователями.
Как только лидер получает подтверждение от более чем половины своих последователей о том, что запись была реплицирована, лидер применяет запись к своей локальной машине состояний, и запрос считается зафиксированным . [1] [4] Это событие также фиксирует все предыдущие записи в журнале лидера. Как только последователь узнает, что запись журнала зафиксирована, он применяет запись к своей локальной машине состояний. Это обеспечивает согласованность журналов между всеми серверами через кластер, гарантируя, что соблюдается правило безопасности Log Matching.
В случае сбоя лидера журналы могут остаться несогласованными, так как некоторые журналы старого лидера не будут полностью реплицированы через кластер. Новый лидер затем будет обрабатывать несогласованность, заставляя последователей дублировать свой собственный журнал. Чтобы сделать это, для каждого из своих последователей лидер сравнит свой журнал с журналом последователя, найдет последнюю запись, где они совпадают, затем удалит все записи, идущие после этой критической записи в журнале последователя, и заменит ее своими собственными записями журнала. Этот механизм восстановит согласованность журнала в кластере, подверженном сбоям.
Raft гарантирует каждое из следующих свойств безопасности:
Первые четыре правила гарантируются деталями алгоритма, описанными в предыдущем разделе. Безопасность государственного аппарата гарантируется ограничением на процесс выборов.
Это правило обеспечивается простым ограничением: кандидат не может победить на выборах, если его журнал не содержит все зафиксированные записи. Чтобы быть избранным, кандидат должен связаться с большинством кластера, и, учитывая правила фиксации журналов, это означает, что каждая зафиксированная запись будет присутствовать по крайней мере на одном из серверов, с которыми связываются кандидаты.
Raft определяет, какой из двух журналов (передаваемых двумя разными серверами) является более актуальным, сравнивая индексный термин последних записей в журналах. Если журналы имеют последнюю запись с разными терминами, то журнал с более поздним термином является более актуальным. Если журналы заканчиваются одним и тем же термином, то тот журнал, который длиннее, является более актуальным.
В Raft запрос кандидата к избирателю включает информацию о журнале кандидата. Если его собственный журнал более актуален, чем журнал кандидата, избиратель отказывает в голосовании кандидату. Такая реализация обеспечивает правило безопасности машины состояний.
Если подписчик выходит из строя, AppendEntries и запросы на голосование , отправленные другими серверами, не будут выполнены. Такие сбои обрабатываются серверами, которые пытаются бесконечно достучаться до упавшего подписчика. Если подписчик перезапускается, ожидающие запросы будут завершены. Если запрос уже был учтен до сбоя, перезапущенный подписчик просто проигнорирует его.
Время имеет решающее значение в Raft для выбора и поддержания устойчивого лидера с течением времени, чтобы иметь идеальную доступность кластера. Стабильность обеспечивается за счет соблюдения требования алгоритма к времени :
broadcastTime << electionTimeout << MTBF
Типичные числа для этих значений могут быть от 0,5 мс до 20 мс для broadcastTime , что подразумевает, что программист устанавливает electionTimeout где-то между 10 мс и 500 мс. Между сбоями одного сервера может пройти несколько недель или месяцев, что означает, что значения достаточны для стабильного кластера.