Thanks to Billy Crook who pointed out this is the right place for my post.
Adam Leventhal integrated triple-parity RAID into ZFS in 2009. The
necessity of triple-parity RAID is described in detail in Adam
Leventhal's article(http://cacm.acm.org/magazines/2010/1/55741-triple-parity-raid-and-beyond/fulltext).
Basically it is because hard drive capacity has doubled
annually(Kryder's law) while hard drive throughput has improved far
more modestly, the time it takes to recover a faulty hard disk in a
double-parity RAID like RAID 6 might become so long(in 2010, it takes
about 4 hours to recover a 1TB SAS hard disk at its full speed) that
the remaining array(essentially a RAID 5 array, which has proven to be
unsafe) might fail and cause data loss during recovery. Earlier this
year, Ostler et
al.(http://www.nature.com/ncomms/journal/v3/n2/full/ncomms1666.html)
established a revolutionary way of writing magnetic substrate using a
heat pulse instead of a traditional magnetic field, which may increase
data throughput on a hard disk by 1000 times in the future. They
estimated the commercial usage of this new technology would be advent
in about 10 years. That said, within the next 10 years, having
triple-parity RAID in a data integrity demanding environment is still
highly desirable.
Unfortunately, due to conflicts between CDDL license of Oracle and GNU
license of Linux, ZFS and hence triple-parity RAID cannot be ported to
Linux. As a die-hard follower of the open source community, I am NOT
exactly pleased by this kind of drama. But instead of claiming the
grape to be sour, I decided to grow my own.
The work I am going to present here builds on top of that of Adam
Leventhal(http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/fs/zfs/vdev_raidz.c)
and Peter Anvin(http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf).
I will generalize Adam Leventhal's work using Peter Anvin's method,
then pick another generator from the Galois field GF(2^8) to
facilitate another triple-parity RAID algorithm that hopefully can be
used by the part of open source community that is not CDDL compliant
and beyond. System engineers who are not exactly familiar with Galois
field theory may find themselves a great exposure for that in Peter
Anvin's article.
I will use the same notation as in Adam Leventhal's work: D_0, ...
D_n-1 represents corresponding bytes in the n data disks in the array,
addition + is bitwise XOR, multiplication * is multiplication in
GF(2^8), multiplication in the power(for example,2(n-1) in g^2(n-1)
below) on the other hand, is multiplication in modulo ring Z_255.
(1) P = D_0 + D_1 + ... + D_n-2 + D_n-1
(2) Q = g^n-1 * D_0 + g^n-2 * D_1 + ... + g^1 * D_n-2 + D_n-1
= ((...((D_0) * g + D_1) * g + ...) * g + D_n-2) * g + D_n-1
(3) R = g^2(n-1) * D_0 + g^2(n-2) * D_1 + ... + g^2 * D_n-2 + D_n-1
= ((...((D_0) * g^2 + D_1) * g^2 + ...) * g^2 + D_n-2) * g^2 + D_n-1
P,Q,R are the definitions of the parity bytes, these are usually
called P,Q,R syndromes in the literature. Adam Leventhal used
generator {02} in the cyclic representation of Galois field GF(2^8), I
instead use an arbitrary generator g in the definition of P,Q and R.
For generator g, g^k is a generator if and only if k is relatively
prime to 255. Since g^255 = 1, g^(-1) = g^254 is a generator for 254
is relatively prime to 255. g^(-1) is the generator I am going to use
to optimize my triple-parity RAID algorithm.
Now let's prove we can always recover from 3 or less disk failures,
namely, we can always solve (1), (2), (3) for a unique solution if 3
or less of {P, Q, R, D_0, ... D_n-1} are unknowns.
We start with the most difficult case, i.e., 3 of {D_0, ... D_n-1} are
unknowns, or 3 data disks have failed and let's call them D_x, D_y and
D_z. For (1), we move the constants on the right to the left and
combine them with P and call the sum to be P_xyz, so (1) becomes
(1)' P_xyz = D_x + D_y + D_z
Similarly, (2) and (3) become
(2)' Q_xyz = g^x * D_x + g^y * D_y + g^z * D_z
(3)' R_xyz = g^2x * D_x + g^2y * D_y + g^2z * D_z
From (1)', we have D_z = P_xyz + D_x + D_y since A + A = 0 in a Galois
field. Substitute this into (2)' and (3)', and move the constants to
the left and call them Q_xyz' and R_xyz', we got
(2)'' Q_xyz' = (g^x + g^z) * D_x + (g^y + g^z) * D_y
(3)'' R_xyz' = (g^2x + g^2z) * D_x + (g^2y + g^2z) * D_y
Here comes the trick, multiply (2)'' by g^y + g^z, the coefficient for
D_y becomes (g^y + g^z) * (g^y + g^z) = g^2y + g^y * g^z + g^z * g^y +
g^2z = g^2y + g^2z(A + A = 0 again), then add it to (3)'' and move the
constants to the left and call it R_xyz'', we have
(3)''' R_xyz'' = [(g^x + g^z) * (g^y + g^z) + g^2x + g^2z] * D_x
= [g^(x+y) + g^(x+z) + g^(z+y) + g^2z + g^2x +g^2z] * D_x
= [g^(x+y) + g^(x+z) + g^(z+y) + g^2x] * D_x (A + A = 0 again)
= [g^y * (g^x + g^z) + g^x *(g^x + g^z)] * D_x
= (g^y + g^x) * (g^x + g^z) * D_x
Now because x, y, z are distinct integers, if we assume 0<= x, y, z<
n<= 255, then neither g^y + g^x nor g^x + g^z can be zero since g is
a generator and we can solve for D_x from (3)'''. A similar argument
can be applied to D_y's coefficient in (2)'' to solve for D_y and from
(1)' we can solve for D_z.
In a failure of 3 disks involving 1 or more parity disks, we may use
the equations not involving a failed data disk to uniquely solve for
unknows representing the failed data disk bytes, then use the rest of
the equations to recalculate the failed parity disk bytes.
In a failure involving only two data disks, we may use an argument
similar to above and two of the three equations to uniquely solve for
the unknowns(you might need to observe that g^2 is also a generator
since 2 is relatively prime to 255), the only question is: does the
solution satisfy the third equation? The answer is it has to. The
reason is we originally(before the two data disks failed) have a
solution for the two unknowns that satisfies all three equations,
hence also satisfies the two we used to solve for the unknowns; but
now we uniquely solve for the unknowns from those two equations, so
they have to be the original values.
The arguments for other cases are similar, but only easier.
There is an important observation here: The Gauss-Jordan elimination
in the proof above can be apply to Adam Leventhal's code although one
has 3 equations, the other has n+3. And this observaton has two
implications:
1) If we replace g with generator {02} in GF(2^8), we have proven that
the algorithm used in Adam Leventhal's code is sound.(I am sure Adam
Leventhal has his own proof, but as another guy with a math
background, I am not convinced until I see it.)
2) For other generators in GF(2^8), we can use the same procedure in
the algorithm of Adam Leventhal's code once the corresponding
logarithm and powers tables are replaced, this enable us to reuse most
of the code in Adam Leventhal's code.
So much for the math, now we enter neverland of a system enggineer.
Let's consider GF(2^8)'s another generator {02}^(-1) and try to
optimize the calculation for the Q ad R syndromes. For this purpose,
we use the second equality in (2) and (3). The addition is just
bitewise XOR, what we need to optimize is the multiplication by
{02}^(-1). Following the way in Peter Anvin's article, we found that
multiplication is implemented by the following bitwise operations:
(x * {02}^(-1))_7 = x_0
(x * {02}^(-1))_6 = x_7
(x * {02}^(-1))_5 = x_6
(x * {02}^(-1))_4 = x_5
(x * {02}^(-1))_3 = x_4 + x_0
(x * {02}^(-1))_2 = x_3 + x_0
(x * {02}^(-1))_1 = x_2 + x_0
(x * {02}^(-1))_0 = x_1
For 32 bit architecture, the C code optimizing it is as follows:
uint32_t v vv;
vv = (v>> 1)& 0x7f7f7f7f;
vv ^= MASK(v)& 0x8e8e8e8e;
uint32_t MASK(uint32_t v)
{
v&= 0x01010101;
return (v<< 8) - v;
}
The code for 64 bit architecture is just a simple extension of this,
or you may consult Adam Leventhal's code.
For arbitrary multiplication in the Gauss-Jordan elimination of the
recovery process, we use the rule:
A * B = C<==> C = g^(log_g A + log_g B)
A / B = C<==> C = g^(log_g A - log_g B)
where log_g is the discrete logarithm and g = {02}^(-1).
And the tables for discrete logarithm and powers of {02}^(-1) is as follows:
Powers table:
0x01, 0x8e, 0x47, 0xad, 0xd8, 0x6c, 0x36, 0x1b,
0x83, 0xcf, 0xe9, 0xfa, 0x7d, 0xb0, 0x58, 0x2c,
0x16, 0x0b, 0x8b, 0xcb, 0xeb, 0xfb, 0xf3, 0xf7,
0xf5, 0xf4, 0x7a, 0x3d, 0x90, 0x48, 0x24, 0x12,
0x09, 0x8a, 0x45, 0xac, 0x56, 0x2b, 0x9b, 0xc3,
0xef, 0xf9, 0xf2, 0x79, 0xb2, 0x59, 0xa2, 0x51,
0xa6, 0x53, 0xa7, 0xdd, 0xe0, 0x70, 0x38, 0x1c,
0x0e, 0x07, 0x8d, 0xc8, 0x64, 0x32, 0x19, 0x82,
0x41, 0xae, 0x57, 0xa5, 0xdc, 0x6e, 0x37, 0x95,
0xc4, 0x62, 0x31, 0x96, 0x4b, 0xab, 0xdb, 0xe3,
0xff, 0xf1, 0xf6, 0x7b, 0xb3, 0xd7, 0xe5, 0xfc,
0x7e, 0x3f, 0x91, 0xc6, 0x63, 0xbf, 0xd1, 0xe6,
0x73, 0xb7, 0xd5, 0xe4, 0x72, 0x39, 0x92, 0x49,
0xaa, 0x55, 0xa4, 0x52, 0x29, 0x9a, 0x4d, 0xa8,
0x54, 0x2a, 0x15, 0x84, 0x42, 0x21, 0x9e, 0x4f,
0xa9, 0xda, 0x6d, 0xb8, 0x5c, 0x2e, 0x17, 0x85,
0xcc, 0x66, 0x33, 0x97, 0xc5, 0xec, 0x76, 0x3b,
0x93, 0xc7, 0xed, 0xf8, 0x7c, 0x3e, 0x1f, 0x81,
0xce, 0x67, 0xbd, 0xd0, 0x68, 0x34, 0x1a, 0x0d,
0x88, 0x44, 0x22, 0x11, 0x86, 0x43, 0xaf, 0xd9,
0xe2, 0x71, 0xb6, 0x5b, 0xa3, 0xdf, 0xe1, 0xfe,
0x7f, 0xb1, 0xd6, 0x6b, 0xbb, 0xd3, 0xe7, 0xfd,
0xf0, 0x78, 0x3c, 0x1e, 0x0f, 0x89, 0xca, 0x65,
0xbc, 0x5e, 0x2f, 0x99, 0xc2, 0x61, 0xbe, 0x5f,
0xa1, 0xde, 0x6f, 0xb9, 0xd2, 0x69, 0xba, 0x5d,
0xa0, 0x50, 0x28, 0x14, 0x0a, 0x05, 0x8c, 0x46,
0x23, 0x9f, 0xc1, 0xee, 0x77, 0xb5, 0xd4, 0x6a,
0x35, 0x94, 0x4a, 0x25, 0x9c, 0x4e, 0x27, 0x9d,
0xc0, 0x60, 0x30, 0x18, 0x0c, 0x06, 0x03, 0x8f,
0xc9, 0xea, 0x75, 0xb4, 0x5a, 0x2d, 0x98, 0x4c,
0x26, 0x13, 0x87, 0xcd, 0xe8, 0x74, 0x3a, 0x1d,
0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
Log table:
0x00, 0x00, 0xfe, 0xe6, 0xfd, 0xcd, 0xe5, 0x39,
0xfc, 0x20, 0xcc, 0x11, 0xe4, 0x97, 0x38, 0xb4,
0xfb, 0x9b, 0x1f, 0xf1, 0xcb, 0x72, 0x10, 0x7e,
0xe3, 0x3e, 0x96, 0x07, 0x37, 0xf7, 0xb3, 0x8e,
0xfa, 0x75, 0x9a, 0xd0, 0x1e, 0xdb, 0xf0, 0xde,
0xca, 0x6c, 0x71, 0x25, 0x0f, 0xed, 0x7d, 0xba,
0xe2, 0x4a, 0x3d, 0x82, 0x95, 0xd8, 0x06, 0x46,
0x36, 0x65, 0xf6, 0x87, 0xb2, 0x1b, 0x8d, 0x59,
0xf9, 0x40, 0x74, 0x9d, 0x99, 0x22, 0xcf, 0x02,
0x1d, 0x67, 0xda, 0x4c, 0xef, 0x6e, 0xdd, 0x77,
0xc9, 0x2f, 0x6b, 0x31, 0x70, 0x69, 0x24, 0x42,
0x0e, 0x2d, 0xec, 0xa3, 0x7c, 0xc7, 0xb9, 0xbf,
0xe1, 0xbd, 0x49, 0x5c, 0x3c, 0xb7, 0x81, 0x91,
0x94, 0xc5, 0xd7, 0xab, 0x05, 0x7a, 0x45, 0xc2,
0x35, 0xa1, 0x64, 0x60, 0xf5, 0xea, 0x86, 0xd4,
0xb1, 0x2b, 0x1a, 0x53, 0x8c, 0x0c, 0x58, 0xa8,
0xf8, 0x8f, 0x3f, 0x08, 0x73, 0x7f, 0x9c, 0xf2,
0x98, 0xb5, 0x21, 0x12, 0xce, 0x3a, 0x01, 0xe7,
0x1c, 0x5a, 0x66, 0x88, 0xd9, 0x47, 0x4b, 0x83,
0xee, 0xbb, 0x6d, 0x26, 0xdc, 0xdf, 0x76, 0xd1,
0xc8, 0xc0, 0x2e, 0xa4, 0x6a, 0x43, 0x30, 0x32,
0x6f, 0x78, 0x68, 0x4d, 0x23, 0x03, 0x41, 0x9e,
0x0d, 0xa9, 0x2c, 0x54, 0xeb, 0xd5, 0xa2, 0x61,
0x7b, 0xc3, 0xc6, 0xac, 0xb8, 0x92, 0xbe, 0x5d,
0xe0, 0xd2, 0xbc, 0x27, 0x48, 0x84, 0x5b, 0x89,
0x3b, 0xe8, 0xb6, 0x13, 0x80, 0xf3, 0x90, 0x09,
0x93, 0x5e, 0xc4, 0xad, 0xd6, 0x62, 0xaa, 0x55,
0x04, 0x9f, 0x79, 0x4e, 0x44, 0x33, 0xc1, 0xa5,
0x34, 0xa6, 0xa0, 0x4f, 0x63, 0x56, 0x5f, 0xae,
0xf4, 0x0a, 0xe9, 0x14, 0x85, 0x8a, 0xd3, 0x28,
0xb0, 0x51, 0x2a, 0x16, 0x19, 0x18, 0x52, 0x17,
0x8b, 0x29, 0x0b, 0x15, 0x57, 0xaf, 0xa7, 0x50
The originally purpose of this work is to enable Linux to have
triple-parity RAID, but I guess it is all right for the rest of the
open source community to use it too. If you are not sure about your
situation or you'd rather talk to me in private about other issues,
please contact me at: creamyfish@xxxxxxxxx
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
