Протокол консенсуса Raft

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

История и предпосылки создания

До появления Raft доминирующим алгоритмом консенсуса в распределённых системах был Paxos, предложенный Лесли Лэмпортом в 1989 году. Несмотря на свою теоретическую обоснованность и широкое использование в промышленных системах (например, в Google Chubby), Paxos известен своей сложностью для понимания и реализации. Многие разработчики и исследователи отмечали, что даже после многократного изучения спецификации Paxos остаётся значительным риском допустить ошибки в реализации.

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

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

Raft решает задачу достижения консенсуса в кластере из N узлов, где система остаётся работоспособной при выходе из строя не более (N-1)/2 узлов (то есть, для кластера из 5 узлов допустим отказ 2). Алгоритм основан на модели реплицированного журнала состояний (state machine replication), где каждый узел хранит последовательность команд, и все узлы применяют эти команды в одинаковом порядке.

Роли узлов

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

• Лидер (Leader): Единственный узел, который обрабатывает запросы от клиентов и управляет репликацией журнала на ведомые узлы. Лидер отвечает за отправку сообщений «Heartbeat» (сердцебиение) для подтверждения своего статуса.
• Кандидат (Candidate): Промежуточное состояние, в которое узел переходит для инициирования выборов нового лидера.
• Последователь (Follower): Пассивное состояние, в котором узел получает и применяет команды от лидера. Если последователь не получает сообщений от лидера в течение определённого тайм-аута (таймаут выборов), он инициирует выборы.

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

Процесс выборов лидера является ключевым механизмом Raft. Он запускается, когда последователь не получает heartbeat от текущего лидера в течение тайм-аута выборов (обычно 150–300 миллисекунд). Последователь увеличивает свой текущий термин (term) — номер эпохи, переходит в состояние кандидата и отправляет запросы на голосование (RequestVote RPC) всем остальным узлам.

Узел голосует за кандидата, если:

1. Кандидат имеет журнал, не менее актуальный, чем у голосующего узла (по номеру последнего зафиксированного термина и индексу записи).
2. Голосующий узел ещё не голосовал в текущем термине.

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

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

После избрания лидера он начинает обрабатывать клиентские запросы. Каждый запрос (например, команда на изменение данных) добавляется в локальный журнал лидера как новая запись. Затем лидер отправляет сообщение AppendEntries RPC всем последователям, содержащее эту запись.

Последователи сохраняют запись в свой журнал и отправляют подтверждение лидеру. Когда лидер получает подтверждение от большинства узлов (включая себя), он считает запись зафиксированной (committed) и применяет её к своему автомату состояний (state machine). Затем лидер уведомляет последователей о том, что запись зафиксирована, и они также применяют её. Этот процесс гарантирует, что все узлы, остающиеся в кластере, в конечном итоге придут к одному и тому же состоянию.

Безопасность и согласованность

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

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

Преимущества и недостатки

Преимущества

• Понятность и простота реализации: Основное преимущество Raft перед Paxos. Алгоритм разбит на чёткие, независимые подзадачи (выборы, репликация, безопасность), что упрощает его изучение и отладку.
• Модульность: Raft использует сильное лидерство, что упрощает управление журналом и обработку конфликтов.
• Надёжность: Обеспечивает строгую согласованность (linearizability) в условиях отказов узлов и сетевых разделов.
• Широкая поддержка: Существует множество реализаций Raft на различных языках программирования (Go, Java, C++, Python, Rust и др.), а также встроенные библиотеки для популярных систем (например, etcd, Consul, TiKV).

Недостатки

• Производительность при лидере: Все операции записи проходят через лидера, что может стать узким местом при высоких нагрузках. Пропускная способность системы ограничена возможностями одного узла.
• Зависимость от лидера: При сбое лидера система временно недоступна для записи до завершения выборов нового лидера.
• Сложность управления состоянием: Требуется тщательная реализация механизмов снимков (snapshots) и сжатия журнала для предотвращения неограниченного роста хранилища.
• Не подходит для всех сценариев: Raft оптимизирован для систем с сильной согласованностью и не подходит для сценариев, где допустима конечная согласованность (eventual consistency) или требуется высокая пропускная способность при большом количестве узлов.

Применение

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

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

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

• Название «Raft» (плот) было выбрано авторами как игра слов: «Raft» — это «Reliable, Replicated, Redundant, And Fault-Tolerant» (надёжный, реплицированный, избыточный и отказоустойчивый).
• В отличие от Paxos, который часто описывается как «алгоритм для достижения консенсуса», Raft изначально проектировался как «алгоритм для управления реплицированным журналом», что делает его более практичным для реализации.
• Существует множество веб-симуляторов Raft, которые позволяют визуально наблюдать за процессом выборов и репликации, что значительно облегчает его понимание.

Критика

Несмотря на свою популярность, Raft подвергается критике за то, что он не является «чистым» алгоритмом консенсуса в том смысле, что он не решает проблему консенсуса в общем виде, а предлагает конкретную архитектуру с сильным лидером. Некоторые исследователи отмечают, что в условиях очень высоких нагрузок или при большом количестве узлов (более 7–9) Raft может демонстрировать снижение производительности из-за накладных расходов на поддержание heartbeat и репликацию. Также высказываются мнения, что Raft, упрощая понимание, может скрывать некоторые тонкие нюансы, связанные с обработкой снимков и изменением конфигурации кластера.

Источники

1. Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX Annual Technical Conference.
2. Ongaro, D. (2014). Consensus: Bridging Theory and Practice. PhD Thesis, Stanford University.
3. Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems.
4. Документация и исходные коды проектов etcd, Consul, TiKV.