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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
