Основы алгоритма
Raft реализуется поверх кластера однообразных слабо связных нод, на каждой из которой работает машина состояний. Raft обеспечивает надёжную доставку сигналов на все ноды в заданном порядке. Таким образом обеспечивается переход всех машин состояний по одним и тем же последовательностям состояний. Таким образом, каждая нода гарантированно приходит в согласие с другими нодами.Каждая нода может находиться в одном из 3-х состояний:
- Лидер (Leader)
- Кандидат (Candidate)
- Ведомый (Follower)
Управление кластером четко разделено на две фазы:
- Выборы лидера (голосование)
- Репликация (передача данных протокола)
Выборы лидера
Raft предполагает, что на кластере всегда существует явно выделенный лидер. Только этот лидер отправляет новые записи на другие ноды кластера. Таким образом, остальные ноды следуют за лидером и не взаимодействуют между собой (за исключением фазы голосования). Если внешний клиент подключается к кластеру через обычную ноду, то все его запросы перенаправляются лидеру и только оттуда приходят на ноды.
Если обычная нода долго не получает сообщений от лидера, то она переходит в состояние «кандидат» и посылает другим нодам запрос на голосование. Другие ноды голосуют за того кандидата, от которого они получили первый запрос. Если кандидат получает сообщение от лидера, то он снимает свою кандидатуру и возвращается в обычное состояние. Если кандидат получает большинство голосов, то он становится лидером. Если же он не получил большинства (это случай, когда на кластере возникли сразу несколько кандидатов и голоса разделились), то кандидат ждёт случайное время и инициирует новую процедуру голосования.
Процедура голосования повторяется, пока не будет выбран лидер. Как только лидер определен, все ноды узнают о нем и начинается процесс репликации данных протокола.
Репликация протокола
Лидер полностью отвечает за правильную репликацию протоколов. Он отправляет все нодам кластера запрос на добавление новой записи и считает транзакцию успешной только после того, как большинство нод подтвердило, что данные были применены и результат сохранён на постоянный носитель (обычно, жёсткий диск).Такой механизм выбора консенсуса имеет ряд преимуществ.
- Четкое разделение фаз управления кластером на 2 фазы сильно упрощают понимание алгоритма, что в конечном счете положительно скажется на реализации.
- Явный выраженный лидер позволяет сократить число взаимодействий между нодами, что сокращает потенциальное число ошибок. Ноды взаимодействуют только с лидером, за исключением фазы голосования.
- Слабая связность нод и гибкий алгоритм голосования позволяют легко менять на лету количество нод. Новые ноды будут автоматически находить лидера и быстро вступать в работу. В случае отказа лидера, ноды "проведут" голосование и кластер продолжит функционировать.
Есть ряд ограничений на протоколы, а также накладные расходы на использование raft.
- Протоколы передачи данных между нодами не должны иметь пропусков. Так как порядок поступающих элементов используется в работе алгоритма.
- Как видно из описания алгоритма, голосование опирается на случайные ожидания. Для того, чтобы алгоритм работал эффективно, должны выполняться соотношения:
- Время рассылки запроса на все ноды кластера должно быть много меньше времени голосования. Если это условие не выполняется, то кластеру становится трудно выбрать лидера из-за разделения голосов между кандидатами.
- Время голосования должно быть много меньше времени нормальной работы кластера. То есть отказ нод и голосования должны случаться достаточно редко.
На практике такое соотношение достигается легко: время взаимодействия нод обычно измеряется миллисекундами. Время голосования — секундами. Время нормальной работы между отказами — месяцами.
Лучше один раз увидеть как работает данный алгоритм, чем сто раз прочитать или услышать.
Применение
Raft относительно молод и уже находит применение в крупных IT проектах.
- Facebook в production использует NoSQL базу данных HBase в механизме сообщений. Они форкнули HBase и доработали кластер с использованием Raft алгоритма. База получила название HydraBase.
- Набирает популярность time series база данных под названием InfluixDB. Написана она на языке Go и в основе ее кластера лежит Raft.
С другими примерами использования Raft можно познакомится на официальном ресурсе в github (ссылку дам чуть позже). Также на этом сайте есть визуализация работы алгоритма с возможностью изменения параметров и имитации остановки/запуска нод. На этом моменте я Вас оставляю и даю возможность поиграть с Raft: официальный ресурс Raft на github
