1、1,A triple erasure Reed-Solomon code, and fast rebuilding,Mark Manasse, Chandu Thekkath Microsoft Research - Silicon Valley Alice Silverberg Ohio State University,10/5/2018,Motivation,Large-scale storage systems can be expensive to build and maintain Erasure codes reduce the system costs below those
2、 of mirroring Erasure codes increase the complexity of recovering from failure In this talk, we present Construction of a triple-erasure correcting code Fast and agile computation for erasure recovery,3,A triple erasure correcting code,Galois fields Vandermonde matrices Definition and determinant In
3、ductive proof of determinant formula Reed-Solomon Erasure Codes Existing practice Simplified construction for up to three erasures Definition Handling 0 or 1 data erasures Handling 2 or 3 data erasures Why it stops at three erasures, and works only for GF(2k),4,Galois fields,The Galois Field of orde
4、r pk (for p prime) is formed by considering polynomials in Z/Zpx modulo a primitive polynomial of degree k. Facts x is a generator of the field (because of primitivity). Any primitive polynomial will do; all the resulting fields are isomorphic. We write GF(pk) to denote one such field. Everything yo
5、u know about algebra is still true. In practice, well be interested only in GF(28k), so multiple bytes turn into equivalent-length groups of bytes,5,Vandermonde matrices,A Vandermonde matrix Vk is of the form and has determinant,6,Inductive step proving the determinant of a Vandermonde matrix is the
6、 product of the differences.Determinant here is 1.Expand on first column; after removing common factors from second through last entries in each column, whats left is Vk-1, with shifted variables.,7,Reed-Solomon Erasure Codes,2. Suppose data disks 2,3 and check disk 3 fail.,4. Multiplying both sides
7、 by R-1, we recover all the data.,3. Omitting failed rows, we get an invertible nn matrix R.,1. We use an n(n+k) coding matrix to store data on n data disks and k check disks. (k=3 in our example),8,Existing practice,The use of the identity in the top of the matrix makes the code systematic, which m
8、eans that data encodes itself Typically, one takes a matrix with the right properties for the invertibility of submatrices (like a Vandermonde or Cauchy matrix) and diagonalizes it This produces a matrix, hard to remember or invert, limited to n+k 257 in GF(256) A simple trick extends to n+k 258,9,A
9、 simple triple-erasure code,The matrix to the right is simple: an nn identity matrix for n 256, and the first three rows of a transposed Vandermonde matrix of size 3n, using 1, x, and x2, where x is any generator of the multiplicative group For k=3, in GF(256), we need n+k 259,10,General invertibili
10、ty background,Consider the matrix after deleting 3 rows To check invertibility, test the determinant To compute the determinant Most rows will contain all zeroes, except for a one in what used to be the diagonal element Expanding along such a row, we get (up to sign), that the determinant is the det
11、erminant of the minor excluding the ones row and column,11,Handling 0 or 1 data erasures,If the 3 deleted rows are the check rows, we know how to compute the check values from the data values Otherwise, what remains is a minor of the Vandermonde rows If 2 deleted rows are check rows, the remaining m
12、inor is a single element, which is a power of x, hence non-zero.,12,Handling 2 or 3 data erasures, and beyond,If the deleted rows are data rows a, b, and c, the minor is a 33 Vandermonde matrix, which is invertible If one deleted row is a check row, and the others are rows a and b, possible minors a
13、re displayed: The first is Vandermonde, as is the second, after factoring out xa and xb The third is Vandermonde, but we need to show that x2a and x2b differ In GF(2k), the order of the multiplicative group is 2k-1, relatively prime to 2, so they do In other characteristics, 1 has two square roots,
14、so we have to keep b - a small If we had added more than three check rows, a 33 minor generally would not be Vandermonde, and its not hard to construct non-invertible minors,13,Fast and agile computation for erasure recovery,14,Reed-Solomon reconstruction,For each failed disk, the matrix multiplicat
15、ion resolves to a dot-product If each data source (data disk or check disk) has an associated processor, the multiplications can be performed locally Accumulating the sum in GF(2k) is just exclusive-or Want high throughput (so disks are rebuilt quickly), low-latency (so blocks can be delivered on de
16、mand, when necessary),15,Computational environment,In what follows, we assume that we have a synchronous network of processors, each with an array of data packets In each time step, each processor can Receive one packet, and XOR the contents with a known packet for the same array index Send one pack
17、et to another processor or to the final destination,16,High throughput, but high latency,A bucket brigade of n processors has unit throughput, but linear latency On step i+k, processor i sends accumulated packet k to processor i+k, and receives packet k+1 from processor i-1, adding the received valu
18、e to known packet k+1 Processor 0 only sends Processor n is the destination After n steps of latency, processor n receives one packet per step,17,Low latency, but low throughput,Build an in-place binary tree Let n = 2k For ik, on step rk+i, node 2i(2s+1) sends packet r to node 2i+1s On step k(r+1),
19、node 0 sends packet r to destination node n Latency log n+1, throughput 1/k, i.e. 1/log nEasy doubling of throughput by sending even blocks down, and odd blocks up (since at least half of nodes only send or only receive at each step),Node 0,Node 1,Node 2,Node 3,Node 4,Node 5,Node 6,Node 7,Step 0,3,S
20、tep 0,3,Step 0,3,Step 0,0,Step 1,4,0,Steps 2,5,Step 1,4,Steps 3,6,18,Moderate throughput, moderate latency,Instead of an in-place binary tree, use a rooted binary tree On step 2(k+l), node 2l(4s+1) sends packet k to node 2l(4s+2) On step 2(k+l)+1, node 2l(4s+3) sends packet k to node 2l(4s+2) Throug
21、hput , latency 2log n, for n = 2k-1 Output every other step, because of input limits,Node 1,Node 2,Node 3,Node 4,Node 5,Node 6,Node 7,Steps 0,2,Steps 0,2,Steps 1,3,Steps 1,3,Steps 2,4,Steps 3,5,19,General observations,The patterns of communication described so far all combine the values of consecuti
22、ve nodes Statically known if incoming block contains values from higher numbered nodes or lower numbered, so can apply XOR left-to-right Not interesting for a commutative operator like XOR, but this can apply to non-commutative monoids (which dont arise in erasure codes, but are cool anyway),20,Recu
23、rsive construction: base case,For one node, on step i, send block i from node 0 to destination node 1; this is G0 For two nodes, on step i, send block i from node 0 to node 1. On step i+1, send block i from node 1 to node 2 Denote edges in graph as 4-tuples Graph G1 is ,Node 0,Node 1,Node 2,Steps 0,
24、1,2, Blocks 0,1,2,Steps 1,2,3, Blocks 0,1,2,21,Inductive hypotheses for Gk,Nodes from 0 to n=2k Node 0 is only a source; is in Gk for all i (recall: step, block, source, dest) Node n is only a destination, in Gk, so log k+1 delay, full throughput If in Gk, for d and are in Gk orand are in Gk For all
25、 blocks, the edges form an unrooted binary tree; the k-level descendants of a node have node numbers matching the first k bits of the node,Node 0,Node 2,Node 4,Node 1,Node 3,22,Recursive construction: doubling up,Given Gk, produce Gk+1 by doubling the number of nodes to 2n. Add edges for s in Gk, ad
26、d an edge to Gk+1 For s1, s2=2s,2s+1 (and similarly d1, d2, d), Gk+1 includes and (unless d=n, when d1=2n, and d2 is irrelevant) Add , and Since every node n is a source in Gk, all pairs will be connected in some direction in step i+1,0,2,Node 4,1,3,0,2,1,3,Steps i=0,2,4,:,Steps i=1,3,5,:,Block i-2,
27、Block i-1,Block i-1,Block i inside every bubble,23,Chains / step but in-place trees / block,0,2,Node 4,1,3,0,2,1,3,Steps i=0,2,4,:,Steps i=1,3,5,:,Block i-2,Block i-1,Block i-1,Block i inside every bubble,0,2,Node 4,1,3,0,2,1,3,Blocks i=0,2,4,:,Blocks i=1,3,5,:,Step i+2,Step i+1,Step i+1,Step i insi
28、de every bubble,24,High throughput, low latency,From that recursive construction, weve doubled the number of nodes We sometimes have to add on the left and sometimes on the right, but the inputs accumulated on any input step are always a contiguous subset adjacent to the contiguous subset currently
29、known to the destination, so associativity is sufficient 2i and 2i+1 are always linked for block b at step b; if we condense some of these nodes, we can reduce the number of nodes to get non-powers of 2,25,Further results,Current patterns of communication repeat every 2log log n blocks We have alternative constructions with slightly worse latency, but full throughput, that are much simpler (repeating patterns every 2 or 3 steps) These constructions require commutativity Generalizations of rooted tree constructions, improving throughput,
