Erasure Coding in Windows Azure Storage - microsoft.com

1 Erasure Coding in Windows Azure StorageCheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey YekhaninMicrosoft CorporationAbstractWindows Azure Storage (WAS) is a cloud Storage sys-tem that provides customers the ability to store seem-ingly limitless amounts of data for any duration of customers have access to their data from anywhere,at any time, and only pay for what they use and store. Toprovide durability for that data and to keep the cost ofstorage low, WAS uses Erasure this paper we introduce a new set of codes for era-sure Coding called Local Reconstruction Codes (LRC).LRC reduces the number of Erasure Coding fragmentsthat need to be read when reconstructing data fragmentsthat are offline, while still keeping the Storage overheadlow. The important benefits of LRC are that it reduces thebandwidth and I/Os required for repair reads over priorcodes, while still allowing a significant reduction in stor-age overhead.

2 We describe how LRC is used in WAS toprovide low overhead durable Storage with consistentlylow read Azure Storage (WAS) [1] is a scalable cloudstorage system that has been in production since Novem-ber 2008. It is used inside microsoft for applicationssuch as social networking search, serving video, musicand game content, managing medical records, and addition, there are thousands of customers outside Mi-crosoft using WAS, and anyone can sign up over the In-ternet to use the system. WAS provides cloud storagein the form of Blobs (user files), Tables (structured stor-age), Queues (message delivery), and Drives (networkmounted VHDs). These data abstractions provide theoverall Storage and work flow for applications runningin the stores all of its data into an append-only dis-tributed file system called the stream layer [1]. Data isappended to the end of activeextents, which are repli-cated three times by the underlying stream layer.

3 Thedata is originally written to 3 full copies to keep the datadurable. Once reaching a certain size ( , 1 GB), ex-tents are sealed. These sealed extents can no longer bemodified and thus make perfect candidates for erasurecoding. WAS then Erasure codes a sealed extent lazily inthe background, and once the extent is Erasure -coded theoriginal 3 full copies of the extent are motivation for using Erasure Coding in WAScomes from the need to reduce the cost of Storage . Era-sure Coding can reduce the cost of Storage over 50%,which is a tremendous cost saving as we will soon sur-pass an Exabyte of Storage . There are the obvious costsavings from purchasing less hardware to store that muchdata, but there are significant savings from the fact thatthis also reduces our data center footprint by 1/2, thepower savings from running 1/2 the hardware, along withother trade-off for using Erasure Coding instead of keep-ing 3 full copies is performance.

4 The performance hitcomes when dealing withi)a lost or offline data frag-ment andii)hot Storage an extent iserasure-coded, it is broken up intokdata fragments, anda set of parity fragments. In WAS, a data fragment maybe lost due to a disk, node or rack failure. In addition,cloud services areperpetually in beta[2] due to frequentupgrades. A data fragment may be offline for seconds toa few minutes due to an upgrade where the Storage nodeprocess may be restarted or the OS for the Storage nodemay be rebooted. During this time, if there is an on-demand read from a client to a fragment on the storagenode being upgraded, WAS reads from enough fragmentsin order to dynamically reconstruct the data being askedfor to return the data to the client. This reconstructionneeds to be optimized to be as fast as possible and useas little networking bandwidth and I/Os as possible, withthe goal to have the reconstruction time consistently lowto meet customer using Erasure Coding , the data fragment theclient s request is asking for is stored on a specific stor-age node, which can greatly increase the risk of a storagenode becoming hot, which could affect latency.

5 One waythat WAS can deal with hot Storage nodes is to recog-nize the fragments that are hot and then replicate them tocooler Storage nodes to balance out the load, or cache thedata and serve it directly from DRAM or SSDs. But, theread performance can suffer for the potential set of readsgoing to that Storage node as it gets hot, until the datais cached or load balanced. Therefore, one optimizationWAS has is if it looks like the read to a data fragment isgoing to take too long, WAS in parallel tries to perform areconstruction of the data fragment (effectively treatingthe Storage node with the original data fragment as if itwas offline) and return to the client whichever of the tworesults is both of the above cases the time to reconstruct adata fragment for on-demand client requests is problem is that the reconstruction operation is onlyas fast as the slowest Storage node to respond to readingof the data fragments.

6 In addition, we want to reducestorage costs down to of the original data usingerasure Coding . This could be accomplished using thestandard approach of Reed-Solomon codes [13] wherewe would have (12, 4), which is 12 data fragments and4 code fragments. This means that to do the reconstruc-tion we would need to read from a set of 12 )greatly increases the chance of hitting a hot stor-age node, andii)increases the network costs and I/Osand adds latency to read that many fragments to do thereconstruction. Therefore, we want to design a new fam-ily of codes to use for WAS that provides the followingcharacteristics:1. Reduce the minimal number of fragments that needto be read from to reconstruct a data fragment. Thisprovides the following benefits:i)reduces the net-work overhead and number of I/Os to perform a re-construction;ii)reduces the time it takes to performthe reconstruction since fewer fragments need to beread.

7 We have found the time to perform the re-construction is often dominated by the slowest frag-ments (the stragglers) to be read Provide significant reduction in Storage overheadto while maintaining higher durability than asystem that keeps 3 replicas for the this paper, we introduce Local Reconstruction Codes(LRC) that provide the above properties. In addition, wedescribe our Erasure Coding implementation and impor-tant design Reconstruction CodesIn this section, we illustrate LRC and its propertiesthrough small examples, which are shorter codes (thushigher overhead) than what we use in production, in or-der to simplify the description of LRC . start with a Reed-Solomon code example to ex-plain the concept ofreconstruction cost. A (6, 3) Reed-Solomon code contains 6 data fragments and 3 parityfragments, where each parity is computed from all the6 data fragments.

8 When any data fragment becomes un-available, no matter which data and parity fragments areused for reconstruction, 6 fragments are always definereconstruction costas the number of frag-ments required to reconstruct an unavailabledata frag-ment. Here, the reconstruction cost equals to goal of LRC is to reduce the reconstruction achieves this by computing some of the parities froma subset of the data fragments. Continuing the examplewith 6 data fragments, LRC generates 4 (instead of 3)parities. The first two parities (denoted asp0andp1) areglobal paritiesand are computed fromallthe data frag-ments. But, for the other two parities, LRC divides thex0y0x1x2y2y1p0p1pypxFigure 1:A (6, 2, 2) LRC Example.(k= 6data frag-ments,l= 2local parities andr= 2global parities.)data fragments into two equal size groups and computesonelocal parityfor each group. For convenience, wename the 6 data fragments (x0,x1andx2) and (y0,y1andy2).

9 Then, local paritypxis computed from the 3data fragments in one group (x0,x1andx2), and localparitypyfrom the 3 data fragments in another group (y0,y1andy2).Now, let s walk through reconstructingx0. Instead ofreadingp0(orp1) and the other 5 data fragments (x1,x2,y0,y1andy2), it is more efficient to readpxand twodata fragments (x1andx2) to computex0. It is easy toverify that the reconstruction ofanysingle data fragmentrequires only 3 fragments, half the number required bythe Reed-Solomon LRC example adds one more parity than theReed-Solomon one, so it might appear that LRC reducesreconstruction cost at the expense of higher Storage over-head. In practice, however, these two examples achievecompletely different trade-off points in the design space,as described in Section In addition, LRC providesmore options than Reed-Solomon code, in terms of trad-ing off Storage overhead and reconstruction now formally define Local Reconstruction (k, l, r)LRC divideskdata fragments intolgroups,withk/ldata fragments in each group.

10 It computes onelocal parity within each group. In addition, it computesrglobal parities from all the data fragments. Letnbethe total number of fragments (data + parity). Thenn=k+l+r. Hence, the normalized Storage overhead isn/k= 1 + (l+r)/k. The LRC in our example is a(6,2,2)LRC with Storage cost of1 + 4/6 = , asillustrated in Figure ToleranceThus far, we have only defined which data fragmentsare used to compute each parity in LRC. To completethe code definition, we also need to determinecodingequations, that is, how the parities are computed fromthe data fragments. We choose the Coding equations suchthat LRC can achieve theMaximally Recoverable(MR)property [14], which means it can decode any failure pat-tern which is information-theoretically s first explain the Maximally Recoverable prop-erty. Given the (6, 2, 2) LRC example, it contains 4 par-ity fragments and can tolerateup to4 failures.