Как мы сотрудничали с Meta (Facebook) для создания Shadow Cache

В сотрудничестве с Meta (Facebook), Принстонским университетом и Alluxio мы разработали «Shadow Cache» — легкий компонент Alluxio для отслеживания размера рабочего набора и бесконечного коэффициента попаданий в кэш. Теневой кеш может динамически отслеживать размер рабочего набора за прошедшее окно и реализуется серией фильтров Блума. Теневой кэш развернут в Meta (Facebook) Presto и используется для понимания узких мест системы и помощи в принятии решений по проектированию маршрутизации.

Мотивация и предыстория

В Meta (Facebook) Presto представляет собой распределенный механизм запросов в реальном времени, использующий язык SQL в качестве интерфейса для выполнения быстрых интерактивных запросов к петабайтам данных. Он поддерживает стандартный ANSI SQL, включая запросы, агрегации, JOIN и оконные функции.

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

Чтобы повысить производительность Presto, необходимо понимать влияние размера кэша и коэффициента попаданий в кэш. Presto необходимо получить определенную информацию о кэшировании от Alluxio, чтобы определить, может ли увеличение размера кэша помочь улучшить коэффициент попаданий в кэш и производительность, когда хранилище кэша ограничено. Эта информация также полезна для оптимизации алгоритмов кэширования. Мы также хотим оптимизировать алгоритм маршрутизации для лучшего баланса и эффективности. В результате то, как лучше отслеживать данные кэша Alluxio и управлять ими, является ключом к принятию решений по предварительной оптимизации.

Два ключевых вопроса должны быть решены со стороны Presto:

1. Как определить размер кеша для каждого арендатора?

2. Каково потенциальное улучшение коэффициента попаданий в кэш?

Мы предлагаем Shadow Cache, облегченный компонент Alluxio для отслеживания размера рабочего набора и частоты попаданий в кэш.

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

Этот легкий компонент Alluxio, Shadow Cache, может предоставить информацию о рабочем наборе кеша и о том, как будет выглядеть частота попаданий в кеш, если есть бесконечное пространство кеша. Чтобы отслеживать состояние кеша кластера, мы определяем следующие ключевые метрики.

• C1: Реальное использование кэша в определенный момент времени

• C2: Рабочий набор теневого кэша во временном окне (1 день / 1 неделя).

• H1: реальный коэффициент попадания в кэш

• H2: Частота попаданий в Shadow Cache

Соревнование

Хотя мы пытались предоставить вышеуказанные показатели для кеша Alluxio, мы столкнулись с рядом проблем.

Низкий объем памяти и нагрузка на ЦП

Shadow Cache — это легкий компонент, который отслеживает размер кэшированных рабочих наборов. Трудно отслеживать «бесконечный» рабочий набор с ограниченной памятью. Shadow Cache также должен иметь низкую нагрузку на ЦП, поскольку он кэширует данные при обработке каждого запроса. В противном случае запросы пользователей будут блокироваться на долгое время.

Точность

Shadow Cache также должен гарантировать точность. В Presto Shadow Cache измеряет состояние кэша кластера, и если предполагаемая предельная частота попаданий в кэш слишком низкая, Presto может ошибочно определить, что это задание не поддерживает кэширование. Напротив, если предполагаемая частота попаданий в кеш лимита слишком высока, Presto может полагать, что расширение кеша кластера на этом этапе значительно улучшит общую производительность.

Динамическое обновление

Presto и другие современные приложения для работы с данными в основном используются для выявления текущих или будущих тенденций. Следовательно, Shadow Cache также должен отбрасывать устаревшие элементы в режиме реального времени. В противном случае это, вероятно, внесет шумовые помехи в решение. Скользящие окна — один из наиболее распространенных методов хранения новейших элементов, но создать структуру данных для модели с скользящими окнами непросто. Когда окно скользит, нам нужно удалить элементы, которые были только что перемещены, в режиме реального времени. Важно как можно быстрее найти элемент, который необходимо удалить, и удалить его.

Решение

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

Фильтры Блума: решение проблем с накладными расходами и точностью

Фильтр Блума — это компактное вероятностное тестирование принадлежности к структуре данных. Фильтр Блума представляет собой массив, инициализированный всеми нулями в битах, и каждый объект представлен всего несколькими битами, что значительно экономит пространство и обеспечивает превосходную эффективность запросов. Фильтры Блума могут определить, существует ли элемент или нет. Элемент не должен существовать, если фильтр Блума возвращает, что он не существует. Обратите внимание, что ложноположительные результаты возможны, а ложноотрицательные — нет.

Фильтр Блума имеет k хеш-функций. Чтобы добавить элемент, примените каждую хэш-функцию и установите бит в 1. Чтобы запросить элемент, примените каждую хэш-функцию и биты И. Когда все биты в k позициях равны 1, элемент считается существующим. В противном случае элемент не считается существующим.

Цепочка фильтров Блума: решение для динамического обновления

Фильтры Блума могут обеспечить как низкие накладные расходы, так и высокую точность, поэтому можем ли мы напрямую применить их к Shadow Cache?

Первая проблема, с которой мы сталкиваемся, заключается в том, что фильтры Блума не поддерживают удаление. Это связано с тем, что нас волнует только размер рабочего набора пользовательского приложения с течением времени, и для этого требуется Shadow Cache. Shadow Cache делает это, связывая несколько фильтров вместе, чтобы создать цепочку фильтров Блума.

Вот как можно использовать цепочку фильтров Блума для обновления размера загрузки рабочего набора в режиме реального времени.

Запрос: Как показано выше, Shadow Cache представляет собой цепочку, состоящую из нескольких фильтров Блума. При отслеживании размера рабочего набора пользователя за последние 24 часа мы можем разделить 24 часа на четыре периода. Фильтр Блума отслеживает каждый период в Shadow Cache, и каждый фильтр Блума отслеживает период. Shadow Cache использует все существующие фильтры Блума или создает новый фильтр Блума для запроса, как показано на следующем рисунке.

Обновление в реальном времени. Чтобы данные хранились в режиме реального времени, нам нужен теневой кэш, чтобы отбрасывать данные, которые устарели, когда временное окно скользит. Значения фильтра Блума должны непрерывно обновляться с течением времени t, а элементы фильтра Блума, уже находящиеся за пределами временного окна, должны быть удалены. Поскольку мы объединяем несколько фильтров Блума, легко определить, где находятся устаревшие элементы в самом конце фильтра Блума, как показано на рисунке ниже. Каждый раз, когда начинается новый период, мы удаляем самый старый фильтр из цепочки и добавляем новый полностью пустой фильтр для записи последних данных.

Рабочий набор Размер: Поскольку фильтры Блума отображают элемент в несколько битов, оценка размера рабочего набора исключительно на основе числа битов до 1 приведет к недопустимой ошибке, поскольку бит может представлять несколько элементов, а элемент может быть разбросан между несколькими битами. Поэтому мы используем формулу, полученную в [Swamidass & Baldi (2007)] (https://en.wikipedia.org/wiki/Bloom_filter#CITEREFSwamidassBaldi2007). Мы используем приближение со следующим уравнением для измерения размера рабочего набора.

Где n* — оценка количества элементов в фильтре, m — длина (размер) фильтра, k — количество хеш-функций, а X — количество битов, равных единице.

Коэффициент попаданий бесконечного размера: После предоставления метрики размера рабочего набора Shadow Cache также должен предоставить коэффициент попаданий бесконечного размера. Мы можем использовать фильтры Блума в качестве кэша с бесконечным пространством, потому что они могут отслеживать огромные объемы данных с небольшим использованием памяти. Количество пользовательских запросов, попавших в фильтр Блума, равно количеству попаданий в бесконечный кэш, обозначаемому как попадание. Общее количество «пользовательских запросов» обозначается как queryNum. QueryNum — это общее количество «запросов пользователей», поэтому коэффициент совпадений равен количеству попаданий/queryNum.

Использование теневого кэша для определения состояния кэша кластера Presto

После завершения цепочки фильтров Блума мы можем быстро узнать ранее определенные метрики H1, H2, C1, C2. На следующем этапе Presto может определить состояние кэша кластера, сравнив соотношение размеров между ними, как показано на следующем рисунке.

Низкое значение H2 указывает на то, что частота попаданий в кэш приложения в этом кластере не может быть достигнута даже при неограниченном объеме кэша. Это означает, что это приложение не поддерживает кеширование. Когда значение H2 высокое, а значение H1 низкое, а C2 > C1, это указывает на то, что в кластере недостаточно места для кэша, и количество попаданий можно повысить, если увеличить емкость кэша. Когда значение H2 высокое, а значение H1 высокое, а C2 < C1, кэш кластера перераспределяется, и ресурсы тратятся впустую. Кластер находится в хорошем состоянии, если H2 > H1 и C2 > C1 и C2 > C1, то есть масштабирование кеша не требуется.

Реализация

Реализация фильтров Блума в Shadow Cache основана на библиотеке Guava BloomFilter и поддерживает определенные конфигурации фильтров на основе определяемого пользователем бюджета накладных расходов на память и окна теневого кэша. В настоящее время Shadow Cache поддерживает размер рабочего набора с точки зрения #pages и #byte, которые представляют, сколько страниц и сколько конкретных байтов содержит рабочий набор соответственно. Для расчета частоты совпадений Shadow Cache поддерживает коэффициент совпадений байтов бесконечного размера и коэффициент совпадений объектов.

Ниже приведены конфигурации.

#Прошлое окно для определения рабочего набора

alluxio.user.client.cache.shadow.window=**24 часа**

#Общий объем памяти для фильтров Блума, используемых для отслеживания

alluxio.user.client.cache.shadow.memory.overhead=**125MB**

#Количество фильтров Блума, используемых для отслеживания. Каждый отслеживает сегмент окна

alluxio.user.client.cache.shadow.bloomfilter.num=**4**

Результаты теста

Мы протестировали Shadow Cache и обнаружили, что, имея всего 125 МБ пространства, Shadow Cache может отслеживать 27 ТБ рабочих наборов с частотой ошибок всего 3%. Кроме того, частота ошибок может быть дополнительно снижена с помощью HyperLogLog, но оценка коэффициента попаданий бесконечного размера не будет поддерживаться, если используется HyperLogLog.

Предварительная оптимизация маршрутизации

Чтобы повысить производительность, Presto нужен способ своевременной настройки кластера, если он узнает конкретное состояние кластера из теневого кэша. Наш следующий шаг — описать текущий алгоритм маршрутизации Presto, а затем предоставить несколько вариантов оптимизации маршрутизации после внедрения Shadow Cache.

Предварительная маршрутизация

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

Как показано на рисунке выше, таблицы с 1 по 4 имеют разные имена таблиц и поэтому назначаются разным кластерам. При запросе данных из таблицы1 алгоритм маршрутизации отправит запрос в кластер1, а при запросе данных из таблицы3 алгоритм маршрутизации отправит запрос в кластер3.

Параметры оптимизации маршрутизации

Время ответа на запрос кластера — это простой способ определить, работает ли кластер. Когда кластер отвечает медленно или слишком долго, мы предполагаем, что в кластере возникла проблема. С Shadow Cache, как упоминалось выше, в сочетании с H1, H2, C1, C2, мы можем быстро определить, испытывает ли кластер снижение производительности из-за нагрузки на кэш.

Presto предлагает следующие три варианта оптимизации маршрутизации для такого неэффективного кластера. Конечно, у каждого варианта есть свой компромисс.

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

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

• Вариант 3: Создайте карту из таблиц в кластеры и сделайте использование ЦП более равномерным. Однако это может привести к неравномерному распределению хранилища кэша и потребует дополнительного места в кэше.

Резюме

Задача отслеживания и оценки размера рабочего набора в кеше является серьезной, поэтому мы разработали облегченный компонент Alluxio Shadow Cache с использованием фильтров Блума. Поскольку нас интересует только последний статус рабочего набора, необходимо использовать модель временного окна, чтобы исключить устаревшие элементы. Для этой цели Shadow Cache делит временное окно на четыре сегмента. Каждый сегмент отслеживается с помощью отдельного фильтра Блума. Новый фильтр Блума создается для отслеживания последних данных, заменяя самые ранние в каждом исключении. Наконец, когда необходимо указать размер рабочего набора, мы используем предложенную [Swamidass & Baldi (2007)] (https://en.wikipedia.org/wiki/Bloom_filter#CITEREFSwamidassBaldi2007) формулу для базовой оценки.

В целом Shadow Cache предоставляет Presto четыре удобных метрики: H1, H2, C1, C2, где H1 и C1 представляют реальную частоту попаданий в кэш и использование соответственно, а H2 и C2 представляют предельную частоту попаданий в кэш и размер кэша. рабочий набор пользователя за определенный период времени. Presto может быстро определить взаимосвязь между объемом кэш-памяти и производительностью приложения и оптимизировать алгоритм маршрутизации для лучшего баланса и эффективности на основе четырех вышеуказанных показателей.

Ссылки

• [Код объединен] (https://github.com/Alluxio/alluxio/blob/master/core/client/fs/src/main/java/alluxio/client/file/cache/CacheManagerWithShadowCache.java)

• [Китайская версия этой статьи] (https://mp.weixin.qq.com/s/LjTPwQSfEENR3WB_Ct3hUg)

Об авторах

Ке Ван — инженер-программист в Meta (Facebook), специализирующийся на запросах с малой задержкой в ​​команде Presto.

Чжэньюй Сон — доктор философии. кандидат кафедры компьютерных наук Принстонского университета, исследующий машинное обучение для повышения эффективности кэширования в CDN.