2014 · 86 citations · 15 references
ComputingComputer EngineeringComputer ScienceCloud StorageQueuing TheoryStorage SystemsData RedundancyData ReplicationFault-tolerant Storage SystemsLatency OptimizationQueueing SystemsQueueing TheoryCloud Latency OptimizationForward Error CorrectionLatency ReductionLatency Reduction TechniquesLatency TradeoffsStorage Access Latency OptimizationStorage LatencyStorage Performance Optimization
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.
15
Network Coding for Distributed Storage Systems
Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu et al. · IEEE Transactions on Information Theory · 2010 · 2K citations
A Survey on Network Codes for Distributed Storage
Alexandros G. Dimakis, Kannan Ramchandran, Yunnan Wu et al. · Proceedings of the IEEE · 2011 · 656 citations
Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services
Yi Lu, Qiaomin Xie, Gabriel Kliot et al. · Performance Evaluation · 2011 · 360 citations · Full text