Recently several works proposed new approaches on how advancements in machine learning can be used to improve indexing strategies on sorted data. This led to the SOSD benchmark, which enabled having a baseline for evaluating different competitors in a standardized way. At the same time, with a wider adoption of network programmability through P4, a trend towards outsourcing computationally intensive procedures to programmable switches started. Our goal is to combine these two advancements and evaluate possibilities of further leveraging the performance of learned indexing algorithms by using the power of network programmability.
After careful evaluation, we come to the decision that we continue our work focusing on the learned indexing algorithm RMI, which suits our idea of implementing parts of it over the network best. Indeed, we find that the P4 specification allows an implementation of the lookup part of RMI on the switch and attains perfect accuracy when tested on simulated network hardware. At this point we analyze how far away our theoretical implementation is, from actually running on real world hardware and find that there is a long way to go. From this result we then generalize our solution to any dataset and arbitrary RMI configuration by adapting the code generation part of the RMI reference implementation to output P4 source code files. We finally conclude our work by coming up with a strategy to, even though having a theoretical implementation, estimate how much our idea of outsourcing RMI calculations to the network could benefit a closed system. We find that we could save around 50-100ns per lookup per last-mile search worker, which would result in a constant speed up that scales horizontally with the amount of last-mile search workers available to a single switch. In comparison to a full RMI calculation and depending on configuration, this would provide a speed up of 10% to 50% per last-mile search worker.
The proposed RMI-P4 implementation can be found here.
Additionally the RMI reference implementation can be found here.
Finally the original SOSD benchmark can be found here.