Re: On the subject of RAID-6 corruption recovery
Mattias Wadenstein wrote: On Mon, 7 Jan 2008, Thiemo Nagel wrote: What you call "pathologic" cases when it comes to real-world data are very common. It is not at all unusual to find sectors filled with only a constant (usually zero, but not always), in which case your **512 becomes **1. Of course it would be easy to check how many of the 512 Bytes are really different on a case-by-case basis and correct the exponent accordingly, and only perform the recovery when the corrected probability of introducing an error is sufficiently low. What is the alternative to recovery, really? Just erroring out and letting the admin deal with it, or blindly assume that the parity is wrong? Erroring out. Only thing to do at that point. -hpa - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Mattias Wadenstein wrote: On Mon, 7 Jan 2008, Thiemo Nagel wrote: What you call "pathologic" cases when it comes to real-world data are very common. It is not at all unusual to find sectors filled with only a constant (usually zero, but not always), in which case your **512 becomes **1. Of course it would be easy to check how many of the 512 Bytes are really different on a case-by-case basis and correct the exponent accordingly, and only perform the recovery when the corrected probability of introducing an error is sufficiently low. What is the alternative to recovery, really? Just erroring out and letting the admin deal with it, blindly assume that the parity is wrong? Currently, 'repair' does blind recalculation of parity. The only benefit of that is (correct me if I'm wrong) to ascertain repeated reads return identical data. The last time I checked, there was not even a warning message. Kind regards, Thiemo Nagel - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
On Mon, 7 Jan 2008, Thiemo Nagel wrote: What you call "pathologic" cases when it comes to real-world data are very common. It is not at all unusual to find sectors filled with only a constant (usually zero, but not always), in which case your **512 becomes **1. Of course it would be easy to check how many of the 512 Bytes are really different on a case-by-case basis and correct the exponent accordingly, and only perform the recovery when the corrected probability of introducing an error is sufficiently low. What is the alternative to recovery, really? Just erroring out and letting the admin deal with it, or blindly assume that the parity is wrong? /Mattias Wadenstein - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
What you call "pathologic" cases when it comes to real-world data are very common. It is not at all unusual to find sectors filled with only a constant (usually zero, but not always), in which case your **512 becomes **1. Of course it would be easy to check how many of the 512 Bytes are really different on a case-by-case basis and correct the exponent accordingly, and only perform the recovery when the corrected probability of introducing an error is sufficiently low. Kind regards, Thiemo Nagel - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Thiemo Nagel wrote: That's why I was asking about the generator. Theoretically, this situation might be countered by using a (pseudo-)random pattern of generators for the different bytes of a sector, though I'm not sure whether it is worth the effort. Changing the generator is mathematically equivalent to changing the order of the drives, so no, that wouldn't help (and would make the common computations a lot more expensive.) -hpa - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
> Thiemo Nagel wrote: For errors occurring on the level of hard disk blocks (signature: most bytes of the block have D errors, all with same z), the probability for multidisc corruption to go undetected is ((n-1)/256)**512. This might pose a problem in the limiting case of n=255, however for practical applications, this probability is negligible as it drops off exponentially with decreasing n: >>> That assumes fully random data distribution, which is almost certainly >>> a >>> false assumption. >> >> Agreed. This means, that the formula only serves to specify a lower >> limit >> to the probability. However, is there an argumentation, why a >> pathologic >> case would be probable, i.e. why the probability would be likely to >> *vastly* deviate from the theoretical limit? And if there is, would >> that >> argumentation not apply to other raid 6 operations (like "check") also? >> And would it help to use different Galois field generators at different >> positions in a sector instead of using a uniform generator? >> > > What you call "pathologic" cases when it comes to real-world data are > very common. It is not at all unusual to find sectors filled with only > a constant (usually zero, but not always), in which case your **512 > becomes **1. That's why I was asking about the generator. Theoretically, this situation might be countered by using a (pseudo-)random pattern of generators for the different bytes of a sector, though I'm not sure whether it is worth the effort. Kind regards, Thiemo Nagel - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Thiemo Nagel wrote: For errors occurring on the level of hard disk blocks (signature: most bytes of the block have D errors, all with same z), the probability for multidisc corruption to go undetected is ((n-1)/256)**512. This might pose a problem in the limiting case of n=255, however for practical applications, this probability is negligible as it drops off exponentially with decreasing n: That assumes fully random data distribution, which is almost certainly a false assumption. Agreed. This means, that the formula only serves to specify a lower limit to the probability. However, is there an argumentation, why a pathologic case would be probable, i.e. why the probability would be likely to *vastly* deviate from the theoretical limit? And if there is, would that argumentation not apply to other raid 6 operations (like "check") also? And would it help to use different Galois field generators at different positions in a sector instead of using a uniform generator? What you call "pathologic" cases when it comes to real-world data are very common. It is not at all unusual to find sectors filled with only a constant (usually zero, but not always), in which case your **512 becomes **1. It doesn't mean it's not worthwhile, but don't try to claim it is anything other than opportunistic. -hpa - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
>> For errors occurring on the level of hard disk blocks (signature: most >> bytes of the block have D errors, all with same z), the probability for >> multidisc corruption to go undetected is ((n-1)/256)**512. This might >> pose a problem in the limiting case of n=255, however for practical >> applications, this probability is negligible as it drops off >> exponentially with decreasing n: >> > > That assumes fully random data distribution, which is almost certainly a > false assumption. Agreed. This means, that the formula only serves to specify a lower limit to the probability. However, is there an argumentation, why a pathologic case would be probable, i.e. why the probability would be likely to *vastly* deviate from the theoretical limit? And if there is, would that argumentation not apply to other raid 6 operations (like "check") also? And would it help to use different Galois field generators at different positions in a sector instead of using a uniform generator? Kind regards, Thiemo Nagel - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Thiemo Nagel wrote: Inverting your argumentation, that means when we don't see z >= n or inconsistent z numbers, multidisc corruption can be excluded statistically. For errors occurring on the level of hard disk blocks (signature: most bytes of the block have D errors, all with same z), the probability for multidisc corruption to go undetected is ((n-1)/256)**512. This might pose a problem in the limiting case of n=255, however for practical applications, this probability is negligible as it drops off exponentially with decreasing n: That assumes fully random data distribution, which is almost certainly a false assumption. -hpa - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Dear hpa, H. Peter Anvin wrote: > I got a private email a while ago from Thiemo Nagel claiming that > some of the conclusions in my RAID-6 paper was incorrect. This was > combined with a "proof" which was plain wrong, and could easily be > disproven using basic enthropy accounting (i.e. how much information > is around to play with.) > > However, it did cause me to clarify the text portion a little bit. In > particular, *in practice* in may be possible to *probabilistically* > detect multidisk corruption. Probabilistic detection means that the > detection is not guaranteed, but it can be taken advantage of > opportunistically. Thank you very much for setting me straight concerning some of my misconceptions about raid 6. Yet, the point that I was trying to make was that the statement "multidisc corruption cannot be detected" -- while correct in a mathematical sense -- is misleading when considering practical application, and I feel confirmed in that by your reply. > There are two patterns which are likely to indicate multi-disk > corruption and where recovery software should trip out and raise > hell: > > * z >= n: the computed error disk doesn't exist. > > Obviously, if "the corrupt disk" is a disk that can't exist, we have > a bigger problem. > > This is probabilistic, since as n approaches 255, the probability of > detection goes to zero. > > * Inconsistent z numbers (or spurious P and Q references) > > If the calculation for which disk is corrupt jumps around within a > single sector, there is likely a problem. Inverting your argumentation, that means when we don't see z >= n or inconsistent z numbers, multidisc corruption can be excluded statistically. For errors occurring on the level of hard disk blocks (signature: most bytes of the block have D errors, all with same z), the probability for multidisc corruption to go undetected is ((n-1)/256)**512. This might pose a problem in the limiting case of n=255, however for practical applications, this probability is negligible as it drops off exponentially with decreasing n: n=255 p=1.8% n=250 p=6.8e-7 n=240 p=5.3e-16 n=10 p=3.6e-745 So it seems to me that for that case, implementing recovery would be safe (maybe limit it to n<240). For errors occurring on the byte level (signature: only one byte of a sector has D error, all other bytes have no error), multidisc corruption is highly unlikely due to a different argumentation: Since 511 out of 512 bytes are ok, it can be concluded, that for errors in this specific sector, there is no correlation between the individual disks. That means, that the probability for double corruption is approximately 8*(n-1)*BER, and the bit error rate (BER) should be low. (For comparison: Some vendors specify 1e-15 as probability of unrecoverable read error (per bit that is read). I'd assume that the probability of silent read errors is much lower, at least for the disk itself; however additional errors might be introduced in (S)ATA transfer or in the controller.) For that case, too, it seems to me that implementing recovery could do no harm. Kind regards, Thiemo Nagel - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
Bill Davidsen wrote: H. Peter Anvin wrote: I got a private email a while ago from Thiemo Nagel claiming that some of the conclusions in my RAID-6 paper was incorrect. This was combined with a "proof" which was plain wrong, and could easily be disproven using basic enthropy accounting (i.e. how much information is around to play with.) However, it did cause me to clarify the text portion a little bit. In particular, *in practice* in may be possible to *probabilistically* detect multidisk corruption. Probabilistic detection means that the detection is not guaranteed, but it can be taken advantage of opportunistically. If this means that there can be no false positives for multidisk corruption but may be false negatives, fine. If it means something else, please restate one more time. Pretty much. False negatives are quite serious, since they will imply a course of action which will introduce further corruption. -hpa - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: On the subject of RAID-6 corruption recovery
H. Peter Anvin wrote: I got a private email a while ago from Thiemo Nagel claiming that some of the conclusions in my RAID-6 paper was incorrect. This was combined with a "proof" which was plain wrong, and could easily be disproven using basic enthropy accounting (i.e. how much information is around to play with.) However, it did cause me to clarify the text portion a little bit. In particular, *in practice* in may be possible to *probabilistically* detect multidisk corruption. Probabilistic detection means that the detection is not guaranteed, but it can be taken advantage of opportunistically. If this means that there can be no false positives for multidisk corruption but may be false negatives, fine. If it means something else, please restate one more time. -- Bill Davidsen <[EMAIL PROTECTED]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark - To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html