Master’s student at NSU implemented a learnable index for Apache Hudi and experimentally evaluated its behavior during write operations

A trained Radix Spline index for indexing in the Apache Hudi data store, designed to locate records by key during write operations, was developed by a graduate student. Faculty of Information Technology of Novosibirsk State University Stanislav Khomchenko. The young researcher is also working under the scientific supervision of a Candidate of Physical and Mathematical Sciences, an associate professor of the programming department Faculty of Mechanics and Mathematics, NSU Pavel Emelyanov conducted an experimental study of the performance of the structure of this index. Overall, at certain values, the Radix Spline index performed quite confidently compared to existing Hudi indexes.

— In modern large data storage systems, an important task is not only the placement of large volumes of information but also the efficient execution of data modification operations. Unlike storage systems oriented solely towards adding new files, modern tabular formats must support insertion, updating, and deletion of records. This is especially important for analytical warehouses where data is regularly changed and must remain accessible for subsequent processing. We applied the learnable index structure Radix Spline for the first time to the task of determining the location of records in Apache Hudi. Unlike existing approaches, the considered index uses a model of the dependency between the numerical key and its position in the sorted set of keys within a partition., — explained Stanislav Khomchenko.

Apache Hudi is an open table format and platform for managing data in a data lake, which provides streaming processing capabilities directly on top of distributed file storage. It allows storing huge volumes of information and supports upsert (update or insert) and delete operations, which have historically been challenging to perform in distributed file systems. When performing write operations, Apache Hudi needs to determine which incoming records already exist in the table and which are new. For this, indexes are used that allow finding the current location of a record by its key.

— The use of Radix Spline allows for exploring an approach to locating records based on the distribution of numeric keys within a partition. Existing Hudi indexes solve this problem in different ways — through filters, hashing, metadata tables, or reading keys from files, but they do not use a model of the key distribution within the partition. Therefore, we implemented the Radix Spline index and conducted a series of experiments. We expected better results, but during testing we found a niche for the index — up to 100–200 thousand initial records with 30–50 partitions. Under these conditions, it shows competitive results compared to existing Apache Hudi indexes. — explained Stanislav Khomchenko.

To achieve this, the researchers implemented a new type of Radix Spline index in the Apache Hudi Spark client, developed tests to verify the correctness of the implementation, and prepared a benchmark to compare various Hudi indexes under the same conditions. The index was implemented for copy-on-write tables; the current implementation has local search semantics and works with keys that can be represented as non-negative numerical values.

— We implemented construction, freshness verification, reading of the index artifact, and location lookup of a record by key. An experimental benchmark was developed and a test bench was prepared, on which Radix Spline was compared with existing Hudi indexes in terms of write operation time and overhead data volume. A set of unit and integration tests was implemented to verify the main components of the index: key encoding, model construction, artifact writing and reading, index searching, and interaction with the Hudi write process. The test results confirmed the correctness of the implemented solution. Next, an experimental benchmark was implemented that executes the same sequence of write operations for different Hudi indexes. It included initial loading, updating existing records, inserting new records, and a mixed operation of updating with insertion. — Stanislav Khomchenko spoke about the progress of the comparative experimental study.

Experimental data on the execution time of write operations and the size of metadata when using Radix Spline and existing Hudi indexes were obtained during the study. It was found that the strengths of Radix Spline are the fast construction of index artifacts, a positive response to an increase in the number of partitions, and competitiveness with small and medium data volumes during mixed update operations with insertion. At the same time, the current implementation has limitations: during mass updating of existing records, the cost of accessing the index artifact increases, and the amount of metadata turns out to be larger than that of record-level indexes. However, overall the researchers are satisfied with the results of the work, which were then presented at the Maltsev Readings in the section “Algebraic-Logical Methods in Information Technologies” and at the “64th International Scientific Student Conference” in the section “Software Engineering and Knowledge Engineering,” where the work was awarded a Second Degree Diploma.

— The developed index and the obtained results can be used by developers and researchers of storage systems to assess the applicability of learned indexes in Apache Hudi and to advance indexing mechanisms in Data Lakehouse systems., — said Stanislav Khomchenko.