Як Roblox зменшує витрати на запити Spark Join за допомогою фільтрів Bloom, оптимізованих за допомогою машинного навчання - Блог Roblox

Перевидано Платоном

читають: 0

абстрактний

Щодня на Roblox, 65.5 мільйони користувачів взаємодіють з мільйонами досвіду, загалом 14.0 мільярд годин щокварталу. Ця взаємодія генерує петабайтне озеро даних, яке збагачується для цілей аналітики та машинного навчання (ML). Об’єднання таблиць фактів і розмірів у нашому озері даних потребує ресурсів, тому, щоб оптимізувати це та зменшити перемішування даних, ми застосували Learned Bloom Filters [1] — розумні структури даних, що використовують ML. Прогнозуючи присутність, ці фільтри значно скорочують об’єднані дані, підвищуючи ефективність і знижуючи витрати. Попутно ми також удосконалили наші архітектури моделей і продемонстрували значні переваги, які вони пропонують для зменшення пам’яті та годин ЦП на обробку, а також підвищення стабільності роботи.

Вступ

У нашому озері даних таблиці фактів і куби даних тимчасово розділені для ефективного доступу, тоді як таблиці розмірностей не мають таких розділів, і об’єднання їх із таблицями фактів під час оновлень потребує ресурсів. Ключовий простір об’єднання керується тимчасовим розділом таблиці фактів, що об’єднується. Сутності виміру, присутні в цьому часовому розділі, є невеликою підмножиною тих, що присутні в усьому наборі даних виміру. Як наслідок, більшість перетасованих даних розмірів у цих об’єднаннях зрештою відкидається. Щоб оптимізувати цей процес і зменшити непотрібне перемішування, ми розглянули можливість використання Фільтри Bloom на різних ключах об’єднання, але зіткнувся з проблемами розміру фільтра та обсягу пам’яті.

Щоб вирішити їх, ми досліджували Вивчені фільтри Блума, рішення на основі ML, яке зменшує розмір фільтра Bloom, зберігаючи при цьому низький рівень помилкових позитивних результатів. Це нововведення підвищує ефективність операцій об’єднання за рахунок зменшення витрат на обчислення та підвищення стабільності системи. Наступна схема ілюструє звичайні та оптимізовані процеси об’єднання в нашому розподіленому обчислювальному середовищі.

Підвищення ефективності об’єднання за допомогою навчених фільтрів Блума

Щоб оптимізувати з’єднання між таблицями фактів і таблицями розмірів, ми застосували Learned Bloom Filter. Ми створили індекс із ключів, присутніх у таблиці фактів, а потім розгорнули індекс для попереднього фільтрування даних виміру перед операцією об’єднання.

Еволюція від традиційних фільтрів Bloom до навчених фільтрів Bloom

Хоча традиційний фільтр Блума є ефективним, він додає 15-25% додаткової пам’яті на робочий вузол, який потрібно завантажити, щоб досягти бажаного рівня помилкових позитивних результатів. Але, використовуючи навчені фільтри Блума, ми досягли значного зменшення розміру індексу, зберігаючи той самий рівень помилкових позитивних результатів. Це пов’язано з перетворенням фільтра Блума в проблему бінарної класифікації. Позитивні мітки вказують на наявність значень в індексі, тоді як негативні мітки означають їх відсутність.

Впровадження моделі ML полегшує початкову перевірку значень, а потім резервний фільтр Блума для усунення хибних негативів. Зменшення розміру пов’язане зі стислим представленням моделі та зменшенням кількості ключів, необхідних для резервного фільтра Bloom. Це відрізняє його від традиційного підходу Bloom Filter.

У рамках цієї роботи ми встановили дві метрики для оцінки нашого підходу Learned Bloom Filter: кінцевий серіалізований розмір об’єкта індексу та споживання ЦП під час виконання запитів на об’єднання.

Навігація під час впровадження

Наше початкове завдання полягало в тому, щоб розглянути дуже упереджений набір навчальних даних із кількома ключами таблиці розмірів у таблиці фактів. При цьому ми спостерігали перекривання приблизно одного з трьох ключів між таблицями. Щоб вирішити цю проблему, ми використали підхід Sandwich Learned Bloom Filter [2]. Це інтегрує початковий традиційний фільтр Блума для відновлення балансу розподілу набору даних шляхом видалення більшості ключів, яких не було в таблиці фактів, фактично усуваючи негативні зразки з набору даних. Згодом лише ключі, включені до початкового фільтра Блума, разом із помилковими спрацьовуваннями були направлені до моделі ML, яку часто називають «навченим оракулом». Результатом такого підходу став добре збалансований набір навчальних даних для вченого оракула, що ефективно подолало проблему упередженості.

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

Третя проблема — затримка логічного висновку — вимагала моделей, які мінімізували помилкові негативи та забезпечували швидку відповідь. Деревоподібна модель із посиленням градієнта була оптимальним вибором для цих ключових показників, і ми скоротили її набір функцій, щоб збалансувати точність і швидкість.

Наш оновлений запит на приєднання з використанням навчених фільтрів Блума виглядає так:

результати

Ось результати наших експериментів із фільтрами Learned Bloom у нашому озері даних. Ми інтегрували їх у п’ять виробничих робочих навантажень, кожна з яких мала різні характеристики даних. Найбільш дорогою частиною цих робочих навантажень є з’єднання між таблицею фактів і таблицею розмірів. Ключовий простір таблиць фактів займає приблизно 30% розмірної таблиці. Для початку ми обговоримо, як навчений фільтр Блума перевершив традиційні фільтри Блума з точки зору остаточного серіалізованого розміру об’єкта. Далі ми показуємо покращення продуктивності, які спостерігали завдяки інтеграції навчених фільтрів Блума в наші конвеєри обробки робочого навантаження.

Порівняння розмірів фільтра Bloom

Як показано нижче, дивлячись на задану частоту помилкових позитивних результатів, два варіанти вивченого фільтра Блума покращують загальний розмір об’єкта на 17-42% порівняно з традиційними фільтрами Блума.

Крім того, використовуючи меншу підмножину функцій у нашій моделі на основі дерева з посиленим градієнтом, ми втратили лише невеликий відсоток оптимізації, але пришвидшили висновок.

Вивчені результати використання фільтра Блума

У цьому розділі ми порівнюємо ефективність об’єднань на основі фільтра Блума з продуктивністю звичайних об’єднань за кількома показниками.

У таблиці нижче порівнюється продуктивність робочих навантажень із використанням навчених фільтрів Блума та без них. Наведений фільтр Блума із загальною ймовірністю хибнопозитивного результату 1% демонструє наведене нижче порівняння, зберігаючи однакову конфігурацію кластера для обох типів з’єднання.

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

По-друге, Learned Bloom Filters мають приблизно на 80% менший загальний розмір даних і приблизно на 80% менше загальних байтів перетасування, ніж звичайне об’єднання. Це призводить до більш стабільної продуктивності об’єднання, як описано нижче.

Ми також помітили зменшення використання ресурсів в інших наших виробничих робочих навантаженнях під час експерименту. Протягом двох тижнів для всіх п’яти робочих навантажень підхід Learned Bloom Filter генерував середнє значення щоденна економія витрат of 25%, що також враховує навчання моделі та створення індексу.

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