From: "H. Peter Anvin" <hpa@zytor.com>
To: Andrea Mazzoleni <amadvance@gmail.com>,
linux-raid@vger.kernel.org, linux-btrfs@vger.kernel.org
Cc: david.brown@hesbynett.no, creamyfish@gmail.com
Subject: Re: Triple parity and beyond
Date: Mon, 18 Nov 2013 14:12:07 -0800 [thread overview]
Message-ID: <528A90B7.5010905@zytor.com> (raw)
In-Reply-To: <CAGKKSfWO4qTZsbd-=10cKc7=O7hTCVceMVQvCTJcUh1Z_gW04Q@mail.gmail.com>
On 11/18/2013 02:08 PM, Andrea Mazzoleni wrote:
> Hi,
>
> I want to report that I recently implemented a support for
> arbitrary number of parities that could be useful also for Linux
> RAID and Btrfs, both currently limited to double parity.
>
> In short, to generate the parity I use a Cauchy matrix specifically
> built to be compatible with the existing Linux parity computation,
> and extensible to an arbitrary number of parities. This without
> limitations on the number of data disks.
>
> The Cauchy matrix for six parities is:
>
> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01...
> 01 02 04 08 10 20 40 80 1d 3a 74 e8 cd 87 13 26 4c 98 2d 5a b4 75...
> 01 f5 d2 c4 9a 71 f1 7f fc 87 c1 c6 19 2f 40 55 3d ba 53 04 9c 61...
> 01 bb a6 d7 c7 07 ce 82 4a 2f a5 9b b6 60 f1 ad e7 f4 06 d2 df 2e...
> 01 97 7f 9c 7c 18 bd a2 58 1a da 74 70 a3 e5 47 29 07 f5 80 23 e9...
> 01 2b 3f cf 73 2c d6 ed cb 74 15 78 8a c1 17 c9 89 68 21 ab 76 3b...
>
> You can easily recognize the first row as RAID5 based on a simple
> XOR, and the second row as RAID6 based on multiplications by powers
> of 2. The other rows are for additional parity levels and they
> require multiplications by arbitrary values that can be implemented
> using the PSHUFB instruction.
>
Hello,
This looks very interesting indeed. Could you perhaps describe how the
Cauchy matrix is derived, and under what conditions it would become
singular?
-hpa
next prev parent reply other threads:[~2013-11-18 22:12 UTC|newest]
Thread overview: 113+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-11-18 22:08 Triple parity and beyond Andrea Mazzoleni
2013-11-18 22:12 ` H. Peter Anvin [this message]
2013-11-18 22:35 ` Andrea Mazzoleni
2013-11-18 23:25 ` H. Peter Anvin
2013-11-19 10:16 ` David Brown
2013-11-19 17:36 ` Andrea Mazzoleni
2013-11-19 22:51 ` Drew
2013-11-20 0:54 ` Chris Murphy
2013-11-20 1:23 ` John Williams
2013-11-20 10:35 ` David Brown
2013-11-20 10:31 ` David Brown
2013-11-20 18:09 ` John Williams
2013-11-20 18:44 ` Andrea Mazzoleni
2013-11-21 6:15 ` Stan Hoeppner
2013-11-21 8:32 ` David Brown
2013-11-20 18:34 ` Andrea Mazzoleni
2013-11-20 18:43 ` H. Peter Anvin
2013-11-20 18:56 ` Andrea Mazzoleni
2013-11-20 18:59 ` H. Peter Anvin
2013-11-20 21:21 ` Andrea Mazzoleni
2013-11-20 19:00 ` H. Peter Anvin
2013-11-20 21:04 ` Andrea Mazzoleni
2013-11-20 21:06 ` H. Peter Anvin
2013-11-21 8:36 ` David Brown
2013-11-19 17:28 ` Andrea Mazzoleni
2013-11-19 20:29 ` Ric Wheeler
2013-11-20 16:16 ` James Plank
2013-11-20 19:05 ` Andrea Mazzoleni
2013-11-20 19:10 ` H. Peter Anvin
2013-11-20 20:30 ` James Plank
2013-11-20 21:23 ` Andrea Mazzoleni
2013-11-27 2:50 ` ronnie sahlberg
2013-11-20 21:28 ` H. Peter Anvin
2013-11-21 1:28 ` Stan Hoeppner
2013-11-21 2:46 ` John Williams
2013-11-21 6:52 ` Stan Hoeppner
2013-11-21 7:05 ` John Williams
2013-11-21 22:57 ` Stan Hoeppner
2013-11-21 23:38 ` John Williams
2013-11-22 9:35 ` Stan Hoeppner
2013-11-22 11:24 ` joystick
2013-11-22 15:01 ` John Williams
2013-11-22 22:28 ` Stan Hoeppner
2013-11-22 23:07 ` NeilBrown
2013-11-23 3:46 ` Stan Hoeppner
2013-11-23 5:04 ` NeilBrown
2013-11-23 5:34 ` John Williams
2013-11-23 7:12 ` NeilBrown
2013-11-24 4:03 ` Stan Hoeppner
2013-11-24 4:03 ` Stan Hoeppner
2013-11-24 5:14 ` John Williams
2013-11-24 21:13 ` Stan Hoeppner
2013-11-24 21:13 ` Stan Hoeppner
2013-11-24 23:28 ` Rudy Zijlstra
2013-11-24 23:28 ` Rudy Zijlstra
2013-11-24 23:53 ` Alex Elsayed
2013-11-25 2:04 ` Stan Hoeppner
2013-11-25 2:04 ` Stan Hoeppner
2013-11-25 4:48 ` Alex Elsayed
2013-11-25 9:15 ` David Brown
2013-11-25 9:15 ` David Brown
2013-11-24 5:19 ` Russell Coker
2013-11-24 21:44 ` Stan Hoeppner
2013-11-24 22:31 ` Mark Knecht
2013-11-25 2:14 ` Russell Coker
2013-11-25 9:20 ` David Brown
2013-11-21 8:08 ` joystick
2013-11-22 0:30 ` Stan Hoeppner
2013-11-22 0:33 ` H. Peter Anvin
2013-11-22 0:45 ` David Brown
2013-11-21 9:07 ` David Brown
2013-11-21 9:54 ` Adam Goryachev
2013-11-21 10:32 ` David Brown
2013-11-22 8:12 ` Russell Coker
2013-11-25 18:23 ` Pasi Kärkkäinen
2013-11-22 8:13 ` Stan Hoeppner
2013-11-22 13:15 ` David Brown
2013-11-22 16:07 ` Stan Hoeppner
2013-11-22 22:59 ` NeilBrown
2013-11-23 17:39 ` David Brown
2013-11-22 16:50 ` Mark Knecht
2013-11-22 19:51 ` Duncan
2013-11-22 19:51 ` Duncan
2013-11-22 8:38 ` Stan Hoeppner
2013-11-22 13:24 ` David Brown
2013-11-28 7:16 ` Stan Hoeppner
2013-11-28 7:36 ` Russell Coker
2013-11-28 9:56 ` David Brown
2013-11-30 7:32 ` Alex Elsayed
2013-12-01 15:37 ` Stan Hoeppner
2013-11-22 14:19 ` David Taylor
2013-11-21 19:56 ` Piergiorgio Sartor
2013-11-19 18:12 ` Piergiorgio Sartor
2013-11-20 10:44 ` David Brown
2013-11-20 21:59 ` Piergiorgio Sartor
2013-11-20 21:59 ` Piergiorgio Sartor
2013-11-21 10:13 ` David Brown
2013-11-21 10:13 ` David Brown
2013-11-21 17:37 ` Goffredo Baroncelli
2013-11-21 17:37 ` Goffredo Baroncelli
2013-11-21 20:05 ` Piergiorgio Sartor
2013-11-21 20:31 ` David Brown
2013-11-21 20:52 ` Piergiorgio Sartor
2013-11-22 0:32 ` David Brown
2013-11-22 20:32 ` Piergiorgio Sartor
2013-11-26 18:10 ` joystick
2013-11-20 21:38 ` Andrea Mazzoleni
2013-11-20 22:29 ` Piergiorgio Sartor
2013-11-23 7:55 ` Andrea Mazzoleni
2013-11-23 22:10 ` Piergiorgio Sartor
2013-11-24 9:39 ` Andrea Mazzoleni
-- strict thread matches above, loose matches on Subject: below --
2013-12-01 17:53 Richard Scobie
2013-12-02 4:30 ` Stan Hoeppner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=528A90B7.5010905@zytor.com \
--to=hpa@zytor.com \
--cc=amadvance@gmail.com \
--cc=creamyfish@gmail.com \
--cc=david.brown@hesbynett.no \
--cc=linux-btrfs@vger.kernel.org \
--cc=linux-raid@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.