Adaptive Parallelism for Web Search

A web search query made to Microsoft Bing is currently par-allelized by distributing the query processing across many servers. Within each of these servers, the query is, however, processed sequentially. Although each server may be pro-cessing multiple queries concurrently, with modern multi-core servers, parallelizing the processing of an individual query within the server may nonetheless improve the user’s experience by reducing the response time. In this paper, we describe the issues that make the parallelization of an in-dividual query within a server challenging, and we present a parallelization approach that effectively addresses these challenges. Since each server may be processing multiple queries concurrently, we also present a adaptive resource management algorithm that chooses the degree of paral-lelism at run-time for each query, taking into account system load and parallelization efficiency. As a result, the servers now execute queries with a high degree of parallelism at low loads, gracefully reduce the degree of parallelism with in-creased load, and choose sequential execution under high load. We have implemented our parallelization approach and adaptive resource management algorithm in Bing servers and evaluated them experimentally with production work-loads. The experimental results show that the mean and 95th-percentile response times for queries are reduced by more than 50 % under light or moderate load. Moreover, under high load where parallelization adversely degrades the sys-tem performance, the response times are kept the same as when queries are executed sequentially. In all cases, we ob-serve no degradation in the relevance of the search results