Reducing Latency via Redundant Requests
Open Access
- 15 June 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 43 (1) , 347-360
Abstract
Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However there is no exact analysis of systems with redundancy. This paper presents the first exact analysis of systems with redundancy. We allow for any number of classes of redundant requests, any number of classes of non-redundant requests, any degree of redundancy, and any number of heterogeneous servers. In all cases we derive the limiting distribution on the state of the system. In small (two or three server) systems, we derive simple forms for the distribution of response time of both the redundant classes and non-redundant classes, and we quantify the "gain" to redundant classes and "pain" to non-redundant classes caused by redundancy. We find some surprising results. First, the response time of a fully redundant class follows a simple Exponential distribution and that of the non-redundant class follows a Generalized Hyperexponential. Second, fully redundant classes are "immune" to any pain caused by other classes becoming redundant. We also compare redundancy with other approaches for reducing latency, such as optimal probabilistic splitting of a class among servers (Opt-Split) and Join-the-Shortest-Queue (JSQ) routing of a class. We find that, in many cases, redundancy outperforms JSQ and Opt-Split with respect to overall response time, making it an attractive solution.Keywords
Funding Information
- Research Council of Finland (268992)
- Intel Science and Technology Center for Cloud Computing
- National Science Foundation (DGE-1252522,CMMI-1334194,CSR-1116282)
- Google (2015/16)
This publication has 27 references indexed in Scilit:
- The tail at scaleCommunications of the ACM, 2013
- Analysis of the fork-join queueIEEE Transactions on Computers, 1989
- Power Series for Stationary Distributions of Coupled Processor ModelsSIAM Journal on Applied Mathematics, 1988
- A distributional form of Little's LawOperations Research Letters, 1988
- Approximate analysis of fork/join synchronization in parallel queuesIEEE Transactions on Computers, 1988
- Characterizations of generalized hyperexponential distribution functionsCommunications in Statistics. Stochastic Models, 1987
- Two Parallel Queues Created by Arrivals with Two Demands IISIAM Journal on Applied Mathematics, 1985
- Two Parallel Queues Created by Arrivals with Two Demands ISIAM Journal on Applied Mathematics, 1984
- Processor-sharing of two parallel linesJournal of Applied Probability, 1981
- Two coupled processors: The reduction to a Riemann-Hilbert problemProbability Theory and Related Fields, 1979