Source-linked AI summary
Low latency via redundancy
Ashish Vulimiri, P. Brighten Godfrey, Radhika Mittal, Justine Sherry, Sylvia Ratnasamy, Scott Shenker
TL;DR
Interactive networked applications need low latency, especially at the tail, but the conditions under which redundancy improves latency are not well understood. The paper analyzes the tradeoff between faster redundant responses and added utilization, then evaluates redundancy in DNS, databases, and packet forwarding, finding substantial latency benefits in a broad class of systems while identifying cost-limited cases.
Problem
The conditions under which redundancy effectively reduces latency, especially tail latency, are not well understood.
Method
The paper combines queueing analysis of replication’s latency-utilization tradeoff with empirical evaluations in DNS, database, and packet-forwarding applications.
Results
Redundancy substantially reduces mean and tail latency in multiple applications, including 6.5× fewer DNS responses later than 500 ms and 50× fewer later than 1.5 sec.
Takeaways & Limitations
Redundancy can convert extra capacity into lower latency and should be applied selectively where performance or cost-effectiveness improves.
Takeaways & Limitations
Replication ceases to help when client-side overhead is a significant fraction of mean service time, including very large files or in-memory databases.
Abstract
from arXiv · showhide
Low latency is critical for interactive networked applications. But while we know how to scale systems to increase capacity, reducing latency --- especially the tail of the latency distribution --- can be much more difficult. In this paper, we argue that the use of redundancy is an effective way to convert extra capacity into reduced latency. By initiating redundant operations across diverse resources and using the first result which completes, redundancy improves a system's latency even under exceptional conditions. We study the tradeoff with added system utilization, characterizing the situations in which replicating all tasks reduces mean latency. We then demonstrate empirically that replicating all operations can result in significant mean and tail latency reduction in real-world systems including DNS queries, database servers, and packet forwarding within networks.
1. INTRODUCTION
The paper argues that redundancy can reduce mean and tail latency by issuing operations across diverse resources and using the first completed result, while characterizing when its added utilization is worthwhile. It supports this argument with queueing analysis and applications spanning DNS, databases, and packet forwarding.
- Motivation: Redundancy issues an operation multiple times across diverse resources and uses the first completed result, reducing latency under unpredictable delays or failures.Replicated DNS queries can mask cache misses, congestion, packet loss, and slow servers.
- Research question: The paper studies when redundancy’s latency benefit outweighs the utilization cost of duplicated work.Its queueing model analyzes expected response time as a function of utilization and server-side service-time distribution.
- Analysis: A server-side threshold load below which replication always improves latency is conjectured to lie between 25% and 50% utilization, approaching 50% as service-time variance increases.The claim assumes client-side replication cost is low.
- Applications: DNS replication reduces responses later than 500 ms by 6.5× and those later than 1.5 sec by 50× versus querying the best individual DNS server.The improvement exceeds the estimated threshold cost-effectiveness by more than an order of magnitude.
- Applications: Database replication provides up to 2× mean and 8× tail latency reduction when most queries are disk-served and files are small, but not for large or in-memory files.Mean latency is reduced up to a server-side threshold load of 30-40%.
- Applications: Packet replication can yield up to a 38% median end-to-end latency reduction for short flows, while duplicated work is presented as a way to improve robustness to variable conditions.The strategy replicates initial packets as lower priority to limit the negative effect of increased utilization.
2. SYSTEM VIEW
The system view models redundancy as a tradeoff between taking the fastest of multiple responses and increasing utilization. It evaluates this interaction through an abstract queueing model and simulations across service-time distributions.
- System view: The system designer’s tradeoff is between the faster response among redundant options and the extra work that increases utilization.The analysis focuses on a fixed set of resources.
- Model: The queueing model assumes N independent identical servers, Poisson arrivals, and k copies of each request enqueued at randomly selected servers.Initial analysis treats redundancy as free for clients apart from increased server utilization.
- Queueing analysis: Figure 1 compares response times as load varies under deterministic and Pareto (α = 2.1) service-time distributions.The measured response time includes queueing delay plus service time.
- Queueing analysis: Replication improves mean latency and can reduce the 99.9th percentile by 5× under Pareto service times, but beyond a threshold load its added utilization overwhelms the benefit.The threshold is higher when service-time distributions are more variable.
- Metric: The threshold load is defined as the largest utilization below which replication always improves mean response time.The paper investigates its dependence on service-time distributions analytically and through simulations.
1. If redundancy adds no client-side cost
With negligible client-side overhead, redundancy improves latency below a server-side threshold, with larger gains when service times are more variable; client overhead can eliminate the benefit.
- Higher service-time variability generally produces larger latency improvements from redundancy.Figure 2 validates this trend across Pareto, Weibull, and two-point distribution families.
- 33% is the threshold load for exponentially distributed service times.
- A queueing model approximates replicated response time by doubling arrival load and taking the minimum of independent server response times.For k = 2, the independence approximation has worst-case simulation error of 3% at N = 10 and less than 0.1% at N = 20.
- Replication’s threshold load cannot exceed 50%, while simulations and analysis support a lower bound above 25%.Heavy-tailed, high-variance distributions can approach the 50% upper bound; deterministic service time is conjectured to be worst for replication, with an approximately 26% threshold.
- Client-side overhead can lower the threshold below 25% and can completely negate mean-latency improvement when it is comparable to server service time.If replication overhead equals mean latency, mean latency cannot improve, although tail latency may still improve.
3. INDIVIDUAL VIEW
In elastic-resource settings, replication can substantially reduce latency, but its cost-effectiveness depends on the metric and the overhead of contacting additional resources.
- Connection establishment: Assuming independent packet losses, sending duplicate handshake packets reduces the loss probability from p to p^2.The three handshake packets are attractive replication targets because they contribute little traffic but have high loss penalties.
- Connection establishment: Replication can reduce TCP-handshake completion time by at least 25 ms in expectation and at least 880 ms at the 99.9th percentile.The modeled benefit increases with RTT and arises from duplicating all three handshake packets.
- Connection establishment: The estimated TCP-handshake savings correspond to roughly 170-6000 ms/KB, exceeding the cost-effectiveness threshold by more than an order of magnitude in the mean and two orders in the tail.The paper cautions that the benchmark comparison is imprecise and merits more rigorous study.
- DNS: Querying 10 DNS servers reduces responses later than 500 ms by 6.5× and those later than 1.5 sec by 50× versus the best individual server.Across 15 PlanetLab nodes, 10-server replication also yields 50-62% response-time reduction across metrics compared with the best fixed server.
- DNS: For DNS, contacting more than 5 servers is not economically justified for mean latency, whereas 10 or more remains useful for the 99th percentile.The recommended number depends on whether mean or tail performance is prioritized.
- DNS: Multiple DNS queries increase caching as a side benefit, but the paper leaves that effect unquantified.This additional caching benefit is identified as an open measurement opportunity.
4. RELATED WORK
The paper distinguishes its general characterization of redundancy from prior work focused on specialized systems or lacking analysis of utilization effects.
- Existing uses: Prior systems used replication for reliability, distributed-job response time, straggler mitigation, DHT queries, and specialized network transmissions.These examples establish that redundancy was already applied across several domains before this paper’s broader treatment.
- Prior limitations: Earlier Google-related work studied specific systems with capabilities such as canceling partially completed requests, but not total-utilization effects.The paper contrasts its broader resource-utilization analysis with those system-specific assumptions.
- Prior limitations: MONET replicated connection-establishment requests and DNS queries, while this paper reports benefits even without path diversity.The cited comparison concerns parallel first-response selection in both contexts.
- Prior limitations: The authors’ earlier workshop paper advocated redundancy but did not characterize when it helps or study optimization of fixed resources.This paper presents those missing analyses as part of its broader contribution.
- This paper: This paper aims to demonstrate redundancy as a general technique by characterizing when it is useful and quantifying gains across applicable use cases.Its contribution spans both conditions for usefulness and empirical performance improvements.
5. CONCLUSION
The paper combines an abstract tradeoff analysis with empirical evaluations showing that redundancy can substantially benefit latency across practical applications.
- Conclusion: The study finds that redundancy can have a net positive impact in a large class of systems despite the overhead it induces.This conclusion follows from an abstract characterization of latency reduction versus overhead cost.
- Conclusion: Empirical results confirm significant redundancy benefits in practical applications spanning both wide-area and data-center settings.The conclusion presents these findings as evidence that redundancy is a powerful technique.