Resource-Efficient Index Shard Replication in Large Scale Search Engines
Resource-Efficient Index Shard Replication in Large Scale Search Engines
复制标题
大规模搜索引擎中资源高效的索引分片复制
DOI：
10.1109/tpds.2019.2924423
复制
发表时间：
2019-12
影响因子：
5.3
通讯作者：
Gang Wang
中科院分区：
文献类型：
--
作者：
Yusen Li;Xueyan Tang;Wentong Cai;Jiancong Tong;Xiaoguang Liu;Gang Wang
随着Web规模的迅速增长，大型搜索引擎不得不建立大量的机器来放置Web内容的索引文件。索引文件通常被划分为较小的索引分片，这些索引分片通常被复制，以便可以并行处理查询。我们从真实的系统中观察到，索引分片复制策略可能对资源使用产生重大影响。在本文中，我们研究的索引碎片复制问题的目标是最大限度地减少资源使用的搜索引擎中心。我们考虑离线版本和在线版本的问题，并制定了非线性整数规划问题。我们提出了几种启发式算法来近似最优解。所提出的算法进行了广泛的实验，使用合成数据和商业搜索引擎的真实的数据进行评估。实验结果验证了所提算法的有效性。我们的工作还产生了许多见解的影响，不同的输入属性对每个算法的性能。我们相信，本文将提供有价值的指导，在实践中的索引分片复制策略的设计。
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.
登录
查看更多内容
DOI：
--
发表时间：
2011
期刊：
--
影响因子：
--
作者：
R. Panigrahy;Kunal Talwar;Lincoln K. Uyeda;Udi Wieder
通讯作者：
R. Panigrahy;Kunal Talwar;Lincoln K. Uyeda;Udi Wieder
DOI：
10.1145/1526709.1526764
发表时间：
2009-04
期刊：
--
影响因子：
--
作者：
Hao Yan;Shuai Ding;Torsten Suel
通讯作者：
Hao Yan;Shuai Ding;Torsten Suel
DOI：
10.1007/978-3-319-16354-3_13
发表时间：
2015-03
期刊：
--
影响因子：
--
作者：
L. Ostroumova;Yury Ustinovsky;E. Samosvat;Damien Lefortier;P. Serdyukov
通讯作者：
L. Ostroumova;Yury Ustinovsky;E. Samosvat;Damien Lefortier;P. Serdyukov
影响因子：
2.5
作者：
Yubin Kim;Jamie Callan;J. Culpepper;Alistair Moffat
通讯作者：
Yubin Kim;Jamie Callan;J. Culpepper;Alistair Moffat
DOI：
10.1145/2505515.2505710
发表时间：
2013-10
期刊：
Proceedings of the 22nd ACM international conference on Information & Knowledge Management
影响因子：
--
作者：
Amin Y. Teymorian;O. Frieder;M. Maloof
通讯作者：
Amin Y. Teymorian;O. Frieder;M. Maloof