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

New York University, New York NY

Investigators

Abstract

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.