Foresight Indexing: Accelerating B+tree Index with Programmable Switches on the Network Path

Abstract

The B+tree indexing scheme is widely employed in file systems and database systems. Modern data centers often adopt a disaggregated architecture, where compute servers and storage servers are deployed on separate machines connected via a network. Storage servers typically rely on B+tree-based indexing. However, with the rapid growth in network bandwidth, the bottleneck has shifted from the network to the indexing, challenging the scalability of these systems. In this paper, we present ForeIn, a novel architecture that offloads part of the storage indexing process to programmable switches within the network path. Specifically, we make three key contributions. First, we develop the PrefixCover algorithm, which converts a B+tree query into a longest prefix match query. This transformation allows partial deployment of B+tree operations in the switches at line rate. Second, we propose a greedy algorithm that dynamically adapts the PrefixCover algorithm to the resource constraints of programmable switches. Third, we design a data plane leveraging programmable switch capabilities, ensuring consistency between servers and switches with minimal overhead and minimal device modifications. We implement ForeIn on a testbed and conduct extensive experiments. Results demonstrate that ForeIn improves the throughput of B+tree-based storage servers by an average of 1.2 times. The source code is publicly available on GitHub [1].