Cloudflare строит глобальный консенсус на QuePaxa вместо Raft и Paxos

Инженеры Cloudflare разобрали, почему Raft плохо переносит интернет-задержки и чем его заменили в сервисе Meerkat.

Обложка: Cloudflare строит глобальный консенсус на QuePaxa вместо Raft и Paxos

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 и ждёт ответа большинства:

  1. Фаза 0, предложить и перенять. Участники выбирают случайный приоритет и перенимают самое приоритетное предложение, полученное от большинства. Если это первый раунд и лидер знает, что его предложение дошло до большинства первым, он принимает решение сразу.
  2. Фаза 1, распространить. Перенятое предложение рассылается большинству recorders, которые запоминают самое приоритетное из увиденных.
  3. Фаза 2, проверить и решить. Участник спрашивает у большинства самое приоритетное предложение предыдущей фазы. Если оно совпадает с его собственным, решение принято.
  4. Фаза 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