About Me!
This blog is about my musings and thoughts. I hope you find it useful, at most, and entertaining, at least.
Other Pages
Presence Elsewhere
Parody of Parity
Date: 2013-09-14
Tags: parity par2 raid
Bit rot: A term referring to the degradation of stored data over a period of time. Often caused by a magnetic mediums’ slow loss of state.
I’m sure we’ve all come across that old file, maybe a picture or report from middle school, that just wont open. This was most likely because of bit rot. It can be a vary annoying phenomena, but, now that we know about it, can we prevent it?
No. Bit rot is part of the inevitable march of the world towards randomness, otherwise known as the Second Law of Thermodynamics. However, the good news is that since we know it will happen, we can take steps to recover from it.
The first thing we might try is to store a checksum of the file along with the file. However, this will only tell us if the file has been corrupted. But, we can store 2 copies of the file with a checksum and then we’ll more-than-likely have one copy that’s good.
What if both are bad? Well, we can store 3 copies with checksums, and if all 3 are bad we can compare byte-by-byte and take the two or more bytes agreeing to be the true value. This takes up a lot of space though. Three-times the size of the file (let’s assume checksums are of negligible size, a sha-256 is only 32-bytes long. for a megabyte sized picture that’s negligible). Can we do better than this?
Well, we can look to RAID for some guidance. RAID is a method of storing data across different hard drives (in most cases, less RAID 0, to guard against disk failure and bit rot. As mentioned, there are different types of RAID setups, called levels. The Standard Raid Levels
Raid-0: Simply splits a file among multiple disks. Used for speed, not for protection. We’re not considering this level.
RAID-1: Keeps multiple copies of the data (each on a separate disk)
RAID-5: Keeps one copy of the data and a parity block (each on a separate disks).
What is a parity block? Well, let’s assume we have 2 files (of the same size for simplicity). A ⊕ B = parity (⊕ is bitwise XOR). What this allows us to do is B ⊕ parity = A as well as A &oplus parity = B.
We can extend this to any number of files. A ⊕ B ⊕ C = parity. Then A ⊕ B ⊕ parity = C and so on. This lets us recover a file if we have the parity block and all the other blocks that made up the parity block. In the case of RAID, if one disk fails, then the data on it can be rebuilt from all the others.
A and B don’t have to be files, just any set of bytes. So if we broke our files (conceptually) into a bunch of equal sized chunks, and then compute the parity of the chunks of each file. This parity could be stored and then used to recreate files lost to bit rot or other issues.
However, if you loose 2 blocks (including the parity block), you’re sunk.
RAID 6: Keeps one copy of the data and two parity block (each on a separate disk).
This second parity block is more complex than a simple bitwise XOR, but it allows the same types of properties as the parity block, but allows you to loose up to 2 blocks (including the parity blocks).
There is a program called parchive2 (or par2) that pretty much