Meerkat: Революция в глобальном консенсусе — быстрее, надёжнее, без сбоев

Многим внутренним сервисам Cloudflare необходимо читать и изменять одно и то же состояние плоскости управления из более чем 330 глобальных центров обработки данных. Им требуются гарантии, что разные читатели никогда не увидят несогласованное состояние, и что система останется доступной для записи даже в случае отказа некоторых центров обработки данных или каналов связи.

Но сеть Cloudflare работает через весь Интернет, а Интернет — непредсказуемое место. Серверы и центры обработки данных выходят из строя. Очереди переполняются. Каналы и кабели обрываются. Эти условия затрудняют работу глобально доступной системы данных, которая гарантирует сильную согласованность (например, что все читатели гарантированно увидят все предыдущие записи), поскольку неблагоприятные условия мешают репликам распределенной системы надежно синхронизировать данные друг с другом.

Один из способов безопасной синхронизации данных, несмотря на неблагоприятные сетевые условия, — это алгоритм консенсуса, который позволяет набору машин договориться об одной и той же последовательности значений, таких как операции put и get в хранилище ключ-значение, при условии, что большинство машин остается в живых и способно обмениваться данными. 

К сожалению, широко применяемые алгоритмы консенсуса, такие как Raft, страдают в глобальных сетях, подобных сети Cloudflare, поскольку они полагаются на лидеров и тайм-ауты. Лидер — это единственная реплика, которой разрешено выполнять записи, и если она выходит из строя из-за сбоя или ухудшения качества сети, система становится недоступной до тех пор, пока какая-либо другая реплика не выйдет из тайм-аута и не будет избран новый лидер. И эти значения тайм-аутов сложно настроить в сетях с непредсказуемыми задержками.

Мы испытали несколько инцидентов, вызванных недоступностью лидеров в системах, основанных на консенсусе.

Поэтому в течение последнего года исследовательская команда Cloudflare создавала новый сервис распределенного консенсуса под названием Meerkat, работающий на основе алгоритма консенсуса QuePaxa, опубликованного в 2023 году исследователями из EPFL. QuePaxa отличается от Raft тем, что все реплики могут выполнять запись в любое время, и прогресс никогда не останавливается из-за тайм-аута, что делает его хорошо подходящим для сети Cloudflare. Мы размещаем приложения, такие как транзакционное хранилище ключ-значение и система аренды, поверх журнала консенсуса Meerkat. Насколько нам известно, это будет первое промышленное развертывание QuePaxa в глобальном масштабе.

Meerkat — это экспериментальный сервис консенсуса, который все еще находится в разработке. Изначально он проектируется для управления небольшими фрагментами состояния плоскости управления (например, лидерством реплицированных баз данных), поэтому в ближайшем будущем он будет использоваться только внутри компании. Эта статья знакомит с Meerkat и закладывает основу для последующих публикаций в блоге, связанных с Meerkat.

Многие сервисы Cloudflare читают и записывают данные плоскости управления — данные, которые помогают этим сервисам корректно работать, с нескольких машин, распределенных по всему миру. Одним из примеров данных плоскости управления является информация о размещении: где хранятся определенные ресурсы (например, экземпляр модели ИИ). Другим примером является информация о лидерстве: какой машине в данный момент разрешено выполнять записи в базу данных.

Данные плоскости управления должны быть как сильно согласованными, так и доступными, несмотря на определенные виды сбоев.

В этом разделе мы точно описываем наши требования к согласованности и отказоустойчивости для сервиса консенсуса Cloudflare. В качестве работающего примера приложения, работающего поверх нашего сервиса консенсуса, мы используем хранилище ключ-значение, хотя возможны и другие приложения (например, распределенные аренды/блокировки).

Уровень согласованности распределенной системы данных описывает, какие виды необычного поведения система может демонстрировать при получении одновременных чтений и записей. Рассмотрим распределенное хранилище ключ-значение, которое хранит одно числовое значение x = 6 на нескольких узлах. Также рассмотрим следующую последовательность записей. Эти записи отправляются на разные узлы по принципу «наилучшего усилия» и могут поступать в любом порядке: 

1. x = x + 1

2. x = x / 2

Уровень согласованности системы говорит вам, какие значения x может увидеть клиент при чтении x после этих записей. Рассмотрим следующую последовательность операций и возможные порядки выполнения при различных уровнях согласованности:

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

В Cloudflare многие сервисы хотят линеаризуемости. В отличие от более слабых форм согласованности, линеаризуемость избавляет программистов от необходимости думать обо всех странных поведениях, которые могут проявлять системы данных. Вместо этого они могут рассуждать о распределенной системе так же, как они рассуждают о локальной памяти на однопоточной машине: все чтения после записи увидят эту запись. Для дополнительного чтения об опасностях слабой согласованности ознакомьтесь с этой статьей Марка Брукера.

(Если вам интересно, хранилище ключ-значение Meerkat также обеспечивает сериализуемость, о чем мы напишем в будущей статье.)

Уровень отказоустойчивости системы описывает, какие виды сбоев система может выдержать до наступления катастроф. Катастрофы обычно представляют собой нарушения свойств, которые система стремится поддерживать, например, что два последовательных чтения без промежуточной записи для одного и того же ключа никогда не увидят разные значения, или что система остается доступной для записи. К сбоям относятся отказы сети или задержки, сбои машин и перезапуски машин. Система обычно явно обрабатывает одни сбои, но не другие (нельзя обработать все сбои, так как вселенная всегда может достичь тепловой смерти). Например, некоторые хранилища ключ-значение могут гарантировать доступность для записи, пока две трети машин в системе могут общаться и не выходят из строя, но не дают никаких обещаний, если машина скомпрометирована и начинает отправлять вредоносные сообщения.

Наши желаемые свойства отказоустойчивости следующие:

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

1. Большинство машин в нашей системе живы и могут общаться друг с другом. (Формально мы допускаем f сбоев в системе из 2f + 1 машин).

2. Клиент может связаться с любой машиной в системе, которая подключена к большинству живых машин.

Это означает, что одиночный сбой машины или ухудшение качества сети на одном канале не влияют на доступность системы. Это свойство не обеспечивается системами на основе Raft, как мы увидим позже.

Во-вторых, система данных остается корректной, пока ни один участник системы не является активно вредоносным (и, конечно, нет ошибок). Мы определяем корректность через безопасность консенсуса позже, но, грубо говоря, это означает, что никакие две актуальные машины никогда не будут расходиться во мнениях о мире (например, одна считает, что key1=1, а другая — что key1=2).

Таким образом, система должна оставаться корректной, даже если машины выходят из строя, перезагружаются, сети отказывают или деградируют, центры обработки данных выходят из строя и т.д. (хотя мы, как и системы на основе Raft, не обрабатываем византийские сбои).

Meerkat — это сервис консенсуса, на основе которого мы можем создавать приложения, обладающие вышеуказанными свойствами (сильная согласованность и отказоустойчивость), такие как хранилище ключ-значение (KV). Чтобы понять, как работает Meerkat, мы сначала опишем общую архитектуру Meerkat, а затем опишем, как выбор алгоритма консенсуса Meerkat помогает обеспечить сильную согласованность и отказоустойчивость.

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

Для взаимодействия со своим кластером клиент разработчика отправляет специфичный для приложения запрос любой реплике в кластере. Одна реплика может размещать множество видов приложений, но самое простое — это хранилище ключ-значение, поэтому самым простым типом запроса, специфичного для приложения, является KV get или put. Реплика отвечает на запрос ответом, специфичным для приложения (например, записи, запрошенные с помощью get). Обратите внимание, что KV чтения (get) гарантированно читают актуальную информацию.

Под капотом реплика преобразует запросы приложений (например, get и put) в события журнала. Эта реплика распространяет каждое событие журнала на все остальные реплики с помощью алгоритма консенсуса, так что все реплики поддерживают одинаковый журнал событий (на практике реплика может отставать, но никогда не запишет разные записи). Эти события произвольны — ядро Meerkat не заботится о том, что в них содержится. Приложения Meerkat заботятся о содержимом событий журнала. Каждая реплика Meerkat «размещает» множество приложений Meerkat (например, хранилище ключ-значение), которые читают события журнала и строят состояние. (Обратите внимание, что каждая реплика принадлежит ровно одному кластеру.)

Например, приложение KV Meerkat строит хранилище ключ-значение в памяти из событий журнала. Поэтому, когда клиент отправляет запись типа put k1 v1, принимающая реплика помещает эту запись в событие журнала и распространяет его на все реплики. Если кто-то другой впоследствии записывает put k1 v11 на другую реплику, это событие также распространяется на все реплики. Поскольку все работающие реплики имеют одинаковый журнал, они могут применять операции из журнала последовательно, чтобы построить точно такое же состояние. Обратите внимание, что запросы get также создают распределенные события журнала (для линеаризуемости, как объясняется в следующем разделе).

Meerkat гарантирует, что если один клиент выполняет put k1 v1, второй клиент впоследствии выполняет put k1 v11, а третий клиент впоследствии выполняет get k1 (с консистентным чтением), они всегда прочитают v11. Это гарантируется даже если каждый запрос отправлен на другую реплику, и эти реплики распределены случайным образом по миру. Это линеаризуемость. Чтобы понять, как Meerkat это гарантирует, мы должны изучить журнал Meerkat более подробно.

Журнал Meerkat представляет собой последовательность слотов. Слот — это ячейка, которая может содержать событие или не содержать. Слот, содержащий событие, называется определённым слотом. Все слоты в журнале определены, кроме последнего слота, который в данный момент определяется. Один из инвариантов Meerkat: если любые две реплики определили значение для слота, эти значения одинаковы. Другими словами, никакие две реплики никогда не будут расходиться в значении определённого слота (хотя одна реплика может считать последний слот пустым, а другая — нет). Это свойство помогает гарантировать желаемые свойства, описанные в предыдущем разделе.

Чтобы определить значение последнего (пустого) слота в журнале, реплики Meerkat выполняют распределенный алгоритм консенсуса. Алгоритм консенсуса позволяет множеству машин, общающихся по сети, согласовать определенное значение слота. Наш алгоритм консенсуса работает, пока живо большинство реплик (более половины).

Таким образом, если журнал в настоящее время содержит две записи, и клиент отправляет put k1 v11 на реплику, эта реплика запускает алгоритм консенсуса для слота 3. Но другой клиент мог отправить put k1 v111 на другую реплику для слота 3. Алгоритм консенсуса гарантирует, что только одно такое предложение для слота 3 побеждает. В частности, он гарантирует, что по крайней мере большинство реплик согласны с одним и тем же предложением, определяя его для слота 3. Неменьшинство никогда не сможет определить другое предложение, но может вообще пропустить тот факт, что слот 3 был определен.

Чтобы увидеть, как это обеспечивает линеаризуемость для нашего хранилища ключ-значение, рассмотрим запись, за которой следует чтение. Одна реплика Z предлагает put k1 v11, и это предложение определяется на слоте 3 большинством реплик, но НЕ репликой Y. Впоследствии читатель выполняет get k1 на реплике Y. Реплика Y считает слот 3 пустым, поэтому предлагает get k1 на слот 3. Критически важно, что большинство реплик не согласятся поместить это событие в слот 3, потому что этот слот уже определен. Они заставят реплику Y определить (получая более старые решения) put k1 v11 в слоте 3 и предложить get k1 для слота 4, таким образом линеаризуя чтение после записи в журнале. (И если эта реплика не может связаться с большинством, она не сможет завершить чтение.)

Определение записей журнала требует распределенного алгоритма консенсуса. Но какого? Все корректные алгоритмы консенсуса обеспечивают требуемые гарантии согласованности и корректности, но не все обеспечивают одинаковые гарантии доступности.

В частности, многие алгоритмы, полагающиеся на авторитетных лидеров, не обеспечивают желаемых гарантий доступности, потому что они могут стать недоступными, когда одна машина испытывает проблемы. Рассмотрим Raft, один из самых известных и, вероятно, самый реализованный алгоритм консенсуса. Raft полагается на авторитетного лидера: единственную реплику в кластере, которая может управлять консенсусом. В результате все записи перенаправляются лидеру. Этот выбор дизайна помогает сделать Raft «понятным» и в сочетании с арендой может сделать чтения, обслуживаемые лидером, автоматически линеаризуемыми (поскольку они гарантированно актуальны). Но это также добавляет единую точку (временного) отказа.

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

Первая проблема усугубляется в глобальных сетях. Представьте, что когда лидер выходит из строя, большинство алгоритмов выбирают нового лидера с помощью тайм-аутов: если реплика, не являющаяся лидером, не получает известий от лидера в течение некоторого времени, она предлагает себя в качестве лидера. В этот момент старый лидер смещен, и система не может принимать записи, пока не будет избран новый лидер. Проблема в том, что когда тайм-аут короче сетевой задержки между исходным лидером и этой репликой, реплики будут постоянно выходить из тайм-аута и, таким образом, блокировать записи. А когда тайм-аут слишком длинный, система медленно реагирует на отказавшего лидера, и в это время записи также блокируются. Кроме того, если несколько реплик одновременно предлагают себя в качестве лидера, их «кампании» могут мешать друг другу, заставляя их постоянно повторно предлагать себя в качестве лидера — все это время блокируя записи. Мы сталкивались с этими проблемами в системах Cloudflare, использующих Raft, потому что задержки в нашей глобальной сети могут и действительно сильно варьироваться, что делает настройку тайм-аутов особенно сложной.

Мы выбрали другой алгоритм консенсуса для Meerkat, называемый QuePaxa, который стремится избежать «тирании тайм-аутов», навязываемой такими протоколами, как Raft. QuePaxa — сложный протокол, но вот основные моменты. Клиент может связаться с любой репликой, и эта реплика может управлять консенсусом для последнего слота. Есть лидер, но он не обязателен — его единственное преимущество в том, что он может управлять консенсусом с меньшим числом обменов (один), чем другие реплики (3+). Критически важно, что клиенты могут свободно связываться с несколькими репликами одновременно для одного и того же предложения, чтобы увеличить шанс успеха предложения. Одновременные предложения не мешают друг другу деструктивно: реплики работают вместе, чтобы определить одно из предложенных значений.

Вкратце, QuePaxa имеет три преимущества перед Raft для наших целей:

1. Поскольку нет обязательного лидера, система никогда не становится недоступной или деградированной из-за того, что одна реплика (лидер) вышла из строя, недоступна или деградирована. Клиенты могут выполнять записи, пока они могут связаться с какой-либо здоровой репликой (в любой точке мира).

2. Поскольку нет лидера, нет выборов лидера, которые деградируют систему. И одновременные предложения, сделанные разными репликами, конструктивно взаимодействуют, в отличие от выборов лидера в Raft. Это идеально для сети Cloudflare, в которой задержки могут сильно варьироваться.

3. QuePaxa был разработан для менее надежной сетевой среды («асинхронности») и для сетей, в которых воображаемый противник может запускать целенаправленные атаки на соединения реплик. Авторы обнаружили, что в таких условиях он поддерживает гораздо более высокую (~10x) пропускную способность, чем Raft и Multi-Paxos. Эти условия более точно отражают нашу собственную сеть, чем условия, предполагаемые другими алгоритмами.

Полное описание QuePaxa мы оставим для другого поста. Огромная благодарность авторам статьи о QuePaxa из EPFL за возможность получить обратную связь и ответы на вопросы об их работе.

У Meerkat есть ограничения. Он не предназначен для создания универсальных систем данных, таких как базы данных.

Все алгоритмы консенсуса имеют свою цену: множество往返ов (round-trips). QuePaxa, в частности, требует от одного до трех往返ов (обычно, хотя может быть и больше) между инициатором предложения и большинством реплик для принятия решения по предложению и добавления события в журнал. Разница заключается в лидере. Если лидер предлагает, требуется один往返 (+ дополнительная рассылка для уведомления реплик о решении), а если предлагает не лидер — три往返а (+ дополнительная рассылка). Если несколько реплик одновременно вносят предложения, может потребоваться больше. Эти коммуникационные затраты указывают на важное ограничение производительности алгоритмов консенсуса в целом: задержка принятия решения пропорциональна задержке между некоторым большинством реплик. Так что если ваши реплики находятся далеко друг от друга, задержка увеличится — от этого никуда не деться.

На первый взгляд кажется, что задержка записи и чтения Meerkat будет довольно высокой. Особенно если все записи и чтения (для обеспечения согласованности) должны проходить через журнал и, следовательно, требуют так много往返ов.

Но есть несколько способов выжать лучшую производительность из Meerkat: 

1. Поскольку разработчики контролируют расположение своих реплик, они могут переместить их ближе друг к другу, уменьшив задержку往返ов (применимо только для сервисов, которым не требуется truly глобальное распределение).

2. Записи можно группировать. Так, если реплика получает 10 записей в течение 10 мс, она может поместить их все в одно предложение, улучшая пропускную способность.

3. Не все чтения должны запускать раунд консенсуса. Если разработчика устраивает чтение устаревших (но никогда не противоречивых) данных, он может читать из локальных данных любой реплики.

4. Несколько операций можно объединить в один раунд консенсуса. Например, наше хранилище ключей-значений поддерживает запись в стиле "сравнить и обменять", при которой запись выполняется только если значение не изменилось с момента его чтения. (Фактически оно поддерживает общие транзакции.)

Тем не менее, фундаментальные ограничения задержки Meerkat остаются, особенно при работе в глобальном масштабе, для чего она и была разработана. Эти ограничения делают ее идеальной в краткосрочной перспективе для информации плоскости управления, которая записывается нечасто, но должна оставаться согласованной.

Meerkat не развернута в production, но мы успешно провели несколько proof-of-concept с до 50 репликами, распределенными по всему миру. Лидеры в наших кластерах proof-of-concept постоянно выходят из строя, но кластер продолжает работу без увеличения частоты ошибок.

Нам еще многое есть что рассказать о Meerkat. В течение следующего года мы будем писать посты о Meerkat, в которых обсудим, как на самом деле работает QuePaxa, как мы формально верифицируем часть нашей реализации на Rust, как работают начальная загрузка и управление кластером, как мы находим оптимальное размещение реплик, как используем детерминированное симуляционное тестирование для поиска ошибок и многое другое. Мы также подготовим рукопись для рецензирования!