1
$\begingroup$

According to this source and Tanenbaum's Modern Operating Systems a possible implementation of RAID 2 consists of 4 data disks and 3 disks which contain parity bits. Why don't we need 4 disks that stores parity bits, why just 3?

Also in RAID 3 we need just one disk for storing parity bytes for 4 data disks. What would be any potential interest in RAID 2 over RAID 3? As far as I understand read/write speeds are the same in RAID 2/RAID 3.

$\endgroup$

1 Answer 1

6
$\begingroup$

RAID 2 doesn't use parity: it uses a Hamming code. This allows error correction as well as error detection. Remember that a parity bit is just a bit that tells you whether the sum of the other bits is odd or even. It wouldn't make sense to have more than one of those because they'd all be telling you the same thing.

If you're using RAID 3 with four data bits and one parity bit, all you can do is detect when an odd number of bits have changed. You read the four data bits, add them together (mod 2) and, if the answer isn't equal to the parity bit, then you know that something has been corrupted. But you don't know what has been corrupted: it could be any one of the data bits, or it could even be the stored parity bit. All the disc controller can say is, "Sorry, but something's gone wrong and I can't give you the data you wanted." Note that, if two bits get corrupted, you won't notice since, e.g., 1+0+0+1=0+0+1+1.

In contrast, RAID 2 would store three error-correcting bits along with the four bits of data. Having the extra two bits gives you more power: you can now detect and fix any single-bit corruption. This works by looking simultaneously at all seven bits (four data, three EC). Because of the way the code is designed, any two valid combinations must differ by at least three bits. If you see a valid combination, you're happy. If you see an invalid combination that's only one bit different from a valid one, then it must be at least two bits different from every other valid combination, so you can fix the error on the assumption that it's more likely that one bit was corrupted than two. (See Wikipedia for full details). We assume that three bits being corrupted simultaneously is so unlikely that it will never happen: in principle, that could corrupt one valid combination into a different one.

The above assumed that two-bit corruptions are much less likely than one-bit corruptions. An alternative RAID 2 set up when two-bit corruptions aren't so rare would be to say "I don't know if this invalid combination was a one-bit or two-bit error but something's gone wrong." That would allow you to detect all one-bit and two-bit errors, but not correct anything.

$\endgroup$
5
  • $\begingroup$ I see, RAID 2 gives essentially the ability to correct errors on the fly. But why do we need 3 disks that store correction code for 4 data disks? Why don't we need a correction disk for each data disk? $\endgroup$
    – Yos
    Commented Jan 11, 2018 at 16:45
  • $\begingroup$ That's not how error correction works. I suggest reading a primer on coding theory. $\endgroup$ Commented Jan 11, 2018 at 16:59
  • $\begingroup$ @YuvalFilmus I saw a notification for your comment in isolation and was thinking "Naw, come on. I can't have messed up that badly!" :-) $\endgroup$ Commented Jan 11, 2018 at 17:15
  • 1
    $\begingroup$ @Yos I've added a brief explanation of how the EC bits are used -- you need three rather than four because that's how the maths works out. I also corrected an error (*badum-tsh*) -- you can fix one-bit errors or detect two-bit errors, but I'd falsely claimed you could do both at the same time. $\endgroup$ Commented Jan 11, 2018 at 17:29
  • $\begingroup$ Yes, the [7,4] Hamming code can either fix one-bit errors or detect two-bit errors. However, the [8,4] extended Hamming code can both fix one-bit errors and also detect two-bit errors [SECDED](en.wikipedia.org/wiki/… ). $\endgroup$
    – David Cary
    Commented Apr 4 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.