The MDS queue: Analysing the latency performance of erasure codes
Authors:
- 1 June 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 861-865
Abstract
In order to scale economically, data centers are increasingly evolving their data storage methods from the use of simple data replication to the use of more powerful erasure codes, which provide the same level of reliability as replication but at a significantly lower storage cost. In particular, it is well known that Maximum-Distance-Separable (MDS) codes, such as Reed-Solomon codes, provide the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in the storage of more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We present insightful scheduling policies that form upper and lower bounds to its performance, and use these to obtain easily computable analytical bounds on the average latency of the MDS queue. These bounds were observed to be quite tight in the settings we simulated. We additionally derive closed-form expressions of the throughputs of these systems. Finally, we employ the framework of the MDS queue to analyse different methods of performing so-called degraded reads (reading of partial data) in distributed data storage.Keywords
This publication has 14 references indexed in Scilit:
- When do redundant requests reduce latency ?2013
- Toward sustainable networking: Storage area networks with network coding2012
- Coding for fast content download2012
- Access vs. bandwidth in codes for storage2012
- Codes can reduce queueing delay in data centers2012
- Repair optimal erasure codes through hadamard designs2011
- Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix ConstructionIEEE Transactions on Information Theory, 2011
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010
- Applied Probability and Stochastic Processes2010
- Structured Markov chains solver2006