Распределённые системы
Raft
Цели урока
- Понимать три роли узлов и механизм переходов между ними
- Объяснять алгоритм выборов лидера и роль randomized timeout
- Описывать процесс репликации лога через AppendEntries
- Знать пять Safety-свойств и почему нельзя коммитить записи чужих term
- Ориентироваться в реальных реализациях (etcd, hashicorp/raft)
Предварительные знания
- Понимание проблемы консенсуса в распределённых системах
- Базовое знание leader election (heartbeats, quorum)
- Представление о replicated state machine
5 из 8 независимых реализаций Paxos содержали баги безопасности (CMU, 2014). Raft создан с одной целью: сделать консенсус понятным настолько, чтобы его правильно реализовывали с первого раза.
- **Kubernetes** использует etcd/raft для хранения всего состояния control plane
- **CockroachDB** реплицирует данные через Raft per-range (каждый диапазон ключей - отдельный Raft-кластер)
- **Consul** выбирает лидера кластера сервисов через hashicorp/raft
- **TiKV** (хранилище TiDB) использует tikv/raft-rs на Rust для ACID-транзакций
- **Vault** (HashiCorp) хранит секреты в Raft-кластере с шифрованием
Диего Онгаро и рождение Raft
Диего Онгаро защитил диссертацию в Stanford в 2014 году под руководством Джона Оустерхаута. Главный тезис: понятность должна быть первоклассным design goal, а не побочным результатом. Авторы провели user study: после обучения оба алгоритма студенты проходили тест на понимание. По Raft результаты были значимо лучше (p < 0.05). Название Raft - аббревиатура "Reliable, Replicated, Redundant, Fault-Tolerant", и одновременно - плот, на котором можно переправиться через Paxos.
Роли узлов и понятие Term
**2014 год. Диего Онгаро, Stanford. Диссертация "In Search of an Understandable Consensus Algorithm".** Пaxos существует с 1989, но настолько сложен, что большинство реализаций содержат баги - эксперимент CMU показал: 5 из 8 независимых реализаций Paxos содержали ошибки безопасности. Raft создан как ответ: тот же гарантии, в два раза меньше концепций. Сегодня Kubernetes, Consul, CockroachDB и TiKV работают именно на Raft.
Каждый узел в Raft-кластере всегда находится в одном из трёх состояний: **Leader**, **Follower** или **Candidate**. В любой момент в кластере не более одного лидера.
| Состояние | Роль | Что делает |
|---|---|---|
| Leader | Управляет кластером | Принимает запросы клиентов, реплицирует лог, шлёт heartbeats |
| Follower | Пассивный узел | Отвечает на запросы лидера и кандидатов, сам инициатив не берёт |
| Candidate | Претендент | Временное состояние во время выборов - пытается стать Leader |
**Term** - логический период времени в Raft. Каждый term начинается с выборов. Term монотонно растёт и никогда не убывает. Если узел видит term больше своего - немедленно обновляет и возвращается в Follower. Максимум один Leader per term.
Если Follower не получает heartbeat за election timeout (150-300 мс по умолчанию) - предполагает смерть лидера и переходит в Candidate, начиная новый term.
Term в Raft - это физическое время, например номер секунды
Term - логический счётчик, монотонно растущий с каждыми новыми выборами. Нет связи с реальным временем.
Raft намеренно не зависит от синхронизации часов. Term служит для определения свежести информации: больший term = более актуальные данные.
Узел Raft получает AppendEntries с term=5, у самого узла currentTerm=7. Что произойдёт?
Leader Election
При истечении election timeout Follower переходит в Candidate: увеличивает currentTerm, голосует за себя и рассылает RequestVote всем узлам кластера. Если кандидат получил голоса от большинства (N/2 + 1) - становится Leader и немедленно рассылает heartbeat, чтобы остановить чужие выборы.
Ключевое условие голосования: лог кандидата должен быть **не хуже** лога голосующего. Это гарантирует, что лидером станет узел с самыми свежими данными. Сравнение: сначала по lastLogTerm (больший - свежее), потом по lastLogIndex (длиннее - свежее).
**Split vote** - ситуация, когда несколько кандидатов стартовали одновременно и никто не набрал большинства. Решение: **randomized election timeout** (каждый узел ждёт случайное время 150-300 мс). Первый проснувшийся кандидат успевает собрать голоса до старта других.
Partition: что происходит со старым лидером
Кластер из 5 узлов. Сетевой разрыв отрезает лидера (Leader-A) от 3 узлов. Большинство (3/5) выбирает нового Leader-B с term=6. Leader-A продолжает принимать запросы, но не может их коммитить - нет кворума. Клиенты получают timeout. Когда сеть восстановится - Leader-A увидит term=6 > своего term, мгновенно вернётся в Follower. Все uncommitted записи Leader-A будут перезаписаны.
В кластере из 5 узлов произошёл split vote: 2 кандидата набрали по 2 голоса. Что произойдёт?
Log Replication
Replicated Log - сердце Raft. Каждая запись содержит: **index** (позиция), **term** (в каком term создана) и **command** (команда для state machine). Лидер принимает команду от клиента, добавляет в свой лог и рассылает AppendEntries всем follower. Запись считается **committed** когда реплицирована на большинство узлов.
| Поле AppendEntries | Назначение |
|---|---|
| prevLogIndex / prevLogTerm | Consistency check: у follower должна быть запись с таким index и term |
| entries[] | Новые записи для добавления (пустой массив = heartbeat) |
| leaderCommit | Lидер сообщает follower, до какого index можно применять к state machine |
**Критическое правило commit:** лидер коммитит только записи **своего term**. Записи предыдущих term коммитятся "заодно" вместе с текущей. Это защита от сценария Figure 8 из paper: без этого правила committed запись можно перезаписать при смене лидера.
Figure 8: почему нельзя коммитить старые terms напрямую
Term 2: S1 (лидер) реплицирует запись на S2. Логи: S1=[1,2], S2=[1,2], S3=[1]. Term 3: S5 становится лидером, добавляет запись term 3. S5=[1,3]. Term 4: S1 снова лидер, реплицирует запись term 2 на S3. Теперь [1,2] на большинстве (S1,S2,S3). Если S1 упадёт - S5 может стать лидером (его term 3 > term 2), и перезапишет term-2 запись! Решение: S1 должен сначала добавить запись term 4 - только когда [1,2,4] на большинстве, всё safe.
Запись committed как только лидер добавил её в свой лог
Запись committed только когда реплицирована на большинство (N/2 + 1) узлов кластера
Если бы лидер считал запись committed сразу, сбой лидера мог бы привести к потере данных, которые клиент уже получил подтверждение. Кворум гарантирует, что данные переживут смерть любого меньшинства.
Follower получил AppendEntries с prevLogIndex=5, prevLogTerm=3, но у него запись на index=5 имеет term=2. Что происходит?
Safety и реальные реализации
Raft доказывает пять свойств Safety, из которых следует корректность алгоритма. Главное: при любом сценарии сбоев committed запись никогда не теряется и не перезаписывается.
| Свойство | Гарантия |
|---|---|
| Election Safety | Не более одного лидера per term |
| Leader Append-Only | Лидер никогда не удаляет и не перезаписывает свой лог |
| Log Matching | Если два лога совпадают на (index, term) - все предыдущие записи идентичны |
| Leader Completeness | Если запись committed в term T - она есть в логе всех лидеров с term > T |
| State Machine Safety | Все узлы применяют одинаковую команду на каждый index лога |
**Joint Consensus** - механизм безопасного изменения membership (добавление/удаление узлов). Создаётся переходная конфигурация C_old,new, где решения требуют большинства в обоих наборах. Более простой подход: **single-server changes** - менять по одному узлу за раз, без переходной конфигурации.
| Реализация | Язык | Используется в |
|---|---|---|
| etcd/raft | Go | Kubernetes, CockroachDB |
| hashicorp/raft | Go | Consul, Nomad, Vault |
| Ratis | Java | Apache Ozone |
| tikv/raft-rs | Rust | TiKV |
| NuRaft | C++ | eBay NuKV |
Оптимизации production-реализаций: **Batching** (несколько команд в одном AppendEntries), **Pipelining** (следующий batch до получения ACK), **Pre-vote** (предварительный round перед выборами, предотвращает disruption от partitioned nodes), **Learners** (non-voting члены для catch-up перед join), **Snapshotting** (compaction лога в snapshot при росте).
Raft - упрощённая версия Paxos с меньшими гарантиями
Raft предоставляет те же гарантии безопасности что и Multi-Paxos, но с принципиально другой декомпозицией проблемы
Raft жертвует некоторой оптимальностью (например, Paxos позволяет принимать записи вне порядка) ради понятности. Safety properties формально эквивалентны, что доказано в диссертации Онгаро.
Почему Log Matching property позволяет лидеру найти точку расхождения с отставшим follower?
Вопросы для размышления
- etcd в Kubernetes хранит всё состояние кластера и является узким местом при масштабировании. Как при этом Raft-кворум влияет на latency каждой операции записи, и почему Kubernetes рекомендует нечётное количество etcd-узлов?
Связанные уроки
- dist-08-paxos — Raft is understood by contrast with Paxos
- ds-06-leader-election — Raft integrates leader election as a core sub-protocol
- dist-06-ordering — Raft log implements total order broadcast
- dist-10-byzantine — Raft assumes crash faults; BFT requires stronger protocols
- ds-11-distributed-locks — Lock services like etcd use Raft internally
- alg-12-bfs