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. The performance of triple parity with PSHUFB is comparable at an alternate triple parity implementation with the third row of coefficients set as powers of 2^-1. This alternate implementation is likely the fastest possible for CPUs without PSHUFB or similar instruction, but it has the limitation of not supporting beyond triple parity. The Cauchy matrix is instead working for any number of parities and at the same time it's compatible with the existing first two parity levels. As far as I know, this is a kind of new result, never appeared in this list or somewhere else. You can see more details, performance results and fast implementations for up to six parity levels at: https://sourceforge.net/p/snapraid/code/ci/master/tree/raid.c This was developed as part of my hobby project SnapRAID, downloadable with full source at: http://snapraid.sourceforge.net/ Please let me know if you are interested in a potential Linux integration. I can surely help on whatever is needed. For reference, past discussions about triple parity in the linux-raid list can be found at: http://thread.gmane.org/gmane.linux.raid/34195 http://thread.gmane.org/gmane.linux.raid/37904 Ciao, Andrea -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
