FT-INDEX: A distributed indexing scheme for switch-centric cloud storage system

Nowadays, cloud storage systems may contain tens of thousands of servers and large scale data sets, which significantly require efficient data management scheme and query processing mechanism. To fulfill these requirements in modern data centers, the infrastructure of cloud systems, we propose FT-Index, a secondary indexing scheme for cloud system with switch-centric topology. FT-Index has a two-layer design. The upper-layer index, called global index, is distributed across different hosts in the system, while the lower-layer index, named local index, is a B+-tree for local query. We further adopt the Interval tree to reorganize the global index and propose two versions of FT-Index with different publishing methods to lower the rate of false positives and reduce the cost of forwarding queries. We provide detailed theoretical analysis on the upper bound of false positives, physical hops per query, and the relationship between them. We also conduct abundant experiments to validate the efficiency of FT-Index.