Latency Analysis of Flexible Redundant Scheme in MDS-Coded Distributed Storage Systems

Abstract

Access latency is the bottle-neck of various web services, and can greatly impact user experience, especially for the data retrieval applications, such as Google search. Many large-scale distributed storage systems are moving to the use of erasure codes to provide low storage overhead and high failure tolerance. Most previous work about coding latency focuses on the case when users desire all the data in a codeword. However, we find that in practical MDS- coded storage systems, the size of a codeword is usually so big that users only desire part of the files in a codeword. Hence, it is significant to analyze the latency in coding systems when users only desire part of a codeword. In this paper, we propose Flexible Redundant Scheme (FRedS) that can deal with the general case in which users only require part of the files from a codeword. In the case of no queueing delay, we give a general and closed-form expression of the coding latency with FRedS. Considering queueing delay, we extend the popular latency bound to analyze the latency performance of FRedS under the general service time distribution. Through extensive simulations using real service time traces from Amazon S3, we validate our latency analysis, demonstrate the tightness of the bounds derived in this work and show the latency comparison of FRedS and the direct read scheme.