Cloudflare строит глобальный консенсус на QuePaxa вместо Raft и Paxos
Инженеры Cloudflare разобрали, почему Raft плохо переносит интернет-задержки и чем его заменили в сервисе Meerkat.
Cloudflare 11 ноября рассказала, почему её экспериментальный сервис распределённого консенсуса Meerkat работает на алгоритме QuePaxa вместо привычных Raft, Multi-Paxos или Viewstamped Replication. QuePaxa опубликован исследователями в 2023 году и почти не встречается в продакшене. Его главное свойство: чтобы принимать решения, кластеру не нужны ни живой лидер, ни детектор сбоев с таймаутами.
Разбор пригодится всем, кто эксплуатирует etcd, Consul, ZooKeeper или собственный сервис на Raft в нескольких регионах. Инженеры Cloudflare по шагам показывают, как короткий сетевой сбой превращается у алгоритмов с лидером в долгий простой, и описывают устройство альтернативы настолько подробно, что его можно пересказать коллегам у доски.
Ключевые выводы
- Meerkat хранит упорядоченный журнал событий для внутренней глобальной control plane Cloudflare; поверх журнала работает, например, key-value хранилище.
- Претензия к Raft и Paxos: при задержках и обрывах связи они останавливаются на время выборов лидера, а таймаут выборов привязан к задержке сети.
- В QuePaxa лидер необязателен: предлагать значение может любая реплика, а конкурирующие предложения сходятся к одному по случайным приоритетам.
- По оценкам Cloudflare, больше 95% решений принимает лидер за один сетевой обмен; в остальных случаях пропускная способность кратковременно падает максимум до трети.
- Алгоритм мало проверен практикой, поэтому реализацию на Rust формально верифицируют.
Что такое Meerkat и почему ему не подошёл Raft?
Cloudflare представила Meerkat в июле 2026 года. Это система, в которой реплики согласуют упорядоченный журнал событий; каждое событие проходит через алгоритм консенсуса, поэтому журналы реплик не расходятся. Поверх журнала работают приложения вроде key-value хранилища, где запись в журнале означает get или put. Ближайшие аналоги авторы называют сами: Consul, etcd и Apache ZooKeeper.
Отличие в масштабе. Кластер Meerkat может быть разнесён по континентам и связан каналами с высокой и нестабильной задержкой, а привычные системы консенсуса рассчитаны на компактные сети со строгими требованиями к задержке. В качестве примера Cloudflare приводит собственный инцидент 2020 года: из-за частичного отказа сетевого коммутатора система на консенсусе деградировала и на время перестала принимать запись, а панель управления, по словам авторов, шесть часов работала до 80 раз медленнее обычного. Данные при этом не потерялись.
Где ломаются алгоритмы с лидером?
Авторы выделяют два механизма. Первый они называют деструктивной интерференцией. В классическом Paxos два участника, предлагающие значения одновременно, могут бесконечно перебивать друг друга более высокими номерами голосований. Raft, Multi-Paxos и Viewstamped Replication обходят это, назначая лидера: предлагает только он, и решение принимается за один сетевой обмен. Цена в том, что лидер должен быть жив и доступен.
Когда лидер пропадает, начинаются выборы, и та же интерференция возвращается: несколько кандидатов Raft могут одновременно собирать голоса и мешать друг другу набрать большинство. Получается метастабильный отказ, который поддерживает сам себя после исчезновения причины. Двухсекундный сбой сети заставляет лидера выглядеть упавшим, запускает выборы, они проваливаются и запускают следующие.
Второй механизм связан с обнаружением сбоев. В асинхронной сети нельзя отличить упавший сервер от медленного канала, детектор всегда гадает по таймауту и иногда ошибается, а каждая ошибка останавливает систему на выборы. Занизить таймаут тоже нельзя: он обязан превышать задержку сети. Raft обычно разворачивают с таймаутом выборов в 5–10 раз больше времени обмена, пишут авторы; документация etcd, на которую они ссылаются, советует не меньше 10. Обмен через полмира занимает сотни миллисекунд, так что даже безошибочное обнаружение упавшего лидера отнимает около секунды, и всё это время кластер стоит.
Как QuePaxa обходится без выборов и детектора сбоев?
QuePaxa описали в 2023 году Теннадж, Бэсеску и соавторы. В нём, как в Paxos, две роли: proposers предлагают значения, recorders записывают всё, что видели, и служат посредниками. Отличие в том, что предлагающие сотрудничают. Каждому предложению назначается случайный приоритет; получив от recorder предложение с приоритетом выше своего, proposer перенимает его и дальше рассылает уже это значение. Заблокировать друг друга навсегда участники не могут: все движутся к самому приоритетному из известных предложений.
Лидер в схеме есть, но он необязателен. В первом раунде его предложение получает максимальный приоритет, и только он может принять решение за один обмен. Если лидер недоступен, клиенты продолжают отправлять запросы другим репликам, и система работает без него.
Чтобы пользоваться быстрым путём и не зависеть от лидера, клиент страхуется (hedging): запрос уходит всем репликам, а остальные ждут небольшой таймаут, давая лидеру шанс принять решение в одиночку. В своей реализации Cloudflare отступила от статьи: таймаут выжидают клиенты вместо реплик, чтобы слать меньше сообщений. Принципиально то, что этот таймаут не служит детектором сбоев и не привязан к задержке сети. Таймаут в 5 мс при задержке сети 100 мс заморозил бы Raft, а в QuePaxa он лишь увеличивает число активных предлагающих. Плата за маленький таймаут: больше трафика и выше шанс, что раунд не завершится решением.
Раунд QuePaxa состоит из четырёх фаз, в каждой предлагающий рассылает текущее предложение всем recorders и ждёт ответа большинства:
- Фаза 0, предложить и перенять. Участники выбирают случайный приоритет и перенимают самое приоритетное предложение, полученное от большинства. Если это первый раунд и лидер знает, что его предложение дошло до большинства первым, он принимает решение сразу.
- Фаза 1, распространить. Перенятое предложение рассылается большинству recorders, которые запоминают самое приоритетное из увиденных.
- Фаза 2, проверить и решить. Участник спрашивает у большинства самое приоритетное предложение предыдущей фазы. Если оно совпадает с его собственным, решение принято.
- Фаза 3, перенести дальше. Тот, кто не решил, перенимает лучшее из увиденного и идёт в следующий раунд.
Безопасность держится на пересечении большинств: любые два большинства recorders имеют хотя бы одного общего участника, поэтому участник следующей фазы обязательно получит либо предложение, дошедшее до большинства, либо более приоритетное. Остальное обеспечивают правила фаз и переноса значений. Случайные приоритеты решают теоретическую проблему: рандомизация позволяет обойти теорему FLP о невозможности детерминированного консенсуса в асинхронной сети. В статье о QuePaxa вероятность решения в раундах без лидера оценивается не ниже 50%, а на практике, по словам Cloudflare, она заметно выше, потому что участники сходятся к одному предложению.
Что показали испытания и чего пока нет?
Cloudflare приводит результаты собственных прогонов на серверах почти на всех континентах, без абсолютных чисел. Meerkat продолжал обрабатывать запросы при падении, отключении и замедлении лидера; полной остановки авторы не наблюдали ни разу. Больше 95% решений принимает лидер в первой фазе. Когда быстрый путь не срабатывает, пропускная способность кратковременно падает, максимум до трети обычной: на решение уходит три обмена вместо одного. Лидера можно менять прямо на работающем кластере: неудачный выбор замедляет систему, но не останавливает её.
Абсолютных значений пропускной способности, сравнения с Raft на том же стенде и описания нагрузки в тексте нет: бенчмарки обещаны в следующих постах серии. Это замеры самой компании на экспериментальном сервисе.
Риски авторы называют прямо. QuePaxa не проверен практикой так, как Raft и Paxos, а Cloudflare ещё и расширяет исходную модель: в статье узлы после сбоя не возвращаются (crash-stop), тогда как Meerkat должен поддерживать восстановление после сбоя. Поэтому реализацию на Rust и сервис целиком формально верифицируют и прогоняют через симуляцию и внедрение отказов.
Что из этого следует для обычного кластера на Raft?
Менять etcd на QuePaxa статья не призывает, да и готовой реализации Cloudflare не публикует: Meerkat остаётся внутренним экспериментом. Практическая польза в диагнозе. Если кластер консенсуса растянут между регионами, его доступность на запись зависит от одного узла и от того, насколько точно выставлен таймаут выборов, а короткие сетевые всплески могут обходиться непропорционально дорого. Это повод посмотреть на свои значения election timeout и heartbeat относительно реальной задержки между площадками и проверить, как кластер переживает и падение лидера, и его замедление.
Следующие публикации серии Cloudflare обещает посвятить верификации Meerkat, тестированию трудновоспроизводимых отказов и бенчмаркам. Авторы текста: Боб Хэлли, Джеймс Лариш и Жуан Педру Лейте.
Источники: Cloudflare Blog: Choosing QuePaxa, an unusual consensus algorithm, Cloudflare Blog: Introducing Meerkat, an experiment in global consensus, ACM: QuePaxa: Escaping the tyranny of timeouts in consensus (SOSP 2023), Авторский PDF статьи QuePaxa, Cloudflare Blog: A Byzantine failure in the real world, etcd: Tuning, time parameters
Изображение на обложке: Cloudflare