Error-Proofing Data With Reed-Solomon Codes

ttsiod recommends a blog entry in which he details steps to apply Reed-Solomon codes to harden data against errors in storage media. Quoting: "The way storage quality has been nose-diving in the last years, you'll inevitably end up losing data because of bad sectors. Backing up, using RAID and version control repositories are some of the methods used to cope; here's another that can help prevent data loss in the face of bad sectors: Hardening your files with Reed-Solomon codes. It is a software-only method, and it has saved me from a lot of grief..."

Comments

Been doing this from the past 3 decades

[xquark]

slow news day anyone?

Re:Been doing this from the past 3 decades

[Nefarious Wheel]

Arrrh, aye, this be done since the dawn of time, matey! Ever since the days before global warming when pirates kept a second pistol in their belt just in case. Cap'n Jack Reed in the Solomons would harden his data with a second powder charge when the occasion demanded it.

"Awk! Parroty Error! Parroty Error! Pieces of Seven, Pieces of Seven"

(*BOOM*) never did like that bird.

Re:Been doing this from the past 3 decades

[Anonymous Coward]

Damn you're old.

Re:Been doing this from the past 3 decades

[Pseudonym]

Indeed. TFA should get to me when it discovers LDPC.

Re:Been doing this from the past 3 decades

[Reed Solomon]

Bah, I never make any erorrs

Re:Been doing this from the past 3 decades

[xquark]

LDPC based codes only work for pure erasure channels and do NOT work for static error channels. How does one perform loopy-belief propagation when the error probability distribution of the medium (in this case the disk) can not be modeled correctly?

Re:Been doing this from the past 3 decades

[arktemplar]

LDPC works for AWGN, I know because I have implemented the decoder. One can just perform min-sum rather than belief propagation, I've never heard of a "loopy" variant though. Now interestingly, research has been done on using LDPC for magnetic storage media - this was an year ago, so their error probability distribution should have been modelled I guess, I'm sure something more must be out.

The down side is to use LDPC it would make more sense if like in those research papers you were thinking of using it with backup magnetic tapes or something, since LDPC requires large message sizes and the way we normally write to the HDD isn't going to be the best for use of LDPC.

LDPC for those who didn't know is Low Density Parity Check Codes, they are a class of codes discovered in the 1960's and have been found to be asymptotically close to the Shannon limit of a channel. Wikipedia has a decent enough introduction for them - Also check out Turbo Codes, and Vitterbi codes - all of them more interesting to work with than Reed-Solomon

Re:Been doing this from the past 3 decades

[xquark]

if you haven't heard of loopy-belief propagation you're probably not aware of the state of the art in LDPCs, it has progressed a long way since Gallager's time rediscovered/reinvented a few times etc...

btw reaching channel capacity requires use of sparse matrices that have some very demanding properties. I believe the current direction at least for pure erasure channels (wifi, udp...) are Rateless codes or in other words Digital Fountains of which Tornado and LT style codes exist.

Re:Been doing this from the past 3 decades

[negRo_slim]

The way storage quality has been nose-diving in the last years, you'll inevitably end up losing data because of bad sectors.

It has? I will? Oh shit! I'm afraid! My precious data?.. Is this Slashdot or fox news?

Re:Been doing this from the past 3 decades

[Anonymous Coward]

How does one perform loopy-belief propagation

Through religeon, as it has always been done.

Re:Been doing this from the past 3 decades

[arktemplar]

I just looked it up, since I was working with projective geometry based implementations on hardware, I never quite worried about optimising the algorithms. I see that you have done work in Galvois fields so you'll know what I'm talking about.

Actually the sparse matrix based implementations are the ones that I've seen being researched so pardon my ignorance of the other side. The challenges involved are not inconsiderable, however the gains are much more interesting and this is where most VLSI implementations focus on - note the DVBS2 standard - it uses hamming codes with LDPC if I'm not mistaken - the implementations I've seen - are all type II PG based regular parity check matrix based. Still - thanks for the information now at least I'm aware of the fact that there is research being done in avoiding sparse matrix based implementations, for the record though it is these sparse matrix based implementations that give you best performance for a channel.

Re:Been doing this from the past 3 decades

[DarthJohn]

A nerd with a parrot on his shoulder walks into a bar.

The bartender looks up at him and smiles: "Hey where'd you get that?" he asks.

"This is Slahsdot... they're everywhere." the parrot replies.

[rimshot]

(adapted from a joke I heard on the History Channel's "History of the Joke")

It can make files a bit hard to read, though

[Bromskloss]

salkdffalkfhwefh2ihr5j45!"Â5jkcq2%"45wceh5 234j5cja4h5c2q4x524qZTkzzj3kzg3qkgl3kzgq3kjgh kq3gkzlq3hwgjlh 34qlgch34ljkw93q0x45c45 #&%#%&5vcXÂ%YXCHGC%ub64bVE5&UBy4vy5yc5E&Â E%vu64EV46rcuw4&C/4w6

Re:It can make files a bit hard to read, though

[xquark]

It really depends where you store the FEC, some techniques store the fec separately others concatenate and others interleave the FEC. Each method has its own advantages and disadvantages.

Re:It can make files a bit hard to read, though

[Tablizer]

2ihr5j45!"Â5jkcq2%"45wceh5 234j5cja4h5c2q4x524q kq3gkzlq3hwgjlh 34qlgch34ljkw93q0x45c45 #&%#%&5vcXÂ%

I for one welcome our Perl Overlords

Re:It can make files a bit hard to read, though

[Anonymous Coward]

The article doesn't mention the rather well established tool PAR2, that is commonly used for forward error correction on usenet. It allows for an adjustable amount of redundancy (and therefore data loss). Typically, PAR-Files are build to restore 2.5% or 5% of the protected archive. PAR2 uses Reed-Solomon Code, and is rather slow. Does anyone know of an efficient open source implementation of Tornado Codes, which allegedly are 10000 times faster?

Re:It can make files a bit hard to read, though

[Intron]

Because God forbid we ever lose any of the precious information on Usenet.

Re:It can make files a bit hard to read, though

[Phroggy]

#!/usr/bin/perl
$x='S24;r)>63/* h@<5+oZ)32"5cz';$me='phroggy'x$];
$x=~y+ -xz+\0-Tx+;print$_^chop$me for split'',$x;

#!/usr/bin/perl
for $a(1,46){for $b(0..7){$c=0;$_?hex substr(q), "ef7fa1866706ca",
Just another Perl Hacker, ("eff02289402844"),2*$_+$a,2)&2**(7-$b):
/..phroggy../ and $c+=2**(7-$_)for(0..7);$d.=chr $c;}}print"$d\n";

Re:It can make files a bit hard to read, though

[VoyagerRadio]

My understanding is that most of the feces end up in the ocean...

Drives already do this

[Rene S. Hollan]

... at least CDROMs employ RS codes.

Re:Drives already do this

[VoyagerRadio]

Do they do this automatically?

Re:Drives already do this

[Architect_sasyr]

From CD-ROM wiki:

A CD-ROM sector contains 2352 bytes, divided into 98 24-byte frames. The CD-ROM is, in essence, a data disk, which cannot rely on error concealment, and therefore requires a higher reliability of the retrieved data. In order to achieve improved error correction and detection, a CD-ROM has a third layer of Reed-Solomon error correction.[1] A Mode-1 CD-ROM, which has the full three layers of error correction data, contains a net 2048 bytes of the available 2352 per sector. In a Mode-2 CD-ROM, which is mostly used for video files, there are 2336 user-available bytes per sector. The net byte rate of a Mode-1 CD-ROM, based on comparison to CDDA audio standards, is 44.1k/s×4B×2048/2352 = 153.6 kB/s. The playing time is 74 minutes, or 4440 seconds, so that the net capacity of a Mode-1 CD-ROM is 682 MB.

I'd say that's a yes.

Re:Drives already do this

[Anonymous Coward]

I am no expert on HD reliability, however my thought is this:

Even if drive reliability per sector has gone up, the massive growth in storage capacitiy has perhaps made it more likely that you will have data corruption somewhere. And perhaps even that the corruption extends beyond the redundancy of RS' ability to regenerate the data.

With an additional layer of RS the effective redundancy should increase, making it possible to recover from data corruption that would otherwise result in data loss? With the processing power and storage capacity in modern computers, there should be little noticable overhead, or not?

Re:Drives already do this

[Marillion]

My biggest failed prediction in the world of computers was the CD-ROM.

I was an audio CD early adopter and I knew from articles I read that audio CD's often had a certain defect rate. The defect rate was usually such that you would never hear it. One artist even published all the defects in the liner notes.

Based upon this, I presumed that you would never get the defect rate to zero and that no one would trust a data medium with anything less than perfection - and thus predicted the CD-ROM would never catch on.

They don't have to get the rate to zero. Just close enough to zero for the RS to function.

Re:Drives already do this

[Anonymous Coward]

Yeah, but is there another problem elsewhere in the system? I have an el-cheapo USB-PATA adapter with a MTBF (mean time to bit flip) of about 2 hours. Every other disk was ruined, and I only knew because of a sick little obsession with par2. Disk data is ECC'd, PATA data is parity checked, and USB data is checksummed. Still, inside one little translator chip, all that can be ruined. and that's why data integrity MUST be an operating/file system service.

Re:Drives already do this

[xquark]

My understanding is that it is possible to drill a few holes no larger than 2mm in diameter equally spread over the surface of an "audio cd" and with the help of h/w RS erasure decoding, channel interleaving and channel prediction (eg:probabilistically reconstruct missing right channel from known left channel) one can produce a near perfect reconstruction - that's what usually happens to overcome scratches and other kinds of simple surface defects.

Re:Drives already do this

[Firehed]

That might be good for music where a near-lossless reconstruction is acceptable, but I'd suggest not drilling holes in your thesis paper, or any other type of data where lossy compression is unacceptable (everything except images, audio and video, basically)

Re:Drives already do this

[wik]

You haven't read too many theses. There are holes all over the place...

Re:Drives already do this

[Solandri]

That's a pretty fundamental part of information theory - communication in a noisy channel. If your communications (or data storage) are digital, you can overcome any level of random noise (error) at the cost of degraded transmission rate (increased storage requirement). Before CDs, it was (and still is) most prevalent in modem protocols and hard drives. Modern hard drives would probably be impossible without it - read errors are the norm, not the exception. It's just hidden from the high-level software by multiple levels of error correction in the low-level firmware.

Re:Drives already do this

[Solandri]

Data is stored linearly on a CD (and DVD). So the data can survive huge scratches running from the center to edge, but is very susceptible to radial scratches rotated around the center. If you think of a CD as an old-style phonograph record, you can scratch across the grooves and the error correction will fix it; but scratching along a groove will quickly corrupt the data because the scratch will destroy sequential data (and its ECC). That's why they recommend cleaning CDs by wiping from the center out, never in a circular motion.

Re:Drives already do this

[femto]

Another view is that everything is a code in a noisy environment, so there is no way to talk about "the underlying device" as it itself is just another type of coding. Magnetic recording can be viewed as a way of encoding information onto the underlying (thermal) noisy matter. There is some very deep stuff happening in information theory. Let's take the empty universe as a noisy channel. Now every structure in the universe (including you and me) becomes information encoded over the empty universe. One gets the feeling that any "ultimate theory" won't be expressed in terms of forces and fields but some underlying, unifying, concept of information.

Re:Drives already do this

[Anonymous Coward]

Thank you for the links!

Re:Drives already do this

[norton_I]

Dude, put the bong down.

Re:Drives already do this

[Lonewolf666]

But not every drive/OS seems to really use it. Some anecdotal evidence:

Back in the Windows 9x days, I helped a friend of mine to reinstall Windows (98 IIRC). After copying files to the HD and restarting, the newly installed system always crashed. There was no error message that indicated there was a problem with reading the data from the CD-ROM (a Liteon which was known to be a bit dodgy).

We finally tried another drive and it worked on the first try. I conclude that there were unreported errors reading from the CD-ROM drive we tried first and the files written to the HD were corrupted. So either the CD-ROM drive or the Windoze installer failed to detect and report the errors.

Re:Drives already do this

[Anonymous Coward]

It all depends on what you mean by cleaning, don't it?

Re:Drives already do this

[Yvan256]

Other valid replies would have been "I'll have what he's having" or "Pass it around, please".

Re:Drives already do this

[Iamthecheese]

Not. When youre daily backups are 80 terrabytes big, everything is a hardware consideration. Faster drives? More tapes? More tape storage? More tape swapping? Firmware upgrades? In any case its certainly not free and probably not simple.

Re:Drives already do this

[MagdJTK]

Indeed. In fact, the code used for CDs can cope with 4000 consecutive bits being unreadable. Quite remarkable!

Re:Drives already do this

[Wowsers]

I loved my DAT (for audio) portable recorder, it employed Double-Reed-Solomon error correction, you would have to do some serious hammering to the side of the recorder to get the tape to "skip" in a way the error correction could not correct it and you'd hear it drop out, running and recording was NOT out of the question though.

Now what do the consumers have for recorders - cr*ppy, cheap, nasty, low bitrate, overcompressed MP3 recorders. The recording industry killed off an excellent (but expensive) format to palm off rubbish compressed audio to the masses. (Proper PCM recorders are no different in price to the DAT decks).

Re:Drives already do this

[complete loony]

AFAIK when a disk is scratched you are more likely to get a tracking error than a failure to decode the audio.

Re:Drives already do this

[mentaldrano]

Radial scratches go from center to edge, azimuthal scratches go around the center.

Re:Drives already do this

[77Punker]

Don't bogart that joint!

Re:Drives already do this

[PitaBred]

Thing is, the "overcompressed" MP3 recorders are good enough. Most people use them to record lecture notes, or a meeting, or just talking to themselves. Those are about the only reasons to really need a portable recorder, and for those uses, mp3 is very good. Just because it's low bitrate doesn't mean it's bad, and just because your DAT recorder had higher quality doesn't mean it's more fit for the purposes it would be used for. Seriously... running and recording? Why would you ever want to do that?

Re:Drives already do this

[wurp]

You should read http://www.hpcoders.com.au/theory-of-nothing.pdf

Re:Drives already do this

[PitaBred]

If you'd spend slightly more on better hardware, you wouldn't be posting that comment. Yes, data can be ruined by cheap components. A bulletproof filesystem won't protect you against a head crash. The only good thing that the bulletproof filesystem would do would possibly make that cheapo USB adapter of yours not work at all, and force you to buy a proper one.

Re:Drives already do this

[Hao Wu]

I remember believing that CD caddies were essential, and people without them were taking a terrible risk.

When it came to burning CDs, I feel I was proven right. For the wasted time and expense of churning out coasters, I would have preferred having caddies.

Re:Drives already do this

[loose electron]

Reed Solomon codes are a first generation ECC (Error Correcting Code) HDD's used to use RS codes about 30 (yikes! closer to 40 now!) years ago. Since then they have evolved into much more powerful ECC's that are designed to correct the types of errors run into in magnetic storage, which is burst errors. (Due to media defects)

All mass storage has a defined acceptable BER (Bit Error Rate) - and that BER is defined two ways, without ECC application and with. The industry standard for audio and data are different, but the whole idea is get to an acceptable BER after applying an ECC.

This is not news, this is ancient history. The article is applying an ECC method on top of another ECC method inherent to the media. Better BER? Sure, but whats the big deal? Also if you look at classic RS codes they are pretty inefficient, and coding theory is light years beyond that point now.

Re:Drives already do this

[maestroX]

Based upon this, I presumed that you would never get the defect rate to zero and that no one would trust a data medium with anything less than perfection - and thus predicted the CD-ROM would never catch on.

You're lucky, I invested my life savings in vinyl.

Re:Drives already do this

[Just Some Guy]

Be careful, as this adds a lot of brightness to the music. You absolutely must follow up with a green marker to restore the vanilla and mossy undertones.

-- Audrey O'File

Re:Drives already do this

[sjames]

read errors are the norm, not the exception [storagereview.com]. It's just hidden from the high-level software by multiple levels of error correction in the low-level firmware.

Some of those could be eliminated with much tighter tolerances and reducing the overall data density a bit, but not all. The catch is, you'd need a second mortgage to buy one and it would only be a bit faster and no more reliable.

qpar

[Anonymous Coward]

it already exists - QPAR

ZFS?

[segfaultcoredump]

Uh, is this not one of the main features of the ZFS file system? It does a checksum on every block written and will reconstruct the data if an error is found? (assuming you are using either raid-z or mirroring. Otherwise it will just tell you that you had an error).

Re:ZFS?

[xquark]

checksums really only help in detecting errors. Once you've found errors, if you have an exact redundancy somewhere else you can repair the errors. What reed-solomon codes do is provide the error detecting ability but also the error correcting ability whilst at the same time reducing the amount of redundancy required to a near theoretical minimum.

btw checksums have limits on how many errors they can detect within lets say a file or other kind of block of data. A simple rule of thumb (though not exact) is that 16 and 32 bit checksums can detect upto 16,32 bit errors respectively anymore and the chance of not detecting every bit error goes up, it could even result in not finding any errors at all.

Re:ZFS?

[Anonymous Coward]

There are two ways of solving this with ZFS:

* RAID-0, mirrored drives.
* Set copies > 1, which tells ZFS to keep at least N copies of all data written to the storage pool.

Case closed! Next!

Re:ZFS?

[atrus]

ZFS does maintain ECC codes to aid in correction. Even on single disks.

Re:ZFS?

[bobbozzo]

Mirroring is RAID-1, not 0.

Re:ZFS?

[this great guy]

I have been a ZFS user for a while and know a lot of its internals. Let me comment on what you said.

checksums really only help in detecting errors.

Not in ZFS. When the checksum reveals silent data corruption, ZFS attempts to self-heal itself by rewriting the sector with a known good copy. Self-healing is possible if you are using mirroring, raidz (single parity), raidz2 (dual parity), or even a single disk (provided the copies=2 filesystem attribute is set). The self-healing algorithm in the raidz and raidz2 cases is actually interesting as it is based on combinatorial reconstruction: ZFS makes a series of guesses as to which drive(s) returned bad data, it reconstructs the data block from the other drives, and then validates whether this guess was correct or not by verifying the checksum.

checksums have limits on how many errors they can detect.

All the ZFS checksumming algorithms (fletcher2, fletcher4, SHA-256) generate 256-bit checksums. The default is fletcher2 and offers very good error detection (even errors affecting more than 256 bits of data) assuming unintentional data corruption (the fletcher family are not a cryptographic hash algorithms, it is actually possible to intentionally find collisions). SHA-256 is collision-resistant therefore it will in practice detect all data corruptions. It would be computationally infeasible to come up with a corrupted data block that still matches the SHA-256 checksum.

A good intro to the ZFS capabilities are these slides

Re:ZFS?

[N Monkey]

checksums really only help in detecting errors. Once you've found errors, if you have an exact redundancy somewhere else you can repair the errors. What reed-solomon codes do is provide the error detecting ability but also the error correcting ability whilst at the same time reducing the amount of redundancy required to a near theoretical minimum.

Having both, however, can be useful. For example, you can arrange your data in a rectangle and use standard error detecting checksums along the rows and RS on the columns. Knowing that particular rows may have an error can effectively double the error correction rate of Reed Solomon. See Erasure

Re:ZFS?

[Rob Simpson]

Using mirrored drives in RAID-1 is a poor solution, and making redundant copies of the every file on the same drive is a terrible one. A filesystem suitable for use on hard drives that can substantially increase the integrity of data with a relatively minor cost in terms of extra space and speed would be very useful. Something like a Mode-1 CD-ROM's error correction. Being able to use it in RAID-1 would be a bonus.

Re:ZFS?

[notany]

The blocks of a ZFS storage pool form a Merkle tree in which each block validates all of its children. Merkle trees have been proven to provide cryptographically-strong authentication for any component of the tree, and for the tree as a whole. ZFS employs 256-bit checksums for every block, and offers checksum functions ranging from the simple-and-fast fletcher2 (the default) to the slower-but-secure SHA-256. When using a cryptographic hash like SHA-256, the uberblock checksum provides a constantly up-to-date digital signature for the entire storage pool. Which comes in handy if you ask UPS to move it.

http://blogs.sun.com/bonwick/entry/zfs_end_to_end_data

Re:ZFS?

[Wesley Felter]

Not really, but if you enable copies=2 ZFS will replicate all data on a single disk.

Re:ZFS?

[Anonymous Coward]

But wouldn't you also need FEC on the metadata, i.e. the filesystem structures themselves? So I guess the RS (or whatever FEC you employ) coding has to be at a level _below_ the filesystem. Otherwise, an error just takes out the whole inode and then it doesn't matter if you had FEC on the data or not.

Re:ZFS?

[illumin8]

It would be computationally infeasible to come up with a corrupted data block that still matches the SHA-256 checksum.

Computationally infeasible, yes, but the interesting ways I've seen data get corrupted I can only imagine that I would be that one in a quintillion chance that it goes undetected... I seem to have bad luck with data.

Re:ZFS?

[this great guy]

A quintillion is only 2**60. Finding an SHA-256 collision requires 2**128 steps. So, no, it will never happen to you. To put things is perspective, the security/integrity of RSA keys (hence TLS/SSL, online banking, etc) depend on primality tests which only guarantee that the randomly generated RSA p and q parameters have a probability of about 1 in 2**80 or so of not being primes...

Can FUSE help?

[ApostleJohn]

It would be nice if it was a file system layer like encFS but for error-correction.

Interesting

[d_jedi]

I've been burned by scratched DVD+Rs too many times. I'd be interested if there were a way to do this kind of thing in Windows..

Re:Interesting

[enoz]

The WinRAR archiver has an optional recovery record which protects against bad blocks.

When you create an archive just specify the amount of protection you require (in practice 3% has served me well).

Re:Interesting

[Anonymous Coward]

The cross platform program dvdisaster will add extra information to your DVD as an error correcting code. Alternatively, you can make a parity file for an already-existing DVD and save it somewhere else.

It actually has a GUI too, so it must be user friendly.

Re:Interesting

[xquark]

I believe the underlying code used in RAR for the recovery record is in fact an RS(255,249) codes

Re:Interesting

[Firehed]

Bit-torrent?

No seriously. I don't know a whole lot about network infrastructure (nor do I care, strictly speaking), but there's clearly some sort of error-checking/correcting going on behind the scenes as I'll grab huge disk images that pass verification before they get mounted (ex. iPhone SDK ~ 1.2GB) all the time. Some sort of network-based solution is really ideal for data transfer.

Of course with residential upload speeds it's often slower than the ol' sneakernet (depends where it's going, how it's getting there, and how much there is), but not unusably so. I'll SSH half-gig files to/from my home system from work all the time. Grabbing them from the house is somewhat of a painful process that'll often run 1/2-1 1/2hr, but oh well.

Obviously splitting your large disk image into a bunch of smaller rars or whatever you prefer could help with connection disruptions, but data integrity issues are almost never an issue.

Re:Interesting

[Hal_Porter]

I've been burned by scratched DVD+Rs too many times. I'd be interested if there were a way to do this kind of thing in Windows..

Actually Reed Solomon error correction doesn't always help with scratched CDs - they still skip. The problem there is a that the laser can't track a scratched media. If it could track, RS would get the data back though.

Re:Interesting

[xquark]

It is possible for a well designed h/w decoder to detect the loss of laser tracking and from there signal the decoder that the current bit or byte read-in is an erasure (ie: it is erroneous, the position is known but the amount of error, meaning the difference from what the decoder gets and what it really should be is unknown) - this is known as side-channel information.

In these cases the decoder is capable of decoding mixtures of errors and erasures. In an "all erasure" decoding scenario and decoder should be able to decode twice as many erasures as it can decode errors.

The relationship is 2E + S = F, where E is the number of errors, S is the number of erasures and F is the number of FEC symbols.

Re:Interesting

[Anonymous Coward]

For my media center I use quickpar http://www.quickpar.org.uk/.
1. DVD Shrink each disk of a season of a show (IE 7 disks of ST:TNG Season 3) output file to a ISO.
2. Use quickpar to create 6000 megs of par2 files. Use small files so you have about 200 par 2 files to work with.
3. Burn ISO to DVD AS MULTISESSION. In the 2nd session fill up disks with pars so that disk one has pars 0-5, disk 2 has 6-10, ect.
4. Burn 8th disk of all remaining pars that didn't fit on any of disks 1-7. Then fill up any extra pars just to max out the DVD.
Now if you loose ANY one of the 8 disks, the missing disk can be recovered. Also EVEN WITH a missing disk, there is STILL enough par's to recover from minor damage to the other 7 disks. Also note when doing recovery you can copy all the misc files that make DVD (the VOB's ect) to your hard drive, and quickpar will repair them to a ISO.

Even better

[Anonymous Coward]

Just use a modern versioning system, such as Git or Mercurial, which keep track of everything using hashes. Then, you not only get to detect and repair errors, you also get version history.

Re:Even better

[ThePromenader]

A modern versioning system called "Git"? You old...

Drive quality

[kipman725]

"The way storage quality has been nose-diving in the last years" I disagree totally all my modern drives are working whereas I used to plagued by hard disk failure. For example are any modern drives as bad as the deathstar? in the past 5 years I have had 0 failures but in the 5 preceding that I had about 8 drive failures. Small sample size I know but to me hard drives are getting better.

Re:Drive quality

[dougnaka]

I just bought a batch of 10 750GB Seagate's from NewEgg and have RMA'd 6 of them, and 1 of the RMA'd drives was DOA and RMA'd. There was almost a silver lining when they shipped us a 1TB replacement, but these are all for RAID 1 mirrors :( Before this I had only had Deathstars, Maxtors and WD's die.

Re:Drive quality

[enoz]

I'm still waiting for the 5 year warranty to expire on my hard drives.

Harden Files

[inKubus]

When he said "harden files", I thought he was going into a long soliloquy on all the porn on his computer, so I went to the next story.

Re:Harden Files

[Anonymous Coward]

It never ceases to amaze me that the juvenile "heh heh heh.. he said 'harden'" response always gets modded funny. Mods, here's a tip: These kinds of jokes aren't funny unless you are a) 13 years old or b) really drunk.

Re:Harden Files

[Anonymous Coward]

It never ceases to amaze me that the juvenile "heh heh heh.. he said 'harden'" response always gets modded funny. Mods, here's a tip: These kinds of jokes aren't funny unless you are a) 13 years old or b) really drunk.

Such jokes are rampant here at slashdot.

Re:Harden Files

[Anonymous Coward]

c) both

Re:Harden Files

[Anonymous Coward]

When he said "harden files", I thought he was going into a long soliloquy on all the porn on his computer, so I went to the next story.

I notice you came back. :-)

Re:Harden Files

[uglydog]

what made you come back? :-)

this is amazing

[Anonymous Coward]

It's like a code that can correct errors!

Never underestimate the redunancy...

[symbolset]

Look, if it's secret, one copy is too many. For everything else, gmail it to five separate recipients. It's not like Google has ever lost any of the millions of emails I've received to date. (This is not a complaint -- they don't show me the spam unless I ask for it).

And if they ever did lose an email, well, to paraphrase an old Doritos commercial, "They'll make more."

Seriously, personally I view the the persistence of data as a problem. It's harder to let go of than it is to keep.

redundancy

[symbolset]

Yeah, I can spell it. Get a libe.

Speed?

[grasshoppa]

My question is of speed; this seems a promising addition to anyone's back up routine. However, most folks I know have 100s of gigs of data to back up. While differentials could be involved, right now tar'ing to tape works fast enough taht the backup is done before the first staff shows up for work.

I assume we're beating the hell out of the processor here; so I'm wondering how painful is this in terms of speed?

Re:Speed?

[Zadaz]

Well since my $100 Radio Shack CD player I bought in 1990 could do it in real-time I'm guessing that the requirements are pretty low. In fact a lot of hardware already uses it.

If you read the rest of the page you find out it's very ingenious and efficient at doing what it does.

While it's certainly not new (it's from 1960) or unused (hell, my phone uses it to read QR codes) I'm sure its something that has been under the radar of a lot of Slashdot readers, so I'll avoid making a "slow news day" snark.

Re:Speed?

[xquark]

The speed of encoding and decoding directly relates to the type of RS and the amount of FEC required. Generally speaking erasure style RS can go as low as O(nlogn) (essentially inverting and solving for a vandermonde or Cauchy style matrix) A more general code that can correct errors (the difference between an error and an erasure is that in the latter you know the location of the error but not its magnitude) may require a more complex process, something like Syndrome-Berlekamp Massey-Forney which is about O(n^2).

It is possible to buy specialised h/w (or even GPUs) to perform the encoding steps (getting roughly 100+MB/s) and most software encoders can do about 50-60+Mb/ for RS(255,223) - YMMV

Re:Speed?

[Anonymous Coward]

Your CD player took about an hour for 600 MB of data. While that is real-time for audio, it might be a tad slow for saving your mixtape to disk.

Re:Speed?

[Anonymous Coward]

Umm, if speed is an issue buy a 1U RAID NAS with Gigabit Ethernet and do disk to disk to tape. The network could handle 125MB/sec without teaming. That 2GB website would be backed up in under 30 seconds for a full. It's a different story when you're talking about multiple TB.

Version control != backups

[XorNand]

Please, please stop thinking of version control as some sort of backup. When we initially started mandating the use of version control software, developers would just using the "commit" button instead of the "save" button. It makes it *much* more difficult to traverse through the repo when you have three dozen commits per day, per developer, each commented with "ok. really should be fixed now." The worst offenders were issued an Etchasketch for a week while their notebooks went in for service *cough*. Problem solved.

Re:Version control != backups

[dgatwood]

Well, you shouldn't commit until you believe you have it in a state where the changes are usable (i.e. don't break the tree), but beyond that, I'd rather see more commits of smaller amounts of code than giant commits that change ten thousand things. If you end up having to back out a change, it's much easier if you can easily isolate that change to a single commit. My rule is commit early, commit often. I'm not the only one, either:

http://blog.red-bean.com/sussman/?p=96

Re:Version control != backups

[ceswiedler]

The best solution is for developers to use their own private branches. Then they can commit as much as they want, and integrate into the main branch when they're ready. Unfortunately subversion has crappy support for integration (even with version 1.5 AFAICT) compared to something like perforce.

Re:Version control != backups

[Anonymous Coward]

The worst offenders were issued an Etchasketch for a week while their notebooks went in for service.

And the president responded by setting the "British Humour" alert status to red.

You are all dumb as there is only one way.

[Anonymous Coward]

Whenever you back up to CD or DVD, fill up any unused remaining space with par files generated from the data being backed up.

Reed-Solomon is ancient compared to par2.

Re:You are all dumb as there is only one way.

[xquark]

Fine we are all dumb, now tell me what happens when the errors on the disk are spread over all the files and the par2 equally to the extent at which the drive wont even send data back - what does one do then? how do you tell the drive about the par fec?

its best to spread data equally over multiple devices as if one device was to totally fail you could still get something back (reconstruct) from the other devices.

Re:You are all dumb as there is only one way.

[Stalin]

I hope you are joking. PAR2 is nothing more than an implementation of RS codes. So how can RS codes be ancient compared to PAR2?

From the PAR2 specification introduction:

"The redundant data in the PAR files is computed using Reed-Solomon codes. These codes can take a set of equal-sized blocks of data and produce a number of same-sized recovery blocks. Then, given a subset of original data blocks and some recovery block, it is possible to reproduce the original data blocks. Reed-Solomon codes can do this recovery as long as the number of missing data blocks does not out number the recovery blocks. The design of the Reed-Solomon codes in this spec is based on James S. Plank's tech report at U. of Tennessee entitled A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. The tech report contains an error, so the design is changed slightly to fix the problem. PAR 2.0 uses a 16-bit Reed-Solomon code and can support 32768 blocks."

Re:You are all dumb as there is only one way.

[billcopc]

Reed-Solomon is ancient compared to par2.

No, you're dumb. Par2 IS Reed-Solomon. Silly me to expect an AC to fact-check the most trivial subjects of a post.

The procedure explained in TFA is basically adapting a different tool to behave more or less like single-file par2. That makes it redundant (in the /. sense, not the data-recovery sense).

There is one thing I would love to see, and that's local disk checksumming. That's right, take a 500gb disk, chop it into slices and do RAID-5 on them as if they were individual spindles. It's been years since I've had a hard drive actually die on me, but I've seen bit-errors more often than I'd like. Having self-checking built into the filesystem (or low-level disk access) would help ensure 100% data integrity, and you could still do RAID-1 on top of it for safety.

Re:You are all dumb as there is only one way.

[swilver]

About the bit errors...

Hard drives themselves already do extensive error correction and checksumming of all their blocks, which led me to believe that any bit errors are not from the hard drives themselves (since the checksum would fail then and it would be flagged as a read error). It's therefore extremely unlikely that a hard drive returns you data with a bit error in it, unless of course it already had this error when the block was written.

I used to have problems on an older system where copying 100 GB of data usually had atleast 1 bit error when compared to the original. Since the problem in my opinion couldn't be the hard drive I went looking for other places such bit errors could be introduced.

What I found was that the bit errors actually occured in the systems main memory. There are no checksums on disk buffers in memory and so any error there goes completely undetected. When copying 100 GB of data, there's a good chance atleast one of those bits gets flipped while in memory. Anyway, after I switched to ECC memory the problem disappeared and I haven't seen it since (and I religiously use a copy program that verifies data after the copy).

Re:You are all dumb as there is only one way.

[brix]

I do the same as the AC, but I keep a copy of the smallest par2 from the set on my local drive for recovery (and back these up as well). If a CD/DVD ever goes bad to the point it won't even read the FS, you can still create an ISO file of it including all errors. The par2 recovery can be done using the ISO image at that point, and as long as the damage to the DVD didn't exceed the redundancy level, full recovery of the original files is possible.

Note that you aren't recovering the ISO itself at this point, you are using the ISO as input to par2repair (or the GUI). The recovery is done using the blocks of the original files and pars. The end result is the original file(s) stored on the disc.

It sounds like dvdisaster does something similar, but I've been using this technique with pars for a few years now.

Re:You are all dumb as there is only one way.

[Anonymous Coward]

There is one thing I would love to see, and that's local disk checksumming.

ZFS does this. It lets you choose your favorite checksuming algorithm and decide how much redundant data you want. And it will verify and correct (they call it scrubbing) with the file system mounted and active.

Re:You are all dumb as there is only one way.

[zippthorne]

The problem with par2 and dvdisaster is that they're not ubiquitous or, apparently, interesting enough to developers.

What is needed is something *like* par2, but that works over directory trees, generally fits in well with the the other unix tools, and is as ubiquitous as dd, tar, cp and gzip.

What good is including ECC with your data if the tools that can be used to recover it lost interest and withered away half a decade after you burned it?

Further, the "best" way would be to extend the CD spec to arbitrary numbers and sizes of extra-layers, so that you can always fill the CD, no matter how much data you put on it, and the extra parity data strikes a good balance between large numbers of errors and large blocks of errors.

Re:You are all dumb as there is only one way.

[Anonymous Coward]

You can slice a disk up and do software RAID on it using logical volumes. No fancy new technology needed.

Re:You are all dumb as there is only one way.

[Anonymous Coward]

The source code for Par2 is only around 200KB
There is no reason you couldn't put a copy of the source code on the CD as well.

huh???

[Jane Q. Public]

If you think storage quality has been nose-diving, then you haven't been around very long. It just isn't so.. and there really is not much more I can say to add to that.

I have been around this industry quite a while, and I call bullshit on that.

Yes, RS should be a file system service.

[Futurepower(R)]

"... data integrity MUST be an operating/file system service."

I agree. I'm willing to have a small loss in speed and a small increase in price to have better data integrity.

There is already data integrity technology embedded in hard drives, and I support making it more robust.

Re:Yes, RS should be a file system service.

[iminplaya]

Those who sacrifice speed for data integrity deserve neither - BF

Re:Yes, RS should be a file system service.

[Anonymous Coward]

Those who sacrifice speed for data integrity deserve neither - BF

Those who sacrifice data integrity for speed deserve neither - Sys Admin

Re:Yes, RS should be a file system service.

[PitaBred]

RAID0 for everyone! Hooray!

Re:Yes, RS should be a file system service.

[Fweeky]

That won't protect you from controller defects, which seem to be quite a significant source of problems going by where people are finding checksum errors with ZFS.

DMA is hard, let's go ride bikes!

This is not very useful for changing data...

[Jane Q. Public]

since it is only a "snapshot" of the data at a particular time. Any time you change the data, you have to do another "snapshot". What a major pain in the ass.

This might be useful for archived files, but not something you change on a regular basis.

I wish PAR2 would have kept improving...

[WoTG]

Yes, CDs and DVDs have error correction built in, but they don't do much if you happen to a nice scratch that follows the spin of the disk. I.e. a moderate scratch from the outside to the inside of a CD is reasonably OK for data, but a scratch the other way will kill your data much more easily.

For a while I was using PAR2, yes, the PAR2 used on USENET, to beef up the safety of my DVD backups of my home data. Unfortunately, PAR2 never really evolved to handle subdirectories properly, which mattered when I wanted an off-site backup of my digital photos.

Eventually, I started using ICE ECC, http://www.ice-graphics.com/ICEECC/IndexE.html, free as in beer, to enhance my DVD backups of stuff like photos and data. IIRC, I tested it's ability to reconstruct missing files and it seemed OK at the time.

Anyways, that's my $0.02 on Reed-Solomon for backups.

Re:I wish PAR2 would have kept improving...

[Fnord666]

Eventually, I started using ICE ECC, http://www.ice-graphics.com/ICEECC/IndexE.html, free as in beer, to enhance my DVD backups of stuff like photos and data. IIRC, I tested it's ability to reconstruct missing files and it seemed OK at the time.

Unfortunately this software looks like it is closed source and windows only. A program to apply error correcting codes to your archived files is only useful if you still have a platform to run it on. Hopefully 15 years from now when you go to recover your files you have an old windows machine still available for use.

Re:I wish PAR2 would have kept improving...

[catenx]

The biggest limitation of PAR2 for me is the lack of directory handling. You can only create and verify parchives for the files within a directory. One solution is a script that runs the PAR creation or verification for each subdirectory but this is hardly elegant. Hard to use backup is backup that isn't used. A better solution is what ICE ECC offers.

Agreeing with Fnord666, the software does not use an open algorithm. The general tone of the site is "use this software it is awesome, don't argue". There doesn't seem to be verification of its awesomeness. Furthermore, the program author's tone in many of the forum posts is abrasive and near combative when people question it.

PAR2 is proven but limited. This /. post is the closest I've seen to addressing the progression of software past Parchives, or at least enhancing the PAR spec for new needs (directory traversing for example).

Is this really the case, that no one has taken PAR2 to the next level? Judging from the lack of links in these comments to the flamebaiting posts of "we've been doing this for years" there isn't much progress.

I want PAR3.

Or you could just use PAR...

[InakaBoyJoe]

TFA introduces some new ".shielded" file format. But do we need yet another file format when PAR (Parchive) has been doing the same job for years now? The PAR2 format is standardized and well-supported cross-platform, and might just have a future even IF you believe that Usenet is dying...

I always thought it would be cool to have a script that:

• Runs at night and creates PAR2 files for the data on your HD.
• Occasionally verifies file integrity against the PAR2 files.

With a system like this, you wouldn't have to worry about throwing away old backups for fear that some random bit error might have crept into your newer backups. Also, if you back up the PAR2 files together with your data, as your backup media gradually degrades with time, you could rescue the data and move it to new media before it was too late.

Of course, at the filesystem level there is always error correction, but having experienced the occasional bit error, I'd like the extra security that having a PAR2 file around would provide. Also, filesystem-level error correction tends to happen silently and not give you any warning until it fails and your data is gone. So a user-level, user-adjustable redundancy feature that's portable across filesystems and uses a standard file format like PAR would be really useful.

Re:Or you could just use PAR...

[Gunstick]

I wrote a script which fills up a CD/DVD with par2 files until it's full and then writes the image.
So you can still recover your data even if some bits miss.

Why I do this? Well I have had too many occasions where I read a CD and find a couple of bits toggled compared to the original image. Typically you write and then verify and the verify comes back bad. Another bad burn? No just one bit. So I add par2 files and don't care anymore if some bits are faulty :-)

Problem: it takes quite some time for doing par2 on a dvd and of course only works on disks which you don't fill up completely with user data.

Re:Or you could just use PAR...

[Anonymous Coward]

Personally, I use RAR - It compresses and provides redundancy data :)

I'm quietly hoping 7zip integrates this kind of ECC stuff in its next version because it's better than RAR in every way, except for this one feature. But it is a BIG feature for me.

PAR2, anyone?

[mystik]

Doesn't par2 already employ reed-solomon? (http://en.wikipedia.org/wiki/Parchive)

And it has all sorts of options let you configure the amount of redundancy you'd like?

And it has (ahem) been very well tested in the recovery of incomplete binary archives ... ?

Now that usenet has been stripped of binaries, we'll have to find other uses for these tools ....

As I understand it...

[warrax_666]

ZFS checksums are actually hashes, as in "cryptographic hash", so they're pretty damn reliable (though theoretically 100% reliable) at detecting errors.

Re:As I understand it...

[xquark]

Ok, lets assume its a 128-bit hash. For a 1GB file how many combinations of 1GB will produce the same hash? the problem here is that at some point the hash/ECC may fail. it always does, its not a matter of if but when.

btw I'm sure ZFS doesn't do the checksums over 1GB blocks perhaps some smaller sized block, regardless the same logic still applies.

Re:As I understand it...

[Firehed]

From what I've read and heard, ZFS is designed to pretty much be the last filesystem we'll ever need. I'm pretty sure they've considered hash collisions with regards to data integrity.

Also consider that you probably won't need to reconstruct the entire sector, but only a few bits from it. If there was some sort of insane scenario where you had to reconstruct a complete 1GB block from a single MD5 hash... (ie, "here's an MD5 hash. Give me a sequence of 1073741824 bytes to make it") well it's technically possible, though the electric bill for your server farm may piss off more than a few treehuggers. On the other hand, if you had only a few bytes that needed repair, brute-force reconstruction, while still time-consuming, suddenly becomes more more feasible. I always wonder why I can't apply this kind of logic to torrents with that one file stuck at 99.98%...

I'm sure that kind of thing is largely irrelevant with ZFS as it's designed to be somewhat more efficient, but you get the point.

Re:As I understand it...

[Pseudonym]

Ok, lets assume its a 128-bit hash. For a 1GB file how many combinations of 1GB will produce the same hash?

You're asking the wrong question.

The right question is: Given a 1Gb file, how much "mutation" do you have to do to it to produce a file with the same hash? And the answer to that is: Enough to make the data unrecoverable no matter what you do.

Re:As I understand it...

[Anonymous Coward]

From what I've read and heard, ZFS is designed to pretty much be the last filesystem we'll ever need. I'm pretty sure they've considered hash collisions with regards to data integrity.

In other words "Of course ZFS does that! I have faith!!"

You must have a pretty Zen relationship with your manager if he accepts arguments like that.

Re:As I understand it...

[profplump]

That's not really true though. While unlikely, it is *possible* that a hash collision occurs on two inputs that vary only by one bit. In most cases we expect a one-bit change in the input to upset about 50% of the bits in the has output, but that's certainly not true for every possible pair of inputs. Checksums are useful for detecting most small errors, but redundant storage and comprehensive bit-by-bit comparison is the only way to be absolutely sure, and that's generally considered too expensive for use in commodity computing.

Re:As I understand it...

[xquark]

That is correct, there is always the possibility that the data can still be viable after a large number of bit flips, and that a problem nonetheless

Re:As I understand it...

[xquark]

heard of the birthday paradox? don't need that much memory to come up with a collision, in fact most MD hash attacks are based on that principle.

Re:As I understand it...

[Eighty7]

This case is different because the checksum is known. The birthday problem is about the probability of at least 1 collision given a certain group size. Given a good uniform n-bit hash, it'll take 2^n tries to collide against a given value, and sqrt(2^n) tries to find a random pair of colliding values. According to wiki, ZFS uses 256-bit checksums.

Re:As I understand it...

[roydeboer]

If there was some sort of insane scenario where you had to reconstruct a complete 1GB block from a single MD5 hash... (ie, "here's an MD5 hash. Give me a sequence of 1073741824 bytes to make it") well it's technically possible, though the electric bill for your server farm may piss off more than a few treehuggers.

If this would be true, you'd have found a very space-efficient datacompression algoritm. The truth is, however, if you map all integers representing 1 GB of data to the integers representing 16 bytes of MD5, your map cannot be bijective.

Re:As I understand it...

[Pseudonym]

OK, so for a 256-bit hash, you need 2^255 bit flips to replicate the hash. You'd be flipping bits on the hash itself before that happened.

Incidentally, if we flip enough bits on my hard drive, there is the possibility that I could end up with the contents of your hard drive, via the infinite monkeys principle.

Re:As I understand it...

[twistedcubic]

You mean to say injective, though being bijective is sufficient.

Re:As I understand it...

[GXTi]

If there was some sort of insane scenario where you had to reconstruct a complete 1GB block from a single MD5 hash... (ie, "here's an MD5 hash. Give me a sequence of 1073741824 bytes to make it") well it's technically possible

Curious... how do you intend to reconstruct 1073741824 bytes from a 16 byte message digest? That's 2 ^ 8589934592 possibilities, of which approximately 2 ^ (8589934592 - 128) satisfy any given message digest. It's possible to brute-force something, but it's not possible to get the original thing without more information (like 1GiB of information)

Re:As I understand it...

[Firehed]

Well at a 1GB target size, I'm sure you'll encounter a number of hash collisions. But of all of the n arbitrary streams of bits that will hash down to whatever, I'd be very surprised to find more than one that would actually result in files that any software could open. Even if you had a hundred to pick from, you're in a situation where a human can figure out the rest (or be treated to some very unusual porn).

That's not entirely unlike the decentralized tracker system Bit-torrent clients have implement of late. You pass them magnet://some md5 hash link, it pings a bunch of nodes in the network if anyone in the swarm has a torrent that hashes down to that hash, and once it finds it, starts the downloads as normal. It's not brute-force reconstruction, but it is creating files from a tiny hash. This is where the beauty of the general lack of hash collisions between non-arbitrary chunks of data shows itself.

Re:As I understand it...

[GXTi]

I'm sure you'll encounter a number of hash collisions

Understatement of the year. Note above where I approximated this number as 2 ^ 1073741696---about 0.999999985 GiB of information. That's barely less than you started with, and plenty with which to make all kinds of different, perfectly valid documents, of any type or content desired. Simply take any file and append random data until the digest matches the original. There are dozens of file formats where you can do this and still get a well-formed document. Does the digest match? Yes. Was it your original file? Probably not, and by "probably" I mean "so improbable as to be effectively impossible".

That's not entirely unlike the decentralized tracker system Bit-torrent clients have implement of late.

Magnet links work because there are specific, existing entities out there that have a given digest, and you're just looking for someone who has the file. You're not conjuring the file out of thin air; the digest is just a key you use to ask others for the document. If you wanted to write a system that works by storing encrypted chunks of data spread across a large mesh of nodes, well let's just say that's been done already, but it's not called ECC. In fact, didn't Google come up with some kind of system like that a few months ago? Haven't heard a peep about it since then, and I've forgotten the name already.

Re:As I understand it...

[Just Some Guy]

Ok, lets assume its a 128-bit hash. For a 1GB file how many combinations of 1GB will produce the same hash?

2^((1024^3)-128).

Re:As I understand it...

[sjames]

The exact numbers aren't too hard to decide. 4096 byte blocks with 16 byte (128 bit) hash means that each hash value must cover 4096/16=256 distinct possible contents of the block. Considering there are 2^32768 possible values for a 4096 byte block, random blocks are exceedingly unlikely to collide.

The odds are made better since we don't typically write random values to blocks. Only a subset of the possible values for the block are at all likely to be usefully written.

More significant is the threat of engineering a hash collision to create a corruption. However, that requires not only predicting the contents of a block that has not yet been written, but also finding a block that has the same hash. Then you have to write that block first.

It is possible to overcome even that by allowing a block's name to contain a few extra bits for additional versions (other data with the same hash), but the cost is that every write requires checking for any already existent blocks with the same hash, and comparing the contents to what you're writing. In the extremely unlikely case that they're different, you have to use the version bits.

The question is, "Is it worth it?", doubling the I/O for every write and burning cycles checking for an event that will probably never happen over the life of the filesystem.

The answer is probably not. For any practical backup scheme including multi level raid with multiple archival tape, the odds of data loss through the failure of the media are far greater than that of data corruption through hash collision.

Venti (a filesystem used in plan 9 OS) predates ZFS by a fair bit and uses SHA1 hashes as unique block names. Search for venti hash collision to find many good arguments against even bothering to avoid the potential( in theory anyway) problem. It's arguable that doing something about it is the wrong decision.

Re:As I understand it...

[sjames]

If there was some sort of insane scenario where you had to reconstruct a complete 1GB block from a single MD5 hash... (ie, "here's an MD5 hash. Give me a sequence of 1073741824 bytes to make it") well it's technically possible, though the electric bill for your server farm may piss off more than a few treehuggers.

The person waiting for that file to be re-constructed will also be ticked off that the only way to complete the project is to will it to his great-great-great-great grandson (since it'll take that long to exhaust the possibilities)

MD5 is only now considered weak because it is computationally feasible to come up with two arbitrary globs of data having the same MD5 hash, not because it is feasible given one glob to come up with the collision.

Notably, if you want to do such a computation, the best approach is to NOT start now. By the time you'd be half way done, computers will be fast enough to finish the job from scratch sooner.

Re:As I understand it...

[tzot]

I always wonder why I can't apply this kind of logic to torrents with that one file stuck at 99.98%...

Um. So you have a file that's completely downloaded except for 16kiB, so you'll have to try at the most 2**131072 combinations for brute-force reconstruction. Of course, on average you would get a match after only 2**130911 attempts, which would be wrong.
I'd suggest you don't wait up.

what about quickpar and dvdisaster?

[MoFoQ]

quickpar especially has been in use on usenet/newsgroups for years....o yea...forgot....they are trying to kill it.

anyways...there's also dvdisaster which now has several ways of "hardening".
one of them seems to catch my attention: adds error correction data to a CD/DVD (via a disc image/iso)

Why IS storage quality going down?

[jerryasher]

I'm glad it's not just me thinking my drives are dying sooner than they once did.

Why is storage quality going down, and what does that mean for that 1TB drive for $200 bucks? Will it's lifespan exceed two years?

Re:Why IS storage quality going down?

[rrohbeck]

Because everybody uses desktop quality SATA drives in enterprise RAIDs. And every vendor pushes density in desktop drives as hard as possible even though it's been getting more and more difficult.
The market for high end "enterprise" drives is almost dead. When was the last time you saw a SCSI (FC,SAS) drive?
There's nothing wrong with the basic approach but you have to do the math and use the correct AFR and TTR numbers. We just went from RAID 5 to RAID 6 because the observed drive failure rates were higher (by a factor of 3) than what the vendors promised and the system failure rates were just too high.
For example, in one drive, it turned out that SATA error recovery (timeout control) didn't work as advertised, so the "enterprise ready" SATA drivers weren't all that enterprise-ish. And, OBTW, FW upgrades in the field turned out to be totally unreliable and turned drives into bricks.
FW upgrade was only tested on Intel ICH SATA ports and the RAID controller just didn't have the right timing :(

Re:Why IS storage quality going down?

[lukas84]

The market for high end "enterprise" drives is almost dead. When was the last time you saw a SCSI (FC,SAS) drive?

What? Maybe on your planet. 2.5" SAS Drives in Servers are common - even in middle class servers.

What kind of servers are you buying that are using SATA instead of SAS?

Re:Why IS storage quality going down?

[Hyppy]

The market for high end "enterprise" drives is almost dead. When was the last time you saw a SCSI (FC,SAS) drive?

I can look over my shoulder at approximately 45 FC drives, 60-70 Ultra320 SCSI Drives, and another dozen or two SAS drives. That's just from my little window into the server room.

Enterprise class drives are far from dead. Unless, of course, you just can't afford them.

Wasn't PAR designed for this problem?

[Anonymous Coward]

http://parchive.sourceforge.net/

hardware

[Anonymous Coward]

Who is storage critical files without error correction and a checksummed file system?

Or in other words, ECC + ZFS.

You can't complain about Data Loss, if you're running cheap desktop hardware on NTFS.

I don't want to spend time making Par2 files.

[Futurepower(R)]

Excellent, I agree. But generation of Par2 files should be automatic. I don't mind having only 3.5 gigabytes on a DVD for data if the Par2 files are generated and tested automatically.

Par2 is apparently Reed-Solomon done in a more helpful way.

Quote from the Parity Volume Set Specification 2.0: "PAR 2.0 uses a 16-bit Reed-Solomon code and can support 32768 blocks."

Re:I don't want to spend time making Par2 files.

[Anonymous Coward]

already mentioned, but you should try dvdisaster.
I used it when I left my last workplace, burned a DVD with 1GB of data, 3GB of redundancy :P

uhhm, raid6?

[RelliK]

RAID6 uses Reed-Solomon error correction. In fact, RAID5 can be viewed as a special case of RAID6.

This thing looks like a solution in search of a problem. Slow news day?

This is not the same thing as PAR ...

[DrJimbo]

... even though both TFA and PAR use Reed-Solomon.

The difference is that TFA interleaves the data so it is robust against sector errors. A bad sector contains bytes from many different data blocks so each data block only loses one byte which is easy to recover from. If you use PAR and encounter a bad sector, you're SOL.

PAR was designed to solve a different problem and it solves that different problem very well but it wasn't designed to solve the problem that is addressed by TFA. Use PAR to protect against "the occasional bit error" as you suggest, but use the scheme given in TFA to protect against bad sectors.

Re:This is not the same thing as PAR ...

[Anonymous Coward]

par is perfectly able to correct whole sectors, or even whole files missing, as long as the missing data is less than the amount of parity data. But then, thats true for all algorithms.

Re:This is not the same thing as PAR ...

[Anonymous Coward]

There is also a GPL project out there called Cleversafe which has appeared on slashdot several times which uses Reed-Solomon codes to rebuild each disk block. Each encoded piece is sent to N different servers, of which K are needed to be available to retrieve the data. N and K being user configurable.

Bose Chaudhuri

[ishmalius]

These codes, http://en.wikipedia.org/wiki/BCH_code , are far superior.. However, both Miller code and these pale in comparison to Low Density Parity Check codes. http://en.wikipedia.org/wiki/Low-density_parity-check_code

Re:Bose Chaudhuri

[xquark]

RS codes are a subset of BCH codes, if anything is far superior it would be RS codes as they are more generalized and have better specific decoding techniques and can be both systematic and linear.

Again as mentioned before LDPCs are not useful in these situations they are only useful in overcoming erasures within data communications.

Re:Bose Chaudhuri

[locofungus]

Again as mentioned before LDPCs are not useful in these situations they are only useful in overcoming erasures within data communications.

Why aren't erasure codes any good here? What errors are we trying to recover from?

Don't we have known bad sectors from the disk?

I don't know if, when you get a bad sector the drive returns nothing or whether the drive can be told to return its best guess so I can see it might depend whether your code word is a sector or something smaller.

Tim.

Re:Bose Chaudhuri

[Anonymous Coward]

It is also difficult to build real time LDPC codecs that approach capacity. It is practical to do so only for specialised classes of LDPC codes. While LDPC parity check matrices are sparse, in general the generator matrices are large and not sparse.

Re:Bose Chaudhuri

[Anonymous Coward]

These codes, http://en.wikipedia.org/wiki/BCH_code , are far superior.

Given your penchant for linking to wikipedia, why not mention http://en.wikipedia.org/wiki/Reed_Solomon#Reed-Solomon_codes_as_BCH_codes ?

Reed-Solomon codes are, in fact, a subset of the BCH codes. To call the BCH codes strictly superior is a little bit misleading.

Re:Bose Chaudhuri

[Anonymous Coward]

Yeah...and don't even get me started on Goppa codes.

Is this step really necessary?

[Kjella]

Yes, this has been done forever etc. but has anyone experienced any ugly "bit rot"? I mean, I've had firewalls that would checksum applications and if it ever complained about surprise changes I didn't catch it. Equally I have about 100GB for which I have CSVs - no spontanious corruption to note. Source code should very easily fail to compile if a random bit was flipped, also can't think of any case. I guess if it's that important having a PAR file with some recovery data won't hurt but first you I'd take RAID + backups any day.

PAR2

[rm-ce]

There is already the pretty mature and fairly widely used par2 application that already does this.

It's handy for downloading binaries off usenet, where you might lose a few parts.
(Say, only be able to download 18 of the 20 files)

I've also used it to success when burning files to cdr, that have later become corrupted beyond what the cd error correction could handle.

Much recommended!

http://en.wikipedia.org/wiki/Parchive

Thank you.

[Anonymous Coward]

This site has really great info. I love finding out about all these codes. Thanks

Jay
Cyber Monday

Information Theory 101

[profplump]

Channel noise can be overcome via increased redundancy in transmission/storage, thereby reducing the effective transfer rate/storage density. Film at 11.

I could be wrong, but I'm pretty sure this is why we have on-disk (and on-bus) checksums and ECC RAM. And frankly if your mission-critical data is being ruined by DVD scratches, adding RS codes to your DVDs is probably not going to solve the fundamental problem of system administrator incompetence.

/ Seriously, these days Fark has more technically competent and interesting articles than /.

Datarecovery "data".

[rew]

Working for a datarecovery company, I know that about half the cases where data is lost the whole drive "disappears". So, bad sectors? You can solve that problem with reed solomon! Fine! But that doesn't replace the need for backups to help you recover from: accidental removal, fire, theft and total disk failure (and probably a few other things I can't come up with right now)... .

Re:Datarecovery "data".

[jd]

Reed-Solomon is designed only for randomly-distributed errors. For errors that are in a large, contiguous block (such as a sector) you need Turbo Codes. So, whilst you are correct that the solution isn't that useful for the bulk of real-world conditions (ie: lost drives), it really isn't useful for the condition it is supposed to fix either (lost sectors). As others have noted, most drives already employ Reed-Solomon to fix random bit errors, so employing it a second time would seem to just hog space with error-correcting codes that you don't need and can't effectively use. I'm not convinced employing Turbo Codes would be that useful either, but at least they'd fix errors not already being fixed.

Re:Datarecovery "data".

[Fweeky]

Reed-Solomon is designed only for randomly-distributed errors. For errors that are in a large, contiguous block (such as a sector) you need Turbo Codes

Uh? Par2 doesn't give a damn where your errors are, if you've got 20MB of .par2 files, you can recover 20MB of the data, wherever it is (assuming you've got the rest).

RS works like a dream for mailing barcodes

[Centurix]

Australia Post implemented the Royal Mail's 4 state barcoding system for all bulk and pre-sorted mail categories. The barcode incorporates RS and greatly improves the scan rate of damaged mail. The RM4SCC was adopted throughout the US and Canada.

Re:RS works like a dream for mailing barcodes

[xquark]

pretty much all 2D barcodes use RS codes as well. These include, QRcode, PostBar, MaxiCode, DataMatrix etc...

Re:RS works like a dream for mailing barcodes

[Centurix]

That's interesting, I was aware of PostBar but not the others incorporating RS. Thanks.

I see...

[warrax_666]

That'll teach me to leave out a "not". Of course, I meant "theoretically NOT 100% reliable". :)

The odds of collisions against a given fixed hash (which a hash for a data block is) of course depend on the method, but they are miniscule -- probably less than random bits flips on the bus or in RAM. Has anyone even ever found a single example of a SHA256 collision?

Even so, you can *NEVER* be absolutely 100% sure that the data is what you wrote. Even a two-way RAID1 doesn't get you there since you could (theoretically) have identical errors on both drives. Increasing it to a three-way RAID1 with a majority vote (or even just outright declaring an unrecoverable error when a mismatch is found) gets you closer to 100%, but errors are still theoretically possible.

So the point is: You can never attain 100%, but how close to 100% do you want to get? For me, ZFS hashes are "good enough".

ATTN MODS

[Hobart]

Mod parent, grandparent, and great grandparent way up please - this is the most significant thread in the comments so far.

they're good for different things

[YesIAmAScript]

BCH is good for correcting large numbers of small errors. RS is good for correcting "bursty" errors.

You want to use BCH in media where bits bear no relation to each other, like in NAND where a cell contains only 1 or 2 bits, and adjacent cells are unaffected.

RS is better on things like hard drives where a flaw in the media is likely to produce longer runs of errors in a row. Two sequential bits on a hard drive are interdependent.

Also, the whole article is dumb. First, hard drives don't appear to be getting worse lately. Additionally, every mass storage device you use (hard drives or NAND flash) already uses error correction. Additionally, SATA uses error correction over the bus, and PCIe does too. If your machine has ECC RAM (most don't) and a SATA storage interface, then your data is already covered by ECC all the way from the storage into memory.

So why add more?

Re:they're good for different things

[xquark]

Your comment is incorrect, RS codes are a subset of BCH codes. In fact BCH codes are a general definition of a class of algebraic codes nothing more. your comment about one being better than the other for a specific purpose is wrong.

Think of BCH codes as "vehicle" and RS codes as "The Bugatti Veyron" that is the relationship.

Re:they're good for different things

[YesIAmAScript]

That's great.

In practice, I guess whatever the NAND industry calls "BCH codes" are some subset of the true field of BCH codes. Because in practice, what I said holds true.

If you have a media where bits are interdependent with adjacent bits, use RS. If you have a media where this is not true, use "BCH ECC", whatever that means.

In the case of the hardware I'm talking about, the BCH ECC can correct 8 single bit errors individually in a field, whereas an RS ECC code using the same amount of ECC data could correct 4 symbols, where each symbol is 10 bits long. So it can correct up to 40 bits, but assuming the errors are placed randomly, it is really only half as effective, only being able to replace 4 random errors. This is with similar amounts of ECC data.

Utterly pointless

[Anonymous Coward]

The problem with this method is that drives already store data with this or similar techniques.
When you get a failure you're likely to lose a sector which is far larger than this scheme can save!

Re:Utterly pointless

[Ed Avis]

Read the article: after adding the parity information, the data is interleaved every 512 bytes to withstand losing whole sectors.

user interface proble

[speedtux]

I'm sorry, but this is stupid. Error correction is done at the level of the disk controller. You gain nothing by re-doing it at the level of the file system. You only get file-system level errors when you don't pay attention to the disk controller telling you that the disk is going bad and wait for the disk to degrade to the point where errors can't be corrected anymore.

Install one of the many utilities that monitor disk health and replace your disk when they tell you there's a problem with your disk.

Re:user interface proble

[Creepy Crawler]

If the gear is consumer-level priced, there is LITTLE/NO error correction. Not even the system RAM is error corrected unless you buy ECC.

If you back up anything on DVD's or tapes, or any other consumer media, you need some real error correction. CD's actually have this built in.

Re:user interface proble

[speedtux]

If the gear is consumer-level priced, there is LITTLE/NO error correction.

All modern disks have extensive error correction; they simply wouldn't work without it.

Not even the system RAM is error corrected unless you buy ECC.

RAM is one thing, disks are a completely different thing.

Information Dispersal Algorithms

[aaaaaaargh!]

They are better for dispersing data over storage media than using error correction codes. In essence, an IDA transforms a file into k blocks of data, and any n (nk blocks suffice to reconstruct the file. (It doesn't matter which blocks you choose for reconstruction, as long as you have n different blocks, you're fine.)

Unfortunately there don't seem to be many tools or libraries available, so you have to implement the IDA yourself and this requires a bit of math.

Re:Information Dispersal Algorithms

[aaaaaaargh!]

Damn it all got messed up. The point was: n is smaller than k, and n different blocks out of the k original blocks suffice for reconstruction.

Re:Information Dispersal Algorithms

[Anonymous Coward]

Unfortunately there don't seem to be many tools or libraries available, so you have to implement the IDA yourself and this requires a bit of math.

Actually there's a company called Cleversafe that's building an open source, large scale storage system that's based on IDAs like Reed Solomon. I haven't tested the beta versions, but it definitely sounds promising.

shell commands?

[Anonymous Coward]

so when is this coming as a block device so its not clumsy as hell?

VDM FEC

[Dr. Tom]

Forward error correction using vandermode matrices does this quite nicely. There are N-K codes that allow K blocks to be encoded in N blocks (N>K) so that any K of the N can be used to decode. Thus you can loose N-K blocks. For blocks, read tracks, or sectors, or whatever unit is typically lost in a media failure.

Yes, but not all...

[serviscope_minor]

.. at least CDROMs employ RS codes.

RS codes are good at corecting randomly scattered bit errors. The error mode in CDs is missing chunks (eg scrathces). So, they use a mechanism which scatters bits around. When a scratch (correlated errors) is descattered, they become randoml sacttered errors, so the RS codes can do their job.

coding theory

[arit]

There is an entire field of study related to this topic, but, in short, Reed-Solomon codes are not currently the state of the art. There are much more efficient iterative codes (e.g. Low-Density Parity-Check codes) and there are also rateless codes for a more incremental protection. At any rate, the right place to use these is probably at the hardware level ... even if efficiency is not an issue, they tend to require a fair amount of redundancy.

oh boy...

[toby]

1. Error reporting paths are not reliable (in fact it's notoriously terrible). Drive failure prediction is not reliable.

2. The data path is not reliable. That includes media, drive controller, firmware, buffers, cabling, controller, host RAM, and other host subsystems. Cosmic rays. Whatever might flip a bit anywhere in your system.

3. Given the foregoing, ZFS detects ALL errors between media and application, and (if redundancy is available) corrects them.

Traditional RAID doesn't even know which side of a mirror is the good side, if they don't match. Some RAID systems do checksumming but this doesn't protect you against errors in the rest of the datapath. And isolated storage subsystems like NetApp, no matter how sophisticated, also do not protect the whole longer more vulnerable datapath.

ZFS is unique in doing that, by design. Join the mailing list or study the material at opensolaris.org. It may change the way you think about storage.

Re:oh boy...

[speedtux]

1. Error reporting paths are not reliable (in fact it's notoriously terrible).

Sounds like you're using the wrong OS or bad hardware, or you're simply doing something wrong.

Drive failure prediction is not reliable.

There ain't nothing to "predict": as soon as the first correctable error shows up in syslog, you should consider the disk dead.

2. The data path is not reliable. That includes media, drive controller, firmware, buffers, cabling, controller, host RAM, and other host subsystems. Cosmic rays. Whatever might flip a bit anywhere in your system.

Yes, and for each of those devices, there is an appropriate level of error detection and correction for that kind of device, which is implemented at the level of the controllers and protocols for that device.

ZFS is unique in doing that, by design.

ZFS is an idiotic design.

I Shouldn't Have to Worry About That

[Greyfox]

No filesystem that's not a complete toy should allow files to become corrupted anyway. If your filesystem IS a complete toy (You know who you are) perhaps you should consider a filesystem that doesn't allow your files to become corrupted. If your OS is a complete toy (Again, you know who you are) and doesn't support a filesystem that's not a complete toy, then perhaps you should consider a different operating system.

Re:I Shouldn't Have to Worry About That

[liquiddark]

I would suggest that if we're dumb enough to use an OS that is "a complete toy", the probability that we don't know who we are is actually quite high.

1970 called

[ameboy]

they want their novel ideas back

ZFS uses this

[ChrisA90278]

Sun's new file system ZFS uses end to end checksums. Nowthat we have multi-core computers and maybe more processing than we need it makes sense to do this. Sun's software is free and open source. Apple is just starting to use it in Mac OS X now.

Stop reoprting on textbook knowledge!

[drolli]

I deeply recommend: "Introduction to Finite Fields and their Applications" Rudolf Lidl, Harald Niederreiter

It's actually end-to-end checking that matters

[Anonymous Coward]

A reed-solomon code isn't really a good way to do this at the highest-level, nor is it very useful for correcting errors at the highest level. Associating an ECC code with a regular file is an exercise in futility. ECC codes have a very small collision space for the bits they use, making them only suitable for error spaces which are well characterized. In other words, ECC works great when matched to a particular media, at the lowest level (e.g. hard drive or flash firmware, or radio, etc), and is horrible when used anywhere else.

Non-ECC codes are best used to detect high-level errors. These have much larger collision spaces. You are much better off doing, say, a (tar|md5) check on a snapshot as a means of high-level validation that the information has not changed. Ultimately what you would really like to do is have the OS track a check code at the highest level (the VNOPS) and then store it independant of the filesystem.

ZFS does a good job detecting errors below the ZFS filesystem layer itself, but can't detect errors made at or above the filesystem layer... for example, due to bugs in the OS itself. Remember it isn't just the filesystem which must be bug-free, the OS has to be too. So ZFS is really good and detecting media errors but no matter how good it is you still couldn't trust your data to a single logical ZFS mount. You still need off-site backups and replication and if you use ZFS you wind up with a severe double-multiplication of storage requirements. As much as I like ZFS (and really like its ability to detect lost writes), it winds up being a very, very heavy-weight solution.

-Matt

Re:Typical linux nutcase: HardD's ALREADY do THIS

[sjames]

All disks already do this, you dumb fuck. Another linux nutcase copying something that's already been done - FOR DECADES !! You are one stupid mofo, and the stupid ass losers who think "oooooo, great idea!" are only a little less of one.

I guess in your world, vendors never cheap out, cables are always perfect and files never go over the net. If only there weren't so many obnoxious cowards there...