Provably optimal probabilistic scheduling for tail latency in erasure-coded storage beyond Pareto file sizes and exponential service times

In erasure-coded distributed storage, a file request completes when k of the n chunks storing an (n,k) MDS-coded file have been retrieved, so latency is governed by the slowest of the k responses and long-tailed service times produce severe tail latency. The probabilistic-scheduling framework dispatches each batch of k chunk requests to a k-subset of the storage nodes chosen with predetermined probabilities, which makes the queues analyzable and supports closed-form tail-latency bounds and joint placement/scheduling optimization. Asymptotic optimality of probabilistic scheduling for the tail metric that has been characterized — the tail index, i.e., the power-law decay exponent of the latency tail probability — is proven only for Pareto (heavy-tailed) file sizes with exponential per-megabyte service times with server-dependent rates on heterogeneous servers, under Poisson arrivals and uniform access probabilities. The open problem posed by Aggarwal, Al-Abbasi, Fan, and Lan (2017) is to determine more general and realistic scenarios — in particular the shifted-exponential service times with server-dependent parameters used in the source model, file-size laws beyond Pareto, general chunk placements, and non-uniform access probabilities — under which probabilistic scheduling is provably optimal in tail index, or to improve the scheduling strategy so as to show optimality for wider distributional classes. Whether probabilistic scheduling remains optimal in tail index in these broader regimes is open.

Background

Erasure coding is the standard space-efficient alternative to replication for reliability in distributed storage: a file is split into $n$ encoded chunks using a maximum-distance-separable (MDS) $(n,k)$ code, and any $k$ of the $n$ chunks suffice to reconstruct the file. A read request therefore completes when its $k$ chunk requests finish, so the request latency is the $k$-th order statistic (maximum) of the accessed servers' response times. Because modern storage clusters exhibit highly skewed per-request service times — 99.9th-percentile response times are orders of magnitude worse than the mean at operators such as Bing, Facebook, and Amazon — the tail of the request-latency distribution is a first-order design concern, and the maximum-over-servers structure amplifies it.

A queueing analysis of this system is hard because the state must track chunk placement, queued requests, and the history of chunk processing at individual nodes. To make the model tractable, Xiang, Lan, Aggarwal, and Chen (2016) introduced probabilistic scheduling: upon each file request, a batch of $k$ chunk requests is dispatched to $k$ out of the $n$ nodes storing the file, chosen randomly with predetermined (nonuniform) access probabilities $\pi$; each node then serves its local queue independently. This decouples the servers so that each queue's waiting-time distribution can be computed (e.g., via the Laplace–Stieltjes transform, a standard queueing representation of a waiting-time distribution from which its moments and tail behavior can be extracted) and combined through order-statistic bounds. Aggarwal, Al-Abbasi, Fan, and Lan (2017) built on this framework to derive closed-form upper bounds on the latency tail probability $\Pr(T>\sigma)$ for arbitrary per-megabyte service-time distributions and heterogeneous files, and to jointly optimize weighted tail probability over file placement and access probabilities; in their numerical model the per-megabyte chunk-transfer time is shifted-exponential (an affine shift plus an exponential component) with server-dependent rates, which is the regime real datacenter measurements suggest.

Separately, Aggarwal and Lan (2016) analyzed a tail metric that admits exact asymptotic characterization: the tail index, defined as the exponent $d$ such that the waiting/latency tail probability decays like $x^{-d}$ as $x\to\infty$, i.e. $d=\lim_{x\to\infty}-\log \Pr(T>x)/\log x$. For Poisson arrivals, Pareto-distributed chunk sizes with shape parameter $\alpha>2$, and exponential per-megabyte service times with server-dependent means $1/\mu_j$ on $n$ heterogeneous servers, they proved that any distributed storage system has tail index at most $\alpha-1$ (a genie-aided bound merging all servers into one server of rate $\sum_j \mu_j$ that serves a single chunk), and that uniform probabilistic scheduling with access probabilities $\pi_{ij}=k/n$ achieves tail index exactly $\alpha-1$ — so probabilistic scheduling is asymptotically optimal for this tail metric; the same paper notes that the argument extends to more than $n$ servers with uniform file placement and a different erasure code per file. However, the file-size and service-time laws of that result (Pareto chunk sizes with exponential per-megabyte service) differ from the shifted-exponential service model and the general file-size laws of the tail-latency framework. The authors' 2021 monograph restates and consolidates these results (Section 4.5, Theorems 4.5.1, 4.5.2 and 4.5.4), and its Notes and Open Problems leave open the extension of the asymptotic-independence and steady-state delay-distribution results of Section 4.4 — currently for equal file sizes and a common erasure code, homogeneous servers, $k^{(n)}=o(n^{1/4})$ and equal scheduling probabilities — to heterogeneous files and servers with non-equal scheduling probabilities; that item is an analysis gap for the delay distribution, not a tail-optimality result. The journal extension of the source paper (Al-Abbasi, Aggarwal, and Lan, TNSM 2019) states tail-index optimality and closed-form upper bounds. Related asymptotic analysis for the mean (not tail) metric exists: Wang, Harchol-Balter, Jiang, Scheller-Wolf, and Srikant (2019) proved asymptotic independence — the property that the servers' queue occupancies become independent as the system grows large — and stochastic upper bounds for uniform probabilistic scheduling when the batch size satisfies $k=o(n^{1/4})$ with exponential service times, and Jinan, Gautam, Parag, and Aggarwal (2023) together with Mohanty, Gautam, Aggarwal, and Parag (2024) analyzed mean task completion time for probabilistic selection among heterogeneous slow and fast servers, deriving near-optimal selection probabilities for an upper bound on the mean. None of these establishes tail-metric optimality.

Problem Statement

Determine under which system models broader than the proven baseline — Poisson arrivals, Pareto-distributed file sizes with shape parameter $\alpha>2$, and exponential per-megabyte service times with server-dependent means $1/\mu_j$ on heterogeneous servers, under uniform access probabilities — the probabilistic-scheduling family is provably optimal in tail index in erasure-coded distributed storage. Concretely, for storage systems where file $i$ is stored under an $(n_i,k_i)$ MDS erasure code on a placement set $S_i$ of nodes, requests for file $i$ arrive as an independent Poisson process of rate $\lambda_i$, and a batch of $k_i$ chunk requests is dispatched to $k_i$ of the $n_i$ storing nodes with predetermined access probabilities $\pi_{ij}$ (feasible when $\sum_j \pi_{ij}=k_i$ and $\pi_{ij}=0$ for $j\notin S_i$), each node then serving its local FIFO queue independently under a stability condition on its aggregate arrival rate $\Lambda_j=\sum_i \lambda_i \pi_{ij}$, and the request latency $T$ is the maximum ($k_i$-th order statistic) of the $k_i$ chunk sojourn times: (a) prove or disprove that probabilistic scheduling attains the optimal tail index $d=\lim_{x\to\infty}-\log\Pr(T>x)/\log x$ — that is, matches the best tail index achievable by any admissible request-scheduling policy for the model considered, as the genie-aided bound does in the proven baseline — under the more realistic service regimes of the tail-latency framework of Aggarwal, Al-Abbasi, Fan, and Lan (2017), including shifted-exponential per-megabyte service times with server-dependent shift $s_j\ge 0$ and rate $\gamma_j>0$ (the per-megabyte service time $X_j$ at server $j$ has density $f_{X_j}(x)=\gamma_j e^{-\gamma_j(x-s_j)}$ for $x\ge s_j$, with mean $s_j+1/\gamma_j$, and a chunk's transfer time is its size in megabytes times $X_j$), heterogeneity beyond distinct exponential service rates, non-uniform access probabilities, general chunk placements, and heavy-tailed file-size laws beyond Pareto$(x_m,\alpha)$ with $\alpha>2$; and (b) if probabilistic scheduling is not optimal in such regimes, exhibit a scheduling strategy and prove its optimality in tail index over these wider distributional classes. The listed regimes are the broader model features relative to the baseline, and the task is a classification over them: they are to be resolved individually or in combination rather than assumed to hold jointly, and the optimality claim is quantified over the probabilistic-scheduling family — whether some feasible access-probability vector $\pi$ attains the optimal tail index, as the uniform schedule $\pi_{ij}=k_i/n_i$ does in the proven baseline. The comparison class is all request-scheduling policies for the stated model. Because the tail index is non-discriminating when the latency tail decays faster than any polynomial — the achieved index and the genie-aided bound are then both infinite, and optimality holds vacuously — the regimes of interest are those in which the latency tail index is finite and set by the file-size and service-time laws, as in the proven baseline.

References

1. Vaneet Aggarwal, Abubakr O. Al-Abbasi, Jingxian Fan, Tian Lan (2017). Taming Tail Latency for Erasure-coded, Distributed Storage Systems. arXiv:1703.08337. https://arxiv.org/abs/1703.08337
2. Vaneet Aggarwal, Jingxian Fan, Tian Lan (2017). Taming tail latency for erasure-coded, distributee storage systems (title as recorded in Crossref). IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1-9. DOI: 10.1109/INFOCOM.2017.8056997. https://doi.org/10.1109/INFOCOM.2017.8056997
3. Vaneet Aggarwal, Tian Lan (2016). Tail Index for a Distributed Storage System with Pareto File Size Distribution. arXiv:1607.06044. https://arxiv.org/abs/1607.06044
4. Abubakr O. Al-Abbasi, Vaneet Aggarwal, Tian Lan (2019). TTLoC: Taming Tail Latency for Erasure-Coded Cloud Storage Systems. IEEE Transactions on Network and Service Management 16(4):1609-1623. DOI: 10.1109/TNSM.2019.2916877. https://doi.org/10.1109/TNSM.2019.2916877
5. Vaneet Aggarwal, Tian Lan (2021). Modeling and Optimization of Latency in Erasure-coded Storage Systems. Foundations and Trends in Communications and Information Theory 18(3):380-525. DOI: 10.1561/0100000108; arXiv:2005.10855. https://arxiv.org/abs/2005.10855
6. Weina Wang, Mor Harchol-Balter, Haotian Jiang, Alan Scheller-Wolf, R. Srikant (2019). Delay asymptotics and bounds for multitask parallel jobs. Queueing Systems 91(3-4):207-239. DOI: 10.1007/s11134-018-09597-5. https://doi.org/10.1007/s11134-018-09597-5
7. Yu Xiang, Tian Lan, Vaneet Aggarwal, Yih-Farn R. Chen (2016). Joint Latency and Cost Optimization for Erasure-Coded Data Center Storage. IEEE/ACM Transactions on Networking 24(4):2443-2457. DOI: 10.1109/TNET.2015.2466453. https://doi.org/10.1109/TNET.2015.2466453
8. Rooji Jinan, Gaurav Gautam, Parimal Parag, Vaneet Aggarwal (2023). Asymptotic Analysis of Probabilistic Scheduling for Erasure-Coded Heterogeneous Systems. ACM SIGMETRICS Performance Evaluation Review 50(4):8-10. DOI: 10.1145/3595244.3595248. https://doi.org/10.1145/3595244.3595248
9. Moonmoon Mohanty, Gaurav Gautam, Vaneet Aggarwal, Parimal Parag (2024). Analysis of Fork-Join Scheduling on Heterogeneous Parallel Servers. IEEE/ACM Transactions on Networking 32(6):4798-4809. DOI: 10.1109/TNET.2024.3432183. https://doi.org/10.1109/TNET.2024.3432183
10. Ajay Badita, Parimal Parag, Vaneet Aggarwal (2020). Optimal Server Selection for Straggler Mitigation. IEEE/ACM Transactions on Networking 28(2):709-721. DOI: 10.1109/TNET.2020.2973224; arXiv:1911.05918. https://arxiv.org/abs/1911.05918
11. Tim Hellemans, Arti Yardi, Tejas Bodas (2021). Download time analysis for distributed storage systems with node failures. IEEE International Symposium on Information Theory (ISIT) 2021, pp. 2060-2065. DOI: 10.1109/ISIT45174.2021.9517730; arXiv:2105.02926. https://arxiv.org/abs/2105.02926
12. Elene Anton, Rhonda Righter, Ina Maria Verloop (2024). Efficient scheduling in redundancy systems with general service times. Queueing Systems 106(3-4):333-372. DOI: 10.1007/s11134-024-09904-3. https://doi.org/10.1007/s11134-024-09904-3
13. Zhiyue Li, Guangyan Zhang, Yang Wang (2025). Flash-oriented Coded Storage: Research Status and Future Directions. ACM Transactions on Storage 21(1):1-37. DOI: 10.1145/3708995. https://doi.org/10.1145/3708995