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.
Introduction
In modern distributed computing environments like Hadoop or Spark, system performance is often bottlenecked by "stragglers"—individual tasks that take significantly longer than average to complete. These delays can stem from hardware heterogeneity, resource contention, or background system processes. To mitigate this, speculative execution or replication is commonly employed. However, traditional approaches often rely on simple "one-shot" or single-fork strategies, which may not optimally balance the tradeoff between job completion time and resource expenditure.
This paper introduces a generalized multi-fork scheduling framework. By adding server replicas at multiple discrete time intervals, the system can more effectively "probe" for task completion, significantly reducing latency while maintaining cost efficiency.
The Multi-Fork Strategy
The proposed policy models a system where $K$ parallel jobs are assigned to a pool of $N$ potential servers. The execution time of each task is modeled using a shifted exponential distribution, which incorporates a constant setup time ($c$) followed by a random, exponentially distributed processing phase.
The multi-fork policy operates in stages:
- Initial Phase: At time $t_0 = 0$, the system launches $n_0$ parallel replicas for a task.
- Sequential Forking: At subsequent pre-defined forking instants $t_1, t_2, \dots, t_m$, the system adds $n_1, n_2, \dots, n_m$ additional replicas for any task that has not yet completed.
- Termination: A task is considered finished as soon as its first replica completes. At this moment, all other redundant replicas for that specific task are immediately terminated to conserve resources.
This approach allows for a more granular control over resource allocation compared to traditional single-fork methods.
Optimization and Tradeoffs
The core of the research involves deriving closed-form analytical expressions for two primary metrics: the mean service completion time ($\mathbb{E}S$) and the mean server utilization cost ($\mathbb{E}W$). The authors formulate a multi-objective optimization problem to minimize a weighted sum of these metrics ($\min \mathbb{E}S + \beta \mathbb{E}W$).
A key finding is the identification of an optimal number of initial servers ($n_0^*$). While intuition might suggest starting with a single copy and adding more only if it straggles, the analysis reveals that "starting strong" with $n_0 > 1$ is often more efficient.
As shown in the figure above, the server utilization cost often exhibits a clear minimum at $n_0 > 1$. When combined with the fact that increasing $n_0$ generally decreases completion time, this demonstrates that multi-forking can simultaneously improve both performance and cost-effectiveness.
Experimental Validation
The theoretical framework was validated through three distinct methods:
- Numerical Simulations: Confirming the derived formulas for shifted exponential distributions.
- Heavy-Tailed Distributions: Testing the strategy against Pareto and Weibull distributions. The results showed that the insights derived from the shifted exponential model remain robust even when tasks exhibit "fat tails," where extreme stragglers are more frequent.
- Real-World Implementation: Experiments on the Intel DevCloud cluster using algebraic computation loops confirmed that real-world task durations closely follow the shifted exponential model, with a distinct constant setup time followed by a light tail.
Conclusion and Future Work
The multi-forking strategy offers orders-of-magnitude improvements in cost for low-latency regimes compared to existing single-fork baselines. By judiciously selecting forking instants and the number of replicas at each stage, distributed systems can significantly mitigate the impact of stragglers.
Future research directions include accounting for the overhead associated with process cancellation, relaxing the assumption of independent and identically distributed (i.i.d.) server times to handle correlated failures, and integrating this approach with erasure coding techniques. Additionally, extending the analysis from a fixed set of jobs to a continuous stream of stochastic arrivals remains a key challenge for future work.
Paper Citation: Ajay Badita, Parimal Parag, and Vaneet Aggarwal. "Optimal Server Selection for Straggler Mitigation." arXiv:1911.05918v1 [cs.NI], 2019.
Summary updated