WikiSort.ru - Не сортированное

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) и другими.

Примечания

Ссылки

• lecture (Raft user study) (англ.)

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники. Викифицировать статью.