Как Roblox снижает затраты на запросы Spark Join с помощью оптимизированных для машинного обучения фильтров Блума - блог Roblox

Как Roblox снижает затраты на запросы Spark Join с помощью оптимизированных для машинного обучения фильтров Блума — блог Roblox

Отметка времени: 28 ноября 2023 г., 12:23
Исходный узел: 2983061

Абстрактные

Каждый день в Роблоксе, 65.5 миллионов пользователей взаимодействуют с миллионами впечатлений, всего 14.0 миллиардов часов ежеквартально. В результате этого взаимодействия создается озеро данных размером в петабайты, которое пополняется для целей аналитики и машинного обучения (ML). Объединение таблиц фактов и измерений в нашем озере данных требует больших ресурсов, поэтому, чтобы оптимизировать это и уменьшить перетасовку данных, мы внедрили Learned Bloom Filters [1] — интеллектуальные структуры данных с использованием машинного обучения. Прогнозируя присутствие, эти фильтры значительно сокращают данные соединений, повышая эффективность и сокращая затраты. Попутно мы также улучшили архитектуру наших моделей и продемонстрировали существенные преимущества, которые они предлагают для сокращения памяти и времени процессора для обработки, а также повышения операционной стабильности.

Введение

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

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

Повышение эффективности соединений с помощью изученных фильтров Блума

Чтобы оптимизировать объединение таблиц фактов и измерений, мы внедрили реализацию Learned Bloom Filter. Мы создали индекс на основе ключей, присутствующих в таблице фактов, и впоследствии развернули его для предварительной фильтрации данных измерения перед операцией соединения. 

Эволюция от традиционных фильтров Блума к изученным фильтрам Блума

Хотя традиционный фильтр Блума эффективен, он добавляет 15–25 % дополнительной памяти на каждый рабочий узел, который необходимо загрузить, чтобы достичь желаемого уровня ложных срабатываний. Но, используя изученные фильтры Блума, мы добились значительного уменьшения размера индекса, сохранив при этом тот же уровень ложных срабатываний. Это связано с преобразованием фильтра Блума в задачу двоичной классификации. Положительные метки указывают на наличие значений в индексе, а отрицательные — на их отсутствие.

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

В рамках этой работы мы установили две метрики для оценки нашего подхода к изученному фильтру Блума: конечный размер сериализованного объекта индекса и потребление ЦП во время выполнения запросов соединения. 

Решение проблем реализации

Нашей первоначальной задачей было обращение к сильно смещенному набору обучающих данных с небольшим количеством ключей таблицы измерений в таблице фактов. При этом мы наблюдали совпадение ключей между таблицами примерно на один из трех. Чтобы решить эту проблему, мы использовали подход сэндвич-обученного фильтра Блума [2]. Он включает в себя первоначальный традиционный фильтр Блума для балансировки распределения набора данных путем удаления большинства ключей, отсутствующих в таблице фактов, что эффективно исключает отрицательные выборки из набора данных. Впоследствии только ключи, включенные в первоначальный фильтр Блума, вместе с ложными срабатываниями были перенаправлены в модель ML, часто называемую «обученным оракулом». Этот подход привел к созданию хорошо сбалансированного набора обучающих данных для обученного оракула, что позволило эффективно преодолеть проблему предвзятости.

Вторая задача была связана с архитектурой модели и особенностями обучения. В отличие от классической проблемы фишинговых URL-адресов [1], наши ключи соединения (которые в большинстве случаев являются уникальными идентификаторами пользователей/опыта) по своей сути не были информативными. Это побудило нас изучить атрибуты измерения как потенциальные функции модели, которые могут помочь предсказать, присутствует ли сущность измерения в таблице фактов. Например, представьте себе таблицу фактов, содержащую информацию о сеансе пользователя для взаимодействия на определенном языке. Географическое местоположение или атрибут языкового предпочтения пользовательского измерения могут быть хорошими индикаторами того, присутствует ли отдельный пользователь в таблице фактов или нет.

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

Наш обновленный запрос на соединение с использованием изученных фильтров Блума показан ниже:

Итоги

Вот результаты наших экспериментов с фильтрами Learned Bloom в нашем озере данных. Мы интегрировали их в пять производственных рабочих нагрузок, каждая из которых имела разные характеристики данных. Самая затратная в вычислительном отношении часть этих рабочих нагрузок — соединение таблицы фактов и таблицы измерений. Ключевое пространство таблиц фактов составляет примерно 30% таблицы измерений. Для начала мы обсудим, как обученный фильтр Блума превзошел традиционные фильтры Блума с точки зрения конечного размера сериализованного объекта. Далее мы покажем улучшение производительности, которое мы наблюдали благодаря интеграции изученных фильтров Блума в наши конвейеры обработки рабочей нагрузки.

Сравнение размеров изученного фильтра Блума

Как показано ниже, при рассмотрении заданного уровня ложных срабатываний два варианта изученного фильтра Блума улучшают общий размер объекта на 17–42% по сравнению с традиционными фильтрами Блума.

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

Результаты использования изученного фильтра Блума 

В этом разделе мы сравниваем производительность объединений на основе фильтра Блума с эффективностью обычных объединений по нескольким показателям. 

В таблице ниже сравнивается производительность рабочих нагрузок с использованием изученных фильтров Блума и без них. Обученный фильтр Блума с общей вероятностью ложного срабатывания 1 % демонстрирует приведенное ниже сравнение при сохранении одной и той же конфигурации кластера для обоих типов соединений. 

Во-первых, мы обнаружили, что реализация Bloom Filter превосходит обычное соединение по процессоро-часам на целых 60%. Мы наблюдали увеличение использования ЦП на этапе сканирования для подхода «Обученный фильтр Блума» из-за дополнительных вычислительных затрат, затраченных на оценку фильтра Блума. Однако предварительная фильтрация, выполненная на этом этапе, уменьшила размер перемешиваемых данных, что помогло уменьшить использование ЦП на последующих этапах, тем самым сократив общее количество часов ЦП.

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

Мы также наблюдали снижение потребления ресурсов в других производственных рабочих нагрузках, находящихся в стадии эксперимента. В течение двух недель во всех пяти рабочих нагрузках подход «Обученный фильтр Блума» позволил получить среднее значение ежедневная экономия средств of 25%, что также учитывает обучение модели и создание индекса.

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

Рекомендации

[1] Т. Краска, А. Бойтель, Э. Х. Чи, Дж. Дин и Н. Полизотис. Аргументы в пользу изученных индексных структур. https://arxiv.org/abs/1712.01208, 2017.

[2] М. Митценмахер. Оптимизация изученных фильтров Блума путем сэндвичинга. 

https://arxiv.org/abs/1803.01474, 2018.

¹По состоянию на 3 месяца, закончившихся 30 июня 2023 г.

²По состоянию на 3 месяца, закончившихся 30 июня 2023 г.

Отметка времени:

Больше от Roblox