PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Redundancy Techniques for Latency Reduction in Cloud Systems

Gauri Joshi, Emina Soljanin, Gregory Wornell

arXiv:1508.03599v3cs.DCcs.ITmath.IT

TL;DR

Redundancy can reduce latency in cloud systems, but may increase computing-resource costs, leaving unclear when it provides a cost-efficient latency reduction. The paper compares redundancy strategies by their task counts and issuance and cancellation times, using latency-cost analysis of fork-join variants. For log-convex tails, more redundancy reduces both latency and cost; for log-concave tails, early cancellation can reduce both, while more replicas raise cost.

  • Problem

    Redundancy can reduce latency in cloud systems, but may increase computing-resource costs, leaving unclear when it provides a cost-efficient latency reduction.

    Source: §1.1 · p. 1

  • Method

    The paper compares redundancy strategies by their task counts and issuance and cancellation times, using latency-cost analysis of fork-join variants.

    Source: §3.2 · p. 5, §4.1 · p. 5, §4.3 · p. 7

  • Results

    For log-convex tails, more redundancy reduces both latency and cost; for log-concave tails, early cancellation can reduce both, while more replicas raise cost.

    Source: §9 · pp. 21–22

  • Takeaways & Limitations

    For Pareto(1, 2.2) service times, simulations found significant latency reduction versus no redundancy and a better latency-cost trade-off than (n, r, k) partial-fork-join; partial early cancellation further reduced latency.

    Source: §8.3 · p. 21

    For k > 1, the latency estimate is an upper bound, and its largest source of inaccuracy can be especially pronounced for larger k and λ.

    Source: §8.2 · p. 20

Abstract

from arXiv · show

In cloud computing systems, assigning a task to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers, and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps understand when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks, and time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e. log of the tail probability is convex) then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e. log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.

1 INTRODUCTION

Cloud queueing variability makes the slowest task a bottleneck for parallel jobs, while redundancy can reduce latency at added resource cost. The paper studies these trade-offs across fork-join variants, from replicated jobs to general k-of-n completion.

1.1 Motivation

  • Queueing, virtualization, and outages create variable response times, and a parallel job is bottlenecked by its slowest task.The paper frames fast and seamless service as a challenge for cloud systems.Source: §1.1 · p. 1
  • Redundancy can reduce latency by running copies on multiple machines, but it increases computing and network resource use.In cloud services, computing time spent on a job is proportional to machine-rental cost.Source: §1.1 · p. 1

1.2 Organization of this Work

  • The paper focuses on the (n, k) fork-join model, in which a job completes once any k of its n tasks finish.The sections proceed from model setup and preliminary concepts to analyses of increasingly general variants and a practical redundancy strategy.Source: §1.2 · pp. 1–2
  • The paper organizes its latency-cost analysis around full forking to all n servers versus partial forking to a subset of r servers.Table I summarizes the main analysis results by fork-join variant.Source: Table I · p. 2

2 SYSTEM MODEL

The system forks each job into tasks at servers and completes it once k tasks have been served; remaining tasks are canceled. Variants cancel at service start or fork to only a subset, while the paper measures response-time latency and server-time cost.

2.1 Fork-Join Model and its Variants

  • An (n, k) fork-join job completes when any k of its n tasks are served, after which the remaining tasks are canceled and leave their queues.The system has n statistically identical servers, and arriving jobs join first-come first-served queues.Source: §2.1 · p. 2
  • Service times are modeled by a positive random variable X, assumed i.i.d. across tasks and servers; X_k:n denotes the kth smallest of n i.i.d. service times.The paper notes that results, particularly for Section 5, can be extended to correlated service times, which are not considered here.Source: §2.1 · p. 2
  • In fork-early-cancel, redundant tasks are canceled when k tasks reach service; if more than k start simultaneously, k are retained uniformly at random.Unlike ordinary fork-join, cancellation occurs at service start rather than after k tasks finish service.Source: §2.1 · p. 3
  • Partial fork-join sends each job to r > k of the n servers, and cancels redundant tasks once any k finish service.The r servers may be selected by scheduling policies such as random, round-robin, or least-work-left.Source: §2.1 · p. 3

2.2 Latency and Cost Metrics

  • Latency T is job response time, while computing cost C is server time spent serving the job, excluding queueing.The analysis focuses on expected latency E[T], and computing cost is proportional to machine-rental spending in cloud services.Source: §2.2 · pp. 3–4

3 PREVIOUS WORK AND MAIN CONTRIBUTIONS

Earlier redundancy analyses often assumed exponential service times, while rigorous treatment of latency and computing cost for general service distributions remained limited. This paper analyzes both measures and finds that the tail distribution’s log-concavity determines which redundancy choices trade latency against cost.

3.1 Related Previous Work

  • Prior systems work explored redundant straggler replicas, but rigorous analysis of redundancy’s effects on latency and resource cost was limited.Several earlier fork-join analyses assumed exponential service times; practical download traces cited in the paper instead indicate shifted-exponential service times.Source: §3.1 · p. 4

3.2 Main Contributions

  • The paper analyzes general service-time distributions and both latency and computing cost, unlike much prior work focused on exponential service times or systems without queueing.The expected computing cost also supports comparisons of redundancy strategies under high load.Source: §3.2 · p. 5
  • For replicated k=1 systems, early cancellation can reduce latency and cost for log-concave tails, but is not effective for log-convex tails.The analysis identifies log-concavity or log-convexity of the service-time tail as a key factor in choosing a strategy.Source: §3.2 · p. 5
  • For log-convex service-time tails, larger r is optimal for both latency and cost; for log-concave tails, it reduces latency only at low traffic and always raises computing cost.These results concern the (n, r, 1) partial-fork-join system.Source: §3.2 · p. 5
  • The authors develop a general strategy for choosing how many servers to use and when to cancel tasks for service-time distributions that are neither log-concave nor log-convex.Related work includes analyses of redundancy for specific service-time classes and exponential-service fork-join systems.Source: §3.2 · p. 5

4 PRELIMINARY CONCEPTS

The section develops expected server time per job, E[C], as a way to compare symmetric redundancy policies, especially under heavy traffic. It shows how service-time tail shape and replica start times govern cost and latency.

4.1 Using E [C] to Compare Systems

  • For symmetric policies, stability requires λ < n/E[C], and the policy minimizing E[C] gives the lowest expected latency in heavy traffic.E[C] is the expected time servers spend on each job.Source: §4.1 · p. 6

4.2 Log-concavity of ¯FX

  • When log Pr(X > x) is concave or convex, rE[X1:r] is respectively non-decreasing or non-increasing in r; for exponential service it is constant.Shifted exponential service is log-concave, while hyperexponential service is a log-convex example.Source: §4.2 · pp. 6–7

4.3 Relative Task Start Times

  • For a replicated job, relative task start times determine S, the time until the first replica finishes, and computing cost is C = S + Σ(S − t_i)+.Here S is the minimum of the service times offset by their relative start times.Source: §4.3 · p. 7
  • With log-convex service times, simultaneous starts minimize E[C], implying that forking to all n servers is optimal.The section uses the cost result to infer the heavy-traffic strategy.Source: §4.3 · p. 8

5 k = 1 CASE WITHOUT AND WITH EARLY CANCELLATION

For full replication, increasing the number of replicas reduces or preserves latency, but its cost effect depends on the service-time tail. Early cancellation trades replica diversity against server work, with its latency advantage depending on tail shape and traffic.

5.1 Latency-Cost Analysis

  • For any service-time distribution, expected latency is non-increasing with n; expected cost is non-decreasing for log-concave tails and non-increasing for log-convex tails.For log-convex tails, latency and cost can both fall as n increases; for shifted exponential service with a positive shift, they trade off.Source: §5.1 · p. 8
  • When λ scales as λ0n, latency decreases with n for log-convex tails, but increases with n in heavy traffic for log-concave tails.The result concerns arrival rates that grow linearly with the number of servers.Source: §5.1 · p. 9

5.2 Early Task Cancellation

  • Early cancellation maps the system to an M/G/n queue and uses less computing cost for log-concave tails, but is ineffective for log-convex tails.Each job has one task served by the first server that becomes idle; E[C] equals E[X].Source: §5.2 · pp. 9–10
  • For log-concave service times, early cancellation raises latency at low λ but lowers it at high λ; for log-convex service times, it raises latency in both regimes.With shifted exponential service, early cancellation is more favorable as the constant shift grows and task service becomes more deterministic.Source: §5.2 · pp. 10–11

6 PARTIAL FORKING (k = 1 CASE)

Partial forking sends a job to r of n servers, with server choice determining replica start times. The section derives cost bounds and identifies how tail shape, traffic, and start-time patterns affect the choice of r and scheduling policy.

6 PARTIAL FORKING (k = 1 CASE)

  • Group-based random assigns jobs to groups of r servers, while uniform random chooses any r servers; for group-based random, each group behaves as an independent (r, 1) fork-join system.The section also bounds expected cost for other symmetric policies, whose tasks can start at different times.Source: §6 · p. 11, §6.1 · p. 12

6.1 Latency-Cost Analysis

  • For log-concave tails, r = 1 minimizes cost; for log-convex tails, r = n does, and these choices give the lowest heavy-traffic latency.For group-based random, the replica count minimizing rE[X1:r] gives the highest service capacity.Source: §6.1 · p. 12, §6.2 · p. 14

6.2 Optimal value of r

  • In low traffic, r = n gives the lowest latency for any service-time distribution; in heavy traffic, r = 1 is best for log-concave tails and r = n for log-convex tails.With a replica limit, r = rmax is optimal for log-convex tails, while r = 1 is optimal for log-concave tails in heavy traffic.Source: §6.2 · pp. 14–15

6.3 Choice of the r servers

  • For fixed r, simultaneous starts lower cost and heavy-traffic latency for log-convex tails, while staggered starts lower both for log-concave tails.In low traffic, uniform random selection gives lower latency than group-based selection for any service-time distribution.Source: §6.3 · p. 15

7 THE GENERAL k CASE

For the general k case, the paper bounds latency and cost in fork-join systems and examines how choosing k trades off redundancy diversity against parallelism. It also analyzes early cancellation and compares scheduling policies across service-time distributions.

7 THE GENERAL k CASE

  • With log-concave service times, uniform random scheduling gives lower E [T] for all λ; with log-convex times, group-based scheduling is better at high λ.The comparisons use n = 6 and r = 3.Source: Figure 14 · p. 16, Figure 15 · p. 16

7.1 Latency and Cost of the (n, k) fork-join system

  • For general k, the paper provides bounds on fork-join latency and computing cost.The latency upper bound becomes looser as k increases; for k = n, Lemma 8 supplies a tighter upper bound.Source: §7.1 · pp. 16–17
  • For k = n, Lemma 8 tightens the latency upper bound; the Theorem 4 upper bound grows looser as k increases.The bound comparison with simulations is shown for Pareto service time, n = 10, and λ = 0.5.Source: §7.1 · p. 16, Figure 16 · p. 17
  • The cost bounds are tight at k = 1 and k = n for the Pareto-service-time simulation.The simulation uses n = 10 and λ = 0.5.Source: §7.1 · p. 17, Figure 17 · p. 17

7.2 Diversity-Parallelism Trade-off

  • As k rises, smaller tasks increase parallelism while fewer redundant tasks reduce diversity; the latency-minimizing k shifts upward as ∆ increases.The simulations use shifted-exponential service times with ∆k = ∆/k; Fig. 18 plots expected latency and Fig. 19 expected cost.Source: §7.2 · p. 18, Figure 18 · p. 18, Figure 19 · p. 18
  • In the low-traffic limit, the latency-minimizing k balances a parallelism term that falls with k against a diversity term that rises with k.The bounds coincide as λ → 0 for shifted-exponential service times.Source: §7.2 · p. 18
  • In heavy traffic, the k that minimizes E [C] also minimizes E [T].The cost-versus-k simulation shows the diversity-parallelism trade-off.Source: §7.2 · p. 18, Figure 19 · p. 18

7.3 Latency and Cost of the (n, k) fork-early-cancel system

  • For log-convex service-time tails, the (n, k) fork-early-cancel system is always worse than fork-join under the paper’s cost-bound comparison.The inference compares the early-cancel cost kE [X] with the fork-join upper bound in (20).Source: §7.3 · p. 19

8 GENERAL REDUNDANCY STRATEGY

The proposed strategy selects redundancy parameters under computing- and network-cost constraints, including for arbitrary service-time distributions or empirical traces. Simulations show a favorable latency-cost trade-off, while the estimates used to choose parameters have stated accuracy limitations.

8 GENERAL REDUNDANCY STRATEGY

  • The strategy is intended for arbitrary service-time distributions and can use empirical traces when the distribution or its order statistics lack closed-form expressions.It builds on insights for log-concave and log-convex service times.Source: §8 · p. 19, §8.2 · p. 20

8.1 Generalized Fork-join Model

  • The generalized (n, rf, r, k) system launches tasks to rf servers, cancels extras once r tasks reach queue heads or service, and cancels remaining tasks once k finish.Early-canceled tasks help identify the r queues with least work left, while waiting for k of the retained tasks provides service-time diversity.Source: §8.1 · p. 19

8.2 Choosing Parameters rf and r

  • The strategy minimizes estimated latency over rf and r subject to computing-cost and network-cost limits, using estimates that can also be obtained from empirical service-time traces.It conjectures setting rf to the maximum allowed by the network constraint, then chooses r by minimizing estimated latency subject to the constraints.Source: §8.2 · p. 20
  • For k > 1, the latency estimate is an upper bound whose looseness grows with k; estimates also abstract from rf and variations in relative task start times.Actual latency and cost can therefore differ from estimates; the actual computing cost is below Ĉ(r) for log-concave tails and above it for log-convex tails.Source: §8.2 · p. 20

8.3 Simulation Results

  • The proposed strategy achieves a better latency-cost trade-off than the partial-fork-join system in the Pareto simulation, with Fig. 20 describing it as close to the best such system.The simulation also reports a significant latency reduction over no redundancy; its constraints are E[C] ≤ 5 and rf ≤ 8.Source: §8.3 · p. 21, Figure 20 · p. 21
  • For the equal-probability exponential and shifted-exponential mixture, cost does not always rise with redundancy, and the strategy selects rf = r = 5 under the network constraint.With rf = r, the selected configuration coincides with the partial-fork-join system.Source: §8.3 · p. 21, Figure 21 · p. 21

9 CONCLUDING REMARKS

The paper identifies service-time tail log-concavity as a key factor in the latency-cost trade-off of redundancy. It also proposes a strategy for arbitrary distributions, including cases where only empirical traces are available.

9 CONCLUDING REMARKS

  • For log-convex service times, more redundancy reduces both latency and cost, whereas for log-concave service times, latency reduction can require higher cost.For log-concave service times, the paper also states that larger r reduces latency only in the low-traffic regime and always increases computing cost.Source: §9 · p. 21
  • Early cancellation can save both latency and cost for log-concave service times, but is not effective for log-convex service times.Source: §9 · p. 22
  • The proposed general redundancy strategy applies to arbitrary service-time distributions and can use empirical traces when a closed-form distribution is unavailable.Source: §9 · p. 22

A LOG-CONCAVITY OF ¯FX

This appendix states properties of the service-time tail that follow from log-concavity or log-convexity. It relates those conditions to residual life, hazard rates, coefficient of variation, and examples of distributions.

A LOG-CONCAVITY OF ¯FX

  • Log-concavity of the tail means its logarithm is concave, giving the tail-probability inequality in (29); the inequality reverses for log-convex tails.The appendix distinguishes tail log-concavity from density log-concavity, noting that log-convexity of a density does not always imply log-convexity of the CDF or tail.Source: A LOG-CONCAVITY OF ¯FX · p. 22
  • For log-concave tails, mean residual life is non-increasing and the hazard rate is non-decreasing; both directions reverse for log-convex tails.Source: A LOG-CONCAVITY OF ¯FX · p. 23
  • The coefficient of variation is at most 1 for log-concave service times and at least 1 for log-convex service times, equaling 1 for pure exponential service.Source: A LOG-CONCAVITY OF ¯FX · p. 24
  • A uniform distribution over any convex set is listed as an example of a distribution with a log-concave tail.Source: A LOG-CONCAVITY OF ¯FX · p. 24
  • Examples of log-convex tails include hyperexponential, Weibull with shape 0 < c < 1, and gamma with shape 0 < c < 1 distributions.Source: A LOG-CONCAVITY OF ¯FX · p. 24

B PROOFS FOR THE k = 1 Case

For the k = 1 case, the proofs express computing cost through task start times and bound it relative to single-task and fully replicated service. The direction of the cost inequalities depends on whether the service-time tail is log-concave or log-convex.

B PROOFS FOR THE k = 1 Case

  • When only r tasks are invoked, the relative start times of tasks r+1 through n are set to infinity in the cost expression.The proof first expresses C in terms of relative task start times and S.Source: B PROOFS FOR THE k = 1 Case · p. 24
  • The cost expression sums the time the first task runs and the additional service time after each later task starts until the first of r tasks finishes.S is the time from the earliest task's service start until any of the r tasks finishes.Source: B PROOFS FOR THE k = 1 Case · p. 24
  • For log-concave service-time tails, E[C] ≥ E[X] and E[C] ≤ rE[X1:r]; the inequalities reverse for log-convex tails.The proof relates these bounds to the signs of terms in the cost expression.Source: B PROOFS FOR THE k = 1 Case · pp. 25–26
  • For log-concave tails, the proof obtains the cost bounds by showing terms in its rearranged integral sum are positive; the proof reverses the inequalities for log-convex tails.The derivation splits integrals, changes variables, and regroups terms before applying the tail-shape property.Source: B PROOFS FOR THE k = 1 Case · pp. 25–26

C PROOFS FOR GENERAL k

For general k, the proofs derive latency bounds using queueing comparisons and bound computing cost through the timing of task starts and cancellations. Early cancellation achieves lower latency than a no-redundancy partial-fork system at the same expected task arrival rate per server.

C PROOFS FOR GENERAL k

  • The split-merge comparison gives an upper latency bound using an M/G/1 queue with service time Xk:n; a separate construction yields a lower bound.The lower-bound construction has preceding jobs require one task, then adds E[Xk:n] to the waiting-time bound.Source: C PROOFS FOR GENERAL k · pp. 26–27
  • For the full-fork latency bound, associated response times support comparison with independent variables when k = n, but that argument does not extend to k < n.The limitation is that the expected-maximum property for associated variables does not hold for the kth order statistic when k < n.Source: C PROOFS FOR GENERAL k · p. 27
  • At least n−k+1 tasks start together after the previous job's kth completion cancels its remaining n−k tasks.The cost-bound proof separates the k−1 tasks that may start early from the n−k+1 that start together, then derives upper and lower bounds from those groups.Source: C PROOFS FOR GENERAL k · p. 27
  • In the (n, k) fork-early-cancel system, exactly k tasks are served, so expected computing cost is kE[X].Tasks not needed for completion are canceled before service begins.Source: C PROOFS FOR GENERAL k · p. 27
  • At the same expected per-server task arrival rate, the (n, k) fork-early-cancel system has lower latency than the no-redundancy (n, k, k) partial-fork system.The n−k redundant tasks provide diversity that helps find the k shortest queues.Source: C PROOFS FOR GENERAL k · p. 27
Loading 1508.03599v3…