5 ms·

What’s surprising to me is that no file system (even ZFS) or database utilize error correction controls. Well aside from 1 bit/byte ECC style codes or raid. The

What’s surprising to me is that no file system (even ZFS) or database utilize error correction controls. Well aside from 1 bit/byte ECC style codes or raid. There are a few forms of forward error correction [1], which are already widely used in hardware [2]. There are some projects trying for long term fixity of storage [3], but nothing default or built in, afaict. I assumed RocksDB or some other modern KV engine would include FEC, at least the meta-data. Using DB’s on embedded devices reveals how easily (and regularly) a whole DB of data can be corrupted. A few bytes of error and an entire IoT DB can be lost. FEC’s can be cpu expensive but not that expensive nowadays. 1: https://en.wikipedia.org/wiki/Forward_error_correction https://en.wikipedia.org/wiki/Forward_error_correction 2: https://www.electronicdesign.com/technologies/communications/article/21789969/use-forward-error-correction-to-improve-data-communications https://www.electronicdesign.com/technologies/communications... 3: https://github.com/lrq3000/pyFileFixity https://github.com/lrq3000/pyFileFixity

zozbot234 7y ago
You can just use dm-raid for that if you like. Just because it's named "raid" doesn't mean you have to use it across disks.
- elcritch 7y ago
  True, and I’ve considered doing that, but it means you’re doing 2/1 or at best 3/2 storage storage rates. Raid only uses XOR, but Reed-Solomon or other FEC codes can produce way better error correction rates. Say full recovery for standard storage error rates using only 1/10 the extra space along with more computation at recovery time. Add CPU hardware support like AES and then even battery devices could use it.
  - elcritch 7y ago
    Article on fec’s and storage, seems Ceph utilizes FEC: https://www.networkcomputing.com/data-centers/putting-erasure-codes-work https://www.networkcomputing.com/data-centers/putting-erasur...
  - zozbot234 7y ago
    The device mapper framework is open source. You could just extend it with additional ECC modes if those would be useful to you, and then these would become usable in both RAID and unRAID setups.
  - p_l 7y ago
    RAID uses more than XOR once you get past RAID5, usually. The lesser known bit about ZFS RAIDZ for example is that each level introduces new error correction code. RAIDZ1 uses plain XOR. RAIDZ1 has one disk with XOR one disk with Reed-Solomon. RAIDZ3 adds third disk which has Reed-Solomon but implemented differently. The effect is that you have 3 different codes available.
chungy 7y ago
> What’s surprising to me is that no file system (even ZFS) or database utilize error correction controls. Maybe I misunderstand your statement, but ZFS has had error correction from the very first versions.
- elcritch 7y ago
  AFAICT, it only has checksums for data, and multiple metadata copies: https://serverfault.com/a/381918 https://serverfault.com/a/381918 So you’d need raid for error correction.
  - garmaine 7y ago
    raidz{1,2,3} are error correction modes built into ZFS.
  - jakeogh 7y ago
    I suppose you could patch in PAR encoding for data, would that be significantly different than specifying copies=N for data and/or making multiple pools single disk and raiding them?
    - ghusbands 7y ago
      PAR encoding is much more space-efficient than storing multiple copies, though using it efficiently would be really tricky. Though not more tricky than most other filesystem development. If you can indeed RAID-z multiple pools across a single disk, that would give many of the same advantages, without having to duplicate everything. Obviously, it would also greatly affect performance, with every IO operation becoming N operations against one disk.
      - jakeogh 7y ago
        Why would PAR be tricky to use efficiently? I just see it as a file encoding.
        7y ago
namibj 7y ago
Many SAS disks offer larger sector sizes, which in turn allow storing such ECC/checksum data right there. But, what e.g. Btrfs does is to just checksum and raid, because silent corruption is _really_ rare, and you'd want some amount of raid anyways. Keep in mind that the disk already implements FEC on a low level.
- elcritch 7y ago
  Yes, btrfs works better on embedded wrt to corruption than ext4. ZFS is too hard to setup. But on embedded devices silent corruption isn’t so rare. After 2-3 months of usage on an SD card it’s almost guaranteed in my experience from last year. USB thumb drives & eMMC fair much better, but I’ve still lost entire DB’s. Given all of that, when corruption does happen you can frustratingly (rocksdb at least) loose an entire dB due to a single checksum error. It’s good rocksdb has checksums but an FEC code could both checksum, and be used to correct the data. Unfortunately off-device backups aren’t an option.
  - zaarn 7y ago
    Might be an idea to offload that. You could reduce the risk of corruption by splitting the database over timeframes, so every 3 weeks, you create a new database, copy all currently relevant data and close out the old one. In case of corruption you can recover from an older version of the database, which is less likely to be corrupted the more versions you keep and the more often you do this (at the expense of flash lifetime).
  - namibj 7y ago
    If you have the space for storing data twice, you can actually use `dup` for the data, not just the metadata. That conversion can be done online, though I managed to make it zero out all superblocks on all 3 disks while converting from raid1 to raid5. That's some time back, however, and there was some unfortunate power cycling.
variaga 7y ago
I would expect that filesystems do not integrate conventional FEC (e.g. block codes), because FEC is poorly suited to the kind of errors that affect filesystems. FEC works against errors that have a predictable expected error rate, where errors are evenly distributed among the data. This applies to block codes (where FEC will have a maximum decodable error rate per block) and convolutional codes which don't have 'blocks', but still have a maximum local error density they can reliably correct. For media where burst errors are a possibility, FEC is almost always paired with interleaving to increase the likelihood hor a ~uniform distribution of errors. FEC works pretty well when the problem is "I wrote some data to disk that I can't read back correctly, but I can read the other data back just fine". At the media level, hard drives have used FEC to protect individual bits/sectors for a long time. Likewise at the disk level, RAID 4/5/6 do use FEC to protect against individual disk failures. Errors experienced at a filesystem level are not usually due to 'random' corruption of the data, but to invalid operations on the data structure e.g. a crash while flushing the data to disk which leaves the filesystem in an inconsistent state. In other words, the filesystem-specific errors are more likely to be "I wrote the wrong data to disk" or "I only wrote some of the data I meant to". FEC will not defend against that well, because any FEC must be written to the disk along with the data to prevent the FEC+data from getting into an inconsistent state. For example, the 'RAID 5 write hole' (which also happens with RAID 1 and RAID 6) exists because physical disks will not commit data to the disk at exactly the same time even when the write commands are issued at the same time (which mostly won't happen anyway, since write commands tend to be serialized on your SCSI/Fiberchannel/whatever interface to multiple drives). That means there exists a time where the data has been updated but the parity has not (or vice versa), and if a drive fails at that time, the RAID array may not be cleanly recoverable. So for practical reasons, if you write the wrong data to disk, you'll probably write the wrong FEC too, and FEC won't help recover much. If your allocation table gets corrupted and you write part of one file on top of another, you'll be overwriting the FEC too. For conventional FEC. BUT... error correction isn't just "conventional FEC". Error correction in general is any time you add redundancy to data to make it more tolerant to errors. In the filesystem space, this happens, but it isn't usually done with parity matricies or convolutional state machines. Instead, redundancy is added by things like log-structured file systems. The 'write what you plan to do, then write the actual data, then write that you successfully did it (in that order)' behavior of log structured file systems does add redundancy and does make error recovery more possible. In summary, "error correction" in general is used at several levels for file storage: - block FEC at the bit level - block FEC at the drive level if RAID is used - robust CRC error detect + automatic repeat request over your PCIe/NVMe link or over a network connection - Redundant metadata in your filesystem journal but the key is to use the right kind of error correction for the expected error conditions.

zozbot234 7y ago

You can just use dm-raid for that if you like. Just because it's named "raid" doesn't mean you have to use it across disks.

elcritch 7y ago
True, and I’ve considered doing that, but it means you’re doing 2/1 or at best 3/2 storage storage rates. Raid only uses XOR, but Reed-Solomon or other FEC codes can produce way better error correction rates. Say full recovery for standard storage error rates using only 1/10 the extra space along with more computation at recovery time. Add CPU hardware support like AES and then even battery devices could use it.
- elcritch 7y ago
  Article on fec’s and storage, seems Ceph utilizes FEC: https://www.networkcomputing.com/data-centers/putting-erasure-codes-work https://www.networkcomputing.com/data-centers/putting-erasur...
- zozbot234 7y ago
  The device mapper framework is open source. You could just extend it with additional ECC modes if those would be useful to you, and then these would become usable in both RAID and unRAID setups.
- p_l 7y ago
  RAID uses more than XOR once you get past RAID5, usually. The lesser known bit about ZFS RAIDZ for example is that each level introduces new error correction code. RAIDZ1 uses plain XOR. RAIDZ1 has one disk with XOR one disk with Reed-Solomon. RAIDZ3 adds third disk which has Reed-Solomon but implemented differently. The effect is that you have 3 different codes available.

chungy 7y ago

> What’s surprising to me is that no file system (even ZFS) or database utilize error correction controls. Maybe I misunderstand your statement, but ZFS has had error correction from the very first versions.

elcritch 7y ago
AFAICT, it only has checksums for data, and multiple metadata copies: https://serverfault.com/a/381918 https://serverfault.com/a/381918 So you’d need raid for error correction.
- garmaine 7y ago
  raidz{1,2,3} are error correction modes built into ZFS.
- jakeogh 7y ago
  I suppose you could patch in PAR encoding for data, would that be significantly different than specifying copies=N for data and/or making multiple pools single disk and raiding them?
  - ghusbands 7y ago
    PAR encoding is much more space-efficient than storing multiple copies, though using it efficiently would be really tricky. Though not more tricky than most other filesystem development. If you can indeed RAID-z multiple pools across a single disk, that would give many of the same advantages, without having to duplicate everything. Obviously, it would also greatly affect performance, with every IO operation becoming N operations against one disk.
    - jakeogh 7y ago
      Why would PAR be tricky to use efficiently? I just see it as a file encoding.
      - 7y ago

namibj 7y ago

Many SAS disks offer larger sector sizes, which in turn allow storing such ECC/checksum data right there. But, what e.g. Btrfs does is to just checksum and raid, because silent corruption is _really_ rare, and you'd want some amount of raid anyways. Keep in mind that the disk already implements FEC on a low level.

elcritch 7y ago
Yes, btrfs works better on embedded wrt to corruption than ext4. ZFS is too hard to setup. But on embedded devices silent corruption isn’t so rare. After 2-3 months of usage on an SD card it’s almost guaranteed in my experience from last year. USB thumb drives & eMMC fair much better, but I’ve still lost entire DB’s. Given all of that, when corruption does happen you can frustratingly (rocksdb at least) loose an entire dB due to a single checksum error. It’s good rocksdb has checksums but an FEC code could both checksum, and be used to correct the data. Unfortunately off-device backups aren’t an option.
- zaarn 7y ago
  Might be an idea to offload that. You could reduce the risk of corruption by splitting the database over timeframes, so every 3 weeks, you create a new database, copy all currently relevant data and close out the old one. In case of corruption you can recover from an older version of the database, which is less likely to be corrupted the more versions you keep and the more often you do this (at the expense of flash lifetime).
- namibj 7y ago
  If you have the space for storing data twice, you can actually use `dup` for the data, not just the metadata. That conversion can be done online, though I managed to make it zero out all superblocks on all 3 disks while converting from raid1 to raid5. That's some time back, however, and there was some unfortunate power cycling.

variaga 7y ago

I would expect that filesystems do not integrate conventional FEC (e.g. block codes), because FEC is poorly suited to the kind of errors that affect filesystems. FEC works against errors that have a predictable expected error rate, where errors are evenly distributed among the data. This applies to block codes (where FEC will have a maximum decodable error rate per block) and convolutional codes which don't have 'blocks', but still have a maximum local error density they can reliably correct. For media where burst errors are a possibility, FEC is almost always paired with interleaving to increase the likelihood hor a ~uniform distribution of errors. FEC works pretty well when the problem is "I wrote some data to disk that I can't read back correctly, but I can read the other data back just fine". At the media level, hard drives have used FEC to protect individual bits/sectors for a long time. Likewise at the disk level, RAID 4/5/6 do use FEC to protect against individual disk failures. Errors experienced at a filesystem level are not usually due to 'random' corruption of the data, but to invalid operations on the data structure e.g. a crash while flushing the data to disk which leaves the filesystem in an inconsistent state. In other words, the filesystem-specific errors are more likely to be "I wrote the wrong data to disk" or "I only wrote some of the data I meant to". FEC will not defend against that well, because any FEC must be written to the disk along with the data to prevent the FEC+data from getting into an inconsistent state. For example, the 'RAID 5 write hole' (which also happens with RAID 1 and RAID 6) exists because physical disks will not commit data to the disk at exactly the same time even when the write commands are issued at the same time (which mostly won't happen anyway, since write commands tend to be serialized on your SCSI/Fiberchannel/whatever interface to multiple drives). That means there exists a time where the data has been updated but the parity has not (or vice versa), and if a drive fails at that time, the RAID array may not be cleanly recoverable. So for practical reasons, if you write the wrong data to disk, you'll probably write the wrong FEC too, and FEC won't help recover much. If your allocation table gets corrupted and you write part of one file on top of another, you'll be overwriting the FEC too. For conventional FEC. BUT... error correction isn't just "conventional FEC". Error correction in general is any time you add redundancy to data to make it more tolerant to errors. In the filesystem space, this happens, but it isn't usually done with parity matricies or convolutional state machines. Instead, redundancy is added by things like log-structured file systems. The 'write what you plan to do, then write the actual data, then write that you successfully did it (in that order)' behavior of log structured file systems does add redundancy and does make error recovery more possible. In summary, "error correction" in general is used at several levels for file storage: - block FEC at the bit level - block FEC at the drive level if RAID is used - robust CRC error detect + automatic repeat request over your PCIe/NVMe link or over a network connection - Redundant metadata in your filesystem journal but the key is to use the right kind of error correction for the expected error conditions.