权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

III: Small: Index Sharding and Query Routing in Distributed Search Engines

III：小：分布式搜索引擎中的索引分片和查询路由

基本信息

批准号：
1718680
负责人：
Torsten Suel
金额：
$ 50万
依托单位：
New York University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-08-01 至 2021-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718680&HistoricalAwards=false
关键词：
III Small Index Sharding Query

项目摘要

Large web search engines now receive billions of search requests per day that are evaluated over hundreds of billions of documents, leading to significant advertising revenue for the engines and many benefits for the overall economy. To process these queries with sub-second latencies, search engines deploy millions of computing cores housed in multiple large and geographically distributed data centers. This project will propose and investigate new techniques for partitioning and replicating document and index data across such systems, and for routing search requests to the data, with the goal of improving query processing efficiency and reducing hardware and energy costs. The work will result in a better understanding of the basic data partitioning and load balancing problems in such systems, and also has the potential to lead to significant economic benefits for existing and future search systems in terms of reduced hardware and energy costs. In addition, the project will support the training of a number of graduate and undergraduate students in search engine technology, a critical expertise sought by many employers. The planned research activities can be divided into two parts. The first part will focus on index sharding and tiering techniques, i.e., how to assign documents and index data to shards and tiers using clustering and index reordering techniques, and how to route queries to shards and tiers for efficient query processing. Here the goal is to minimize overall average query processing costs, without considering issues such as load balancing between machines, queuing delays, and resulting query latencies. The second part will focus on shard assignment and replication and on query routing, i.e., how to assign and replicate shards over machines, and how to adaptively route queries to shard replicas, in order to achieve increased query throughput across a range of realistic service level agreements (SLAs) on query latencies and result quality. Here the focus is on studying the basic load balancing problems arising in large search architectures, and on performing an end-to-end evaluation of the new index sharding and tiering techniques from the first part, to show that they can satisfy realistic latency and quality constraints with state-of-the-art load balancing methods.

大型网络搜索引擎现在每天接收数十亿个搜索请求，这些请求在数千亿个文档中进行评估，为引擎带来了可观的广告收入，并为整体经济带来了许多好处。为了以亚秒级的延迟处理这些查询，搜索引擎部署了数百万个位于多个大型地理分布数据中心的计算核心。该项目将提出和研究新技术，用于在这些系统中划分和复制文档和索引数据，并将搜索请求路由到数据，目的是提高查询处理效率，降低硬件和能源成本。这项工作将导致更好地了解在这样的系统中的基本数据划分和负载平衡问题，也有可能导致显着的经济效益，为现有的和未来的搜索系统在减少硬件和能源成本。此外，该项目还将支持对一些研究生和本科生进行搜索引擎技术方面的培训，这是许多雇主寻求的一项关键专业知识。计划中的研究活动可分为两个部分。第一部分将重点介绍索引分片和分层技术，即，如何使用聚类和索引重新排序技术将文档和索引数据分配到分片和层，以及如何将查询路由到分片和层以实现高效的查询处理。这里的目标是最小化总体平均查询处理成本，而不考虑机器之间的负载平衡、排队延迟和最终查询延迟等问题。第二部分将关注分片分配和复制以及查询路由，即，如何在机器上分配和复制分片，以及如何自适应地将查询路由到分片副本，以便在一系列关于查询延迟和结果质量的现实服务级别协议（SLA）上实现增加的查询吞吐量。这里的重点是研究大型搜索架构中出现的基本负载平衡问题，并对第一部分中的新索引分片和分层技术进行端到端评估，以表明它们可以满足现实的延迟和质量约束。