Optimal Server Selection for Straggler Mitigation

Ajay Badita, Parimal Parag, Vaneet Aggarwal

In the world of large-scale distributed computing, your system is only as fast as its slowest component. This is the "straggler" problem: a single sluggish server can delay an entire job, wasting resources and increasing latency. While replication—running multiple copies of the same task—is a common fix, it creates a difficult tradeoff: how do you minimize completion time without blowing your budget on server costs?

A recent paper by Ajay Badita, Parimal Parag, and Vaneet Aggarwal, titled "Optimal Server Selection for Straggler Mitigation," provides a rigorous analytical framework to solve this. By moving beyond simple "one-shot" replication to a multi-stage "forking" strategy, the authors demonstrate how to achieve orders-of-magnitude improvements in efficiency.

TL;DR

The paper introduces a multi-fork scheduling strategy where additional server replicas are added at multiple time intervals to mitigate stragglers. By analytically modeling task times as shifted exponential distributions, the authors prove that starting with multiple replicas and adding more in stages is significantly more cost-effective than traditional single-fork methods.

What Problem Does This Paper Address?

In distributed systems (like Hadoop or Spark), jobs are broken into tasks and spread across many servers. Because of hardware variations, virtualization overhead, or co-hosting interference, some servers inevitably perform poorly. These are stragglers.

To mitigate this, systems often use speculative execution: if a task is taking too long, start a second copy elsewhere. However, most existing research focuses on a "single forking point"—waiting until a certain time or until a fraction of jobs are done to replicate the remaining ones. This paper addresses the lack of a generalized framework for multi-forking, where you can judiciously add servers at several different time increments to optimize the tradeoff between mean service completion time ($ES$) and mean server utilization cost ($EW$).

Methods

The authors model the system using $K$ parallel jobs, each assigned $N$ potential servers. They assume task execution times follow a shifted exponential distribution—a model that accounts for a constant setup time ($c$) followed by a random, exponentially distributed processing time.

The Multi-Fork Policy:

  1. Initial Phase: At time $t_0 = 0$, start $n_0$ parallel replicas for a task.
  2. Sequential Forking: At subsequent "forking instants" $t_1, t_2, \dots, t_m$, add $n_1, n_2, \dots, n_m$ additional replicas for any unfinished tasks.
  3. Completion: The task finishes as soon as the first replica completes, and all other replicas for that task are immediately canceled.

Key Innovations:

  • Analytical Closed-Forms: The authors derive exact mathematical expressions for $ES$ and $EW$ for any number of forking points.
  • Joint Optimization: They formulate a multi-objective optimization problem ($min\ ES + \beta EW$) and solve it using linear programming relaxation to find the optimal number of servers to add at each stage.
  • Inflection Point Analysis: They identify that starting with only one copy ($n_0 = 1$) is often mathematically suboptimal, finding a specific "sweet spot" ($n_0^*$) for initial replicas.

Datasets & Evaluation

The paper validates its theoretical findings through three distinct lenses:

  1. Numerical Simulations: Using the derived formulas for shifted exponential distributions.
  2. Heavy-Tailed Distributions: Simulations using Pareto and Weibull distributions to see if the insights hold for tasks with "fat tails" (where extreme stragglers are more common).
  3. Real-World Cluster: Experiments conducted on the Intel DevCloud, a cluster of Intel Xeon nodes. They ran algebraic computation loops $10^4$ times to collect empirical data on job completion times.

Key Insights and Ideas

  • The Power of "Starting Strong": Contrary to some prior work suggesting starting with one copy and replicating later, this paper shows that starting with multiple copies ($n_0 > 1$) can simultaneously reduce both latency and cost if the forking threshold is low.
  • Multi-Forking > Single-Forking: By adding servers in smaller batches at multiple intervals, the system can "probe" for completion more efficiently, resulting in a much better Pareto frontier (the set of optimal tradeoffs).
  • Distribution Robustness: One of the most surprising "aha moments" is that the insights derived from the shifted exponential model—which is mathematically tractable—continue to hold for heavy-tailed distributions like Pareto. This suggests the multi-fork strategy is robust to different types of real-world noise.

Key Results

  • Cost Savings: The proposed multi-forking model shows orders of magnitude improvement in server utilization cost for low completion times compared to the state-of-the-art single-fork baselines.
  • Optimal Thresholds: For a single fork, the authors identified a threshold $v_3$. If your normalized forking time is below this, the optimal strategy is to start with more than one server.
  • Empirical Validation: The Intel DevCloud experiments confirmed that real-world task times indeed follow a shifted exponential-like distribution (a distinct constant shift followed by a light tail), validating the choice of the analytical model.

Limitations and Future Work

While the paper provides a robust framework, a few areas remain open for exploration:

  • Cancellation Overhead: The model assumes that canceling redundant replicas is instantaneous and free. In real systems, killing a process can incur overhead.
  • I.I.D. Assumption: The analysis assumes server times are independent and identically distributed. In practice, network congestion or shared rack power might cause correlated straggling.
  • Coded Computation: The authors suggest that combining this multi-forking approach with erasure coding (instead of simple replication) is a promising future direction to further reduce the redundancy required.
  • Queuing Dynamics: This study looks at a fixed set of jobs. Extending this to a continuous stream of arriving jobs (stochastic arrivals) remains an open analytical challenge.

Paper Citation: Ajay Badita, Parimal Parag, and Vaneet Aggarwal. "Optimal Server Selection for Straggler Mitigation." arXiv:1911.05918v1 [cs.NI], 2019.

Summary updated

Abstract

The performance of large-scale distributed compute systems is adversely impacted by stragglers when the execution time of a job is uncertain. To manage stragglers, we consider a multi-fork approach for job scheduling, where additional parallel servers are added at forking instants. In terms of the forking instants and the number of additional servers, we compute the job completion time and the cost of server utilization when the task processing times are assumed to have a shifted exponential distribution. We use this study to provide insights into the scheduling design of the forking instants and the associated number of additional servers to be started. Numerical results demonstrate orders of magnitude improvement in cost in the regime of low completion times as compared to the prior works.
BibTeX
@article{badita2020optimal,
  author = {Ajay Badita and Parimal Parag and Vaneet Aggarwal},
  title = {{Optimal Server Selection for Straggler Mitigation}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2020},
  url = {https://openreview.net/forum?id=yZAd5vIbTG},
}

Loading related content...

Figure