Алгоритм консенсуса Raft: как кластер выбирает лидера

В распределённой системе несколько серверов хранят копию одних и тех же данных, и при отказе любого из них кластер должен продолжать работать так, будто ничего не случилось. Чтобы все узлы согласовали единый порядок операций, нужен алгоритм консенсуса. Raft - это алгоритм консенсуса, который придумали Диего Онгаро и Джон Остерхаут в 2014 году специально как понятную замену сложному Paxos. Его сила в том, что задача распадается на три почти независимые части: выбор лидера, репликацию журнала и обеспечение безопасности. Ниже разберём, как это работает, что происходит при отказах и чем Raft отличается от предшественников. Если нужно разобрать конкретную задачу по Raft - сформулируйте её в инструменте ниже.

Зачем нужен консенсус

Представьте реплицированную базу данных из пяти серверов. Клиент шлёт команду «записать x = 5». Если каждый сервер применит свои команды в своём порядке, копии разъедутся, и система перестанет быть единым целым. Задача консенсуса - добиться, чтобы все исправные узлы согласовали один и тот же порядок команд, даже если часть серверов падает, а сеть теряет и задерживает сообщения.

Формально набор узлов хранит реплицированный журнал (replicated log) - упорядоченную последовательность команд. Если журналы всех узлов одинаковы, то и конечный автомат, применяющий эти команды, придёт в одно и то же состояние. Поверх такого согласованного журнала строят надёжные хранилища с ACID-свойствами транзакций. Raft гарантирует, что журналы сходятся, пока работает большинство узлов.

Ключевое условие живучести - кворум большинства: из $N$ узлов любое решение требует согласия хотя бы $\lfloor N/2 \rfloor + 1$ из них. Поэтому кластер из пяти серверов переживает отказ двух, а из трёх - отказ одного.

Три роли узла

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

• Последователь (follower) - пассивная роль по умолчанию. Узел только отвечает на запросы лидера и кандидатов, сам инициативы не проявляет.
• Кандидат (candidate) - переходное состояние: узел заметил, что лидера нет, и пытается им стать, собирая голоса.
• Лидер (leader) - единственный активный узел. Он принимает все команды клиентов, рассылает их последователям и поддерживает порядок в журнале.

В нормальном режиме в кластере ровно один лидер, а все остальные - последователи. Клиенты общаются только с лидером; если клиент случайно обратился к последователю, тот перенаправляет его к текущему лидеру.

Рассчитать для своей задачи

Сроки: логическое время кластера

Raft делит время на сроки (terms) - последовательно нумерованные периоды произвольной длины. Каждый срок начинается с выборов и продолжается, пока у власти стоит один лидер. Номер срока - это монотонно растущий счётчик, по сути логические часы кластера.

Каждый узел хранит свой currentTerm. В любом сообщении узлы обмениваются номерами сроков, и работает простое правило:

$$\text{если } term_{\text{входящий}} > currentTerm,\ \text{то } currentTerm \leftarrow term_{\text{входящий}}$$

Узел, который видит срок больше своего, немедленно становится последователем и подчиняется. А узел, получивший сообщение с устаревшим сроком, отвергает его. Так срок служит детектором устаревших лидеров: «отколовшийся» старый лидер с меньшим номером срока автоматически теряет полномочия, как только встречает узел из нового срока.

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

Лидер периодически шлёт всем последователям heartbeat - пустые сообщения, подтверждающие, что он жив. Каждый последователь держит случайный таймаут выборов (election timeout), обычно 150–300 мс. Если за это время heartbeat не пришёл, последователь решает, что лидер пропал, и начинает выборы:

1. Увеличивает свой currentTerm на единицу.
2. Переходит в состояние кандидата и голосует за себя.
3. Рассылает остальным запрос голоса (RequestVote).

Каждый узел в одном сроке отдаёт голос только одному кандидату - по принципу «первый пришёл - первого обслужил». Кандидат, набравший голоса большинства, становится лидером и сразу начинает рассылать heartbeat, подавляя новые выборы.

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

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

Получив команду от клиента, лидер дописывает её в свой журнал новой записью и параллельно рассылает последователям запрос AppendEntries с этой записью. Каждая запись журнала содержит команду, индекс (позицию) и номер срока, в котором она создана.

Запись считается зафиксированной (committed), когда лидер реплицировал её на большинство узлов. Только после фиксации лидер применяет команду к своему конечному автомату и отвечает клиенту. Зафиксированная запись гарантированно не пропадёт: раз она лежит на большинстве, любой будущий лидер обязан её содержать.

Рассчитать для своей задачи

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

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

Чтобы выборы не привели к потере зафиксированных данных, Raft накладывает ограничение на голосование: узел отдаёт голос кандидату только если журнал кандидата не менее актуален, чем его собственный. Актуальность сравнивается по паре «срок последней записи, затем её индекс».

Это гарантирует, что новым лидером может стать только узел с самым полным журналом - то есть содержащий все ранее зафиксированные записи. Лидер в Raft никогда не перезаписывает и не удаляет свои записи, он только дополняет журнал (свойство Leader Append-Only). Вместе эти правила дают центральную гарантию: если запись зафиксирована в некотором сроке, она присутствует в журналах всех лидеров последующих сроков.

Изменение состава кластера

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

Raft решает это через совместный консенсус (joint consensus): вводится промежуточная конфигурация $C_{old,new}$, в которой решение требует большинства одновременно и в старом, и в новом составе. Сначала кластер переходит в $C_{old,new}$, затем - в чистую новую конфигурацию $C_{new}$. На каждом шаге не существует момента, когда два непересекающихся большинства могли бы принять конфликтующие решения.

Сжатие журнала через снимки

Журнал нельзя растить бесконечно - он съест диск. Raft применяет снимки (snapshots): узел сериализует текущее состояние конечного автомата в один снимок и отбрасывает все записи журнала до точки снимка. В снимке сохраняются индекс и срок последней включённой записи, чтобы согласованность не нарушилась.

Снимки делает каждый узел независимо. Если отставший последователь нуждается в записях, которые лидер уже отбросил, лидер шлёт ему весь снимок целиком запросом InstallSnapshot, а дальше догоняет обычной репликацией.

Raft против Paxos

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

• Сильный лидер. В Raft записи журнала текут только в одну сторону - от лидера к последователям. Это упрощает рассуждение по сравнению с симметричным Paxos, где любой узел может предлагать значения.
• Декомпозиция. Raft явно разбивает задачу на выборы лидера, репликацию журнала и безопасность, тогда как «голый» Paxos описывает согласование одного значения, а из него ещё нужно собрать Multi-Paxos для журнала.

По гарантиям корректности и отказоустойчивости (переживает отказ меньшинства узлов) Raft и Paxos эквивалентны. Поэтому на практике Raft вытеснил Paxos в новых системах: на нём построены etcd (хранилище конфигурации Kubernetes), Consul, TiKV и многие другие.

Частые ошибки

• Путают консенсус с синхронизацией часов. Raft не согласует физическое время; срок (term) - это логический счётчик, а не временная метка. Реальные таймауты нужны только чтобы заметить пропажу лидера.
• Считают, что нужен голос всех узлов. Достаточно большинства. Поэтому кластер из пяти узлов работает при двух отказавших - требовать единогласия значило бы остановиться при первом же сбое.
• Думают, что запись применяется сразу при дописывании. Нет: лидер применяет команду к автомату и отвечает клиенту только после фиксации записи на большинстве.
• Делают чётное число узлов. Кластер из четырёх переживает тот же один отказ, что и из трёх, но требует большего кворума. Берут нечётное число (3, 5, 7) - это оптимум по отказоустойчивости.
• Забывают про случайность таймаута. С фиксированным таймаутом выборов узлы хронически раскалывают голоса и кластер подолгу остаётся без лидера.

FAQ

Сколько отказов переживает Raft? Кластер из $N$ узлов сохраняет работоспособность, пока живо большинство, то есть переживает отказ до $\lfloor N/2 \rfloor$ узлов. Для трёх узлов это один отказ, для пяти - два, для семи - три. Отсюда правило нечётного размера кластера.

Что произойдёт, если лидер внезапно отключится? Последователи перестанут получать heartbeat, у одного из них истечёт случайный таймаут выборов, он станет кандидатом и инициирует новый срок. Набрав большинство голосов, он станет новым лидером. Зафиксированные записи при этом не теряются - ограничение на голос гарантирует, что лидером станет узел с полным журналом.

Чем Raft отличается от Paxos на практике? Гарантии у них одинаковые, разница в инженерной ясности. Raft проще понять и корректно реализовать благодаря сильному лидеру и явной декомпозиции, поэтому большинство современных систем (etcd, Consul) выбирают именно его.

Коротко

Raft - алгоритм консенсуса для реплицированных журналов, спроектированный ради понятности. Узел бывает последователем, кандидатом или лидером; время разбито на сроки с монотонным номером. При пропаже heartbeat случайный таймаут запускает выборы, и кандидат, собравший большинство голосов, становится лидером. Лидер тиражирует команды последователям; запись фиксируется и применяется только после репликации на большинство. Ограничение на голос (лидером становится узел с самым актуальным журналом) и принцип «лидер только дополняет журнал» обеспечивают сохранность зафиксированных данных. Смена состава идёт через совместный консенсус, рост журнала гасится снимками. По гарантиям Raft эквивалентен Paxos, но проще в понимании и реализации, поэтому лежит в основе etcd, Consul и TiKV.