Few-to-Many: Incremental Parallelism for Reducing Tail Latency in Interactive Services ⇤

Interactive services, such as Web search, recommendations, games, and finance, must respond quickly to satisfy cus-tomers. Achieving this goal requires optimizing tail (e.g., 99th+ percentile) latency. Although every server is multi-core, parallelizing individual requests to reduce tail latency is challenging because (1) service demand is unknown when requests arrive; (2) blindly parallelizing all requests quickly oversubscribes hardware resources; and (3) parallelizing the numerous short requests will not improve tail latency. This paper introduces Few-to-Many (FM) incremental parallelization, which dynamically increases parallelism to reduce tail latency. FM uses request service demand pro-files and hardware parallelism in an offline phase to com-pute a policy, represented as an interval table, which spec-ifies when and how much software parallelism to add. At runtime, FM adds parallelism as specified by the interval ta-ble indexed by dynamic system load and request execution time progress. The longer a request executes, the more paral-lelism FM adds. We evaluate FM in Lucene, an open-source enterprise search engine, and in Bing, a commercial Web search engine. FM improves the 99th percentile response time up to 32 % in Lucene and up to 26 % in Bing, compared to prior state-of-the-art parallelization. Compared to running requests sequentially in Bing, FM improves tail latency by a factor of two. These results illustrate that incremental paral-lelism is a powerful tool for reducing tail latency