SYS Системы и большие данные Алгоритм
Raft
Также: Raft consensus · алгоритм Raft · консенсус · реплицированный журнал · replicated log · выборы лидера · leader election · кворум · consensus algorithm
Пять серверов держат один и тот же журнал записей, хотя любой из них может упасть, а сеть — разделиться. Raft выбирает лидера со случайными тайм-аутами, копирует журнал от лидера к остальным и считает запись принятой, когда она у большинства. Вся тонкость — в двух правилах: за кого можно голосовать и какие записи лидер вправе объявить зафиксированными.
Ниже пять серверов, которые хранят один и тот же журнал. Клиент каждые 20 мс присылает запись — правки файлов из истории этого сайта, — а серверы должны согласиться, в каком порядке эти записи идут, и не потерять ни одной принятой, даже если кто-то упадёт. Время замедлено в двадцать раз. Подождите, пока выберется лидер, а потом уроните его нажатием или разделите сеть и посмотрите, что будет.
Лидер рассылает записи остальным; черта под журналом — граница того, что уже зафиксировано, то есть есть у большинства и не пропадёт. Уроните лидера: остальные перестанут получать от него сообщения, через 150–300 мс у кого-то кончится тайм-аут, он объявит новый срок и соберёт голоса. Разделите сеть: лидер окажется в меньшей части. Он ещё считает себя лидером и даже принимает записи, но зафиксировать их не может — большинство его не слышит. В большей части тем временем выберут нового лидера. Когда сеть соединится, старый увидит срок новее своего, уступит, а его незафиксированные записи будут стёрты.
Идея
Серверы хранят журнал — последовательность записей, — и всё, что важно, должно оказаться в журнале каждого в одном и том же порядке. Писать в журнал может только лидер; остальные копируют записи у него. Время делится на сроки с номерами, в каждом не больше одного лидера. Лидера выбирают большинством голосов, и запись считается зафиксированной, когда её копия есть у большинства. Любые два большинства пересекаются, и это пересечение переносит знание из срока в срок: новый лидер обязательно получит голос сервера, который видел все зафиксированные записи.
Зачем журнал? Если серверы применяют одни и те же записи в одном и том же порядке к одинаковым начальным состояниям, они приходят к одному и тому же состоянию: так из журнала получается надёжная база ключ-значение, очередь или реестр настроек. Задача согласиться хотя бы об одном значении — консенсус; почему её трудно решить, как её решает Паксос и откуда взялась идея лидера, рассказывает глава курса о распределённых системах. Здесь — как Raft поддерживает целый журнал и почему он не теряет принятое.
У серверов всего два вида запросов. RequestVote: «я кандидат срока t, моя последняя запись — номер i срока s, проголосуй за меня». AppendEntries: «я лидер срока t; перед новыми записями у меня запись номер p срока q; вот записи; зафиксировано до номера c». Пустой AppendEntries — сердцебиение: «я жив, я лидер». Любое сообщение со сроком новее своего заставляет сервер признать новый срок и стать последователем.
Выборы
Последователь ждёт сообщений от лидера. Если их долго нет — дольше его тайм-аута, — он увеличивает номер срока, голосует за себя и рассылает RequestVote. Каждый сервер в каждом сроке голосует не больше одного раза, поэтому двух лидеров одного срока не бывает: оба собрали бы больше половины голосов, а половины не пересекаются только в пустом множестве. Тайм-аут у каждого сервера свой и случайный, в статье для примера — от 150 до 300 мс. Если бы тайм-ауты совпадали, кандидаты выдвигались бы одновременно, делили голоса, никто бы не набирал большинства, и всё повторялось бы — та же беда, что у повторов без джиттера. Со случайными тайм-аутами первым почти всегда просыпается кто-то один и успевает собрать голоса, пока остальные спят.
Голос дают не всякому. Сервер голосует за кандидата, только если журнал кандидата не отстаёт от его собственного: срок последней записи у кандидата больше или такой же, а журнал не короче. Это правило выборов — одно из двух, на которых держится безопасность Raft, и вторая задача статьи о нём.
Репликация журнала
Лидер дописывает новую запись в свой журнал с номером своего срока и отправляет последователям. Каждый AppendEntries несёт номер и срок записи, которая стоит перед новыми. Последователь принимает новые записи, только если у него на этом месте та же запись — тот же срок. Иначе он отказывает, и лидер отступает на шаг назад и пробует снова, пока не найдёт место, где журналы совпадают. С этого места последователь стирает свой хвост и принимает хвост лидера.
Если у двух серверов записи с одним номером имеют один и тот же срок, то в этих записях одна и та же команда, и все записи перед ними у двух серверов тоже совпадают.
Первая часть: в каждом сроке один лидер, и он создаёт в данной позиции не больше одной записи, а записи из журнала не переезжают на другие места. Вторая — индукцией по номеру записи. Запись попадает к последователю только вместе с проверкой: на предыдущем месте у последователя стоит запись того же срока, что у лидера. По предположению индукции из совпадения на предыдущем месте следует совпадение всего, что раньше. Значит, когда запись i легла к последователю, весь журнал до неё у него совпал с журналом лидера, — и так у каждого, кто получил эту запись.
Поэтому журналу достаточно проверять один предыдущий шаг: совпадение на месте p гарантирует совпадение всего начала. В листинге лидер отступает на одну запись за раз; если последователь долго лежал, а записей много, это сотни лишних кругов. Уже в статье о Raft упомянуто ускорение: последователь в отказе сообщает срок конфликтующей записи и первый номер, где у него этот срок начинается, и лидер перепрыгивает весь срок за один круг.
Что зафиксировано
Лидер знает, сколько записей подтвердил каждый последователь. Казалось бы, запись зафиксирована, как только её копии у большинства. Это неверно, и вторая сцена показывает почему — шаг за шагом, по рисунку 8 из статьи о Raft.
Запись старого срока у большинства ещё может пропасть. Сервер, у которого последняя запись — более позднего срока, выиграет выборы голосами тех, у кого эта старая запись лежит последней: его журнал новее по сроку. А став лидером, он заставит их журналы совпасть со своим. Поэтому правило фиксации в Raft такое: лидер объявляет зафиксированной только запись своего текущего срока, когда она у большинства, — и вместе с ней всё, что перед ней. Старые записи фиксируются «под прикрытием» новой.
Если запись зафиксирована в каком-то сроке, она есть в журнале лидера каждого следующего срока.
Пусть запись e зафиксировал лидер срока t: у большинства A есть и e, и запись срока t не раньше неё. Пусть u — первый следующий срок, лидер которого e не имеет. Его выбрало большинство B; A и B пересекаются, и общий сервер v получил e раньше, чем проголосовал в сроке u, — иначе, узнав срок u, он отказал бы лидеру срока t. Лидеры между t и u имели e и стереть её у v не могли. Значит, когда v голосовал, срок его последней записи был не меньше t, а журнал кандидата не отстаёт от его журнала.
Если срок последней записи кандидата больше, чем у v, он больше t, и эту запись создал лидер одного из сроков между t и u. У того лидера e была, и по совпадению журналов она есть и у кандидата. Если сроки равны, журнал кандидата не короче журнала v, и по совпадению журналов в нём есть всё, что есть у v, включая e. В обоих случаях получилось противоречие.
Из полноты лидера и совпадения журналов следует главное: если сервер применил к своему состоянию запись номер i, ни один сервер никогда не применит под этим номером другую запись. Это и проверяет листинг в конце: зафиксированные части журналов всех пяти серверов — начала одного и того же журнала. Первая задача — правило фиксации в чистом виде.
Код
Листинг — та же модель, что в первой сцене: случайные задержки сообщений и тайм-ауты, общий для Python и Go генератор, поэтому события совпадают до миллисекунды. Сценарий — 6 секунд: в 1,5 с падает лидер, в 3 с он поднимается, в 4 с сеть разделяется так, что лидер с одним соседом оказывается в меньшей части, в 5 с сеть соединяется.
Первые выборы прошли за 177 мс: лидером стал S5, у которого раньше всех кончился тайм-аут. После падения лидера в 1500 мс новый выбран за 154 мс, после разделения сети — за 202 мс. Из 284 записей клиента 16 пропали: их принял лидер, который упал, не успев разослать, или лидер, отрезанный от большинства. Клиент не получил на них подтверждения и должен повторить — Raft обещает сохранность только зафиксированного. Остальные 268 записей лежат в журнале последнего лидера, 266 из них уже зафиксированы, две ещё в пути.
Сколько это стоит
Кластер из n серверов работает, пока живо и связано большинство: пять серверов выдерживают падение двух, три — одного. Поэтому кластеры делают из нечётного числа машин: четыре сервера выдерживают тоже одно падение, а стоят дороже. Запись стоит одного круга сообщений от лидера до большинства и обратно и n − 1 сообщений, если не собирать записи в пачки; на деле их собирают, как в листинге — по 50 за раз. Выборы занимают тайм-аут плюс круг сообщений: в модели — от 154 до 202 мс. Пока нет лидера, кластер ничего не принимает.
Чтение тоже требует осторожности. Лидер, отрезанный от большинства, ещё считает себя лидером и мог бы ответить устаревшими данными. Поэтому для чтения без сюрпризов лидер либо проводит его через журнал, либо перед ответом убеждается сердцебиением, что большинство его ещё слышит.
Что ещё нужно в жизни
- Снимки. Журнал растёт бесконечно. Серверы время от времени записывают снимок состояния и выбрасывают начало журнала; отставшему последователю лидер присылает снимок целиком.
- Смена состава. Добавить или убрать сервер нельзя «всем сразу»: в момент перехода могут найтись два большинства — по старому составу и по новому. Raft меняет состав либо по одному серверу за раз, либо через промежуточную конфигурацию, где решение требует большинства и старого, и нового состава.
- Предварительное голосование. Сервер, отрезанный от остальных, раз за разом увеличивает срок; когда сеть соединится, его большой срок сбросит работающего лидера. Поэтому перед настоящими выборами кандидат спрашивает, отдали бы ему голоса, и не трогает срок, если нет.
Всё это описано в диссертации Диего Онгаро и есть в зрелых реализациях. Сам алгоритм в статье умещается в одну страницу правил, но реализация, которая переживает настоящие сети и диски, — это тысячи строк и тесты, которые роняют серверы и рвут сеть в случайные моменты.
Где работает
Хранилища настроек. etcd — хранилище, в котором Kubernetes держит состояние кластера, и Consul, реестр сервисов, — оба реплицированные журналы на Raft.
Базы данных. CockroachDB и TiKV делят ключи на диапазоны, и у каждого диапазона своя маленькая группа Raft из трёх-пяти копий: так согласие масштабируется на тысячи машин.
Очереди. Apache Kafka заменила ZooKeeper собственным служебным кворумом KRaft на основе Raft: в нём лежат сведения о темах, разделах и брокерах.
История
Алгоритм консенсуса для журнала существовал задолго до Raft — Паксос Лесли Лэмпорта, — но его считали трудным и для понимания, и для реализации; историю о парламенте острова Паксос рассказывает глава курса. Диего Онгаро и Джон Остераут поставили целью понятность: выделили лидера как главный механизм, разбили задачу на выборы, репликацию и безопасность и сузили пространство состояний. Статья «In Search of an Understandable Consensus Algorithm» вышла в 2014 году, а подробности — смена состава, снимки, чтение — в диссертации Онгаро того же года.
Задачи
Что зафиксировано Кто может стать лидеромДанные: История правок файлов legost.in (git, до 16.10.2026)