ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Пошаговый разбор Raft: terms, выбор лидера, AppendEntries, commitIndex, кворум из пяти серверов и реальные границы гарантий.
Raft решает задачу консенсуса для реплицированного журнала: несколько серверов должны применять одну последовательность команд и выглядеть для клиента как единая надёжная машина состояний. Алгоритм не устраняет сбои и разделения сети. Он определяет, при каких условиях система может продолжать работу и какие записи нельзя потерять или заменить другой командой.
Авторы Raft, Диего Онгаро и Джон Оустерхут, разделили алгоритм на выбор лидера, репликацию лога и правила безопасности. Такой разбор полезнее запоминания фразы «лидер пишет на большинство»: самые опасные ошибки находятся в уточнениях к этой фразе.
Сервер находится в одной из трёх ролей:
Время разбито на последовательно растущие terms. Каждый term начинается с выборов и может продолжиться работой одного лидера. Сервер, увидев сообщение с более высоким term, обновляет свой term и становится follower. В одном term сервер отдаёт не более одного голоса.
Для кластера из N серверов кворум равен floor(N / 2) + 1. Пять серверов требуют три голоса или три реплики, поэтому могут сохранять доступность при отказе любых двух серверов — если оставшиеся три способны общаться друг с другом и с клиентом.
Лидер периодически отправляет пустые AppendEntries — heartbeat. Если follower не получает допустимое сообщение до election timeout, он:
Одновременные кандидаты могут разделить голоса. Raft использует случайные election timeouts, чтобы следующая попытка с большей вероятностью началась у одного сервера раньше других. Интервал 150–300 мс в статье — пример для экспериментов авторов, а не универсальная настройка для любой сети.
Большинство предотвращает двух победителей в одном term: любые два большинства пересекаются хотя бы на одном сервере, а сервер не отдаёт два голоса в одном term.
Одного ограничения «голосовать один раз» недостаточно. Сервер со старым логом мог бы стать новым лидером и затереть уже зафиксированную команду. Поэтому voter сравнивает лог кандидата со своим. Сначала сравнивается term последней записи; если terms равны — индекс последней записи. Кандидат с менее актуальным логом голос не получает.
Это правило вместе с пересечением кворумов обеспечивает Leader Completeness: лидер нового term содержит записи, зафиксированные в предыдущих terms.
Пусть в кластере пять серверов S1–S5, а S1 — лидер term 8. Клиент отправляет команду SET theme dark.
| Шаг | S1 | S2 | S3 | S4 | S5 |
|---|---|---|---|---|---|
| 1. Лидер добавил запись | 8:SET | — | — | — | — |
| 2. Два follower подтвердили | 8:SET | 8:SET | 8:SET | — | — |
| 3. Есть большинство | commit | stored | stored | — | — |
| 4. Следующий heartbeat | commit | commit | commit | catch up | catch up |
Лидер вместе с S2 и S3 образует большинство. Он повышает commitIndex, применяет команду к своей машине состояний и сообщает новое значение commitIndex followers в последующих AppendEntries. Отстающие S4 и S5 догоняют позже.
Если S1 успел записать команду только себе и упал, запись не зафиксирована. Новый лидер вправе перезаписать конфликтующий хвост. Клиент не должен считать такую команду выполненной только по факту приёма TCP-запроса старым лидером.
Упрощённая функция показывает арифметику большинства:
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.
AppendEntries содержит индекс и term записи, непосредственно предшествующей новым. Follower отклоняет запрос, если такой пары в его логе нет. Лидер уменьшает nextIndex для этого follower и повторяет попытку, пока не найдёт общую границу.
Если по одному индексу находятся записи разных terms, follower удаляет конфликтующую запись и весь хвост после неё, затем добавляет записи лидера. Уже committed часть не должна попасть под такое удаление благодаря правилам выборов и полноты лидера.
Базовые свойства относятся к crash fault model: сервер может остановиться, позже восстановиться из устойчивого состояния, сообщения могут задерживаться, теряться, дублироваться и приходить не по порядку. Для безопасности журналов алгоритм не полагается на точные часы. Плохие тайминги могут лишить кластер прогресса, но не должны заставить две машины применить разные команды по одному индексу.
При этом Raft:
Клиент может не получить ответ после 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-система добавляет собственную модель хранения, сетевой протокол, наблюдаемость и операционные ограничения. Для реального сервиса разумнее выбрать зрелую реализацию и проверять её гарантии, чем переносить этот разбор в код построчно.
Raft становится понятным, когда разделены три вопроса: кто имеет право вести журнал, как followers согласуют его префикс и почему зафиксированную команду не сможет заменить будущий лидер.
Самостоятельный редакционный разбор ЯдроКода по статье Diego Ongaro и John Ousterhout и диссертации Diego Ongaro. Факты и идеи изложены редакцией самостоятельно; фрагменты исходного текста, код и иллюстрации не воспроизводятся.
Оригинальные диаграммы Raft не копируются. Перед публикацией используется собственная схема событий и проверяется терминология.