When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds
- 1 April 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1042-1050
Abstract
Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- FAST CLOUD: Pushing the Envelope on Delay Performance of Cloud Storage With CodingIEEE/ACM Transactions on Networking, 2013
- Toward sustainable networking: Storage area networks with network coding2012
- Codes can reduce queueing delay in data centers2012
- Managing Queues with Heterogeneous ServersJournal of Applied Probability, 2011
- Avoiding Interruptions — A QoE Reliability Function for Streaming Media ApplicationsIEEE Journal on Selected Areas in Communications, 2011
- A Survey on Network Codes for Distributed StorageProceedings of the IEEE, 2011
- Grid scheduling with NBU service timesOperations Research Letters, 2010
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010
- Reducing repair traffic for erasure coding-based storage via interference alignment2009
- On the delay of network coding over line networks2009