Abstract
Distributed 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 being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique in distributed storage to achieve high data reliability while attaining space efficiency, taming tail latency remains an open problem due to the lack of mathematical models for analyzing such erasure-coded storage systems. In this paper, we quantify tail latency in distributed storage systems that employ erasure coding. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Simulation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload.