<html style="direction: ltr;">
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<style type="text/css">body p { margin-bottom: 0.2cm; margin-top: 0pt; } </style>
</head>
<body style="direction: ltr;" bidimailui-charset-is-forced="true"
bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 10/08/15 20:56, Omer Zak wrote:<br>
</div>
<blockquote cite="mid:1439229412.10934.108.camel@zak.co.il"
type="cite">
<pre wrap="">All those discussions about inverting matrices over Z2 make me curious
to know what kind of problems can be solved by inverting such matrices.
I suppose that the actual problem, with which Shachar is struggling, is
proprietary information. However, is it possible to indicate the kind of
problems which can be attacked by inverting a matrix over Z2?</pre>
</blockquote>
I think I'm not letting on too much by giving the broad area.<br>
<br>
When calculating RAID-6 parity, one of the common methods is called
"erasure coding". You have n data blocks in a stripe which you need
to write to n+p actual disks, such that for any number of failures
up to p, you can recover the original n data blocks.<br>
<br>
One of the ways to do that is by employing a family of algorithms
called "Erasure codes", the most famous of which is Reed Solomon.
The basic idea is that you write a matrix which is n over n+p, and
you multiply the n data blocks by that matrix, resulting in n+p data
blocks, which you then write to your disks. When p disks failed, you
erase from your matrix the lines that correspond to the disks that
failed, and invert the resulting n*n matrix. Multiplying the n disks
you do have by that matrix result in the origin n data blocks.<br>
<br>
The obvious first requirement from your erasure code matrix,
therefor, is that it be inversible after deleting any combination of
p lines from it. This is the property I'm trying to verify in my
project at hand.<br>
<br>
The usual erasure code matrix is calculated over "ze ozer finite
field", i.e. Galois field. Frankly, I don't feel I understand Galois
field, and in particular, the way it is used in this particular
case, enough to explain why. One of the properties that make it
attractive, however, is that addition over GF is XOR. As a result,
almost all RAID erasure code matrices have their first n+1 lines
look like this:<br>
<pre>1 0 0 0 ....
0 1 0 0 ....
0 0 1 0 ....
0 0 0 1 ....
........1 0 0
........0 1 0
........0 0 1
1 1 1 ... 1 1
</pre>
The practical upshot of the above is that the first n disks receive
the same data they would have received without applying erasure
coding (i.e. - if they are available, they can be read directly
without going through the matrix, and more importantly, without
reading the rest of the disks in the stripe). Furthermore, the first
protection disk contains the XOR of all data disks in the stripe. In
other words, if we lost only one disk, we can employ RAID-5 as
usual.<br>
<br>
A side effect of the above is that the matrix is extremely sparse.
Almost all lines (all but the protection disks) contain just one
non-zero number, already on the diagonal.<br>
<br>
Using Z2 instead of GF gives certain performance benefits. It does
have the cost of making the matrix much much much larger (hence the
somewhat insane numbers quoted in my original mail. I am not really
building a stripe of 272+12). Since the matrix is still extremely
sparse, however, this does not cost the full n^3 quoted by Matan.<br>
<br>
Look up "evenodd" for an example of an algorithm that is based on
XOR rather than GF. It is not phrased in matrix form, but that is
just a convenience.<br>
<br>
Hope this gives enough of an insight to quelch your curiosity :-)<br>
<br>
Shachar<br>
</body>
</html>