Re: Is this enough for us to have triple-parity RAID?

[David Brown <david@westcontrol.com>]

On 17/04/12 19:16, Piergiorgio Sartor wrote:
> Hi David,
>
>> My current state is that I've got theory worked out and written up -
>> not just for triple parity, but for more parities as well.  For some
>> of it, I've got Python code to test and verify the maths.  It turns
>> out that triple parity can work well - but for quad parity the limit
>> is 21 data disks (using generators 2, 4, and 8), or up to 33 (using
>> for example 0x07, 0x35 and 0x8b as generators).  Realistically, I
>> think triple parity is the limit for practical implementations.
>
> Why is that? An RS code (255,251) should be possible, like
> it is a (255,223). What's the limitation?
> I'm sure there is even a "RAID-96", which is (96,64).
>
> My wild guess would be that the generators must be chosen
> in some way.
>
> Have you had a look at the "par2" code? That seems to be
> capable of doing a parametric RS, even if in 16bit words.
>
> bye,
>

It is certainly possible to make raid systems using as many disks as you 
want, and as many parities as you want.  The trick is to do so in an 
efficient manner.

The way raid6 is implemented is using simple polynomials over the Galois 
field G(2⁸):

Py = g_y^0 . D0 + g_y^1 . D1 + g_y^2 . D2 + ... + g_y^n . Dn

For raid5, you have one parity generators, and g0 is 1 (i.e., a simple 
xor).  For raid6, you have two parity - 1 and 2.  For triple parity, we 
would use g0 = 1, g1 = 2 and g2 = 4.  The whole thing is therefore 
simple (or relatively simple!) to implement, and should run fast - 
calculating the third parity will only be slightly slower than 
calculating the second parity in raid6 is today, and recovery will be as 
fast as raid6 unless you need to recover from 3 data disk failures.

For quad parity, we can try g3 = 8 as the obvious next choice in the 
pattern.  Unfortunately, we start hitting conflicts.  To recover missing 
data, we have to solve multiple simultaneous equations over G(2⁸), whose 
coefficients depend on the index numbers of the missing disks.  With 
parity generators (1, 2, 4, 8), some of these combinations of missing 
disk indexes lead to insoluble equations when you have more that 21 disks.

I didn't find any neat way to prove this, or prove that all combinations 
of missing disks for parity generators (1, 2, 4) work out okay.  I wrote 
some brute-force checking code, and let my computer do the hard work.

There are other ways to make a raid system with quad parity or more. 
The parities don't have to be calculated in such a neat form as above - 
perhaps even something as simple as re-ordering the powers of the parity 
generators would help.  We could use a different operation rather than 
the "G(2⁸) multiply".  We could use different sized Galois fields.  Or 
we could try something completely different, such as RS codes. 
Somewhere there we would get quad parity and more - for as many disks as 
we like.

However, I would be surprised if there were another method that had the 
practicality of implementation that we get with this system.  There are 
/huge/ benefits in having the triple-parity raid being the same as raid6 
but with an extra parity, and being able to generate it in the same way. 
  If quad parity is something that appeals to anyone, then it could be 
implemented at the same time - and 21 data disks (25 disks total) would 
be the limit.  Even though the same equations with different generators 
can give up to 33 data disks, I expect that compatibility with raid6 and 
triple-parity would outweigh the benefits of supporting more disks. 
After all, a 25 disk array is already pretty big for a single array.

mvh.,

David

--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html