Алгоритм Raft

Raft — алгоритм для решения задач консенсуса в сети ненадёжных вычислений.[1] Raft разрабатывался с учётом недостатков более старого алгоритма Паксос. При выборе ключевых идей, предпочтение отдавалось более простым и практичным решениям. Тем не менее, несмотря на относительную простоту, Raft обеспечивает безопасную и эффективную реализацию машины состояний поверх кластерной вычислительной системы. Существует множество реализаций Raft с открытым исходным кодом на разных языках программирования[2].

Особенности алгоритма Raft
  • Чёткое разделение фаз. Raft предлагает декомпозицию задачи управления кластером на несколько слабо связанных подзадач, основные из которых: выбор лидера (голосование) и репликация протоколов. Каждая из этих задач допускает более детальное разделение. Это упрощает понимание алгоритма и снижает риск ошибок при его реализации.
  • Явно выделенный лидер. Raft предполагает, что на кластере всегда существует явно выделенный лидер. Только этот лидер отправляет новые записи на другие узлы кластера. Таким образом, остальные узлы следуют за лидером и не взаимодействуют между собой (за исключением фазы голосования). Если внешний клиент подключается к кластеру через обычный узел, то все его запросы перенаправляются лидеру и только оттуда приходят на узлы.
  • Протоколы работы не могут содержать пропусков. То есть записи добавляются строго последовательно. Это накладывает некоторые ограничения, по сравнению с Паксос, но позволяет очень сильно упростить алгоритм. Кроме того, специфика прикладных задач, чаще всего, не позволяет корректно работать с протоколами, содержащими пропуски. То, что Паксос допускает возникновение таких пропусков, зачастую является недостатком Паксос, с которым очень трудно бороться.
  • Изменение размера кластера. Raft позволяет легко менять конфигурацию кластера, не останавливая работы: добавлять или удалять узлы.

Основы алгоритма Raft

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

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

Выбор лидера

Если обычный узел долго не получает сообщений от лидера, то он переходит в состояние «кандидат» и посылает другим узлам запрос на голосование. Другие узлы голосуют за того кандидата, от которого они получили первый запрос. Если кандидат получает сообщение от лидера, то он снимает свою кандидатуру и возвращается в обычное состояние. Если кандидат получает большинство голосов, то он становится лидером. Если же он не получил большинства (это случай, когда на кластере возникли сразу несколько кандидатов и голоса разделились), то кандидат ждёт случайное время и инициирует новую процедуру голосования.

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

Репликация протоколов

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

Накладные расходы

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

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

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

Интересные факты

Алгоритм, очень похожий на Raft, начал использоваться в ключевых системах Яндекса задолго до появления оригинальной статьи.[3]

Несмотря на обиходное противопоставление Raft и Paxos, по сути Raft является протоколом семейства Paxos, и имеет много общих деталей реализации с MultiPaxos, ZAB (Zookeeper Atomic Broadcast) и другими.

Примечания
  1. Ongaro, Diego; Ousterhout, John In Search of an Understandable Consensus Algorithm (недоступная ссылка) (2013). Дата обращения: 2 сентября 2015. Архивировано 8 сентября 2014 года.
  2. Raft Consensus Algorithm (2014).
  3. YT — новая платформа распределённых вычислений.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.