Work stealing for interactive services to meet target latency
Work stealing for interactive services to meet target latency
复制标题
DOI：
10.1145/2851141.2851151
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Jing Li;Kunal Agrawal;S. Elnikety;Yuxiong He;I. Lee;Chenyang Lu;K. McKinley
中科院分区：
文献类型：
--
作者：
Jing Li;Kunal Agrawal;S. Elnikety;Yuxiong He;I. Lee;Chenyang Lu;K. McKinley
交互式Web服务日益推动关键业务工作负载，如搜索、广告、游戏、购物和金融。虽然优化并行程序和分布式服务器系统历来关注平均延迟和吞吐量，但交互式应用的主要指标是一致的响应性，即最小化未达到目标延迟的请求数量。本文首次展示了如何推广工作窃取，以优化具有多个并行请求的交互服务中的目标延迟。工作窃取传统上用于最小化单个并行作业的最大完成时间。我们设计了一种新的自适应工作窃取策略，称为尾部控制，它减少了未命中目标延迟的请求数量。它使用即时请求进度、系统负载和目标延迟来选择何时将请求与窃取并行化、何时接纳新请求以及何时限制大型请求的并行度。我们在英特尔线程构建块(TBB)库中实施了此方法，并在实际工作负载和合成工作负载上对其进行了评估。尾部控制策略大大减少了超过所需目标延迟的请求数量，与各种基准策略相比，可提供高达58%的相对改进。这种针对多个请求的工作窃取的泛化有效地优化了在目标延迟内完成的请求数量，这是交互服务的关键指标。
Interactive web services increasingly drive critical business workloads such as search, advertising, games, shopping, and finance. Whereas optimizing parallel programs and distributed server systems have historically focused on average latency and throughput, the primary metric for interactive applications is instead consistent responsiveness, i.e., minimizing the number of requests that miss a target latency. This paper is the first to show how to generalize work-stealing, which is traditionally used to minimize the makespan of a single parallel job, to optimize for a target latency in interactive services with multiple parallel requests. We design a new adaptive work stealing policy, called tail-control, that reduces the number of requests that miss a target latency. It uses instantaneous request progress, system load, and a target latency to choose when to parallelize requests with stealing, when to admit new requests, and when to limit parallelism of large requests. We implement this approach in the Intel Thread Building Block (TBB) library and evaluate it on real-world workloads and synthetic workloads. The tail-control policy substantially reduces the number of requests exceeding the desired target latency and delivers up to 58% relative improvement over various baseline policies. This generalization of work stealing for multiple requests effectively optimizes the number of requests that complete within a target latency, a key metric for interactive services.