Алгоритм Raft: как распределённые системы договариваются об истине

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

Raft был предложен Диего Онгаро и Джоном Оустерхаутом в 2014 году как более понятная альтернатива Paxos. Авторы поставили цель: создать алгоритм консенсуса, который легко понять и правильно реализовать. Результат — де-факто стандарт для систем вроде etcd, CockroachDB, TiKV и Consul.

Что такое консенсус в распределённых системах?

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

• Узлы могут выходить из строя и восстанавливаться
• Сеть между узлами может задерживать или теряла сообщения
• Нельзя заранее знать, упал ли узел или просто замедлился
• Система должна продолжать работу при отказе меньшинства узлов

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

Три ключевых компонента Raft

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

Raft разделяет время на термы (terms) — монотонно возрастающие целые числа. Каждый терм начинается с выборов: один или несколько узлов становятся кандидатами и запрашивают голоса у остальных. Узел становится лидером, если получает голоса от большинства (⌊N/2⌋ + 1 узлов).

"Raft гарантирует, что в один момент времени может быть только один лидер в пределах данного терма — именно это делает алгоритм безопасным."

Последователи переходят в состояние кандидата, если не получили heartbeat от лидера в течение случайного интервала (election timeout). Случайность необходима, чтобы избежать одновременного старта выборов несколькими узлами.

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

Лидер принимает все записи от клиентов. Каждая запись сначала добавляется в локальный журнал лидера, затем отправляется последователям через RPC AppendEntries. Когда большинство узлов подтвердили запись, она считается «закреплённой» (committed) и применяется к машине состояний.

Важное свойство: лидер никогда не перезаписывает и не удаляет записи из своего журнала. Он только добавляет. Это упрощает рассуждения о правильности алгоритма.

3. Безопасность

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

Практическое применение: etcd и Kubernetes

etcd — основное хранилище состояния Kubernetes — построен на Raft. Каждое изменение ресурса в кластере (создание пода, обновление ConfigMap) сначала реплицируется через Raft на большинство узлов etcd, и только потом Kubernetes API Server сообщает клиенту об успехе.

Это означает: при потере связи с большинством etcd-узлов, запись в кластер Kubernetes прекратится. Доступность приносится в жертву ради согласованности — типичный CP-выбор в терминах CAP-теоремы.

Raft против Paxos: в чём реальное различие?

Paxos — более старый алгоритм, математически эквивалентный Raft по гарантиям безопасности. Ключевое отличие — в декомпозиции. Raft явно разделяет выборы лидера, репликацию журнала и безопасность на независимые подзадачи. Paxos описывает только консенсус для одного значения, а Multi-Paxos для журнала — уже неформальное расширение, реализованное по-разному в разных системах.

Исследование авторов Raft показало, что студенты, изучившие оба алгоритма, значительно лучше отвечали на вопросы по Raft. Это не значит, что Paxos хуже — но инженерная ценность понятности высока: меньше ошибок в реализации, проще код-ревью, быстрее онбординг.

Ограничения и когда Raft не подходит

Raft оптимален для кластеров из 3–7 узлов. При большем количестве задержки выборов и стоимость репликации на большинство могут стать заметными. Для масштабов в сотни узлов лучше рассматривать иерархические или партиционированные подходы.

Raft также не решает задачу Byzantine fault tolerance: он предполагает, что узлы могут упасть, но не могут вести себя злонамеренно. Для систем, требующих защиты от компрометации узла, необходимы PBFT или аналогичные BFT-алгоритмы.