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.
@cite_26: In distributed storage systems, erasure codes have been increasingly deployed to tolerate server failures without loss of data. Traditional erasure codes, such as Reed-Solomon codes, suffer from a high volume of network transfer and disk I O to recover unavailable data at failed storage servers. Typically, unavailable data at different failed storage servers in a distributed storage system are fixed separately. It has been shown that it is possible to reduce the volume of network transfer significantly by reconstructing data from multiple storage servers at the same time. However, there has been no construction of erasure codes to achieve it without imposing strict constraints on system parameters. In this paper, we propose Beehive codes, designed for optimizing the volume of network transfers to fix the data on multiple failed storage servers. Beehive codes can be constructed over a wide range of system parameters at code rate no more than 0.5, while incurring slightly more storage overhead than Reed-Solomon codes. To achieve the optimal storage overhead as Reed-Solomon codes, we further extend vanilla Beehive codes to MDS Beehive codes, which incurs near-optimal volumes of network transfers during reconstruction. We implement both Beehive and MDS Beehive Codes in C++ and evaluate their performance on Amazon EC2. Our evaluation results have clearly shown that the volume of both network transfers and disk I O can be conserved by a substantial margin.
@cite_21: Data centers increasingly adopt erasure coding to ensure fault-tolerant storage with low redundancy, yet the hierarchical nature of data centers incurs substantial oversubscribed cross-rack bandwidth in failure repair. We present Double Regenerating Codes (DRC), whose idea is to perform two-stage regeneration, so as to minimize the cross-rack repair bandwidth for a single-node repair with the minimum storage redundancy. We prove the existence of a DRC construction, and show via quantitative comparisons that DRC significantly reduces the cross-rack repair bandwidth of state-of-the-art minimum storage regenerating codes.
@cite_3: In the traditional two-rack distributed storage system (DSS) model, due to the assumption that the storage capacity of each node is the same, the minimum bandwidth regenerating (MBR) point becomes infeasible. In this paper, we design a new non-homogeneous two-rack model by proposing a generalization of the threshold function used to compute the tradeoff curve. We prove that by having the nodes in the rack with higher regenerating bandwidth stores more information, all the points on the tradeoff curve, including the MBR point, become feasible. Finally, we show how the non-homogeneous two-rack model outperforms the traditional model in the tradeoff curve between the storage per node and the repair bandwidth.
@cite_19: A new system model reflecting the clustered structure of distributed storage is suggested to investigate interplay between storage overhead and repair bandwidth as storage node failures occur. Large data centers with multiple racks disks or local networks of storage devices (e.g., sensor network) are good applications of the suggested clustered model. In realistic scenarios involving clustered storage structures, repairing storage nodes using intact nodes residing in other clusters are more bandwidth consuming than restoring nodes based on information from intra-cluster nodes. Therefore, it is important to differentiate between intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling distributed storage. Capacity of the suggested model is obtained as a function of fundamental resources of distributed storage systems, namely, node storage capacity, intra-cluster repair bandwidth, and cross-cluster repair bandwidth. The capacity is shown to be asymptotically equivalent to a monotonic decreasing function of number of clusters, as the number of storage nodes increases without bound. Based on the capacity expression, feasible sets of required resources which enable reliable storage are obtained in a closed-form solution. Specifically, it is shown that the cross-cluster traffic can be minimized to zero (i.e., intra-cluster local repair becomes possible) by allowing extra resources on storage capacity and intra-cluster repair bandwidth, according to the law specified in the closed form. The network coding schemes with zero cross-cluster traffic are defined as intra-cluster repairable codes , which are shown to be a class of the previously developed locally repairable codes .
@cite_27: The capacity of heterogeneous distributed storage systems under repair dynamics is studied. Examples of these systems include peer-to-peer storage clouds, wireless, and Internet caching systems. Nodes in a heterogeneous system can have different storage capacities and different repair bandwidths. Lower and upper bounds on the system capacity are given. These bounds depend on either the average resources per node, or on a detailed knowledge of the node characteristics. Moreover, the case in which nodes may be compromised by an adversary (passive or active) is addressed and bounds on the secure capacity of the system are derived. One implication of these new results is that symmetric repair maximizes the capacity of a homogeneous system, which justifies the model widely used in the literature.
@cite_23: Erasure codes, such as Reed-Solomon (RS) codes, are increasingly being deployed as an alternative to data-replication for fault tolerance in distributed storage systems. While RS codes provide significant savings in storage space, they can impose a huge burden on the I O and network resources when reconstructing failed or otherwise unavailable data. A recent class of erasure codes, called minimum-storage-regeneration (MSR) codes, has emerged as a superior alternative to the popular RS codes, in that it minimizes network transfers during reconstruction while also being optimal with respect to storage and reliability. However, existing practical MSR codes do not address the increasingly important problem of I O overhead incurred during reconstructions, and are, in general, inferior to RS codes in this regard. In this paper, we design erasure codes that are simultaneously optimal in terms of I O, storage, and network bandwidth. Our design builds on top of a class of powerful practical codes, called the product-matrix-MSR codes. Evaluations show that our proposed design results in a significant reduction the number of I Os consumed during reconstructions (a 5× reduction for typical parameters), while retaining optimality with respect to storage, reliability, and network bandwidth.
@cite_15: Repair performance in hierarchical data centers is often bottlenecked by cross-rack network transfer. Recent theoretical results show that the cross-rack repair traffic can be minimized through repair layering, whose idea is to partition a repair operation into inner-rack and cross-rack layers. However, how repair layering should be implemented and deployed in practice remains an open issue. In this article, we address this issue by proposing a practical repair layering framework called DoubleR. We design two families of practical double regenerating codes (DRC), which not only minimize the cross-rack repair traffic but also have several practical properties that improve state-of-the-art regenerating codes. We implement and deploy DoubleR atop the Hadoop Distributed File System (HDFS) and show that DoubleR maintains the theoretical guarantees of DRC and improves the repair performance of regenerating codes in both node recovery and degraded read operations.
@cite_16: Large distributed storage systems use erasure codes to reliably store data. Compared to replication, erasure codes are capable of reducing storage overhead. However, repairing lost data in an erasure coded system requires reading from many storage devices and transferring over the network large amounts of data. Theoretically, Minimum Storage Regenerating (MSR) codes can significantly reduce this repair burden. Although several explicit MSR code constructions exist, they have not been implemented in real-world distributed storage systems. We close this gap by providing a performance analysis of Butterfly codes, systematic MSR codes with optimal repair I O. Due to the complexity of modern distributed systems, a straightforward approach does not exist when it comes to implementing MSR codes. Instead, we show that achieving good performance requires to vertically integrate the code with multiple system layers. The encoding approach, the type of inter-node communication, the interaction between different distributed system layers, and even the programming language have a significant impact on the code repair performance. We show that with new distributed system features, and careful implementation, we can achieve the theoretically expected repair performance of MSR codes.
@cite_10: 
@cite_25: 
@cite_17: We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are @math clusters in total, with @math nodes per cluster. A data file is coded and stored across the @math nodes, with each node storing @math symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of @math clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading @math symbols each from any set of @math other clusters, dubbed remote helper clusters, and also up to @math symbols each from any set of @math surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever @math . We then obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Under functional repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes @math in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing @math not only increases intra-cluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions.
There are many follow-up studies on RC along different directions, such as practical implementation @cite_10 @cite_23 @cite_16 @cite_26 and the repair problem with heterogeneous structures @cite_3 @cite_27 @cite_25 @cite_21 @cite_19 @cite_15 @cite_17 .