On Fri, Apr 01, 2016 at 11:18:05PM -0700, Gregory Farnum wrote: > On Fri, Apr 1, 2016 at 10:05 PM, Chris Dunlop <chris@xxxxxxxxxxxx> wrote: >> On Fri, Apr 01, 2016 at 07:51:07PM -0700, Gregory Farnum wrote: >>> Forgive me if I'm wrong here — I haven't done anything with >>> checksumming since I graduated college — but good checksumming is >>> about probabilities and people suck at evaluating probability: I'm >>> really not sure any of the explanations given in this thread are >>> right. Bit errors aren't random and in general it requires a lot more >>> than one bit flip to collide a checksum, so I don't think it's a >>> linear relationship between block size and chance of error. Finding >> >> A single bit flip can certainly result in a checksum collision, with the >> same chance as any other error, i.e. 1 in 2^number_of_checksum_bits. > > That's just not true. I'll quote from > https://en.m.wikipedia.org/wiki/Cyclic_redundancy_check#Introduction > >> Typically an n-bit CRC applied to a data block of arbitrary length will detect any single error burst not longer than n bits and will detect a fraction 1 − 2^(−n) of all longer error bursts. Ouch, got me! :-) In my defense, I was talking about checksums in general rather than specifically CRC. But no, I wasn't actually aware that CRCs provide guaranteed detection of single n-bit error bursts. That changes my contention that block size doesn't matter. My contention was based on a (generic, good) checksum being equally good at picking up multiple errors as single errors. However this property of CRCs means that, if you have multiple errors further apart than the n-bits of a CRC checksum, you lose your guarantee of detection (although you still have a very, very good chance of detection). So in a larger block you're more likely to see another error further away, and thus more likely to get an undetected error. Well, I've learnt something! Thanks all, for your patience. Chris > And over (at least) the ranges they're designed for, it's even better: > they provide guarantees about how many bits (in any combination or > arrangement) must be flipped before they can have a false match. (It > says "typically" because CRCs are a wide family and yes, you do have > to select the right ones in the right ways in order to get the desired > effects.) > > As Allen says, flash may require something different, but it will be > similar. Getting the people who actually understand this is definitely > the way to go — it's an active research field but I think over the > ranges we're interested in it's a solved problem. And certainly if we > try and guess about things based on our intuition, we *will* get it > wrong. So somebody interested in this feature set needs to go out and > do the reading or talk to the right people, please! :) > -Greg -- To unsubscribe from this list: send the line "unsubscribe ceph-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
