Обучаемый индекс Radix Spline для индексирования в хранилище данных Apache Hudi, предназначенный для определения местоположения записей по ключу при выполнении операций записи, разработал студент магистратуры Факультета информационных технологий Новосибирского государственного университета Станислав Хомченко. Также молодой исследователь под научным руководством кандидата физико-математических наук, доцента кафедры программирования Механико-математического факультета НГУ Павла Емельянова провел экспериментальное исследование производительности структуры данного индекса. В целом при определённых значениях индекс Radix Spline показал себя достаточно уверенно по сравнению с существующими индексами Hudi.
— В современных системах хранения больших данных важной задачей является не только размещение больших объемов информации, но и эффективное выполнение операций изменения данных. В отличие от хранилищ, ориентированных только на добавление новых файлов, современные табличные форматы должны поддерживать вставку, обновление и удаление записей. Это особенно важно для аналитических хранилищ, в которых данные регулярно изменяются и должны оставаться доступными для последующей обработки. Мы впервые применили обучаемую индексную структуру Radix Spline к задаче определения местоположения записей в Apache Hudi. В отличие от существующих подходов, рассматриваемый индекс использует модель зависимости между числовым ключом и его позицией в отсортированном наборе ключей внутри партиции, — пояснил Станислав Хомченко.
Apache Hudi — открытый формат таблиц и платформа для управления данными в озере данных (Data Lake), которая предоставляет возможности потоковой обработки непосредственно поверх распределенного файлового хранилища. Позволяет хранить огромные объемы информации и поддерживает операции upsert (обновление или вставка) и delete (удаление), которые исторически было сложно выполнять в распределенных файловых системах. При выполнении операций записи Apache Hudi должна определить, какие входящие записи уже существуют в таблице, а какие являются новыми. Для этого используются индексы, которые позволяют найти текущее местоположение записи по ее ключу.
— Применение Radix Spline позволяет исследовать подход к поиску местоположения записей на основе распределения числовых ключей внутри партиции. Существующие индексы Hudi решают эту задачу другими способами — через фильтры, хеширование, таблицу метаданных или считывание ключей из файлов, но не используют модель распределения ключей внутри партиции. Поэтому нами был реализован индекс Radix Spline и проведена серия экспериментов. Мы ожидали лучших результатов, однако в ходе тестирования нашли нишу индекса — до 100–200 тыс. начальных записей при 30–50 партициях. В этих условиях он показывает конкурентоспособные результаты по сравнению с существующими индексами Apache Hudi, — пояснил Станислав Хомченко.
Для этого исследователи реализовали новый тип индекса Radix Spline в Spark-клиенте Apache Hudi, разработали тесты для проверки корректности реализации и подготовили бенчмарк для сравнения различных индексов Hudi в одинаковых условиях. Индекс был реализован для таблиц типа «копирование при записи»; текущая реализация имеет локальную семантику поиска и работает с ключами, которые могут быть представлены как неотрицательные числовые значения.
— Мы реализовали построение, проверку актуальности, чтение индексного артефакта и поиск местоположения записи по ключу. Был разработан экспериментальный бенчмарк и подготовлен тестовый стенд, на котором Radix Spline сравнивался с существующими индексами Hudi по времени операций записи и объему служебных данных. Реализовали набор модульных и интеграционных тестов для проверки основных компонентов индекса: кодирования ключей, построения модели, записи и чтения артефакта, поиска по индексу и взаимодействия с процессом записи Hudi. Результаты тестирования подтвердили корректность реализованного решения. Далее был реализован экспериментальный бенчмарк, выполняющий одинаковую последовательность операций записи для разных индексов Hudi. Он включал в себя начальную загрузку, обновление существующих записей, вставку новых записей и смешанную операцию обновления со вставкой, — рассказал о ходе сравнительного экспериментального исследования Станислав Хомченко.
В ходе исследования были получены экспериментальные данные о времени выполнения операций записи и размере служебных данных при использовании Radix Spline и существующих индексов Hudi. Выяснилось, что сильными сторонами Radix Spline являются быстрое построение индексных артефактов, положительная реакция на увеличение числа партиций и конкурентоспособность на малых и средних объемах данных при смешанной операции обновления со вставкой. При этом текущая реализация имеет ограничения: при массовом обновлении существующих записей возрастает стоимость обращения к индексному артефакту, а объем служебных данных оказывается больше, чем у индексов на уровне записей. Однако в целом исследователи довольны результатами проведенной работы, которые затем были представлены на Мальцевских чтениях в секции «Алгебро-логические методы в информационных технологиях» и «64-й международной научной студенческой конференции» в секции «Программная инженерия и инженерия знаний», где работа была отмечена Дипломом II степени.
—
Разработанный индекс и полученные результаты могут использоваться разработчиками и исследователями систем хранения данных при оценке применимости обучаемых индексов в Apache Hudi и развитии механизмов индексирования в Data Lakehouse-системах, — сказал Станислав Хомченко.
