Erasure coding is widely used for massive storage in data centers to achieve high fault tolerance and low storage redundancy. Since the cross-rack communication cost is often high, it is critical to design erasure codes that minimize the cross-rack repair bandwidth during failure repair. In this paper, we analyze the optimal trade-off between storage redundancy and cross-rack repair bandwidth specifically for data centers, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. We characterize the optimal trade-off curve under functional repair, and propose a general family of erasure codes called rack-aware regenerating codes (RRC) , which achieve the optimal trade-off. We further propose exact repair constructions of RRC that have minimum storage redundancy and minimum cross-rack repair bandwidth, respectively. We show that (i) the minimum storage redundancy constructions support a wide range of parameters and have cross-rack repair bandwidth that is strictly less than that of the classical minimum storage regenerating codes in most cases, and (ii) the minimum cross-rack repair bandwidth constructions support all the parameters and have less cross-rack repair bandwidth than that of the minimum bandwidth regenerating codes for almost all of the parameters.
The closest related work to ours is by Prakash @cite_17 . In their model, a file needs to be retrieved from a certain number of racks, and hence @math must be a multiple of number of nodes in each rack. On the other hand, our model allows a file to be retrieved from any @math nodes. Therefore, our RRC can tolerate more failure patterns than the codes in @cite_17 . We show that the trade-off curve of RRC coincides with the optimal trade-off curve in @cite_17 when @math is a multiple of number of nodes in each rack, yet our exact repair constructions for MSRR codes and MBRR codes can support much more parameters than that of the minimum storage codes and the minimum bandwidth codes in @cite_17 , respectively (see for details). More importantly, the cross-rack repair bandwidth of our MSRR codes with additional parameters is strictly less than that of MSRR codes with the nearest @math that is a multiple of number of nodes in each rack (see the remark in ). Table compares our RRC with the other related work for erasure-coded data centers.
@cite_17
2606114015
Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an @math - @math MSR code @math over @math stores a file @math consisting of @math symbols over @math among @math nodes, each storing @math symbols, in such a way that: 1) the file @math can be recovered by downloading the content of any @math of the @math nodes and 2) the content of any failed node can be reconstructed by accessing any @math of the remaining @math nodes and downloading @math symbols from each of these nodes. In practice, the file @math is typically available in uncoded form on some @math of the @math nodes, known as systematic nodes , and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only . Such codes are called systematic–repair MSR codes . Unfortunately, finite– @math constructions of @math MSR codes are known only for certain special cases: either low rate, namely @math , or high repair connectivity, namely @math . Our main result in this paper is a finite– @math construction of systematic-repair @math MSR codes for all possible values of parameters @math . We also introduce a generalized construction for @math MSR codes to achieve the optimal repair bandwidth for all values of @math simultaneously.