Work stealing for interactive services to meet target latency

Jing Li, Kunal Agrawal, Sameh Elnikety, Yuxiong He, I. Ting Angelina Lee, Chenyang Lu, Kathryn S. McKinley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

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 tailcontrol, 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.

Original languageEnglish (US)
Title of host publication21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 - Proceedings
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450340922
DOIs
StatePublished - Feb 27 2016
Externally publishedYes
Event21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 - Barcelona, Spain
Duration: Mar 12 2016Mar 16 2016

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
Volume12-16-March-2016

Other

Other21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016
CountrySpain
CityBarcelona
Period3/12/163/16/16

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Work stealing for interactive services to meet target latency'. Together they form a unique fingerprint.

Cite this