Resource-Efficient Index Shard Replication in Large Scale Search Engines

Yusen Li, Xueyan Tang, Wentong Cai, Jiancong Tong, Xiaoguang Liu, Gang Wang

Abstract

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice.
BibTeX
@article{li2019resource,
  author = {Yusen Li and Xueyan Tang and Wentong Cai and Jiancong Tong and Xiaoguang Liu and Gang Wang},
  title = {{Resource-Efficient Index Shard Replication in Large Scale Search Engines}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2019},
  doi = {10.1109/tpds.2019.2924423},
}

Loading related content...

Figure