Алгоритм Raft простыми словами: выбор лидера, репликация лога и сравнение с Paxos
Как работает консенсус Raft: термы, выбор лидера, репликация лога и правило коммита. Модель на Python, где Raft используется (etcd, Consul, CockroachDB) и чем он отличается от Paxos.
Коротко
| Вопрос | Ответ |
|---|---|
| Какую задачу решает | Несколько серверов договариваются об одной последовательности команд, даже если часть упала |
| Сколько сбоев переживает | Кластер из узлов переживает отказов: 3 узла — 1, 5 узлов — 2 |
| Главная идея | Один лидер на терм, лог течёт только от лидера к фолловерам, запись закоммичена большинством |
| Цена | Каждая запись — минимум один сетевой круг до большинства; без большинства записи стоят |
| Где встречается | etcd (а значит Kubernetes), Consul, Vault, CockroachDB, TiKV, KRaft в Kafka |
- Raft придумали Диего Онгаро и Джон Аустерхаут в 2014 году специально как понятную замену Paxos. По гарантиям они эквивалентны.
- Время разбито на термы. В каждом терме не больше одного лидера, и любой узел, увидевший терм новее своего, сразу подчиняется.
- Лидером может стать только узел, лог которого не отстаёт от большинства. Поэтому новый лидер уже содержит все закоммиченные записи.
- Raft защищает от падений и потери сообщений, но не от узлов, которые врут: это не византийская отказоустойчивость.
Зачем вообще нужен консенсус
Представьте сервис конфигурации, где хранится «кто сейчас владеет шардом 7». Если хранить это на одном сервере, его падение останавливает всё. Если на трёх с асинхронной репликацией, то при падении основного реплика может не знать последних записей, и два клиента получат разные ответы. Об этой проблеме подробно говорится в статье о распределённых блокировках.
Консенсус даёт другую гарантию: если запись подтверждена, она переживёт отказ любого меньшинства узлов, и все узлы увидят записи в одном и том же порядке. Это называется реплицированным конечным автоматом (replicated state machine): одинаковые команды в одинаковом порядке приводят детерминированный автомат в одинаковое состояние на каждом узле.
Важно понимать, что консенсус дорог и медленнее обычной репликации. Поэтому его редко используют для всех пользовательских данных напрямую. Чаще им защищают «маленькие, но критичные» вещи: конфигурацию, метаданные, выбор лидера, распределение шардов. Исключения — базы вроде CockroachDB и TiKV, где отдельная группа Raft стоит за каждым диапазоном ключей.
Роли и термы
Каждый узел в каждый момент находится в одной из трёх ролей:
- Follower (фолловер) — пассивен: отвечает на запросы лидера и кандидатов.
- Candidate (кандидат) — пытается стать лидером в новом терме.
- Leader (лидер) — принимает команды клиентов и рассылает их остальным.
Терм (term) — это монотонно растущее число, логические часы кластера. Каждые выборы начинают новый терм. Правила простые:
- Каждое сообщение несёт терм отправителя.
- Узел, получивший сообщение с термом больше своего, обновляет свой терм и становится фолловером. Даже если был лидером.
- Сообщение с термом меньше текущего отвергается.
Благодаря этому «старый» лидер, который отвалился от сети и вернулся, не сможет ничего испортить: первое же сообщение от кластера покажет ему, что мир ушёл вперёд.
Узел хранит на диске три вещи, и они должны быть сохранены (fsync) до ответа на любой запрос: currentTerm, votedFor (за кого голосовал в этом терме) и сам лог. Если узел перезапустится и «забудет», что уже голосовал, в одном терме может появиться два лидера.
Выбор лидера
Лидер регулярно шлёт фолловерам heartbeat — пустой AppendEntries. Пока heartbeat приходят, фолловер спокоен. Если в течение election timeout ничего не пришло, фолловер решает, что лидера нет:
- Увеличивает
currentTermна 1 и становится кандидатом. - Голосует за себя.
- Рассылает остальным
RequestVote(term, candidateId, lastLogIndex, lastLogTerm).
Дальше возможны три исхода:
- Набрал большинство голосов — становится лидером и сразу шлёт heartbeat, чтобы остальные не начали свои выборы.
- Получил сообщение от лидера с термом не меньше своего — признаёт его и становится фолловером.
- Никто не набрал большинства (голоса разделились) — по таймауту начинает новые выборы с термом ещё на 1 больше.
Каждый узел голосует в терме не больше одного раза, по принципу «кто первый попросил». Поскольку большинств в кластере не бывает два непересекающихся, в одном терме не может быть двух лидеров.
Почему таймаут случайный
Если бы все фолловеры ждали одинаково, после падения лидера они бы одновременно стали кандидатами, разделили голоса, снова одновременно проснулись — и так по кругу. Raft решает это просто: каждый узел выбирает таймаут случайно из диапазона, в статье предлагается 150–300 мс. Обычно кто-то просыпается первым и успевает собрать голоса до того, как проснутся остальные.
Для корректной работы нужно соотношение
где broadcastTime — время круга RPC до узлов, а MTBF — среднее время между отказами сервера. Если таймаут сравним с задержками сети, кластер будет постоянно переизбирать лидера. В etcd по умолчанию heartbeat 100 мс, а election timeout 1000 мс: межсерверные задержки в реальных сетях больше, чем в лаборатории.
Ограничение на выборы
Голос за кандидата отдают не всем подряд. Фолловер голосует, только если лог кандидата не отстаёт от его собственного:
- у кандидата терм последней записи больше — лог новее;
- термы последних записей равны, а лог кандидата не короче — тоже годится.
Это ключевая деталь безопасности. Закоммиченная запись лежит на большинстве узлов, а для победы нужно большинство голосов. Эти два большинства пересекаются хотя бы в одном узле, и он не проголосует за кандидата без этой записи. Поэтому новый лидер всегда содержит все закоммиченные записи, и данные никогда не перетекают от фолловеров к лидеру.
Репликация лога
Лог — это массив записей (term, command) с индексами, начиная с 1. Клиент отправляет команду лидеру (фолловер перенаправит его к лидеру). Дальше:
- Лидер дописывает запись в свой лог.
- Рассылает
AppendEntries(term, prevLogIndex, prevLogTerm, entries[], leaderCommit)всем фолловерам. - Когда запись сохранило большинство, включая самого лидера, она закоммичена.
- Лидер применяет её к своему автомату и отвечает клиенту.
- В следующих
AppendEntriesфолловеры узнают новыйleaderCommitи тоже применяют запись.
Проверка согласованности
Поля prevLogIndex и prevLogTerm — сердце протокола. Фолловер принимает новые записи, только если у него на позиции prevLogIndex лежит запись с термом prevLogTerm. Иначе отвечает отказом.
Из этой проверки по индукции следует Log Matching Property: если у двух логов запись с одинаковым индексом и термом, то логи совпадают целиком до этой позиции включительно.
Если фолловер отказал, лидер уменьшает для него nextIndex на 1 и пробует снова, пока не найдёт общую точку. Всё, что у фолловера после неё и не совпадает с лидером, перезаписывается. Лидер свой лог никогда не переписывает и не удаляет записи — только дописывает.
На практике откат по одной записи слишком медленный, поэтому фолловер в отказе обычно подсказывает терм конфликта и первый индекс этого терма, и лидер перепрыгивает сразу через весь терм.
Правило коммита: ловушка со старыми термами
Интуитивно кажется: «запись есть на большинстве — значит, закоммичена». Для записей текущего терма лидера это так. Но для записей предыдущих термов — нет.
В статье Raft разобран сценарий (рисунок 8), где запись старого терма оказывается на большинстве, после чего её всё равно перезаписывает другой лидер. Дело в том, что узел с более новым термом последней записи может выиграть выборы, даже если у него нет этой старой записи.
Поэтому правило такое: лидер считает реплики только для записей своего терма. Когда закоммичена запись текущего терма, все записи до неё коммитятся автоматически благодаря Log Matching. По этой же причине новый лидер сразу после избрания дописывает пустую запись (no-op): иначе он не смог бы закоммитить хвост, оставшийся от предшественника, пока не придёт новая команда клиента.
Модель на Python
Ниже — не полноценная реализация (нет сети, таймеров и диска), а модель трёх правил, о которых спрашивают чаще всего: голосование с проверкой лога, обработка AppendEntries и вычисление индекса коммита. Код требует Python 3.10+.
from dataclasses import dataclass, field @dataclass class Entry: term: int command: str @dataclass class Node: id: int current_term: int = 0 voted_for: int | None = None log: list = field(default_factory=list) # индексы с 1, log[0] — запись №1 commit_index: int = 0 def last_log(self): """(индекс, терм) последней записи; (0, 0) для пустого лога.""" if not self.log: return 0, 0 return len(self.log), self.log[-1].term def term_at(self, index): return 0 if index == 0 else self.log[index - 1].term # --- RequestVote --- def handle_request_vote(self, term, candidate_id, last_index, last_term): if term > self.current_term: # увидели более новый терм — откатываемся в фолловеры self.current_term, self.voted_for = term, None if term < self.current_term: return self.current_term, False my_index, my_term = self.last_log() # лог кандидата не хуже нашего: сначала сравниваем термы, потом длину up_to_date = (last_term, last_index) >= (my_term, my_index) if self.voted_for in (None, candidate_id) and up_to_date: self.voted_for = candidate_id return self.current_term, True return self.current_term, False # --- AppendEntries --- def handle_append_entries(self, term, prev_index, prev_term, entries, leader_commit): if term < self.current_term: return self.current_term, False self.current_term = term # проверка согласованности: на prev_index у нас должна быть запись того же терма if prev_index > len(self.log) or self.term_at(prev_index) != prev_term: return self.current_term, False for i, entry in enumerate(entries): index = prev_index + 1 + i if index <= len(self.log) and self.log[index - 1].term != entry.term: del self.log[index - 1:] # конфликт: обрезаем хвост if index > len(self.log): self.log.append(entry) if leader_commit > self.commit_index: self.commit_index = min(leader_commit, prev_index + len(entries)) return self.current_term, True def leader_commit_index(leader_term, log, match_index, old_commit): """match_index — сколько записей подтвердил каждый узел, включая лидера.""" n = len(match_index) for index in range(len(log), old_commit, -1): replicated = sum(1 for m in match_index if m >= index) # коммитим по большинству и только запись своего терма if replicated > n // 2 and log[index - 1].term == leader_term: return index return old_commit
Проверим каждое правило:
# 1. Голосование: отстающий кандидат не получает голос voter = Node(id=2, current_term=3, log=[Entry(1, "x=1"), Entry(3, "x=2")]) print(voter.handle_request_vote(term=4, candidate_id=1, last_index=5, last_term=2)) print(voter.handle_request_vote(term=4, candidate_id=3, last_index=2, last_term=3)) print(voter.handle_request_vote(term=4, candidate_id=1, last_index=9, last_term=4)) # 2. AppendEntries чинит расходящийся лог фолловера f = Node(id=3, current_term=2, log=[Entry(1, "a"), Entry(2, "b"), Entry(2, "c")]) print(f.handle_append_entries(3, 2, 2, [Entry(3, "d")], 0)) # prev=(2,2) совпал print([(e.term, e.command) for e in f.log]) print(f.handle_append_entries(3, 5, 3, [Entry(3, "z")], 0)) # дырка — отказ # 3. Правило коммита: старый терм по большинству не коммитим log = [Entry(1, "a"), Entry(2, "b")] print(leader_commit_index(4, log, [2, 2, 2, 1, 1], 1)) log.append(Entry(4, "c")) print(leader_commit_index(4, log, [3, 3, 3, 1, 1], 1))
(4, False) (4, True) (4, False) (3, True) [(1, 'a'), (2, 'b'), (3, 'd')] (3, False) 1 3
Разберём вывод:
- Первый кандидат длиннее (5 записей), но его последняя запись из терма 2, а у голосующего — из терма 3. Длина не спасает: голоса нет.
- Второй кандидат с таким же последним термом и не короче — голос получен.
- Третий запрос в том же терме 4 отклонён, хотя лог кандидата новее: голос в этом терме уже отдан.
- Фолловер с лишней записью
(2, 'c')получил от лидера(3, 'd')на её место, и хвост был заменён. - Запись терма 2 лежит на трёх узлах из пяти, но лидер терма 4 её не коммитит. Как только на большинстве оказывается запись терма 4, коммитятся сразу все три.
Что происходит при сбоях
Падает фолловер. Лидер бесконечно повторяет AppendEntries. Когда узел вернётся, проверка согласованности найдёт общую точку и догонит лог. Запросы идемпотентны, так что повтор безопасен.
Падает лидер. Через election timeout фолловеры выбирают нового. Незакоммиченные записи старого лидера могут выжить (если попали к новому лидеру) или пропасть. Клиент, не получивший ответа, не знает, применилась ли команда. Поэтому ретраи должны быть идемпотентными: в диссертации Онгаро для этого предлагаются клиентские сессии с порядковыми номерами запросов.
Разделение сети. Пусть старый лидер оказался в меньшинстве (2 узла из 5). Он продолжает принимать запросы, но не может собрать большинство и ничего не коммитит. В большинстве выбирают нового лидера с большим термом. Когда сеть восстановится, старый лидер увидит больший терм и станет фолловером, а его незакоммиченный хвост перезапишут. Это ровно то поведение «CP», о котором рассказано в статье про теорему CAP: меньшинство теряет возможность писать, но не теряет согласованность.
Чтение с устаревшего лидера. Тонкий момент: лидер в меньшинстве может ещё не знать, что его свергли, и вернуть старые данные. Для линеаризуемых чтений лидер должен убедиться, что он всё ещё лидер. Варианты:
- провести чтение через лог как обычную команду — надёжно, но дорого;
- ReadIndex: запомнить текущий
commitIndex, обменяться heartbeat с большинством и только потом отвечать; - lease read: доверять аренде по времени, без лишнего круга. Быстро, но корректность зависит от того, насколько ровно идут часы.
Что ещё есть в настоящем Raft
Базового алгоритма хватает для собеседования, но в продакшен-реализациях есть ещё несколько механизмов. Полезно хотя бы знать их названия:
- Снапшоты и компактификация лога. Лог не может расти бесконечно. Узел периодически сохраняет снимок состояния автомата и выбрасывает префикс лога. Отстающему фолловеру лидер отправляет снапшот через
InstallSnapshot. - Смена состава кластера. Нельзя одновременно переключить все узлы со старой конфигурации на новую: в какой-то момент возможны два лидера с разными большинствами. В статье предложен joint consensus — промежуточная конфигурация, где решения требуют большинства и старого, и нового состава. Позже Онгаро описал упрощение: менять состав по одному узлу за раз.
- PreVote. Узел, отрезанный от сети, бесконечно поднимает терм. Когда он вернётся, его огромный терм сбросит здорового лидера. С PreVote кандидат сначала спрашивает «проголосовали бы вы за меня?» без увеличения терма. В etcd это включено.
- CheckQuorum. Лидер, который давно не слышал большинство, сам уходит в фолловеры.
- Батчинг и конвейер. Лидер отправляет пачки записей и не ждёт ответа на предыдущую, иначе пропускная способность упирается в задержку сети и
fsync.
Где используется Raft
| Система | Для чего Raft |
|---|---|
| etcd | Всё хранилище ключ-значение. Через etcd — состояние кластера Kubernetes |
| Consul, Nomad, Vault | Серверы HashiCorp реплицируют состояние через общую библиотеку hashicorp/raft |
| CockroachDB, TiKV, YugabyteDB | Каждый диапазон (range, region, tablet) — отдельная группа Raft, тысячи групп на кластер (Multi-Raft) |
| Kafka (KRaft) | Кворум контроллеров хранит метаданные кластера. С Kafka 4.0 ZooKeeper не поддерживается |
| RabbitMQ | Quorum-очереди на библиотеке Ra |
| ClickHouse Keeper | Замена ZooKeeper для координации ClickHouse |
KRaft в Kafka — это вариант Raft, а не реализация «по статье»: фолловеры сами забирают записи у лидера (pull), как обычные реплики Kafka, вместо того чтобы лидер их рассылал. Похожая история с MongoDB: протокол выборов в replica set основан на идеях Raft, но репликация устроена по-своему. На собеседовании лучше так и говорить: «вдохновлено Raft», а не «это Raft».
Кто использует не Raft: ZooKeeper работает на своём протоколе ZAB (по устройству очень близок к Raft), Google Spanner и Chubby — на Paxos.
Raft и Paxos
Paxos описал Лесли Лэмпорт: статья «The Part-Time Parliament» вышла в 1998 году, а более доступная «Paxos Made Simple» — в 2001-м. Классический Paxos договаривается об одном значении. Чтобы получить лог, его запускают отдельно для каждой позиции и добавляют выделенного лидера — это Multi-Paxos. Проблема в том, что Multi-Paxos в оригинале описан эскизно, и каждая реализация достраивала детали по-своему.
Raft сознательно жертвует гибкостью ради понятности. Отличия, которые стоит назвать на собеседовании:
| Аспект | Raft | (Multi-)Paxos |
|---|---|---|
| Лидер | Обязателен. Без лидера ничего не происходит | В базовой версии предлагать может любой, лидер — оптимизация |
| Направление данных | Только от лидера к фолловерам | Новый лидер в первой фазе собирает у остальных значения, которых у него нет |
| Кто может стать лидером | Только узел с актуальным логом | Любой. Недостающие значения он узнаёт у кворума |
| Дырки в логе | Нет: записи коммитятся строго по порядку | Возможны: позиции согласуются независимо |
| Спецификация | Полная: выборы, репликация, смена состава, снапшоты | Ядро строго доказано, практические части описаны неполно |
| Отказоустойчивость | узлов на отказов | Те же |
| Стоимость записи в норме | Один круг до большинства | Тоже один круг (при стабильном лидере фазу 1 пропускают) |
Главное, что нужно сказать: по гарантиям и производительности в устойчивом режиме они эквивалентны. Raft — это по сути Multi-Paxos с сильным лидером и жёсткими правилами, которые делают алгоритм проще для понимания и реализации. Paxos гибче: например, существуют варианты без лидера (EPaxos) и с кворумами разного размера для разных фаз (Flexible Paxos).
Типичные ошибки и заблуждения
- «Запись на большинстве — значит закоммичена». Только для записей текущего терма лидера. Старые записи коммитятся опосредованно.
- «Чем больше узлов, тем надёжнее и быстрее». Надёжнее — да, быстрее — нет. Каждая запись ждёт большинство, а пять узлов против трёх означают больше трафика у лидера. Обычно используют 3 или 5 узлов, для чтения добавляют неголосующих учеников (learners).
- Чётное число узлов. Четыре узла переживают столько же отказов, сколько три (одного), но большинство уже 3 из 4. Чётность ничего не даёт.
- Голос не сохранён на диск. Перезапуск без
votedFor— и в одном терме два лидера. - Чтение с лидера без проверки лидерства. Лидер в меньшинстве ответит устаревшими данными.
- Raft защищает от злонамеренных узлов. Нет. Узел, который шлёт ложные термы или подделывает лог, сломает кластер. Для этого нужны византийские протоколы вроде PBFT.
Как отвечать на собеседовании
Вопрос про Raft на system design обычно возникает в одном из двух видов.
«Как устроен Raft?» Хватит рассказа на 3–5 минут по плану:
- Задача: реплицированный лог, переживающий отказ меньшинства.
- Термы и три роли.
- Выборы: таймаут, случайный разброс, один голос на терм, ограничение по актуальности лога.
- Репликация:
AppendEntriesс проверкойprevLogIndex/prevLogTerm, коммит по большинству. - Безопасность: новый лидер содержит все закоммиченные записи; записи старых термов не коммитятся подсчётом.
«Нам нужен выбор лидера / конфигурация / блокировка — что возьмёте?» Здесь Raft как алгоритм реализовывать не нужно. Правильный ответ — взять готовую систему (etcd, Consul, ZooKeeper) и объяснить последствия: запись требует кворума, кластер из 3–5 узлов, при потере большинства записи останавливаются, ресурс защищается fencing-токеном. Если нужно масштабировать сами данные, а не метаданные, вспомните Multi-Raft из CockroachDB и TiKV и обсудите шардирование и репликацию.
Хороший сигнал для интервьюера — когда вы сами называете цену: задержка записи не меньше круга до ближайшего большинства. Если узлы в трёх регионах, каждая запись ждёт межрегиональную сеть. Отсюда решения вроде размещения лидеров ближе к пользователям или кворума внутри одного региона.