Re: single disk reed solomon codes
An experiment of applying RS codes for protecting data, worth a look http://ttsiodras.googlepages.com/rsbep.html He overwrites a series of 127 sectors and still manages to correctly recover his data. We all know disks give us unreadable sectors every now and then, so at least on workstations/laptops this could really be useful ? Advantage over single-disk-raid1 is storage efficiency (4.2MB becomes 5.2MB), that means we get 80% of useable disk space, instead of 50% if I decide to raid1 everything ? On Mon, Jul 21, 2008 at 6:03 PM, Dongjun Shin [EMAIL PROTECTED] wrote: On Mon, Jul 21, 2008 at 4:40 PM, Ahmed Kamal [EMAIL PROTECTED] wrote: I definitely hope btrfs has this per-object copies property too. However, simply replicating the whole contents of a directory, wastes too much disk space, as opposed to RS codes Although adding redundancy mechanism will help increasing the integrity of data, I'm not sure whether repeating the same kind of mechanism twice will help. (AFAIK, RS is common in HDD and BCH is common in flash due to their own physical characteristics) I think it is better to have another redundancy mechanism (like RAID1) which is independent of the algorithm used by the underlying storage. -- Dongjun -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
Dnia 2008-07-19, sob o godzinie 17:18 +0200, Gerald Nowitzky pisze: In the end, you would add very little security by the price of -at least- cutting half your write performance. Thus, I don't think there is any point in adding redundancy to single disk systems. ZFS can store multiple copies of data block within one disk. Using your words, it's like Intra-Disk-RAID1. After reading data, when checksum shows it's corrupted, another copy (hopefully correct) is read from other disk location. This is adding security by the price of half storage capacity. Which seems like a fair game, given todays 1,5TB HDDs. -- Tomasz Torcz -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
ECC codes like Reed-Solomon are very useful to recognize and locate random bit-errors. On a HDD as a unit, as it is seen from OS level, I don't think it will be of any help: When a HDD drive reads a sector from disk, it does a whole bunch of error recognition and correction measures. Usually there are, at least, two layers of error correction with different bit spreads on it. *If* this still isn't enough, it is very likely that the whole sector will come back completely spoiled, or, much more likely, won't come back at all and the drive will report a read error. So, the only thing that could be done is to add some redundancy on sector-level with something like a Intra-Disk-RAID5 by adding a number of parity sectors. A simple parity will be enough, as error recognition and location can be done by sector checksums. However, there will be a *huge* performance penalty, as every sector write will cause an additional seek and write for the parity sector. In the end, you would add very little security by the price of -at least- cutting half your write performance. Thus, I don't think there is any point in adding redundancy to single disk systems. Just my 2 cents... (Gerald) Hi, Since btrfs is someday going to be the default FS for Linux, and will be on so many single disk PCs and laptops, I was thinking it should be a good idea to insert some redundancy in single disk deployments. Of course it can help with disk failures, since it's obviously a single disk, but it can help with bit-rot, and with hardware sector read errors. To get that we'd need to implement some kind of forward error correction, possibly reed solomon code. I am not sure why no filesystem seems to implement such scheme, although I believe at the hardware level, such schemes are being used (so the idea is applicable) ? Not that I am an expert on such matters, but I thought I'd drop that suggestion here, maybe at least I'll know why no one else seems to do that -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
On Sat, 2008-07-19 at 15:21 +0300, Ahmed Kamal wrote: Hi, Since btrfs is someday going to be the default FS for Linux, and will be on so many single disk PCs and laptops, I was thinking it should be a good idea to insert some redundancy in single disk deployments. Of course it can help with disk failures, since it's obviously a single disk, but it can help with bit-rot, and with hardware sector read errors. To get that we'd need to implement some kind of forward error correction, possibly reed solomon code. I am not sure why no filesystem seems to implement such scheme, although I believe at the hardware level, such schemes are being used (so the idea is applicable) ? We have implementations of such schemes in lib/reed_solomon/ in the kernel already. I'm quite interested in using btrfs on flash (I mean _real_ flash not SSDs where they have their own internal pseudo-fs pretending to be a disk). For that, we'd probably want to use precisely this kind of error correction. Although it's normal to do it at the block level rather than the filesystem object level; I don't know if the failure modes on real disks are likely to be helped by this kind of scheme or not. After all, the disks already do a similar RS-based error correction for themselves. If we're unlucky in our choice of error correction, it might even be possible to end up in a situation where the only errors we'd _see_ are the ones which were uncorrectable. -- dwmw2 -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
RS-based error correction for themselves. If we're unlucky in our choice of error correction, it might even be possible to end up in a situation where the only errors we'd _see_ are the ones which were uncorrectable. but since at the FS level, the redundancy would be at a different place, than the hardware level redundancy, it might be correctable to you -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
Gerald Nowitzky wrote: When a HDD drive reads a sector from disk, it does a whole bunch of error recognition and correction measures. Usually there are, at least, two layers of error correction with different bit spreads on it. *If* this still isn't enough, it is very likely that the whole sector will come back completely spoiled, or, much more likely, won't come back at all and the drive will report a read error. With larger and larger disks, it is increasingly likely we will see undetected/uncorrected errors (the drive bit error rates are not improving - 1 in 10^17 is typical). It is clear we cannot rely completely on the hardware to catch everything. Also, errors that happen in the hardware between the drive and the CPU can be caused by bad cables, interfaces, etc. For even single disk systems (even without mirroring), it is still valid to have some means of verifying integrity. It is far better to know an error occurred and which files are affected than to have it happen silently. If caught, undetected errors will be less likely to migrate onto backups over time and slowly corrupt data there too, making eventual recovery impossible. That's why btrfs's checksums are so cool! See my blog for my personal experiences with silent hard disk errors: http://planet.gentoo.org/developers/lavajoe/ -Joe -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: single disk reed solomon codes
On Sat, Jul 19, 2008 at 04:15:43PM -0600, Joe Peterson wrote: Gerald Nowitzky wrote: When a HDD drive reads a sector from disk, it does a whole bunch of error recognition and correction measures. Usually there are, at least, two layers of error correction with different bit spreads on it. *If* this still isn't enough, it is very likely that the whole sector will come back completely spoiled, or, much more likely, won't come back at all and the drive will report a read error. With larger and larger disks, it is increasingly likely we will see undetected/uncorrected errors (the drive bit error rates are not improving - 1 in 10^17 is typical). It is clear we cannot rely completely on the hardware to catch everything. Also, errors that happen in the hardware between the drive and the CPU can be caused by bad cables, interfaces, etc. For even single disk systems (even without mirroring), it is still valid to have some means of verifying integrity. It is far better to know an error occurred and which files are affected than to have it happen silently. If caught, undetected errors will be less likely to migrate onto backups over time and slowly corrupt data there too, making eventual recovery impossible. That's why btrfs's checksums are so cool! See my blog for my personal experiences with silent hard disk errors: http://planet.gentoo.org/developers/lavajoe/ I've seen an interesting discussion elsewhere about this very issue, in the context of retrofitting some sort of checksumming support to FFS. The suggestion was to make 128th block a checksum block for the previous 127 blocks (scale to your liking). Without changing the filesystem format _at_all_ you could still checksum so long as you read in 128 blocks at a time. This isn't a major problem, since you'll probably want that sort of readahead anyway. Of course - that's just error detection, not error correction. Bron. -- To unsubscribe from this list: send the line unsubscribe linux-btrfs in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html