3 ms·
Stupid question: even if we use checksums and parity files and such to verify the integrity of our data, how do we verify that these integrity measures don't th
by kibwen 13y ago
Stupid question: even if we use checksums and parity files and such to verify the integrity of our data, how do we verify that these integrity measures don't themselves become corrupted? Is it just "that's very unlikely to happen"?
- mnw21cam 13y agoBasically, yes. In the old days, integrity was ensured by using 1 bit in 8 parity, that is for every eight bits there would be an extra bit, and counting the bits set to 1 should always be even (or odd, depending). This meant that if there was a single bit flipped, you were guaranteed to detect the failure, but powerless to correct it. However, if you had two bits flipped, the parity would pass. Nowadays, we use something more like a hash function, where we take the block of 4kB or so and produce a 64-bit hash of it. In order for this check to fail, the failure has a 1 in 2^64 chance of guessing a correct checksum for the corrupted data, which is very unlikely to happen. Also, we have the possibility of using Reed-Solomon error correcting codes in some applications, which can not only detect errors but also correct them.
- steveklabnik 13y agoI've only had one cup of coffee so far, but... The problem would be if the checksum AND the data _both_ became corrupted in a way that the checksum were still valid. After all, if the checksum were to change, you'd get a failure, and then you could just verify that the data was not actually changed and/or lost. Not to mention that if you stored the checksum in two places, it'd be pretty easy to see that it was the checksum that itself changed.
- masklinn 13y ago> how do we verify that these integrity measures don't themselves become corrupted? In ZFS, a storage pool is a merkle tree[0], the checksums themselves are checksummed (as part of their ancestor blocks). The one risk is that the uberblock itself (the root of the tree holding a checksum for the whole thing) becomes corrupted, which is why IIRC zfs stores the last 128 revisions of the uberblock in 4 different physical locations[1]. [0] http://en.wikipedia.org/wiki/Merkle_tree http://en.wikipedia.org/wiki/Merkle_tree [1] sadly does not mean you can rollback to any of them, when a new uberblock is created (which is common) the previous's set of metadata (meta-object set MOS) becomes reclaimable, and once the MOS has been reclaimed/reused the corresponding uberblock is useless
- ChuckMcM 13y agoIts actually a reasonable question, for parity it was always possible for two, complementary, bit errors to result in a successful parity computation in the presence of corrupted data. The CRC function can detect multi-bit errors because it encodes not only bit state but also bit sequence in the error check. There is an excellent discussion of the tradeoffs in the book with Richard Feynman's lectures on computation. Generally when you design such a system you can often say what would have to be true for you to "miss" that something was corrupted. In our parity example, an even number of bits would have to change state. In the CRC example bit changes would need to be correlated across a longer string of bits. Once you have ways that you know you would not be able to detect errors, then you start breaking the system apart to change up detection and correction. So for example at NetApp a block (which was 4K bytes at the time I was there) on disk was 8 sectors, then there was an additional sector that included information about both a CRC calculation for the available bytes, as well as information about which block it was and what 'generation' it was (monotonically increasing number indicating file generation). The host bus adapter (HBA) would do its own CRC check on the data that came from the drive, passed through it, and landed in memory. That would detect most bit flips that occurred on the channel (SATA or Fibre Channel port) as data went through it. ECC on memory would detect if memory written had its bits flipped. Software would recompute the block parameters and compare them to the data in the check sector. So if data on the disk was bad, that check sector would not work, if the data had been written correctly initially and gone bad, the RAID parity check would catch it, if the data was corrupted crossing the disk/memory channel the HBA would catch it, if the data got to memory but memory corrupted it, the ECC would catch it, if the memory some how didn't see the corruption the check against the block check sector would catch it. All layers of interlocking checks and re-checks in order to decrease the likelyhood that something corrupted yoru data without knowing it.
- kibwen 13y agoThis is fascinating! Thanks everyone for answering.