Meerkat, сервис консенсуса Cloudflare на базе QuePaxa

Подразделение Cloudflare Research целый год разрабатывало Meerkat - сервис консенсуса для данных control plane, распределённых по более чем 330 дата-центрам. Причина создания вполне конкретна: компания пережила несколько инцидентов из-за недоступности лидеров в Raft, а сильные колебания задержек в глобальных сетях (WAN) делают таймауты, от которых зависит Raft, практически ненастраиваемыми. Вместо него Meerkat использует QuePaxa - алгоритм 2023 года за авторством Tennage, Băsescu et al., в котором нет обязательного лидера и который никогда не блокируется в ожидании таймаута. Cloudflare заявляет, что это будет первое промышленное развёртывание QuePaxa в глобальном масштабе.

Хранимые данные невелики по объёму и перезаписываются редко: например, где запущен экземпляр модели ИИ или какая машина сейчас держит лидерство на запись в реплицированной базе данных. Это не база данных общего назначения, и превращать её в таковую никто не планирует.

Что требуется

В первую очередь - линеаризуемость. Не потому, что это самый строгий пункт в меню, а потому, что любая более слабая модель заставляет автора каждого сервиса анализировать, к каким перестановкам операций готов его код. Линеаризуемое чтение позволяет разработчикам думать о кластере так же просто, как о локальной памяти в рамках одного потока.

Во вторую очередь - отказоустойчивость особого рода. Система остаётся доступной для чтения и записи от клиента в любом дата-центре до тех пор, пока живо и связано между собой большинство машин (f сбоев из 2f + 1), а клиент может связаться с любой машиной, подключённой к этому большинству. Отказ одной машины или деградация одного сетевого соединения не должны влиять на доступность где бы то ни было ещё. Системы на базе Raft такого не дают. Как и Raft, Meerkat не защищает от византийских сбоев - корректность опирается на предположение, что ни один участник не действует злонамеренно.

Журнал

Разработчик запрашивает кластер реплик, при необходимости задавая ограничения по дата-центрам, и Meerkat размещает их. Каждая реплика соединяется со всеми остальными и принимает как операции чтения, так и записи. Клиент отправляет запрос приложения на любую реплику по своему выбору.

Реплика превращает этот запрос в событие журнала и запускает консенсус, чтобы занять им следующий слот. Ядро Meerkat не интерпретирует события - этим занимаются работающие поверх каждой реплики приложения. Так, приложение key-value хранилища просто воспроизводит журнал в map в оперативной памяти. Корректность опирается на инвариант: две реплики ни при каких обстоятельствах не могут принять разные значения для одного и того же слота. Реплика может отставать и считать, что последний слот ещё пуст, хотя это не так, но записать что-то другое она не сможет никогда.

Чтение тоже проходит через журнал, и объяснение этого механизма - самая наглядная часть статьи. Реплика Z фиксирует решение put k1 v11 в слоте 3 благодаря большинству, в которое не входила реплика Y. Затем клиент отправляет запрос get k1 на реплику Y. Реплика Y считает слот 3 свободным и предлагает записать туда операцию чтения. Большинство отвергает это предложение, поскольку решение по слоту 3 уже принято. Реплику Y заставляют узнать, что в слоте 3 записано put k1 v11, и заново предложить операцию чтения уже для слота 4. Тем самым чтение линеаризуется строго после записи, результаты которой оно обязано увидеть. Если Y не может связаться с большинством, чтение завершается ошибкой, а не возвращает устаревшие данные.

Почему не Raft

Полномочный лидер в Raft - единственная реплика, которой разрешено вести консенсус. Это упрощает понимание и обеспечивает линеаризуемое чтение с лидера при помощи lease-механизма. Но это же создаёт единую точку временного отказа. Если лидер умирает, запись блокируется до завершения выборов. Если он просто начинает тормозить - из-за перегрузки или плохого канала, - вместе с ним тормозит вся система, поскольку альтернативного пути для записи нет.

Глобальные сети лишь усугубляют проблему выборов. Обнаружение сбоев завязано на таймаут: если таймаут меньше реальной сетевой задержки, реплики будут постоянно инициировать выборы без причины, блокируя запись. Если таймаут больше - реакция на реальную смерть лидера окажется слишком долгой, и всё это время запись опять же будет заблокирована. Одновременные заявки кандидатов мешают друг другу: предвыборные кампании сталкиваются, реплики голосуют за себя заново, и запись простаивает на протяжении всего процесса. Cloudflare утверждает, что они сталкивались ровно с такими сбоями в продакшене.

Отличия QuePaxa, если суммировать материал статьи: любая реплика может вести консенсус для текущего слота, поэтому состояние одной машины не ставит под угрозу доступность всей системы. Лидер есть, но исключительно как оптимизация: с лидером решение принимается за один round trip, без него реплике требуется три или больше. Параллельные предложения от разных реплик влияют друг на друга конструктивно: реплики кооперируются, чтобы согласовать одно из предложенных значений, а не сбивают друг друга с ног. Это означает, что клиент может обращаться сразу к нескольким репликам для повышения шансов на успех. Наконец, алгоритм изначально проектировался в расчёте на асинхронность и сценарии, когда нарушитель точечно деградирует каналы между репликами. В этих условиях авторы зафиксировали пропускную способность примерно в 10 раз выше, чем у Raft и Multi-Paxos.

Цена решения

Накладные расходы на round trip'ы, обойти которые невозможно. Один round trip, если предлагает лидер, три - если не-лидер, плюс широковещательная рассылка для объявления решения, и ещё больше - при коллизиях предложений. Задержка принятия решения ограничена снизу сетевой задержкой до некоторого большинства реплик, поэтому реплики, разбросанные по всей планете, медлительны просто по своей природе.

Сгладить это помогают четыре меры, хотя фундаментального предела они не меняют. Разработчики контролируют размещение реплик, поэтому кластеры, не требующие глобального охвата, можно размещать ближе друг к другу. Близкие по времени операции записи объединяются в пакеты (batching) в рамках одного предложения. Чтения, допускающие чтение слегка устаревших (но ни в коем случае не противоречивых) данных, могут обслуживаться из локального состояния любой реплики без раунда консенсуса. Наконец, в один раунд можно упаковывать сразу несколько операций, включая compare-and-swap записи и транзакции общего вида.

Отсюда и границы применимости: редко обновляемые, критически важные данные control plane, для которых несколько межрегиональных round trip'ов на операцию записи - вполне приемлемая цена.

Текущий статус

Ещё не в продакшене. Прототипы (PoC) тестировались на масштабе до 50 реплик по всему миру, и главный результат: лидеры в таких кластерах постоянно падали без малейшего роста доли ошибок. В этом и была цель, ведь в Raft каждое такое падение приводило бы к простою. В будущих публикациях обещаны подробности внутреннего устройства QuePaxa, формальная верификация частей реализации на Rust, инициализация и управление кластером, оптимальное размещение реплик и детерминированное имитационное тестирование. Готовится статья для рецензируемого научного издания.

Связанные страницы

distributed-consensus - обзор Paxos, Raft и пространства компромиссов, где Meerkat занимает свой угол; flp-impossibility - о том, почему обнаружение сбоев по таймаутам является предположением о синхронности, а не просто деталью реализации (QuePaxa не утверждает, что обходит FLP, но не превращает асинхронность в потерю доступности). lee-holloway, сооснователь и первый ведущий инженер Cloudflare, разработал самый первый прототип компании.