[prev in list] [next in list] [prev in thread] [next in thread] 

List:       linux-raid
Subject:    RE: SW RAID6 ?
From:       "Stephenson, Dale" <dstephenson () snapserver ! com>
Date:       2002-03-28 16:37:37
[Download RAW message or body]

 
Laurence Berland wrote:
> I wrote:
>> You can get parity sets of the appropriate size (and necessary
>> non-multiple intersection) by calculating parity vertically 
>> as well as horizontally.  Evenodd utilizes this with fixed parity
>> drives, IIRC.  The illustration of RAID6 at 
>> http://www.acnc.com/04_01_06.html implies this, though the
>> illustration they show will not work (losing the first and last
>> drive would lose data block A0 as well as parity A and parity 0.
>> Rule of thumb -- a chunk that is a member of a two parity 
>> sets cannot have both parity blocks on the same drive).  
>> However, there ARE schemes that will work with simple
>> encoding.  The original RAID 6 implementation did not use simple
>> encoding,
>> IIRC it used Huffman codes.

As pointed out elsewhere in the thread, it was actually Reed-Solomon.  RAID
2 does use error correcting codes.

> I've been wracking my brain, but am completely unable to come up with
> how you would avoid this.  Any ideas?

Well, here's a simple 4-drive example that works

 A1   A2  (P1) (PA)
(P2) (PB)  B2   B1
 C4   C3  (PC) (P3)
(PD) (P4)  D3   D4

Disclaimer: I took that from Patent 6,353,895.  If you look it up you'll see
a lot of different schemes and discussion of XOR-based RAID 6, in language
disguised as English.  You'll also see that I'm listed as the inventor.
That's four companies back for me, but my current employer unknowingly has
some rights to it, so I hope it will see the light of day sometime.

Without getting into philosophical musings about whether the algorithm
inside an implementation description inside a patent would draw the wrath of
lawyers, let me say there are a lot of NxN arrangements that can provide
dual-fault tolerance with XOR.  The 4x4 arrangement listed above is not the
only one possible.  There are hundreds of 6x6 arrangements just as good as
the one listed in the patent.  When N is a prime number, there is an optimal
arrangement, but there are plenty of non-optimal arrangements that will also
work.

Dale Stephenson
steph@snapserver.com
-
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
[prev in list] [next in list] [prev in thread] [next in thread]