A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50% of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error. > <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r/spl les/8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2/sup m/), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols. <s> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development. <s> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> Peer-to-peer systems are positioned to take advantage of gains in network bandwidth, storage capacity, and computational resources to provide long-term durable storage infrastructures. In this paper, we quantitatively compare building a distributed storage infrastructure that is self-repairing and resilient to faults using either a replicated system or an erasure-resilient system. We show that systems employing erasure codes have mean time to failures many orders of magnitude higher than replicated systems with similar storage and bandwidth requirements. More importantly, erasure-resilient systems use an order of magnitude less bandwidth and storage to provide similar system durability as replicated systems. <s> BIB004 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> Availability is a storage system property that is both highly desired and yet minimally engineered. While many systems provide mechanisms to improve availability - such as redundancy and failure recovery - how to best configure these mechanisms is typically left to the system manager. Unfortunately, few individuals have the skills to properly manage the trade-offs involved, let alone the time to adapt these decisions to changing conditions. Instead, most systems are configured statically and with only a cursory understanding of how the configuration will impact overall performance or availability. While this issue can be problematic even for individual storage arrays, it becomes increasingly important as systems are distributed - and absolutely critical for the wide-area peer-to-peer storage infrastructures being explored. ::: ::: This paper describes the motivation, architecture and implementation for a new peer-to-peer storage system, called TotalRecall, that automates the task of availability management. In particular, the TotalRecall system automatically measures and estimates the availability of its constituent host components, predicts their future availability based on past behavior, calculates the appropriate redundancy mechanisms and repair policies, and delivers user-specified availability while maximizing efficiency. <s> BIB005 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> This paper exhibits a class of universal Raptor codes: for a given integer k, and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + /spl epsiv/) is sufficient to recover the original k symbols, with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations. <s> BIB006 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> We consider the problem of recovering from a single node failure in a storage system based on an (n, k) MDS code. In such a scenario, a straightforward solution is to perform a complete decoding, even though the data to be recovered only amount to 1/kth of the entire data. This paper presents techniques that can reduce the network traffic incurred. The techniques perform algebraic alignment so that the effective dimension of unwanted information is reduced. <s> BIB007 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3/4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I/O is also minimized. <s> BIB008 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called regenerating codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, regenerating codes can reduce maintenance bandwidth use by 25% or more compared with the best previous design - a hybrid of replication and erasure codes - while simplifying system architecture. <s> BIB009 </s> A Survey on Network Codes for Distributed Storage <s> I. INTRODUCTION <s> Distributed storage systems provide large-scale reliable data storage by storing a certain degree of redundancy in a decentralized fashion on a group of storage nodes. To recover from data losses due to the instability of these nodes, whenever a node leaves the system, additional redundancy should be regenerated to compensate such losses. In this context, the general objective is to minimize the volume of actual network traffic caused by such regenerations. A class of codes, called regenerating codes, has been proposed to achieve an optimal trade-off curve between the amount of storage space required for storing redundancy and the network traffic during the regeneration. In this paper, we jointly consider the choices of regenerating codes and network topologies. We propose a new design, referred to as RCTREE, that combines the advantage of regenerating codes with a tree-structured regeneration topology. Our focus is the efficient utilization of network links, in addition to the reduction of the regeneration traffic. With the extensive analysis and quantitative evaluations, we show that RCTREE is able to achieve a both fast and stable regeneration, even with departures of storage nodes during the regeneration. <s> BIB010
In recent years, the demand for large-scale data storage has increased significantly, with applications like social networks, file, and video sharing demanding seamless storage, access and security for massive amounts of data. When the deployed storage nodes are individually unreliable, as is the case in modern data centers and peer-to-peer networks, redundancy must be introduced into the system to improve reliability against node failures. The simplest and most commonly used form of redundancy is straightforward replication of the data in multiple storage nodes. However, erasure coding techniques can potentially achieve orders of magnitude more reliability for the same redundancy compared to replication (see, e.g., BIB004 ). To realize the increased reliability of coding however, one has to address the challenge of maintaining an erasure encoded representation. Given two positive integers k and n > k, an ðn; kÞ maximum distance separable (MDS) code can be used for reliability: initially the data to be stored are separated into k information packets. Subsequently, using the MDS code, these are encoded into n packets (of the same size) such that any k out of these n suffice to recover the original data (see Fig. 1 for an example). MDS codes are optimal in terms of the redundancyreliability tradeoff because k packets contain the minimum amount of information required to recover the original data. In a distributed storage system, the n encoded packets are stored at different storage nodes (e.g., disks, servers, or peers) spread over a network, and the system can tolerate any ðn À kÞ node failures without data loss. Note that throughout this paper we will assume a storage system of n storage nodes that can tolerate ðn À kÞ node failures and use the idea of subpacketization: each storage node can Each storage node (box) is storing two blocks that are linear binary combinations of the original data blocks A 1 ; A 2 ; B 1 ; B 2 . In this example, the total stored size is M ¼ 4 blocks. Observe that any k ¼ 2 out of the n ¼ 4 storage nodes contain enough information to recover all the data. store multiple subpackets that will be referred to as blocks (essentially using the idea of array codes BIB001 , BIB002 ). The benefits of coding for storage are well known and there has been a substantial amount of work in the area. Reed-Solomon codes  are perhaps the most popular MDS codes and together with the very similar information dispersal algorithm (IDA)  have been investigated in distributed storage applications (e.g., BIB003 and BIB005 ). Fountain codes BIB006 and low-density parity-check (LDPC) codes  are recent code designs that offer approximate MDS properties and fast encoding-and-decoding complexity. Finally, there has been a large body of related work on codes for RAID systems and magnetic recording (e.g., see BIB001 -  and references therein). In this tutorial, we focus on a new problem that arises when storage nodes are distributed and connected in a network. The issue of repairing a code arises when a storage node of the system fails. The problem is best illustrated through the example of Fig. 2 . Assume a file of total size M ¼ 4 blocks is stored using the ð4; 2Þ evenodd code of the previous example and the first node fails. A new node (to be called the newcomer) needs to construct and store two new blocks so that the three existing nodes combined with the newcomer still form a ð4; 2Þ MDS code. We call this the repair problem and focus on the required repair bandwidth. Clearly, repairing a single failure is easier than reconstructing all the data: since by assumption any two nodes contain enough information to recover all the data, the newcomer could download four blocks (from any two surviving nodes), reconstruct all four blocks, and store A 1 ; A 2 . However, as the example shows, it is possible to repair the failure by communicating only three blocks which can be used to solve for A 1 ; A 2 . Fig. 3 shows the repair of the fourth storage node. This can be achieved by using only three blocks BIB008 but one key difference is that the second node needs to compute a linear combination of the stored packets B 1 ; B 2 and the actual communicated block is B 1 þ B 2 . This shows clearly the necessity of network coding, creating linear combinations in intermediate nodes during the repair process. If the network bandwidth is more critical resource compared to disk access, as is often the case, an important consideration is to find what is the minimum required bandwidth and which codes can achieve it. The repair problem and the corresponding regenerating codes were introduced in BIB009 and received some attention in the recent literature  -  , BIB007 - BIB010 . Somehow surprisingly these new code constructions can achieve a rather significant reduction in repair network bandwidth, compared with the straightforward application of Reed-Solomon or other existing codes. In this paper, we provide an overview of this recent work and discuss several related research problems that remain open.