15 ms·

Reed-Solomon error recovery in RAID-6

101 points by signa11 6y ago

layoutIfNeeded 6y ago
Edit: I was wrong
- bfuclusion 6y ago
  Correct me if I'm wrong, but I think that scheme will protect you from at most one erasure. Fail D1 and P1 There's no way to recover D1s data since P2 has no data from D1 in it.
  - layoutIfNeeded 6y ago
    Actually, you're right!
  - jakubp 6y ago
    There is no mention of "P1" in the entire article. What did you mean?
eps 6y ago
There's also this paper, which is quite good - https://mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf https://mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/... Also there are simpler, xor-based encoding schemes that allow recovering from double failures (e.g. EvenOdd and such), but the problem is that they are all patented.
- est31 6y ago
  This E-Mail about increased numbers of parities is also interesting: https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg28964.html https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg...
  - huhtenberg 6y ago
    That's the SnapRAID dev! Also, check out this bit - >> Could you perhaps describe how the Cauchy matrix is >> derived, and under what conditions it would become >> singular? > The Cauchy matrix has the mathematical property ... > ... > Besides the mathematical proof, I've also inverted all > the 377,342,351,231 possible submatrices for up to 6 > parities and 251 data disks, and got an experimental > confirmation of this. "Trust, but verify" :) [0] https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg28966.html https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg...
- deleted 6y ago
  [deleted]
miahi 6y ago
The talk about striping (the fact that all the disks contain both data and the two levels of parity) is glossed over, but what it means is that there are not 7 types of failure/recovery, there are just two - when one drive fails, and when two drives fail. And the recovery actually contains all cases all the time (case 1-3 for 1 disk, case 4-7 for two disks).
redis_mlc 6y ago
I'm a storage engineer. There's a huge difference bewtween theory and practise. - rebuilds can timeout - load can really cause timeouts - raid controllers can have tested modes that work, and some that don't - batches of drives can all fail at the same time, esp. during rebuilds - the nvram might not be portable across controllers.
- mchristen 6y ago
  More than once I've lost a RAID array during a rebuild. That's what backups are for, I suppose.
  - sliken 6y ago
    1st lesson on using a RAID should be that RAID is not a replacement for backups.
  - klodolph 6y ago
    This is to be expected. RAID 5 is not safe. It is common for a RAID 5 array to be running in a degraded state during “normal” operation without the operator’s knowledge. Then, when one drive fails, rebuilding the array is impossible; you have already lost data. This is common because there is often no good way to repair a RAID 5 system which is running in degraded state, and there is often no monitoring to respond to array degradation (if you can’t fix it, why monitor it?) In other words, RAID 5 does not protect very well against drive failures. RAID 6 is more durable but inefficient (there are systems which are both more durable and more efficient than RAID 6). RAID is generally optimized for implementation simplicity over other concerns.
    - tutfbhuf 6y ago
      > there are systems which are both more durable and more efficient than RAID 6 RAID 10?
      - speakeron 6y ago
        RAID 10 is more efficient (if that equates to performant) than RAID 6, but not more durable. In fact it's less. As an example, a 4-disk array (which has the same capacity in both RAID 6 and RAID 10) has 4 2-disk failure modes. RAID 6 can handle all of these failure modes without losing data, whereas RAID 10 can only handle 2 of them.
alanfranz 6y ago
Is there any system for error recovery in userspace? Something like, I’ve got directory DATA, i want to create a recovery file for all the contents in such directory. Ideally I’d like to be able to tune the size of the recovery, larger recovery = recover more errors
- auxym 6y ago
  We used to use this when creating backups on CD-Rs and later DVDs, before hard drives became cheap... https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive
  - bestham 6y ago
    I used a program named Dvdisaster for the same use case. You could use it I two modes: (1) One disc with additional out of band reed-solomon ECC. Create an iso that are smaller by a certain percentage than the medium you want to burn it to. Dvdisaster will create a new ISO that uses the full capacity of the medium and fill the remaining space with parity-information that protects the whole file system and all user files. (2) Put your parity information on the next disc you burn. A parity file is crated for the first disc you burn, this is later added to the file system of the second disc you burn. Repeat indefinitely. You always have the last yet-to-be-burned parity file on your computer and can thus recover bit-errors in every disc you have burned.
  - dylan604 6y ago
    We used to use this in Newsgroup days. Large files got broken into smaller chunks (maybe floppy disk sized??) in the RAR format. You could recover missing files if they expired before you get them downloaded on your dial-up modem or your particular newsgroup service wasn't reliable enough.
- dmayle 6y ago
  What you're looking for is called Parchive. It uses Reed-Solomon coding in order to generate redundant files that can be used to recover the original. Look for PAR2 utilities (the current major version of the format). It has multiple implementations, open source and closed, across platforms and architectures. https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive
dragontamer 6y ago
On the one hand, this is a great "brute force" method to learn how one implementation of RAID6 could happen. This blogpost achieves understanding of error-correction in the 2-parity case through brute force alone, and that's actually quite commendable. On the other hand, its a very, very bad way to learn Reed Solomon codes. Reed Solomon codes "in general" are a concept that's broader than just 2-parity symbols... and also broader than just "protection vs erasures". Reed Solomon is designed to correct errors as well (a far "harder" computation than simply an erasure). I've fortunately found a good "ELI5" version of Reed Solomon: https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM That's a very non-technical talk, but that talk gives the full concepts of "Polynomial in Finite Field" that Reed Solomon codes are based off of. For a proper computer-based Reed Solomon code, you choose the GF(2^8) extension field for 8-bit symbols (Pararchive uses 2^16 for 16-bit symbols). Extension fields are extremely complicated to understand however, this will take a few days of Abstract Algebra study to understand how extension fields work. But once you know how a finite extension field works, you then extend a polynomial into the extension field, and bam, you have Reed Solomon codes. That is: a Quadratic equation can protect 3-data. All quadratic equations are ax^2 + bx + c, so any 3-points define a quadratic equation. Generate (x,y) coordinates on a graph as (0, data0), (1, data1), (2, data2). Then, solve for a quadratic equation f(x) = ax^2 + bx + c. Then, to generate parity, f(3) is your first parity symbol, f(4) is your next parity symbol, f(5) is the parity symbol after that. Etc. etc. Note in a 8-bit finite field, you can only go up to f(255) before "looping back" to f(0). From there: 2-check symbols will protect against either 2-erasures or 1-error. So Quadratic Equation with 4-check symbols (aka: 4 "other points" of the quadratic equation passed with the data) can protect against 4 erasures... or 2-errors, or 2-erasures + 1 error.
- klodolph 6y ago
  Note that the size of the field only has to be as large as the size of the redundancy set (data + code). So if you are striping across 16 or fewer disks, you can use GF(2^4), but if you are striping across 17 disks you can’t use GF(2^4). Well, if I remember the math correctly.
  - dragontamer 6y ago

101 points by signa11 6y ago

layoutIfNeeded 6y ago

Edit: I was wrong

bfuclusion 6y ago
Correct me if I'm wrong, but I think that scheme will protect you from at most one erasure. Fail D1 and P1 There's no way to recover D1s data since P2 has no data from D1 in it.
- layoutIfNeeded 6y ago
  Actually, you're right!
- jakubp 6y ago
  There is no mention of "P1" in the entire article. What did you mean?

eps 6y ago

There's also this paper, which is quite good - https://mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf https://mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/... Also there are simpler, xor-based encoding schemes that allow recovering from double failures (e.g. EvenOdd and such), but the problem is that they are all patented.

est31 6y ago
This E-Mail about increased numbers of parities is also interesting: https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg28964.html https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg...
- huhtenberg 6y ago
  That's the SnapRAID dev! Also, check out this bit - >> Could you perhaps describe how the Cauchy matrix is >> derived, and under what conditions it would become >> singular? > The Cauchy matrix has the mathematical property ... > ... > Besides the mathematical proof, I've also inverted all > the 377,342,351,231 possible submatrices for up to 6 > parities and 251 data disks, and got an experimental > confirmation of this. "Trust, but verify" :) [0] https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg28966.html https://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg...
deleted 6y ago
[deleted]

miahi 6y ago

The talk about striping (the fact that all the disks contain both data and the two levels of parity) is glossed over, but what it means is that there are not 7 types of failure/recovery, there are just two - when one drive fails, and when two drives fail. And the recovery actually contains all cases all the time (case 1-3 for 1 disk, case 4-7 for two disks).

redis_mlc 6y ago

I'm a storage engineer. There's a huge difference bewtween theory and practise. - rebuilds can timeout - load can really cause timeouts - raid controllers can have tested modes that work, and some that don't - batches of drives can all fail at the same time, esp. during rebuilds - the nvram might not be portable across controllers.

mchristen 6y ago
More than once I've lost a RAID array during a rebuild. That's what backups are for, I suppose.
- sliken 6y ago
  1st lesson on using a RAID should be that RAID is not a replacement for backups.
- klodolph 6y ago
  This is to be expected. RAID 5 is not safe. It is common for a RAID 5 array to be running in a degraded state during “normal” operation without the operator’s knowledge. Then, when one drive fails, rebuilding the array is impossible; you have already lost data. This is common because there is often no good way to repair a RAID 5 system which is running in degraded state, and there is often no monitoring to respond to array degradation (if you can’t fix it, why monitor it?) In other words, RAID 5 does not protect very well against drive failures. RAID 6 is more durable but inefficient (there are systems which are both more durable and more efficient than RAID 6). RAID is generally optimized for implementation simplicity over other concerns.
  - tutfbhuf 6y ago
    > there are systems which are both more durable and more efficient than RAID 6 RAID 10?
    - speakeron 6y ago
      RAID 10 is more efficient (if that equates to performant) than RAID 6, but not more durable. In fact it's less. As an example, a 4-disk array (which has the same capacity in both RAID 6 and RAID 10) has 4 2-disk failure modes. RAID 6 can handle all of these failure modes without losing data, whereas RAID 10 can only handle 2 of them.

alanfranz 6y ago

Is there any system for error recovery in userspace? Something like, I’ve got directory DATA, i want to create a recovery file for all the contents in such directory. Ideally I’d like to be able to tune the size of the recovery, larger recovery = recover more errors

auxym 6y ago
We used to use this when creating backups on CD-Rs and later DVDs, before hard drives became cheap... https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive
- bestham 6y ago
  I used a program named Dvdisaster for the same use case. You could use it I two modes: (1) One disc with additional out of band reed-solomon ECC. Create an iso that are smaller by a certain percentage than the medium you want to burn it to. Dvdisaster will create a new ISO that uses the full capacity of the medium and fill the remaining space with parity-information that protects the whole file system and all user files. (2) Put your parity information on the next disc you burn. A parity file is crated for the first disc you burn, this is later added to the file system of the second disc you burn. Repeat indefinitely. You always have the last yet-to-be-burned parity file on your computer and can thus recover bit-errors in every disc you have burned.
- dylan604 6y ago
  We used to use this in Newsgroup days. Large files got broken into smaller chunks (maybe floppy disk sized??) in the RAR format. You could recover missing files if they expired before you get them downloaded on your dial-up modem or your particular newsgroup service wasn't reliable enough.
dmayle 6y ago
What you're looking for is called Parchive. It uses Reed-Solomon coding in order to generate redundant files that can be used to recover the original. Look for PAR2 utilities (the current major version of the format). It has multiple implementations, open source and closed, across platforms and architectures. https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive

dragontamer 6y ago

On the one hand, this is a great "brute force" method to learn how one implementation of RAID6 could happen. This blogpost achieves understanding of error-correction in the 2-parity case through brute force alone, and that's actually quite commendable. On the other hand, its a very, very bad way to learn Reed Solomon codes. Reed Solomon codes "in general" are a concept that's broader than just 2-parity symbols... and also broader than just "protection vs erasures". Reed Solomon is designed to correct errors as well (a far "harder" computation than simply an erasure). I've fortunately found a good "ELI5" version of Reed Solomon: https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM That's a very non-technical talk, but that talk gives the full concepts of "Polynomial in Finite Field" that Reed Solomon codes are based off of. For a proper computer-based Reed Solomon code, you choose the GF(2^8) extension field for 8-bit symbols (Pararchive uses 2^16 for 16-bit symbols). Extension fields are extremely complicated to understand however, this will take a few days of Abstract Algebra study to understand how extension fields work. But once you know how a finite extension field works, you then extend a polynomial into the extension field, and bam, you have Reed Solomon codes. That is: a Quadratic equation can protect 3-data. All quadratic equations are ax^2 + bx + c, so any 3-points define a quadratic equation. Generate (x,y) coordinates on a graph as (0, data0), (1, data1), (2, data2). Then, solve for a quadratic equation f(x) = ax^2 + bx + c. Then, to generate parity, f(3) is your first parity symbol, f(4) is your next parity symbol, f(5) is the parity symbol after that. Etc. etc. Note in a 8-bit finite field, you can only go up to f(255) before "looping back" to f(0). From there: 2-check symbols will protect against either 2-erasures or 1-error. So Quadratic Equation with 4-check symbols (aka: 4 "other points" of the quadratic equation passed with the data) can protect against 4 erasures... or 2-errors, or 2-erasures + 1 error.

klodolph 6y ago
Note that the size of the field only has to be as large as the size of the redundancy set (data + code). So if you are striping across 16 or fewer disks, you can use GF(2^4), but if you are striping across 17 disks you can’t use GF(2^4). Well, if I remember the math correctly.
- dragontamer 6y ago