PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Straggler Replication in Large-scale Parallel Computing

Da Wang, Gauri Joshi, Gregory Wornell

arXiv:1503.03128v3cs.DC

TL;DR

Straggler tasks can bottleneck large parallel jobs, yet replication’s latency and computing-cost effects have received limited mathematical analysis. The paper analyzes replication choices and estimates performance from empirical task-time distributions. It identifies regimes where replicating a small fraction of tasks can reduce latency and computing cost together.

  • Problem

    The latency and computing-cost effects of replication in jobs with many parallel tasks have received limited mathematical analysis.

    Source: §1 · p. 1

  • Method

    The paper analyzes replication policies across the fraction of stragglers, replica count, and whether the original copy is kept, and proposes bootstrapping to estimate latency and cost from empirical execution-time distributions.

    Source: §1.2 · p. 2, §4 · p. 9, §5.1 · p. 13

  • Results

    The analysis identifies regimes where replicating a small fraction of stragglers can drastically reduce latency and computing cost simultaneously.

    Source: §5.1 · p. 13

  • Takeaways & Limitations

    The characterized latency–cost trade-off can guide scheduling-policy optimization according to users’ sensitivity to latency and computing cost.

    Source: §1.2 · p. 2

    The analysis focuses on single-fork policies; multifork policies may improve the latency–cost trade-off but add delay and complexity in obtaining and terminating replicas.

    Source: §2.3 · p. 4

Abstract

from arXiv · show

In a cloud computing job with many parallel tasks, the tasks on the slowest machines (straggling tasks) become the bottleneck in the job completion. Computing frameworks such as MapReduce and Spark tackle this by replicating the straggling tasks and waiting for any one copy to finish. Despite being adopted in practice, there is little analysis of how replication affects the latency and the cost of additional computing resources. In this paper we provide a framework to analyze this latency-cost trade-off and find the best replication strategy by answering design questions such as: 1) when to replicate straggling tasks, 2) how many replicas to launch, and 3) whether to kill the original copy or not. Our analysis reveals that for certain execution time distributions, a small amount of task replication can drastically reduce both latency as well as the cost of computing resources. We also propose an algorithm to estimate the latency and cost based on the empirical distribution of task execution time. Evaluations using samples in the Google Cluster Trace suggest further latency and cost reduction compared to the existing replication strategy used in MapReduce.

1 Introduction

Stochastic task times make stragglers a bottleneck in large parallel jobs, while much prior mathematical analysis of replication focused on single tasks. The paper develops a framework for analyzing replication choices and their latency–cost trade-off.

1 Introduction

  • Stochastic execution-time variation makes waiting for the slowest tasks a key source of latency in large parallel jobs.The cited prior work reports a 140 ms latency for many parallel tasks versus a 1 ms median latency for a single task.Source: §1 · p. 1

1.1 Related prior work

  • Although replication is used in MapReduce and Spark [27], mathematical analysis has largely focused on single tasks rather than large jobs.Related systems work also developed replication strategies, including speculative execution in Spark.Source: §1.1 · p. 2

1.2 Our contributions

  • The framework studies when to replicate stragglers, how many replicas to launch, and whether to keep the original, identifying regimes where replicating a small fraction can reduce latency and computing cost.These characterizations can guide policy optimization according to sensitivity to latency and computing cost.Source: §1.2 · p. 2

2 Problem Formulation

The paper models a large parallel job with i.i.d. task times and single-fork replication policies, then evaluates their latency and computing cost. Its setup includes keeping or killing the original task copy and uses normalized total machine running time as the cost measure.

2.1 Notation

  • For i.i.d. task times, X_j:n denotes the j-th smallest of n observations; the notation also distinguishes random variables, values, c.d.f.s, and tail distributions.The passage defines the tail as 1−F_X(x).Source: §2.1 · p. 2

2.2 System Model

  • The model has n parallel tasks on different machines, with execution times drawn i.i.d. from F_X to capture machine-response variability.The paper treats this variability as exogenous to the user; the identical-distribution assumption corresponds to task sizes proportional to machine processing power.Source: §2.2 · p. 3

2.3 Scheduling Policy

  • A single-fork policy launches all tasks at time 0 and waits until (1−p)n finish before acting on the remaining pn stragglers.The scheduler receives completion feedback but no intermediate task-status feedback.Source: §2.3 · p. 3
  • At the fork, the scheduler either keeps the original and launches r replicas or kills it and launches r+1; either choice leaves r+1 copies running.When one copy finishes, the other copies of that task are terminated; p=0 is the no-replication baseline.Source: §2.3 · p. 3
  • MapReduce backup tasks and Spark speculative execution correspond to the keep-original policy with r=1; Spark’s speculation quantile corresponds to p.The policy illustration depicts the single-fork choice between keeping and killing the original.Source: §2.3 · p. 3, Figure 1 · p. 4

2.4 Performance Metrics

  • Expected latency is the expected time until at least one replica of every task finishes, with job completion determined by the slowest task completion.Replica execution times are modeled as i.i.d. draws from F_X.Source: §2.4 · p. 4
  • Expected computing cost is total machine running time normalized by the number of tasks, and is proportional to users’ machine-rental charges.Running time ends when a task finishes or the scheduler kills it; the section introduces these metrics to compare replication policies.Source: §2.4 · p. 4
  • In the two-task illustration, latency T is 10 and normalized computing cost C is 14.5.The example computes T as the maximum task completion time and C as (8 + 6 + 10 + 5)/2.Source: Figure 2 · p. 5, §2.4 · p. 5

3 Single-fork policy analysis

The single-fork analysis characterizes how replication timing, replica count, and keeping or killing the original task shape latency and computing cost. For shifted-exponential and Pareto execution times, the trade-off depends on the distribution and can include latency and cost reductions from limited replication.

3.1 Performance characterization

  • Forking earlier reduces pre-fork latency but increases the post-fork maximum; with suitable p and r, the first-stage reduction can outweigh the second-stage increase.The post-fork term is the expected maximum of pn residual execution times.Source: §3.1 · pp. 5–6
  • For any 0 < p ≤ 1, inequality (8) holds for new-longer-than-used distributions; shifted exponential is an example, and its latency-cost trade-off is analyzed in Section 3.2.Source: §3.1 · p. 6

3.2.1 Shifted exponential execution time

  • For shifted-exponential times, keeping the original is always better, and earlier replication lowers latency by Θ(ln p) while increasing cost linearly when Δ > 0.For Δ = 0, cost is independent of p and r while latency falls as p and r increase; the paper notes that practical task times have Δ > 0. Figure 3 shows close agreement between analytical and simulated latency for n ≥ 100, especially when the original is killed.Source: §3.2.1 · pp. 6–7, Figure 3 · p. 7

3.2.2 Pareto execution time

Case 1: Killing the original task

  • In the Pareto case with the original task killed, the analysis gives a separate expression for the expected residual execution time after replication.The residual-time expression is one of the quantities that depends on whether the original task is killed or kept.Source: §3.2.2 · p. 8, Case 1: Killing the original task · p. 8

Case 2: Keeping the original task

  • For Pareto execution times, latency can fall from 70 to about 15 while computing cost also falls for r = 1 and r = 2.Figure 6c varies p along the latency-cost trade-off curves.Source: Figure 6 · p. 9, Case 2: Keeping the original task · p. 9
  • For Pareto times, heavier tails make expected latency grow faster with job size, while the latency benefit of increasing redundancy diminishes as r rises.The latter diminishing return follows from the 1/(r+1) factor in the exponent.Source: Case 2: Keeping the original task · p. 9
  • With the original task kept, small p and r can significantly reduce Pareto latency, but further increases in p may raise latency when r = 0.The reported curves also show that replica completion can save computing cost, though that benefit diminishes beyond a threshold in p and r.Source: Case 2: Keeping the original task · p. 9

4 Empirical execution time distributions

The section estimates latency and cost from empirical task-time distributions, then uses Google Cluster Trace jobs to show how replication choices shape their trade-off. Users can select policies according to their sensitivity to latency and computing cost.

4 Empirical execution time distributions

  • Bootstrap sampling estimates latency and cost from empirical execution-time samples, using the empirical distribution to approximate the true distribution and deriving the residual-time distribution for Y.The framework supports evaluation directly from execution traces rather than requiring a fitted task-time distribution.Source: §4.1 · p. 10, §4 · p. 10

4.1 Latency and Cost Estimation

  • Estimation error for expected cost and the first latency term decreases as O(1/√mn), while the maximum-order-statistic latency term decreases as O(1/√m).Cost estimation is more robust, though sufficiently large m can make errors in both metrics small.Source: §4.1 · p. 10

4.2 Demonstration using Google Cluster Trace

  • A small replication fraction reduces both expected latency and cost for the two Google jobs, but too much redundancy can raise both metrics for Job 2.Increasing the replica count has diminishing latency benefits; for the tail-shortened trace, killing the original copy increases latency, while keeping it and adding modest redundancy can lower latency and cost together.Source: §4.2 · pp. 11–12
  • For Job 1, πkeep(p, r = 1) yields (E [C], E [T]) = (807, 2008), while πkeep(p, r = 2) yields (815, 1798).The Job 1 trade-off is shown in Figure 8; a higher replica count gives lower latency at slightly higher cost.Source: §4.2 · p. 11, Figure 8 · p. 12

4.3 Scheduling policy selection

  • Users can choose a scheduling policy by optimizing for latency or cost, with constraints such as a maximum replica count; COBYLA is effective in the low-dimensional search.The paper presents policies obtained from the latency-sensitive and cost-sensitive formulations in Table 1.Source: §4.3 · pp. 12–13, Table 1 · p. 13

5 Concluding remarks

The paper analyzes straggler replication’s latency-cost trade-off, finding that its impact on job latency depends on the task-time distribution’s tail. It identifies settings where replicating a small fraction of stragglers can reduce latency and computing cost, and outlines future extensions.

5.1 Main Implications

  • Figure 10 plots the latency-cost trade-off for a 485-task tail-shortened job, with adjacent dots representing p changes of 0.01.Source: Figure 10 · p. 14
  • Careful replication strategies improve the latency-cost trade-off over MapReduce’s default on Google Cluster Trace data.The analysis identifies regimes where replicating a small fraction of stragglers can drastically reduce both latency and computing cost.Source: §5.1 · pp. 13–14

5.2 Future Directions

  • Future work includes generalizing the model to heterogeneous servers, dependent tasks, queueing delays, approximate computing, and online learning of task-time distributions.Source: §5.2 · p. 14
  • The framework may also apply to systems with stochastic task durations, such as crowdsourcing, where workers take variable time to complete tasks.Source: §5.2 · p. 14

A.1 Results from Order Statistics

The appendix reviews asymptotic results for order statistics and extremes used in the analysis. It relates the behavior of maxima and minima to distributional tail properties and states conditions for asymptotic normality of central order statistics.

A.1 Results from Order Statistics

  • For 0 < p < 1 and a finite positive density at the p-quantile, the kth order statistic is asymptotically normal when k = np + o(√n).Source: §A.1 · pp. 14–15
  • Extreme value theory characterizes maxima asymptotically when the distribution belongs to one of three domains of attraction.The limiting extreme-value distribution and its normalizing values depend on the domain of attraction, and hence on the execution-time distribution’s tail behavior.Source: §A.1 · p. 15
  • Exponential, heavy, and bounded short tails correspond respectively to the Gumbel, Fréchet, and Weibull domains of attraction.Source: §A.1 · p. 15
  • The appendix derives expected extreme values from the extreme-value limit and states the resulting expression using the Euler–Mascheroni constant and Gamma function.Source: §A.1 · p. 16
  • The sample minimum can be characterized through the maximum of negated samples, but the distribution of the negated variable may belong to a different domain of attraction.Source: §A.1 · p. 16

A.2 Proofs of Single Fork Analysis

The proofs decompose expected latency and cost around the single-fork point, then characterize residual straggler times under policies that kill or keep the original task. They use order-statistic and extreme-value results to derive asymptotic expressions and compare the two policies.

A.2 Proofs of Single Fork Analysis

  • Expected latency is split into time before forking, when (1 − p)n tasks finish, and the additional time until completion afterward.As n grows, the forking time approaches the (1 − p)-quantile of the task execution-time distribution.Source: §A.2 · pp. 16–18
  • The latency derivation uses the expected (1 − p)n-th order statistic, which converges to the inverse CDF at 1 − p as n grows.Source: §A.2 · p. 17
  • With the original task killed, a straggler’s residual time is the minimum of r + 1 independent task times; keeping it combines its conditional residual time with the new replicas.Source: §A.2 · p. 17
  • Expected computing cost is the normalized sum of machine runtimes before and after forking, with post-fork cost summing the runtimes of the straggler replicas.When replicas are killed as soon as one finishes, each straggler’s expected post-fork runtime is (r + 1)E[Y].Source: §A.2 · pp. 17–18
  • Killing the original is better when its residual-time distribution stochastically dominates the keep policy’s residual-time distribution; the reverse condition favors keeping it.Source: §A.2 · p. 18
  • For Pareto task times, the proofs use the Fréchet domain for the original distribution and derive the corresponding residual-time domain and expressions separately for kill and keep policies.Source: §A.2 · pp. 20–21
Loading 1503.03128v3…