Raft: выбор лидера и репликация лога на понятном примере

Пошаговый разбор Raft: terms, выбор лидера, AppendEntries, commitIndex, кворум из пяти серверов и реальные границы гарантий.

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

Авторы Raft, Диего Онгаро и Джон Оустерхут, разделили алгоритм на выбор лидера, репликацию лога и правила безопасности. Такой разбор полезнее запоминания фразы «лидер пишет на большинство»: самые опасные ошибки находятся в уточнениях к этой фразе.

Роли, terms и большинство

Сервер находится в одной из трёх ролей:

• follower принимает сообщения лидера и отвечает кандидатам;
• candidate пытается выиграть выборы;
• leader принимает команды клиентов и реплицирует записи.

Время разбито на последовательно растущие terms. Каждый term начинается с выборов и может продолжиться работой одного лидера. Сервер, увидев сообщение с более высоким term, обновляет свой term и становится follower. В одном term сервер отдаёт не более одного голоса.

Для кластера из N серверов кворум равен floor(N / 2) + 1. Пять серверов требуют три голоса или три реплики, поэтому могут сохранять доступность при отказе любых двух серверов — если оставшиеся три способны общаться друг с другом и с клиентом.

Как проходит выбор лидера

Лидер периодически отправляет пустые AppendEntries — heartbeat. Если follower не получает допустимое сообщение до election timeout, он:

1. увеличивает текущий term;
2. становится candidate и голосует за себя;
3. рассылает RequestVote остальным серверам;
4. становится leader, получив большинство голосов в этом term.

Одновременные кандидаты могут разделить голоса. Raft использует случайные election timeouts, чтобы следующая попытка с большей вероятностью началась у одного сервера раньше других. Интервал 150–300 мс в статье — пример для экспериментов авторов, а не универсальная настройка для любой сети.

Большинство предотвращает двух победителей в одном term: любые два большинства пересекаются хотя бы на одном сервере, а сервер не отдаёт два голоса в одном term.

Почему голос зависит от состояния лога

Одного ограничения «голосовать один раз» недостаточно. Сервер со старым логом мог бы стать новым лидером и затереть уже зафиксированную команду. Поэтому voter сравнивает лог кандидата со своим. Сначала сравнивается term последней записи; если terms равны — индекс последней записи. Кандидат с менее актуальным логом голос не получает.

Это правило вместе с пересечением кворумов обеспечивает Leader Completeness: лидер нового term содержит записи, зафиксированные в предыдущих terms.

Репликация одной команды: пошаговый пример

Пусть в кластере пять серверов S1–S5, а S1 — лидер term 8. Клиент отправляет команду SET theme dark.

Лидер вместе с S2 и S3 образует большинство. Он повышает commitIndex, применяет команду к своей машине состояний и сообщает новое значение commitIndex followers в последующих AppendEntries. Отстающие S4 и S5 догоняют позже.

Если S1 успел записать команду только себе и упал, запись не зафиксирована. Новый лидер вправе перезаписать конфликтующий хвост. Клиент не должен считать такую команду выполненной только по факту приёма TCP-запроса старым лидером.

Проверка кворума — ещё не весь commit rule

Упрощённая функция показывает арифметику большинства:

def quorum(cluster_size: int) -> int:
    return cluster_size // 2 + 1


def has_majority(cluster_size: int, follower_acks: int) -> bool:
    replicas = 1 + follower_acks  # лидер уже хранит запись
    return replicas >= quorum(cluster_size)


print(has_majority(cluster_size=5, follower_acks=2))  # True
print(has_majority(cluster_size=5, follower_acks=1))  # False

Но production-реализация обязана учитывать term записи. Raft-лидер напрямую продвигает commitIndex по большинству только для записи из своего текущего term. Когда такая запись зафиксирована, предыдущие записи также становятся зафиксированными косвенно. В статье приведён контрпример, где старая запись уже находится на большинстве машин, но всё ещё может быть перезаписана до фиксации записи текущего term.

Как follower исправляет расходящийся хвост

AppendEntries содержит индекс и term записи, непосредственно предшествующей новым. Follower отклоняет запрос, если такой пары в его логе нет. Лидер уменьшает nextIndex для этого follower и повторяет попытку, пока не найдёт общую границу.

Если по одному индексу находятся записи разных terms, follower удаляет конфликтующую запись и весь хвост после неё, затем добавляет записи лидера. Уже committed часть не должна попасть под такое удаление благодаря правилам выборов и полноты лидера.

Что именно гарантирует Raft

Базовые свойства относятся к crash fault model: сервер может остановиться, позже восстановиться из устойчивого состояния, сообщения могут задерживаться, теряться, дублироваться и приходить не по порядку. Для безопасности журналов алгоритм не полагается на точные часы. Плохие тайминги могут лишить кластер прогресса, но не должны заставить две машины применить разные команды по одному индексу.

При этом Raft:

• не защищает от Byzantine-поведения, когда узел лжёт или отправляет разным соседям противоречивые сообщения;
• не сохраняет доступность на стороне разделения сети без большинства;
• не делает прикладную команду идемпотентной;
• не превращает любой способ чтения в линейризуемый автоматически;
• не освобождает реализацию от устойчивой записи currentTerm, votedFor и журнала перед ответом на RPC.

Клиентские повторы и дедупликация

Клиент может не получить ответ после commit: лидер применил команду, но соединение оборвалось. Повтор той же операции без идентификатора способен дважды увеличить счётчик или создать два заказа. В диссертации Raft взаимодействие с клиентом рассматривается отдельно от базовой репликации лога.

Практический протокол добавляет стабильный clientId и монотонный sequenceNumber. Машина состояний хранит последний обработанный номер и ответ для клиента. Повтор команды тогда возвращает прежний результат, а не выполняет побочный эффект снова.

Изменение состава — отдельный протокол

Нельзя безопасно заменить конфигурацию {S1, S2, S3} на {S3, S4, S5} независимым обновлением каждого узла: на переходе могут существовать два непересекающихся большинства. Работа Raft описывает joint consensus с перекрывающимися кворумами старой и новой конфигураций; диссертация дополнительно развивает более простой подход одиночных изменений. Для исходного текста этого подхода автор позднее опубликовал errata с исправлением, поэтому его также нельзя переносить в реализацию без проверки актуальной спецификации.

Это важная граница учебного примера: выборы и AppendEntries ещё не составляют готовую библиотеку консенсуса. Нужны snapshotting, восстановление, membership changes, client sessions, корректные reads и тестирование всех переходов состояний.

Ограничения исходной оценки

Цель авторов была не только производительность, но и понятность. В пользовательском исследовании участвовали 43 студента двух университетов; после обучения обоим алгоритмам 33 лучше ответили на вопросы о Raft, чем о Paxos. Это свидетельство в пользу конкретного учебного дизайна, но не универсальное доказательство, что любой инженер реализует Raft без ошибок.

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

Что проверить у готовой реализации

1. Какая модель отказов поддерживается и что именно записывается синхронно на диск?
2. Как реализованы линейризуемые чтения и защита от устаревшего лидера?
3. Как дедуплицируются повторные запросы клиентов?
4. Как выполняются snapshots, восстановление и изменение состава кластера?
5. Какие метрики показывают term, leader changes, commitIndex, lag и потерю кворума?

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