2016/07/20 by Vaneet Aggarwal, Tian Lan, Aggarwal, Vaneet +1
Computer Science · Mathematics · #Advanced Data Storage Technologies #Algorithm #Caching and Content Delivery #Computer science #Decoding methods #Distributed #Distributed computing #Distributed data store #Erasure #Erasure code #FOS: Computer and information sciences #Heavy-tailed distribution #Information Theory (cs.IT) #Latency (audio) #Mathematical optimization #Mathematics #Networking and Internet Architecture (cs.NI) #Parallel #Peer-to-Peer Network Technologies #Probabilistic logic #Probability distribution #Scheduling (production processes) #Statistics #Telecommunications #and Cluster Computing (cs.DC) #cs.DC #cs.IT #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.1607.06044
Theorem 1 proof was replaced with a proof that uses the result in [21], thus simplifying the analysis and making the paper concise
openalex publication_date 2016/07/20 · arxiv created 2017/08/03 · arxiv updated 2017/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Distributed storage systems often employ erasure codes to achieve high data reliability while attaining space efficiency. Such storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with 99.9th percentile response times that are orders of magnitude worse than the mean. Taming tail latency is very challenging in erasure-coded storage systems since quantify tail latency (i.e., xth-percentile latency for arbitrary x∈[0,1]) has been a long-standing open problem. In this paper, we propose a mathematical model to quantify \em tail index of service latency for arbitrary erasure-coded storage systems, by characterizing the asymptotic behavior of latency distribution tails. When file size has a heavy tailed distribution, we find tail index, defined as the exponent at which latency tail probability diminishes to zero, in closed-form, and further show that a family of probabilistic scheduling algorithms are (asymptotically) optimal since they are able to achieve the exact tail index.