Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Raft - это согласованный алгоритм, разработанный как альтернатива семейству алгоритмов Paxos . Он должен был быть более понятным, чем Paxos, благодаря разделению логики, но он также формально признан безопасным и предлагает некоторые дополнительные функции. [1] Raft предлагает общий способ распределения конечного автомата по кластеру вычислительных систем, гарантируя, что каждый узел в кластере согласовывает одну и ту же серию переходов состояний. Он имеет ряд эталонных реализаций с открытым исходным кодом с реализациями с полной спецификацией на Go , C ++ , Java и Scala . [2]Он назван в честь «Надежный, тиражируемый, избыточный и отказоустойчивый». [3]

Raft не является византийским отказоустойчивым алгоритмом: узлы доверяют избранному лидеру. [1]

Основы [ править ]

Raft достигает консенсуса через избранного лидера. Сервер в кластере рафта является либо лидером, либо ведомым , и может быть кандидатом в конкретном случае выборов (лидер недоступен). Лидер отвечает за репликацию журнала для последователей. Он регулярно информирует последователей о своем существовании, отправляя контрольное сообщение. У каждого ведомого есть тайм-аут (обычно от 150 до 300 мс), в течение которого он ожидает сердцебиение от лидера. Тайм-аут сбрасывается при получении контрольного сигнала. Если пульс не получен, ведомый изменяет свой статус на кандидата и начинает выборы лидера. [1] [4]

Подход к проблеме консенсуса в Raft [ править ]

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

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

Выборы лидера [ править ]

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

В этом случае в кластере начинается новый термин . Срок - это произвольный период времени на сервере, на который необходимо избрать нового лидера. Каждый семестр начинается с выборов лидера. Если выборы завершены успешно (т. Е. Избран один лидер), срок полномочий продолжается в обычном режиме, организованном новым лидером. Если выборы не удались, начинается новый срок с новыми выборами.

Выборы лидера запускаются сервером кандидатов . Сервер становится кандидатом, если он не получает сообщения от лидера в течение периода, называемого тайм-аутом выборов., поэтому предполагается, что действующего лидера больше нет. Он начинает выборы, увеличивая счетчик сроков, голосуя за себя как нового лидера и отправляя сообщение всем другим серверам с просьбой проголосовать. Сервер будет голосовать только один раз за срок, в порядке очереди. Если кандидат получает сообщение от другого сервера с числом терминов, превышающим текущий срок кандидата, то выборы кандидата не принимаются, и кандидат превращается в последователя и признает лидера легитимным. Если кандидат получает большинство голосов, он становится новым лидером. Если ни то, ни другое не происходит, например, из-за раздельного голосования, начинается новый срок и начинаются новые выборы. [1]

Raft использует случайный тайм-аут выборов, чтобы обеспечить быстрое решение проблем с разделением голосов. Это должно снизить вероятность разделения голосов, потому что серверы не станут кандидатами одновременно: один сервер выйдет из строя, выиграет выборы, затем станет лидером и отправит контрольные сообщения другим серверам, прежде чем кто-либо из последователей сможет стать кандидатом. . [1]

Репликация журнала [ править ]

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

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

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

Безопасность [ править ]

Правила безопасности в Raft [ править ]

Raft гарантирует каждое из этих свойств безопасности:

  • Безопасность выборов: за один срок может быть избран не более одного лидера.
  • Только для добавления к выноске: лидер может только добавлять новые записи в свои журналы (он не может ни перезаписывать, ни удалять записи).
  • Сопоставление журналов : если два журнала содержат запись с одинаковым индексом и термином, то журналы идентичны во всех записях до данного индекса.
  • Полнота лидера: если запись в журнале совершена в определенный срок, то она будет присутствовать в журналах лидеров с этого срока.
  • Безопасность конечного автомата: если сервер применил конкретную запись журнала к своему конечному автомату, то никакой другой сервер не может применить другую команду для того же журнала.

Первые четыре правила гарантированы деталями алгоритма, описанного в предыдущем разделе. Безопасность Государственного аппарата гарантируется ограничением избирательного процесса.

Безопасность конечного автомата [ править ]

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

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

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

Сбой подписчика [ править ]

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

Сроки и доступность [ править ]

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

BroadcastTime << ВыборыTimeout << Среднее время безотказной работы

  • broadcastTime - это среднее время, которое требуется серверу для отправки запроса каждому серверу в кластере и получения ответов. Это относительно используемой инфраструктуры.
  • MTBF (среднее время наработки на отказ) - это среднее время наработки на отказ сервера. Это также связано с инфраструктурой.
  • selectionTimeout такой же, как описано в разделе «Выборы лидера». Это то, что должен выбрать программист.

Типичное значение для этих значений может составлять от 0,5 до 20 мс для broadcastTime , что означает, что программист устанавливает значение selectionTimeout где-то между 10 и 500 мс. Между сбоями одного сервера может пройти несколько недель или месяцев, что означает, что значений достаточно для стабильного кластера.

Ссылки [ править ]

  1. ^ a b c d e f Онгаро, Диего; Остерхаут, Джон (2013). «В поисках понятного алгоритма консенсуса» (PDF) .
  2. ^ «Алгоритм консенсуса Raft» . 2014 г.
  3. ^ Почему название «Плот»?
  4. ^ a b «Плот: понятный распределенный консенсус» . Проверено 14 марта 2015 . CS1 maint: обескураженный параметр ( ссылка )

Внешние ссылки [ править ]

  • Официальный веб-сайт
  • Список реализаций
  • Иллюстрированное прохождение Raft.