# Having Your Cake and Eating It Too: Jointly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth

←

**Page content transcription**

If your browser does not render page correctly, please read the page content below

Having Your Cake and Eating It Too: Jointly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth KV Rashmi, Preetum Nakkiran, Jingyan Wang, Nihar B. Shah, and Kannan Ramchandran, University of California, Berkeley https://www.usenix.org/conference/fast15/technical-sessions/presentation/rashmi This paper is included in the Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST ’15). February 16–19, 2015 • Santa Clara, CA, USA ISBN 978-1-931971-201 Open access to the Proceedings of the 13th USENIX Conference on File and Storage Technologies is sponsored by USENIX

Having Your Cake and Eating It Too: Jointly Optimal Erasure Codes for I/O, Storage and Network-bandwidth K. V. Rashmi, Preetum Nakkiran, Jingyan Wang, Nihar B. Shah, Kannan Ramchandran University of California, Berkeley Abstract Traditionally, data centers have been employing triple replication in order to ensure that the data is reliable and Erasure codes, such as Reed-Solomon (RS) codes, are that it is available to the applications that wish to con- increasingly being deployed as an alternative to data- sume it [15, 35, 10]. However, more recently, the enor- replication for fault tolerance in distributed storage sys- mous amount of data to be stored has made replication tems. While RS codes provide significant savings in an expensive option. Erasure coding offers an alternative storage space, they can impose a huge burden on the means of introducing redundancy, providing higher lev- I/O and network resources when reconstructing failed els of reliability as compared to replication while requir- or otherwise unavailable data. A recent class of era- ing much lower storage overheads [5, 39, 37]. Data cen- sure codes, called minimum-storage-regeneration (MSR) ters and cloud storage providers are increasingly turning codes, has emerged as a superior alternative to the popu- towards this option [14, 9, 10, 4], with Reed-Solomon lar RS codes, in that it minimizes network transfers dur- (RS) codes [31] being the most popular choice. RS ing reconstruction while also being optimal with respect codes make optimal use of storage resources in the sys- to storage and reliability. However, existing practical tem for providing reliability. This property makes RS MSR codes do not address the increasingly important codes appealing for large-scale, distributed storage sys- problem of I/O overhead incurred during reconstructions, tems where storage capacity is one of the critical re- and are, in general, inferior to RS codes in this regard. sources [1]. It has been reported that Facebook has saved In this paper, we design erasure codes that are simultane- multiple Petabytes of storage space by employing RS ously optimal in terms of I/O, storage, and network band- codes instead of replication in their data warehouse clus- width. Our design builds on top of a class of powerful ter [3]. practical codes, called the product-matrix-MSR codes. Under RS codes, redundancy is introduced in the fol- Evaluations show that our proposed design results in a lowing manner: a file to be stored is divided into equal- significant reduction the number of I/Os consumed dur- sized units, which we will call blocks. Blocks are ing reconstructions (a 5× reduction for typical parame- grouped into sets of k each, and for each such set of k ters), while retaining optimality with respect to storage, blocks, r parity blocks are computed. The set of these reliability, and network bandwidth. (k + r) blocks consisting of both the data and the par- ity blocks constitute a stripe. The parity blocks possess 1 Introduction the property that any k blocks out the (k + r) blocks in The amount of data stored in large-scale distributed a stripe suffice to recover the entire data of the stripe. It storage architectures such as the ones employed in data follows that the failure of any r blocks in a stripe can centers is increasing exponentially. These storage sys- be tolerated without any data loss. The data and parity tems are expected to store the data in a reliable and avail- blocks belonging to a stripe are placed on different nodes able fashion in the face of multitude of temporary and in the storage network, and these nodes are typically cho- permanent failures that occur in the day-to-day opera- sen from different racks. tions of such systems. It has been observed in a num- Due to the frequent temporary and permanent failures ber of studies that failure events that render data unavail- that occur in data centers, blocks are rendered unavail- able occur quite frequently in data centers (for example, able from time-to-time. These blocks need to be replaced see [32, 14, 28] and references therein). Hence, it is im- in order to maintain the desired level of reliability. Un- perative that the data is stored in a redundant fashion. der RS codes, since there are no replicas, a missing block USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 81

1" 1" 1" 1" 1" 1" decoding ! decoding! 2" 2" 2" 16MB"read" 2" 2.7MB"read" node! node! total"data"read" total"data"read" helpers! ="176MB" ="29.7MB" 6" total"transfer" 6" total"transfer" 6" 16MB"read" 6" 2.7MB"read" helpers! helpers! """"="96MB" helpers! """="29.7MB" 7" 7" 7" 16MB"read" 7" 2.7MB"read" 8" 8" 8" 16MB"read" 8" 2.7MB"read" 12" 12" 12" 16MB"read" 12" 2.7MB"read" (a) RS (b) MSR (e.g., PM-MSR) (a) PM-MSR (b) PM-RBT (this paper) Figure 1: Amount of data transfer involved in reconstruc- Figure 2: Amount of data read from disks during recon- tion of block 1 for an RS code with k = 6, r = 6 and an struction of block 1 for k = 6, r = 6, d = 11 with blocks MSR code with k = 6, r = 6, d = 11, with blocks of size of size 16MB. 16MB. The data blocks are shaded. with k = 6, r = 6 and d = 11. For these parameters, re- is replaced by downloading all data from (any) k other construction of block 1 under an MSR code is illustrated blocks in the stripe and decoding the desired data from in Figure 1b. In this example, the total network transfer it. We will refer to this operation as a reconstruction op- is only 29.7MB as opposed to 96MB under RS. MSR eration. A reconstruction operation may also be called codes are optimal with respect to storage and network upon to serve read requests for data that is currently un- transfers: the storage capacity and reliability is identical available. Such read requests are called degraded reads. to that under RS codes, while the network transfer is Degraded reads are served by reconstructing the requi- significantly lower than that under RS and in fact, is site data on-the-fly, i.e., immediately as opposed to as a the minimum possible under any code. However, MSR background job. codes do not optimize with respect to I/Os. The I/O Let us look at an example. Consider an RS code with overhead during a reconstruction operation in a system k = 6 and r = 6. While this code has a storage overhead employing an MSR code is, in general, higher than of 2x, it offers orders of magnitude higher reliability than that in a system employing RS code. This is illustrated 3x replication. Figure 1a depicts a stripe of this code, in Figure 2a which depicts the amount data read from and also illustrates the reconstruction of block 1 using the disks for reconstruction of block 1 under a practical data from blocks 2 to 7. We call the blocks that are called construction of MSR codes called product-matrix-MSR upon during the reconstruction process as helpers. In (PM-MSR) codes. This entails reading 16MB at each of Figure 1a, blocks 2 to 7 are the helpers. In this example, the 11 helpers, totaling 176MB of data read. in order to reconstruct a 16MB block, 6×16MB = 96MB I/Os are a valuable resource in storage systems. With of data is read from disk at the helpers and transferred the increasing speeds of newer generation network in- across the network to the node performing the decoding terconnects and the increasing storage capacities of in- computations. In general, the disk read and the network dividual storage devices, I/O is becoming the primary transfer overheads during a reconstruction operation is bottleneck in the performance of storage systems. More- k times that under replication. Consequently, under RS over, many applications that the storage systems serve codes, reconstruction operations result in a large amount today are I/O bound, for example, applications that serve of disk I/O and network transfers, putting a huge burden a large number of user requests [7] or perform data- on these system resources. intensive computations such as analytics [2]. Motivated There has been considerable interest in the recent by the increasing importance of I/O, in this paper, we in- past in designing a new class of (network-coding based) vestigate practical erasure codes for storage systems that codes called minimum-storage-regenerating (MSR) are I/O optimal. codes, which were originally formulated in [12]. Under In this paper, we design erasure codes that are simul- an MSR code, an unavailable block is reconstructed taneously optimal in terms of I/O, storage, and network by downloading a small fraction of the data from any bandwidth during reconstructions. We first identify two d (> k) blocks in the stripe, in a manner that the total properties that aid in transforming MSR codes to be disk- amount of data transferred during reconstruction is read optimal during reconstruction while retaining their lower than that in RS codes. Let us consider an example storage and network optimality. We show that a class 2 82 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

of powerful practical constructions for MSR codes, the block"1" w"symbols" ."".""." w"symbols" product-matrix-MSR codes (PM-MSR) [29], indeed sat- …" …" block"k" w"symbols" ."".""." w"symbols" isfy these desired properties. We then present an algo- rithm to transform any MSR code satisfying these prop- block"k+1" w"symbols" ."".""." w"symbols" erties into a code that is optimal in terms of the amount …" …" of data read from disks. We apply our transformation to block"n"" w"symbols" ."".""." w"symbols" """"(=k+r)" PM-MSR codes and call the resulting I/O optimal codes byte@level"" as PM-RBT codes. Figure 2b depicts the amount of stripe" data read for reconstruction of block 1: PM-RBT entails Figure 3: Illustration of notation: hierarchy of sym- reading only 2.7MB at each of the 11 helpers, totaling bols, byte-level stripes and block-level stripe. The first 29.7MB of data read as opposed to 176MB under PM- k blocks shown shaded are systematic. MSR. We note that the PM-MSR codes operate in the regime r ≥ k − 1, and consequently the PM-RBT codes also operate in this regime. tal number of blocks in a stripe. In order to encode the We implement PM-RBT codes and show through ex- k data blocks in a stripe, each of the k data blocks are periments on Amazon EC2 instances that our approach first divided into smaller units consisting of w symbols results in 5× reduction in I/Os consumed during re- each. A set of w symbols from each of the k blocks is construction as compared to the original product-matrix encoded to obtain the corresponding set of w symbols in codes, for a typical set of parameters. For general pa- the parity blocks. We call the set of data and parities at rameters, the number of I/Os consumed would reduce the granularity of w symbols as a byte-level stripe. Thus approximately by a factor of (d − k + 1). For typical in a byte-level stripe, B = kw original data symbols (w values of d and k, this can result in substantial gains. symbols from each of the k original data blocks) are en- We then show that if the relative frequencies of recon- coded to generate nw symbols (w symbols for each of the struction of blocks are different, then a more holistic n encoded blocks). The data symbols in different byte- system-level design of helper assignments is needed to level stripes are encoded independently in an identical optimize I/Os across the entire system. Such situations fashion. Hence in the rest of the paper, for simplicity of are common: for instance, in a system that deals with de- exposition, we will assume that each block consists of a graded reads as well as node failures, the data blocks will single byte-level stripe. We denote the B original data be reconstructed more frequently than the parity blocks. symbols as {m1 , . . . , mB }. For i ∈ {1, . . . , n}, we denote We pose this problem as an optimization problem and the w symbols stored in block i by {si1 , . . . , siw }. The present an algorithm to obtain the optimal solution to value of w is called the stripe-width. this problem. We evaluate our helper assignment algo- During reconstruction of a block, the other blocks rithm through simulations using data from experiments from which data is accessed are termed the helpers for on Amazon EC2 instances. that reconstruction operation (see Figure 1). The ac- cessed data is transferred to a node that performs the 2 Background decoding operation on this data in order to recover the 2.1 Notation and Terminology desired data. This node is termed the decoding node. The computations for encoding, decoding, and recon- 2.2 Linear and Systematic Codes struction in a code are performed using what is called A code is said to be linear, if all operations includ- finite-field arithmetic. For simplicity, however, through- ing encoding, decoding and reconstruction can be per- out the paper the reader may choose to consider usual formed using linear operations over the finite field. Any arithmetic without any loss in comprehension. We will linear code can be represented using a (nw × B) matrix refer the smallest granularity of the data in the system G, called its generator matrix. The nw encoded symbols as a symbol. The actual size of a symbol is dependent can be obtained by multiplying the generator matrix with on the finite-field arithmetic that is employed. For sim- a vector consisting of the B message symbols: plicity, the reader may consider a symbol to be a single byte. T G m 1 m2 · · · m B . (1) A vector will be column vector by default. We will use boldface to denote column vectors, and use T to denote We will consider only linear codes in this paper. a matrix or vector transpose operation. In most systems, the codes employed have the prop- We will now introduce some more terminology in ad- erty that the original data is available in unencoded (i.e., dition to that introduced in Section 1. This terminology raw) form in some k of the n blocks. This property is is illustrated in Figure 3. Let n (= k + r) denote the to- appealing since it allows for read requests to be served 3 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 83

directly without having to perform any decoding opera- by a helper may, in general, depend on the choice of tions. Codes that possess this property are called system- (d − 1) other helpers. atic codes. We will assume without loss of generality Consider the reconstruction of block f . Let D denote that the first k blocks out of the n encoded blocks store that set of d helpers participating in this reconstruction the unencoded data. These blocks are called systematic operation. We denote the symbol that a helper block h blocks. The remaining (r = n − k) blocks store the en- transfers to aid in the reconstruction of block f when the coded data and are called parity blocks. For a linear sys- set of helpers is denoted by D as th f D . This resulting tematic code, the generator matrix can be written as symbol is transferred to the decoding node, and the d symbols received from the helpers are used to reconstruct I block f . , (2) Ĝ Like RS codes, MSR codes are optimal with respect to the storage-reliability tradeoff. Furthermore, they meet where I is a (B × B) identity matrix, and Ĝ is a ((nw − the lower bound on the amount of data transfer for recon- B) × B) matrix. The codes presented in this paper are struction, and hence are optimal with respect to storage- systematic. bandwidth tradeoff as well. 2.3 Optimality of Storage Codes 2.5 Product-Matrix-MSR Codes A storage code is said to be optimal with respect to Product-matrix-MSR codes are a class of practical the storage-reliability tradeoff if it offers maximum fault constructions for MSR codes that were proposed in [29]. tolerance for the storage overhead consumed. A (k, r) RS These codes are linear. We consider the systematic ver- code adds r parity blocks, each of the same size as that sion of these codes where the first k blocks store the data of the k data blocks. These r parity blocks have the prop- in an unencoded form. We will refer to these codes as erty that any k out of these (k + r) blocks are sufficient to PM-vanilla codes. recover all the original data symbols in the stripe. Thus PM-vanilla codes exist for all values of the system failure of any r arbitrary blocks among the (k + r) blocks parameters k and d satisfying d ≥ (2k − 2). In order in a stripe can be tolerated without any data loss. It is to ensure that, there are atleast d blocks that can act well known from analytical results [22] that this is the as helpers during reconstruction of any block, we need maximum possible fault tolerance that can be achieved atleast (d +1) blocks in a stripe, i.e., we need n ≥ (d +1). for the storage overhead used. Hence, RS codes are opti- It follows that PM-vanilla codes need a storage overhead mal with respect to the storage-reliability tradeoff. of In [12], the authors introduced another dimension of n 2k − 1 1 ≥ = 2− . (3) optimality for storage codes, that of reconstruction band- k k k width, by providing a lower bound on the amount of data We now briefly describe the reconstruction operation that needs to be transferred during a reconstruction op- in PM-vanilla codes to the extent that is required for the eration. Codes that meet this lower bound are termed exposition of this paper. We refer the interested reader optimal with respect to storage-bandwidth tradeoff. to [29] for more details on how encoding and decoding operations are performed. Every block i (1 ≤ i ≤ n) is 2.4 Minimum Storage Regenerating Codes assigned a vector gi of length w, which we will call the A minimum-storage-regenrating (MSR) code [12] is reconstruction vector for block i. Let gi = [gi1 , . . . , giw ]T . associated with, in addition to the parameters k and r in- The n (= k + r) vectors, {g1 , . . . , gn }, are designed such troduced Section 1, a parameter d (> k) that refers to the that any w of these n vectors are linearly independent. number of helpers used during a reconstruction opera- During reconstruction of a block, say block f , each tion. For an MSR code, the stripe-width w is dependent of the chosen helpers, take a linear combination of their on the parameters k and d, and is given by w = d − k + 1. w stored symbols with the reconstruction vector of the Thus, each byte-level stripe stores B = kw = k(d − k + 1) failed block, gf , and transfer the result to the decoding original data symbols. node. That is, for reconstruction of block f , helper block We now describe the reconstruction process under the h computes and transfers the symbol framework of MSR codes. A block to be reconstructed w can choose any d other blocks as helpers from the re- th f D = maining (n − 1) blocks in the stripe. Each of these d ∑ sh j g f j , (4) j=1 helpers compute some function of the w symbols stored whose resultant is a single symbol (for each byte-level where {sh1 , . . . , shw } are the w symbols stored in block h, stripe). Note that the symbol computed and transferred and D denotes the set of helpers. 4 84 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

PM-vanilla codes are optimal with respect to the We now present our technique for achieving the storage-reliability tradeoff and storage-bandwidth trade- reconstruct-by-transfer property in MSR codes. off. However, PM-vanilla codes are not optimal with re- spect to the amount of data read during reconstruction: 3.2 Achieving Reconstruct-by-transfer The values of most coefficients g f j in the reconstruction Towards the goal of designing reconstruct-by-transfer vector are non-zero. Since the corresponding symbol sh j codes, we first identify two properties that we would like must be read for every g f j that is non-zero, the absence a helper to satisfy. We will then provide an algorithm to of sparsity in g f j results in a large I/O overhead during convert any (linear) MSR code satisfying these two prop- the rebuilding process, as illustrated in Figure 2a (and erties into one that can perform reconstruct-by-transfer at experimentally evaluated in Figure 7). such a helper. Property 1: The function computed at a helper is in- 3 Optimizing I/O during reconstruction dependent of the choice of the remaining (d − 1) helpers. We will now employ the PM-vanilla codes to con- In other words, for any choice of h and f , th f D is inde- struct codes that optimize I/Os during reconstruction, pendent of D (recall the notation th f D from Section 2.4). while retaining optimality with respect to storage, reli- This allows us to simplify the notation by dropping the ability and network-bandwidth. In this section, we will dependence on D and referring to th f D simply as th f . optimize the I/Os locally in individual blocks, and Sec- Property 2: Assume Property 1 is satisfied. Then the tion 4 will build on these results to design an algorithm to helper would take (n − 1) linear combinations of its own optimize the I/Os globally across the entire system. The data to transmit for the reconstruction of the other (n − 1) resulting codes are termed the PM-RBT codes. We note blocks in the stripe. We want every w of these (n − 1) that the methods described here are more broadly appli- linear combinations to be linearly independent. cable to other MSR codes as discussed subsequently. We now show that under the product-matrix-MSR (PM-vanilla) codes, every helper satisfies the two prop- 3.1 Reconstruct-by-transfer erties enumerated above. Recall from Equation (4), the computation performed at the helpers during reconstruc- Under an MSR code, during a reconstruction opera- tion in PM-vanilla codes. Observe that the right hand tion, a helper is said to perform reconstruct-by-transfer side of Equation (4) is independent of ‘D’, and therefore (RBT) if it does not perform any computation and merely the data that a helper transfers during a reconstruction transfers one its stored symbols (per byte-level stripe) to operation is dependent only on the identity of the helper the decoding node.1 In the notation introduced in Sec- and the block being reconstructed. The helper, therefore, tion 2, this implies that gf in (4) is a unit vector, and does not need to know the identity of the other helpers. th f D ∈ {sh1 , . . . , shw } . It follows that PM-vanilla codes satisfy Property 1. Let us now investigate Property 2. Recall We call such a helper as an RBT-helper. At an RBT- from Equation (4), the set of (n − 1) symbols, helper, the amount of data read from the disks is equal to {th1 , . . . ,th(h−1) ,th(h+1) , . . . ,thn }, that a helper block h the amount transferred through the network. transfers to aid in reconstruction of each the other (n − 1) During a reconstruction operation, a helper reads req- blocks in the stripe. Also, recall that the reconstruction uisite data from the disks, computes (if required) the de- vectors {g1 , . . . , gn } assigned to the n blocks are chosen sired function, and transfers the result to the decoding such that every w of these vectors are linearly indepen- node. It follows that the amount of network transfer per- dent. It follows that for every block, the (n − 1) linear formed during reconstruction forms a lower bound on the combinations that it computes and transfers for the re- amount of data read from the disk at the helpers. Thus, construction of the other (n − 1) blocks in the stripe have a lower bound on the network transfers is also a lower the property of any w being independent. PM-vanilla bound on the amount of data read. On the other hand, codes thus satisfy Property 2 as well. MSR codes are optimal with respect to network trans- PM-vanilla codes are optimal with respect to the fers during reconstruction since they meet the associated storage-bandwidth tradeoff (Section 2.3). However, lower bound [12]. It follows that, under an MSR code, these codes are not optimized in terms of I/O. As we will an RBT-helper is optimal with respect to the amount of show through experiments on the Amazon EC2 instances data read from the disk. (Section 5.3), PM-vanilla codes, in fact, have a higher I/O overhead as compared to RS codes. In this section, 1 This property was originally titled ‘repair-by-transfer’ in [34] since we will make use of the two properties listed above to the focus of that paper was primarily on node failures. In this paper, transform the PM-vanilla codes into being I/O optimal we consider more general reconstruction operations that include node- repair, degraded reads etc., and hence the slight change in nomencla- for reconstruction, while retaining its properties of being ture. storage and network optimal. While we focus on the PM- 5 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 85

vanilla codes for concreteness, we remark that the tech- described below. nique described is generic and can be applied to any (lin- Since every step of Algorithm 1 is linear, the encod- ear) MSR code satisfying the two properties listed above. ing under Algorithm 1 can be represented by a generator Under our algorithm, each block will function as an matrix, say GAlg1 , of dimension (nw × B) and the encod- RBT-helper for some w other blocks in the stripe. For ing can be performed by the matrix-vector multiplica- T the time being, let us assume that for each helper block, tion: GAlg1 m1 m2 · · · mB . Partition GAlg1 as the choice of these w blocks is given to us. Under this assumption, Algorithm 1 outlines the procedure to con- G1 GAlg1 = , (5) vert the PM-vanilla code (or in general any linear MSR G2 code satisfying the two aforementioned properties) into one in which every block can function as an RBT-helper where G1 is a (B × B) matrix corresponding to the en- for w other blocks. Section 4 will subsequently provide coded symbols in the first k systematic blocks, and G2 is an algorithm to make the choice of RBT-helpers for each an ((nw − B) × B matrix. The symbol remapping step to block to optimize the I/O cost across the entire system. make the transformed code systematic involves multipli- Let us now analyze Algorithm 1. Observe that each cation by G−11 . The invertibility of G1 follows from the block still stores w symbols and hence Algorithm 1 fact that G1 corresponds to the encoded symbols in the does not increase the storage requirements. Further, first k blocks and all the encoded symbols in any set of k recall from Section 2.5 that the reconstruction vectors blocks are linearly independent. Thus the entire encod- gih1 , · · · , gihw are linearly independent. Hence the ing process becomes transformation performed in Algorithm 1 is an invertible transformation within each block. Thus the property of m1 m1 m2 m being able to recover all the data from any k blocks con- G1 I 2 G−1 . = .. , (6) tinues to hold as under PM-vanilla codes, and the trans- G2 1 .. G2 G1−1 . formed code retains the storage-reliability optimality. mB mB Let us now look at the reconstruction process in the transformed code given by Algorithm 1. The symbol where I is the (B×B) identity matrix. We can see that the transferred by any helper block h for the reconstruc- symbol remapping step followed by Algorithm 1 makes tion of any block f remains identical to that under the the first k blocks systematic. PM-vanilla code, i.e., is as given by the right hand side Since the transformation involved in the symbol of Equation (4). Since the transformation performed in remapping step is invertible and is applied to the data Algorithm 1 is invertible within each block, such a re- symbols before the encoding process, this step does not construction is always possible and entails the minimum affect the performance with respect to storage, reliability, network transfers. Thus, the code retains the storage- and network and I/O consumption during reconstruction. bandwidth optimality as well. Observe that for a block f in the set of the w blocks for which a block h intends to 3.4 Making Reads Sequential function as an RBT-helper, block h now directly stores Optimizing the amount of data read from disks might the symbol th f = [sh1 · · · shw ]g f . As a result, whenever not directly correspond to optimized I/Os, unless the data called upon to help block f , block h can directly read and read is sequential. In the code obtained from Algo- transfer this symbol, thus performing a reconstruct-by- rithm 1, an RBT-helper reads one symbol per byte-level transfer operation. As discussed in Section 3.1, by virtue stripe during a reconstruction operation. Thus, if one of its storage-bandwidth optimality and reconstruct-by- chooses the w symbols belonging to a byte-level stripe transfer, the transformed code from Algorithm 1 (lo- within a block in a contiguous manner, as in Figure 3, cally) optimizes the amount of data read from disks at the data read at the helpers during reconstruction oper- the helpers. We will consider optimizing I/O across the ations will be fragmented. In order to the read sequen- entire system in Section 4. tial, we employ the hop-and-couple technique introduced 3.3 Making the Code Systematic in [27]. The basic idea behind this technique is to choose symbols that are farther apart within a block to form the Transforming the PM-vanilla code using Algorithm 1 byte-level stripes. If the stripe-width of the code is w, may result in a loss of the systematic property. A fur- then choosing symbols that are a w1 fraction of the block ther transformation of the code, termed ‘symbol remap- size away will make the read at the helpers during recon- ping’, is required to make the transformed code system- struction operations sequential. Note that this technique atic. Symbol remapping [29, Theorem 1] involves trans- does not affect the natural sequence of the raw data in the forming the original data symbols {m1 , . . . , mB } using a data blocks, so the normal read operations can be served bijective transformation before applying Algorithm 1, as directly without any sorting. In this manner, we ensure 6 86 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

Algorithm 1 Algorithm to achieve reconstruct-by-transfer at helpers Encode the data in k data blocks using PM-vanilla code to obtain the n encoded blocks for every block h in the set of n blocks ...Let {ih1 , . . . , ihw } denote the set of w blocks that block h will help to reconstruct by transfer ...Let {sh1 , . . . , shw } denote the set of w symbols that block h stores under PM − vanilla ...Compute [sh1 · · · shw ] gih1 · · · gihw and store the resulting w symbols in block h instead of the original w symbols that reconstruct-by-transfer optimizes I/O at the helpers along with the amount of data read from the disks. 4 Optimizing RBT-Helper Assignment In Algorithm 1 presented in Section 3, we assumed the choice of the RBT-helpers for each block to be given to us. Under any such given choice, we saw how to perform a local transformation at each block such that reconstruction-by-transfer could be realized under that (a) Total number of I/Os consumed assignment. In this section, we present an algorithm to make this choice such that the I/Os consumed during re- construction operations is optimized globally across the entire system. Before going into any details, we first make an observation which will motivate our approach. A reconstruction operation may be instantiated in any one of the following two scenarios: • Failures: When a node fails, the reconstruction op- eration restores the contents of that node in another storage nodes in order to maintain the system reli- (b) Maximum of the I/O completion times at ability and availability. Failures may entail recon- helpers struction operations of either systematic or parity Figure 4: Reconstruction under different number of blocks. RBT-helpers for k = 6, d = 11, and a block size of 16MB. • Degraded reads: When a read request arrives, the systematic block storing the requested data may be busy or unavailable. The request is then served by of reconstruction operations between the parity and sys- calling upon a reconstruction operation to recover tematic blocks or the preferential treatment that one may the desired data from the remaining blocks. This is wish to confer to the reconstruction of systematic blocks called a degraded read. Degraded reads entail re- in order to serve degraded reads faster. construction of only the systematic blocks. When reconstruction of any block is to be carried out, either for repairing a possible failure or for a degraded A system may be required to support either one or both read, not all remaining blocks may be available to help in of these scenarios, and as a result, the importance asso- the reconstruction process. The parameter p (0 ≤ p ≤ 1) ciated to the reconstruction of a systematic block may aims to capture this fact: when the reconstruction of a often be higher than the importance associated to the re- block is to be performed, every other block may indi- construction of a parity block. vidually be unavailable with a probability p independent We now present a simple yet general model that we of all other blocks. Our intention here is to capture the will use to optimize I/Os holistically across the system. fact that if a block has certain number of helpers that can The model has two parameters, δ and p. The relative function as RBT-helpers, not all of them may be avail- importance between systematic and parity blocks is cap- able when reconstruction is to be performed. tured by the first parameter δ . The parameter δ takes We performed experiments on Amazon EC2 measur- a value between (and including) 0 and 1, and the cost ing the number of I/Os performed for reconstruction associated with the reconstruction of any parity block when precisely j (0 ≤ j ≤ d) of the available helpers is assumed to be δ times the cost associated to the re- are RBT-helpers and the remaining (d − j) helpers are construction of any systematic block. The “cost” can be non-RBT-helpers. The non-RBT-helpers do not perform used to capture the relative difference in the frequency reconstruct-by-transfer, and are hence optimal with re- 7 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 87

Algorithm 2 Algorithm for optimizing RBT-helper assignment //To compute number of RBT-helpers for each block Set num rbt helpers[block] = 0 for every block for total rbt help = nw to 1 ...for block in all blocks ......if num rbt helpers[block] < n-1 .........Set improvement[block] = Cost(num rbt helpers[block]) - Cost(num rbt helpers[block]+1) ......else .........Set improvement[block] = -1 ...Let max improvement be the set of blocks with the maximum value of improvement ...Let this block be a block in max improvement with the largest value of num rbt helpers ...Set num rbt helpers[this block] = num rbt helpers[this block]+1 ... //To select the RBT-helpers for each block Call the Kleitman-Wang algorithm [20] to generate a digraph on n vertices with incoming degrees num rbt helpers and all outgoing degrees equal to w for every edge i → j in the digraph ...Set block i as an RBT-helper to block j spect to network transfers but not the I/Os. The result ber of RBT-helpers for each block as determined above of this experiment aggregated from 20 runs is shown in and that no block can help itself. The Kleitman-Wang Figure 4a, where we see that the number of I/Os con- algorithm [20] facilitates such a construction. sumed reduces linearly with an increase in j. We also The following theorem provides rigorous guarantees measured the maximum of the time taken by the d helper on the performance of Algorithm 2. blocks to complete the requisite I/O, which is shown Fig- ure 4b. Observe that as long as j < d, this time decays Theorem 1 For any given (δ , p), Algorithm 2 minimizes very slowly upon increase in j, but reduces by a large the expected amount of disk reads for reconstruction op- value when j crosses d. The reason for this behavior is erations in the system. Moreover, among all options re- that the time taken by the non-RBT-helpers to complete sulting in this minimum disk read, the algorithm further the required I/O is similar, but is much larger than the chooses the option which minimizes the expected time of time taken by the RBT-helpers. reconstruction. Algorithm 2 takes the two parameters δ and p as in- The proof proceeds by first showing that the expected re- puts and assigns RBT-helpers to all the blocks in the construction cost of any particular block is convex in the stripe. The algorithm optimizes the expected cost of I/O number of RBT-helpers assigned to it. It then employs for reconstruction across the system, and furthermore this convexity, along with the fact that the expected cost subject to this minimum cost, minimizes the expected must be non-increasing in the number of assigned RBT- time for reconstruction. The algorithm takes a greedy ap- helpers, to show that no other assignment algorithm can proach in deciding the number of RBT-helpers for each yield a lower expected cost. We omit the complete proof block. Observing that, under the code obtained from Al- of the theorem due to space constraints. gorithm 1, each block can function as an RBT-helper for The output of Algorithm 2 for n = 15, k = 6, d = 11 at most w other blocks, the total RBT-helping capacity and (δ = 0.25, p = 0.03) is illustrated in Fig 5. Blocks in the system is nw. This total capacity is partitioned 1, . . . , 6 are systematic and the rest are parity blocks. among the n blocks as follows. The allocation of each Here, Algorithm 2 assigns 12 RBT-helpers to each of the unit of RBT-helping capacity is made to the block whose systematic blocks, and 11 and 7 RBT-helpers to the first expected reconstruction cost will reduce the most with and second parity blocks respectively. the help of this additional RBT-helper. The expected re- The two ‘extremities’ of the output of Algorithm 2 construction cost for any block, under a given number form two interesting special cases: of RBT-helper blocks, can be easily computed using the parameter p; the cost of a parity block is further mul- 1. Systematic (SYS): All blocks function as RBT- tiplied by δ . Once the number of RBT-helpers for each helpers for the k systematic blocks. block is obtained as above, all that remains is to make the choice of the RBT-helpers for each block. In making this 2. Cyclic (CYC): Block i ∈ {1, . . . , n} functions as an choice, the only constraints to be satisfied are the num- RBT-helper for blocks {i + 1, . . . , i + w} mod n. 8 88 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

14 5 6 7 13 15 1 8 12 Figure 6: Total amount of data transferred across the network from the helpers during reconstruction. Y-axes 9 scales vary across plots. 4 2 11 3 10 attached to 410 GB of hard disk storage). We chose m1.medium type since these instances have hard-disk storage. We evaluated the encoding and decoding per- Figure 5: The output of Algorithm 2 for the parameters formance on instances of type m3.medium which run on n = 15, k = 6, d = 11, and (δ = 0.25, p = 0.03) depict- an Intel Xeon E5-2670v2 processor with a 2.5GHz clock ing the assignment of RBT-helpers. The directed edges speed. All evaluations are single-threaded. from a block indicate the set of blocks that it helps to All the plots are from results aggregated over 20 inde- reconstruct-by-transfer. Systematic blocks are shaded. pendent runs showing the median values with 25th and 75th percentiles. In the plots, PM refers to PM-vanilla codes and RBT refers to PM-RBT codes. Unless other- Algorithm 2 will output the SYS pattern if, for example, wise mentioned, all evaluations on reconstruction are for reconstruction of parity blocks incur negligible cost (δ is (n = 12, k = 6, d = 11), considering reconstruction of close to 0) or if δ < 1 and p is large. Algorithm 2 will block 1 (i.e., the first systematic block) with all d = 11 output the CYC pattern if, for instance, the systematic RBT-helpers. We note that all evaluations except the one and the parity blocks are treated on equal footing (δ is on decoding performance (Section 5.5) are independent close to 1), or in low churn systems where p is close to of the identity of the block being reconstructed. 0. While Theorem 1 provides mathematical guarantees 5.2 Data Transfers Across the Network on the performance of Algorithm 2, Section 5.7 will present an evaluation of its performance via simulations Figure 6 compares the total amount of data trans- using data from Amazon EC2 experiments. ferred from helper blocks to the decoding node during reconstruction of a block. We can see that, both PM- 5 Implementation and Evaluation vanilla and PM-RBT codes have identical and signifi- cantly lower amount of data transferred across the net- work as compared to RS codes: the network transfers during the reconstruction for PM-vanilla and PM-RBT 5.1 Implementation and Evaluation Set- are about 4x lower than that under RS codes. ting 5.3 Data Read and Number of I/Os We have implemented the PM-vanilla codes [29] and the PM-RBT codes (Section 3 and Section 4) in C/C++. A comparison of the total number of disk I/Os and In our implementation, we make use of the fact that the total amount of data read from disks at helpers dur- the PM-vanilla and the PM-RBT codes are both lin- ing reconstruction are shown in Figure 7a and Figure 7b ear. That is, we compute the matrices that represent respectively. We observe that the amount of data read the encoding and decoding operations under these codes from the disks is as given by the theory across all block and execute these operations with a single matrix-vector sizes that we experimented with. We can see that while multiplication. We employ the Jerasure2 [25] and GF- PM-vanilla codes provide significant savings in network Complete [26] libraries for finite-field arithmetic opera- transfers during reconstruction as compared to RS as tions also for the RS encoding and decoding operations. seen in Figure 6, they result in an increased number of We performed all the evaluations, except those in Sec- I/Os. Furthermore, the PM-RBT code leads to a signif- tion 5.5 and Section 5.6, on Amazon EC2 instances of icant reduction in the number of I/Os consumed and the type m1.medium (with 1 CPU, 3.75 GB memory, and amount of data read from disks during reconstruction. 9 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 89

(a) Total number of disk I/Os consumed Figure 9: Comparison of decoding speed during recon- struction for various values of k with n = 2k, and d = 2k − 1 for PM-vanilla and PM-RBT. 5.5 Decoding Performance (b) Total amount of data read from disks We measure the decoding performance during re- Figure 7: Total number of disk I/Os and total amount of construction in terms of the amount of data of the data read from disks at the helpers during reconstruction. failed/unavailable block that is decoded per unit time. Y-axes scales vary across plots. We compare the decoding speed for various values of k, and fix n = 2k and d = 2k − 1 for both PM-vanilla and PM-RBT. For reconstruction under RS codes, we observed that a higher number of systematic helpers re- sults in a faster decoding process, as expected. In the plots discussed below, we will show two extremes of this spectrum: (RS1) the best case of helper blocks compris- ing all the existing (k − 1) = 5 systematic blocks and one parity block, and (RS2) the worst case of helper blocks comprising all the r = 6 parity blocks. Figure 9 shows a comparison of the decoding speed Figure 8: Maximum of the I/O completion times at during reconstruction of block 0. We see that the best helpers. Y-axes scales vary across plots. case (RS1) for RS is the fastest since the operation in- volves only substitution and solving a small number of linear equations. On the other extreme, the worst case (RS2) for RS is much slower than PM-vanilla and PM- For all the block sizes considered, we observed approx- RBT. The actual decoding speed for RS would depend on imately a 5x reduction in the number of I/Os consumed the number of systematic helpers involved and the per- under the PM-RBT as compared to PM-vanilla (and ap- formance would lie between the RS1 and RS2 curves. proximately 3× reduction as compared to RS). We can also see that the transformations introduced in this paper to optimize I/Os does not affect the decoding performance: PM-vanilla and PM-RBT have roughly the 5.4 I/O Completion Time same decoding speed. In our experiments, we also ob- served that in both PM-vanilla and PM-RBT, the decod- The I/O completion times during reconstruction are ing speeds were identical for the n blocks. shown in Figure 8. During a reconstruction operation, the I/O requests are issued in parallel to the helpers. 5.6 Encoding Performance Hence we plot the the maximum of the I/O completion times from the k = 6 helpers for RS coded blocks and We measure the encoding performance in terms of the the maximum of the I/O completion times from d = 11 amount of data encoded per unit time. A comparison helpers for PM-vanilla and PM-RBT coded blocks. We of the encoding speed for varying values of k is shown can see that PM-RBT code results in approximately 5× in Figure 10. Here we fix d = 2k − 1 and n = 2k and to 6× reduction I/O completion time. vary the values of k. The lower encoding speeds for PM- 10 90 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

Figure 11: A box plot of the reconstruction cost for dif- ferent RBT-helper assignments, for δ = 0.25, p = 0.03, Figure 10: Encoding speed for various values of k with n = 15, k = 6, d = 11, and block size of 16MB. In each n = 2k, and d = 2k − 1 for PM-vanilla and PM-RBT. box, the mean is shown by the small (red) square and the median is shown by the thick (red) line. vanilla and PM-RBT as compared to RS are expected 5.7 RBT-helper Assignment Algorithm since the encoding complexity of these codes is higher. In RS codes, computing each encoded symbol involves a As discussed earlier in Section 4, we conducted exper- linear combination of only k data symbols, which incurs iments on EC2 performing reconstruction using differ- a complexity of O(k), whereas in PM-vanilla and PM- ent number of RBT-helpers (see Figure 4). We will now RBT codes each encoded symbol is a linear combination evaluate the performance of the helper assignment algo- of kw symbols which incurs a complexity of O(k2 ). rithm, Algorithm 2, via simulations employing the mea- surements obtained from these experiments. The plots of Interestingly, we observe that encoding under PM- the simulation results presented here are aggregated from RBT with the SYS RBT-helper pattern (Section 4) is one million runs of the simulation. In each run, we failed significantly faster than that under the PM-vanilla code. one of the n blocks chosen uniformly at random. For its This is because the generator matrix of the code under the reconstruction operation, the remaining (n − 1) blocks SYS RBT-helper pattern is sparse (i.e., has many zero- were made unavailable (busy) with a probability p each, valued entries); this reduces the number of finite-field thereby also making some of the RBT-helpers assigned multiplication operations, that are otherwise computa- to this block unavailable. In the situation when only j tionally heavy. Thus, PM-RBT with SYS RBT-helper RBT-helpers are available (for any j in {0, . . . , d}), we pattern results in faster encoding as compared to PM- obtained the cost of reconstruction (in terms of number vanilla codes, in addition to minimizing the disk I/O dur- of I/Os used) by sampling from the experimental values ing reconstruction. Such sparsity does not arise under the obtained from our EC2 experiments with j RBT-helpers CYC RBT-helper pattern, and hence its encoding speed and (d − j) non-RBT-helpers (Figure 4a). The recon- is almost identical to PM-vanilla. struction cost for parity blocks is weighted by δ . We believe that the significant savings in disk I/O of- Figure 11 shows the performance of the RBT-helper fered by PM-RBT codes outweigh the cost of decreased assignment algorithm for the parameter values δ = 0.25 encoding speed. This is especially true for systems stor- and p = 0.03. The plot compares the performance of ing immutable data (where encoding is a one-time over- three possible choices of helper assignments: the assign- head) and where encoding is performed as a background ment obtained by Algorithm 2 for the chosen param- operation without falling along any critical path. This eters (shown in Figure 5), and the two extremities of is true in many cloud storage systems such as Windows Algorithm 2, namely SYS and CYC. We make the fol- Azure and the Hadoop Distributed File System where lowing observations from the simulations. In the CYC data is first stored in a triple replicated fashion and then case, the unweighted costs for reconstruction are homo- encoded in the background. geneous across systematic and parity blocks due to the homogenity of the CYC pattern, but upon reweighting Remark: The reader may observe that the speed by δ , the distribution of costs become (highly) bi-modal. (MB/s) of encoding in Figure 10 is faster than that of de- In Figure 11, the performance of SYS and the solution coding during reconstruction in Figure 9. This is because obtained from Algorithm 2 are comparable, with the out- encoding addresses k blocks at a time while the decoding put of Algorithm 2 slightly outperforming SYS. This is operation addresses only a single block. as expected since for the given choice of parameter val- 11 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 91

ues δ = 0.25 and p = 0.03, the output of Algorithm 2 the current paper are inspired by the techniques intro- (see Figure 5) is close to SYS pattern. duced in [33]. In [36] and [38], the authors present op- timizations to reduce the amount of data read for recon- 6 Related Literature struction in array codes with two parities. [19] presents In this section, we review related literature on optimiz- a search-based approach to find reconstruction symbols ing erasure-coded storage systems with respect to net- that optimize I/O for arbitrary binary erasure codes, but work transfers and the amount of data read from disks this search problem is shown to be NP-hard. during reconstruction operations. Several works (e.g., [8, 24, 11]) have proposed system- In [17], the authors build a file system based on level solutions to reduce network and I/O consumption the minimum-bandwidth-regenerating (MBR) code con- for reconstruction, such as caching the data read during structions of [34]. While system minimizes network reconstruction, batching multiple reconstruction opera- transfers and the amount of data read during reconstruc- tions, and delaying the reconstruction operations. While tion, it mandates additional storage capacity to achieve these solutions consider the erasure code as a black-box, the same. That is, the system is not optimal with respect our work optimizes this black-box and can be used in to storage-reliability tradeoff (recall from Section 2). conjunction with these system-level solutions. The storage systems proposed in [18, 23, 13] employ a class of codes called local-repair codes which opti- 7 Conclusion mize the number of blocks accessed during reconstruc- tion. This, in turn, also reduces the amount of disk reads With rapid increases in the network-interconnect and network transfers. However, these systems also ne- speeds and the advent of high-capacity storage de- cessitate an increase in storage-space requirements in vices, I/O is increasingly becoming the bottleneck in the form of at least 25% to 50% additional parities. many large-scale distributed storage systems. A family In [21], authors present a system which combines local- of erasure-codes called minimum-storage-regeneration repair codes with the graph-based MBR codes presented (MSR) codes has recently been proposed as a superior in [34]. This work also necessitates additional storage alternative to the popular Reed-Solomon codes in terms space. The goal of the present paper is to optimize I/Os of storage, fault-tolerance and network-bandwidth con- consumed during reconstruction without losing the opti- sumed. However, existing practical MSR codes do not mality with respect to storage-reliability tradeoff. address the critically growing problem of optimizing for [16] and [6], the authors present storage systems based I/Os. In this work, we show that it is possible to have on random network-coding that optimize resources con- your cake and eat it too, in the sense that we can min- sumed during reconstruction. Here the data that is recon- imize disk I/O consumed, while simultaneously retain- structed is not identical and is only “functionally equiv- ing optimality in terms of both storage, reliability and alent” to the failed data. As a consequence, the system network-bandwidth. is not systematic, and needs to execute the decoding pro- Our solution is based on the identification of two key cedure for serving every read request. The present paper properties of existing MSR codes that can be exploited designs codes that are systematic, allowing read requests to make them I/O optimal. We presented an algorithm during the normal mode of operation to be served directly to transform Product-Matrix-MSR codes into I/O opti- without executing the decoding procedure. mal codes (which we term the PM-RBT codes), while re- In [27], the authors present a storage system based taining their storage and network optimality. Through an on a class of codes called Piggybacked-RS codes [30] extensive set of experiments on Amazon EC2, we have that also reduces the amount of data read during recon- shown that our proposed PM-RBT codes result in signif- struction. However, PM-RBT codes provide higher sav- icant reduction in the I/O consumed. Additionally, we ings as compared to these codes. On the other hand, have presented an optimization framework for helper as- Piggybacked-RS codes have the advantage of being ap- signment to attain a system-wide globally optimal solu- plicable for all values of k and r, whereas PM-RBT codes tion, and established its performance through simulations are only applicable for d ≥ (2k − 2) and thereby necessi- based on EC2 experimentation data. tate a storage overhead of atleast (2 − 1k ). In [19], authors present Rotated-RS codes which also reduce the amount 8 Acknowledgements of data read during rebuilding. However, the reduction achieved is significantly lower than that in PM-RBT. We thank Ankush Gupta and Diivanand Ramalingam In [33], the authors consider the theory behind for their contributions to the initial version of the PM- reconstruction-by-transfer for MBR codes, which as dis- vanilla code implementation. We also thank our shep- cussed earlier are not optimal with respect to storage- herd Randal Burns and the anonymous reviewers for reliability tradeoff. Some of the techniques employed in their valuable comments. 12 92 13th USENIX Conference on File and Storage Technologies (FAST ’15) USENIX Association

References [18] H UANG , C., S IMITCI , H., X U , Y., O GUS , A., C ALDER , B., G OPALAN , P., L I , J., AND Y EKHANIN , S. Erasure coding in [1] Facebook’s Approach to Big Data Storage Challenge. Windows Azure Storage. In USENIX Annual Technical Confer- http://www.slideshare.net/Hadoop Summit/facebooks-approach- ence (ATC) (June 2012). to-big-data-storage-challenge. [19] K HAN , O., B URNS , R., P LANK , J., P IERCE , W., AND H UANG , [2] Hadoop. http://hadoop.apache.org. C. Rethinking erasure codes for cloud file systems: minimizing [3] HDFS RAID. http://www.slideshare.net/ydn/hdfs-raid-facebook. I/O for recovery and degraded reads. In Proc. Usenix Conference [4] Seamless reliability. http://www.cleversafe.com/overview/reliable, on File and Storage Technologies (FAST) (2012). Feb. 2014. [20] K LEITMAN , D. J., AND WANG , D.-L. Algorithms for construct- [5] A BD -E L -M ALEK , M., C OURTRIGHT II, W. V., C RANOR , ing graphs and digraphs with given valences and factors. Discrete C., G ANGER , G. R., H ENDRICKS , J., K LOSTERMAN , A. J., Mathematics 6, 1 (1973), 79–88. M ESNIER , M. P., P RASAD , M., S ALMON , B., S AMBASIVAN , R. R., S INNAMOHIDEEN , S., S TRUNK , J. D., T HERESKA , E., [21] K RISHNAN , M. N., P RAKASH , N., L ALITHA , V., S ASIDHA - WACHS , M., AND W YLIE , J. J. Ursa minor: Versatile cluster- RAN , B., K UMAR , P. V., NARAYANAMURTHY, S., K UMAR , R., based storage. In FAST (2005), vol. 5, pp. 5–5. AND NANDI , S. Evaluation of codes with inherent double repli- cation for hadoop. In Proc. USENIX HotStorage (2014). [6] A NDR É , F., K ERMARREC , A.-M., L E M ERRER , E., L E S COUARNEC , N., S TRAUB , G., AND VAN K EMPEN , A. [22] M AC W ILLIAMS , F., AND S LOANE , N. The Theory of Error- Archiving cold data in warehouses with clustered network cod- Correcting Codes, Part I. North-Holland Publishing Company, ing. In Proceedings of the Ninth European Conference on Com- 1977. puter Systems (2014), ACM, p. 21. [23] M AHESH , S., A STERIS , M., PAPAILIOPOULOS , D., D IMAKIS , [7] B EAVER , D., K UMAR , S., L I , H. C., S OBEL , J., VAJGEL , P., A. G., VADALI , R., C HEN , S., AND B ORTHAKUR , D. Xoring ET AL . Finding a needle in haystack: Facebook’s photo storage. elephants: Novel erasure codes for big data. In VLDB Endowment In OSDI (2010), vol. 10, pp. 1–8. (2013). [8] B HAGWAN , R., TATI , K., C HENG , Y. C., S AVAGE , S., AND [24] M ICKENS , J., AND N OBLE , B. Exploiting availability prediction VOELKER , G. M. Total recall: System support for automated in distributed systems. In NSDI (2006). availability management. In Proc. 1st conference on Sympo- sium on Networked Systems Design and Implementation (NSDI) [25] P LANK , J. S., AND G REENAN , K. M. Jerasure: A library (2004). in c facilitating erasure coding for storage applications–version [9] B ORTHAKUR , D. Hdfs and erasure codes (HDFS-RAID). 2.0. Tech. rep., Technical Report UT-EECS-14-721, University http://hadoopblog.blogspot.com/2009/08/hdfs-and-erasure- of Tennessee, 2014. codes-hdfs-raid.html, 2009. [26] P LANK , J. S., M ILLER , E. L., G REENAN , K. M., A RNOLD , [10] C ALDER , B., WANG , J., O GUS , A., N ILAKANTAN , N., B. A., B URNUM , J. A., D ISNEY, A. W., AND M C B RIDE , A. C. S KJOLSVOLD , A., M C K ELVIE , S., X U , Y., S RIVASTAV, S., Gf-complete: A comprehensive open source library for galois W U , J., S IMITCI , H., ET AL . Windows Azure storage: a field arithmetic, version 1.0. Tech. Rep. CS-13-716, University highly available cloud storage service with strong consistency. In of Tennessee, October 2013. Proc. ACM Symposium on Operating Systems Principles (2011), pp. 143–157. [27] R ASHMI , K., S HAH , N. B., G U , D., K UANG , H., B ORTHAKUR , D., AND R AMCHANDRAN , K. A hitchhiker’s [11] C HUN , B.-G., DABEK , F., H AEBERLEN , A., S IT, E., W EATH - guide to fast and efficient data reconstruction in erasure-coded ERSPOON , H., K AASHOEK , M. F., K UBIATOWICZ , J., AND data centers. In Proceedings of the 2014 ACM conference on M ORRIS , R. Efficient replica maintenance for distributed stor- SIGCOMM (2014), ACM, pp. 331–342. age systems. In NSDI (2006), vol. 6, pp. 225–264. [12] D IMAKIS , A. G., G ODFREY, P. B., W U , Y., WAINWRIGHT, [28] R ASHMI , K. V., S HAH , N. B., G U , D., K UANG , H., M., AND R AMCHANDRAN , K. Network coding for distributed B ORTHAKUR , D., AND R AMCHANDRAN , K. A solution to the storage systems. IEEE Transactions on Information Theory 56, 9 network challenges of data recovery in erasure-coded distributed (Sept. 2010), 4539–4551. storage systems: A study on the Facebook warehouse cluster. In Proc. USENIX HotStorage (June 2013). [13] E SMAILI , K. S., PAMIES -J UAREZ , L., AND DATTA , A. CORE: Cross-object redundancy for efficient data repair in storage sys- [29] R ASHMI , K. V., S HAH , N. B., AND K UMAR , P. V. Optimal tems. In IEEE International Conference on Big data (2013), exact-regenerating codes for the MSR and MBR points via a pp. 246–254. product-matrix construction. IEEE Transactions on Information [14] F ORD , D., L ABELLE , F., P OPOVICI , F., S TOKELY, M., Theory 57, 8 (Aug. 2011), 5227–5239. T RUONG , V., BARROSO , L., G RIMES , C., AND Q UINLAN , [30] R ASHMI , K. V., S HAH , N. B., AND R AMCHANDRAN , K. A S. Availability in globally distributed storage systems. In 9th piggybacking design framework for read-and download-efficient USENIX Symposium on Operating Systems Design and Imple- distributed storage codes. In IEEE International Symposium on mentation (Oct. 2010). Information Theory (July 2013). [15] G HEMAWAT, S., G OBIOFF , H., AND L EUNG , S. The Google [31] R EED , I., AND S OLOMON , G. Polynomial codes over certain file system. In ACM SIGOPS Operating Systems Review (2003), finite fields. Journal of the Society for Industrial and Applied vol. 37, ACM, pp. 29–43. Mathematics 8, 2 (1960), 300–304. [16] H U , Y., C HEN , H. C., L EE , P. P., AND TANG , Y. Nccloud: Ap- plying network coding for the storage repair in a cloud-of-clouds. [32] S CHROEDER , B., AND G IBSON , G. Disk failures in the real In USENIX FAST (2012). world: What does an MTTF of 1,000,000 hours mean to you? In Proc. 5th USENIX conference on File and Storage Technologies [17] H U , Y., Y U , C., L I , Y., L EE , P., AND L UI , J. NCFS: On (FAST) (2007). the practicality and extensibility of a network-coding-based dis- tributed file system. In International Symposium on Network [33] S HAH , N. B. On minimizing data-read and download for Coding (NetCod) (Beijing, July 2011). storage-node recovery. IEEE Communications Letters (2013). 13 USENIX Association 13th USENIX Conference on File and Storage Technologies (FAST ’15) 93

You can also read