Алгоритм Raft¶

Алгоритм Raft — это консенсусный протокол, предназначенный для управления реплицированным журналом (log) в распределённых системах. Он был разработан как более понятная и простая в реализации альтернатива алгоритму Paxos, сохраняя при этом эквивалентные гарантии безопасности и живучести (liveness). Основная цель Raft — обеспечить согласованность данных между несколькими узлами (серверами) в условиях отказов и сетевых разделений, что является фундаментальной задачей для построения отказоустойчивых распределённых баз данных, координаторов и систем хранения состояния.

¶История и предпосылки

Алгоритм Raft был впервые представлен в 2014 году в статье «In Search of an Understandable Consensus Algorithm» (В поисках понятного алгоритма консенсуса) учёными Диего Онгаро (Diego Ongaro) и Джоном Остерхаутом (John Ousterhout) из Стэнфордского университета. Основной мотивацией для создания Raft послужила сложность понимания и корректной реализации Paxos, который на протяжении десятилетий оставался доминирующим, но труднодоступным для широкого круга разработчиков алгоритмом консенсуса. Онгаро и Остерхаут провели исследование, показавшее, что студенты, изучившие Raft, понимают его значительно лучше, чем те, кто изучал Paxos.

С момента публикации Raft получил широкое распространение в индустрии. Он лёг в основу таких известных проектов, как etcd (распределённое хранилище ключ-значение, используемое в Kubernetes), Consul (система обнаружения сервисов), TiKV (распределённая база данных), а также многих других систем, требующих надёжной репликации и отказоустойчивости.

¶Принцип работы

Алгоритм Raft решает задачу консенсуса, разбивая её на три ключевые подзадачи: выборы лидера (leader election), репликация журнала (log replication) и обеспечение безопасности (safety). Протокол гарантирует, что все корректные (non-faulty) узлы в конечном итоге согласятся с одним и тем же набором записей в журнале, который упорядочен во времени.

¶Роли серверов

В любой момент времени каждый узел (сервер) в кластере Raft находится в одном из трёх состояний:

• Лидер (Leader): Обрабатывает все запросы от клиентов. Он управляет репликацией записей журнала на другие узлы. В нормальном режиме работы кластера существует ровно один лидер.
• Кандидат (Candidate): Узел, который инициирует новые выборы лидера. Это переходное состояние, используемое для избрания нового лидера.
• Последователь (Follower): Пассивное состояние. Узел реагирует на запросы от лидера и кандидатов. В отсутствие лидера последователи становятся кандидатами.

¶Выборы лидера

Процесс выборов лидера запускается, когда последователи не получают сообщений от текущего лидера в течение определённого времени, называемого тайм-аутом выборов (election timeout). Тайм-аут на каждом узле задаётся случайным образом в интервале, например, от 150 до 300 миллисекунд. Это предотвращает одновременный запуск выборов всеми узлами.

1. Последователь, чей тайм-аут истёк первым, увеличивает свой срок (term) — монотонно возрастающий номер эпохи — и переходит в состояние кандидата.
2. Кандидат голосует сам за себя и отправляет запросы на голосование (RequestVote RPC) всем остальным узлам.
3. Другие узлы голосуют за первого кандидата, от которого получают запрос, при условии, что срок кандидата не меньше их собственного.
4. Если кандидат получает голоса от большинства (кворума) узлов кластера, он становится лидером на текущий срок.
5. Если выборы не завершаются (например, из-за разделения голосов), начинается новый тур с новым тайм-аутом.

После избрания лидер начинает отправлять пустые сообщения Heartbeat (сердцебиение) всем последователям, чтобы предотвратить запуск новых выборов.

¶Репликация журнала

Когда лидер получает запрос от клиента (например, команду на изменение данных), он выполняет следующие шаги:

1. Добавление записи: Лидер добавляет новую запись в свой локальный журнал. Каждая запись содержит команду и номер срока, в который она была добавлена.
2. Параллельная отправка: Лидер отправляет сообщение AppendEntries RPC всем последователям, содержащее новую запись.
3. Подтверждение: Последователи добавляют запись в свои журналы и отправляют подтверждение лидеру. Запись считается зафиксированной (committed), как только лидер получает подтверждение от большинства узлов (включая себя).
4. Применение: После фиксации лидер применяет команду к своему конечному автомату (state machine) и уведомляет клиента об успехе. В последующих сообщениях AppendEntries лидер сообщает последователям, какие записи уже зафиксированы, чтобы те могли применить их к своим конечным автоматам.

¶Безопасность и гарантии

Raft гарантирует несколько ключевых свойств безопасности:

• Свойство безопасности выборов (Election Safety): В течение одного срока может быть избран не более одного лидера.
• Свойство безопасности журнала (Log Matching): Если две записи в журналах разных узлов имеют одинаковый индекс и срок, то все предыдущие записи в этих журналах также идентичны.
• Свойство полноты лидера (Leader Completeness): Зафиксированная запись присутствует в журнале всех будущих лидеров. Это достигается тем, что кандидат может стать лидером, только если его журнал не менее «полный», чем у большинства узлов (сравнение по последнему сроку и индексу записи).
• Свойство безопасности фиксации (State Machine Safety): Если сервер применил команду из определённого индекса к своему конечному автомату, то ни один другой сервер не применит другую команду к тому же индексу.

¶Обработка сбоев

Алгоритм Raft спроектирован для корректной работы при различных типах отказов:

• Отказ лидера: Если лидер перестаёт отвечать, последователи запускают новые выборы. Новый лидер продолжает работу с того места, где остановился предыдущий.
• Отказ последователя: Если последователь выходит из строя, лидер продолжает отправлять ему сообщения AppendEntries. После восстановления последователь догоняет журнал с помощью механизма повторной синхронизации.
• Разделение сети (Network Partition): При разделении сети на две части, в одной из которых оказывается большинство узлов, выборы проходят успешно, и лидер продолжает работу. В меньшей части выборы не могут завершиться из-за отсутствия кворума. Когда разделение устраняется, лидер из меньшей части автоматически переходит в состояние последователя, а его журнал синхронизируется с журналом действующего лидера.

¶Изменение конфигурации кластера

Raft поддерживает безопасное динамическое изменение набора узлов кластера (например, добавление или удаление сервера). Для этого используется механизм совместного консенсуса (joint consensus). Кластер временно переходит в переходное состояние, в котором решения принимаются на основе правил двух различных конфигураций (старой и новой). Это гарантирует, что в любой момент времени не возникнет ситуации с двумя независимыми лидерами в разных конфигурациях.

¶Применение

Благодаря своей понятности и надёжности, алгоритм Raft широко применяется в различных областях распределённых вычислений:

• Распределённые базы данных: Обеспечение согласованности данных при репликации (например, TiDB, CockroachDB).
• Системы управления конфигурацией: Хранение и синхронизация конфигурационных данных (etcd, Consul).
• Координация микросервисов: Сервисы обнаружения и блокировки (например, ZooKeeper, использующий собственный протокол Zab, похожий на Raft, или etcd).
• Системы хранения: Обеспечение отказоустойчивости для распределённых файловых систем и блоковых хранилищ.

¶Критика и ограничения

Несмотря на широкое признание, алгоритм Raft имеет определённые ограничения и подвергался критике:

• Производительность: Как и Paxos, Raft требует подтверждения от большинства узлов для каждой записи, что может создавать задержки (latency) в географически распределённых кластерах.
• Обработка перегрузок: При высокой нагрузке частые выборы лидера могут деградировать производительность.
• Сложность реализации: Хотя Raft проще Paxos, его корректная реализация всё ещё является нетривиальной задачей, особенно в части обработки граничных случаев и изменения конфигурации.
• Синхронный лидер: Все запросы проходят через единственного лидера, что может стать узким местом (bottleneck).

¶Источники

• Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. Proceedings of the 2014 USENIX Annual Technical Conference (USENIX ATC 14).
• Ongaro, D. (2014). Consensus: Bridging Theory and Practice (PhD thesis). Stanford University.
• Howard, H. (2015). ARC: Analysis of Raft Consensus. University of Cambridge Computer Laboratory Technical Report.