4 ms·

A Gentle Introduction to Erasure Codes (2017)

57 points by akalin 8y ago

omazurov 8y ago
> Cauchy matrices are more foolproof, which is why I started with them. I always wanted to know but was afraid to ask. I see why people choose Cauchy for encoding: it's simple and fast (more foolproof? - that I don't see). However, Cauchy erasure decoding would always involve matrix inversion, which is not as simple and fast (Hadoop 3.0 is a good example). But what do people do when they want to do error correction after Cauchy encoding?
- akalin 8y ago
  My “foolproof” comment was based on Vandermonde matrices not always being invertible during decoding without an extra step, which tripped up multiple implementations. (PAR1 suffered from this problem, then they tried to fix it with PAR2 but still failed!) I think we discussed a while ago doing Vandermonde decoding without matrix inversion, so that’s one advantage that Vandermonde matrices have. (Although I haven’t seen an implementation do that optimization.) I don’t actually know if Cauchy matrices apply for error correction and not just erasure codes —- I’d be interested if other people know!
  - omazurov 8y ago
    According to Wikipedia, PAR1 suffered from: > The recovery algorithm had a bug, due to a flaw[1] in the academic paper[2] on which it was based. I remember that the same bug was cited by ZFS[3]. Amazing. Of all algorithm descriptions, one with a bug seems to have been picked up the most. Of course, there is nothing wrong with Vandermonde encoding itself, just don't use that paper any more. Cauchy is equivalent to Vandermonde, so it should allow for error correction to the same extent but I couldn't find any algorithm description/implementation. [1] Plank, James S.; Ding, Ying (April 2003). "Note: Correction to the 1997 Tutorial on Reed-Solomon Coding" [2] Plank, James S. (September 1997). "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems" [3] https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/fs/zfs/vdev_raidz.c https://github.com/illumos/illumos-gate/blob/master/usr/src/...
    - omazurov 8y ago
      It turns out there is a simple, though not trivial, conversion from Cauchy to Vandermonde, so all error correction techniques apply.
      - akalin 8y ago
        Cool, what does the conversion look like? Do you have a reference?
deleted 8y ago
[deleted]

57 points by akalin 8y ago

> Cauchy matrices are more foolproof, which is why I started with them. I always wanted to know but was afraid to ask. I see why people choose Cauchy for encoding: it's simple and fast (more foolproof? - that I don't see). However, Cauchy erasure decoding would always involve matrix inversion, which is not as simple and fast (Hadoop 3.0 is a good example). But what do people do when they want to do error correction after Cauchy encoding?

akalin 8y ago
My “foolproof” comment was based on Vandermonde matrices not always being invertible during decoding without an extra step, which tripped up multiple implementations. (PAR1 suffered from this problem, then they tried to fix it with PAR2 but still failed!) I think we discussed a while ago doing Vandermonde decoding without matrix inversion, so that’s one advantage that Vandermonde matrices have. (Although I haven’t seen an implementation do that optimization.) I don’t actually know if Cauchy matrices apply for error correction and not just erasure codes —- I’d be interested if other people know!
- omazurov 8y ago
  According to Wikipedia, PAR1 suffered from: > The recovery algorithm had a bug, due to a flaw[1] in the academic paper[2] on which it was based. I remember that the same bug was cited by ZFS[3]. Amazing. Of all algorithm descriptions, one with a bug seems to have been picked up the most. Of course, there is nothing wrong with Vandermonde encoding itself, just don't use that paper any more. Cauchy is equivalent to Vandermonde, so it should allow for error correction to the same extent but I couldn't find any algorithm description/implementation. [1] Plank, James S.; Ding, Ying (April 2003). "Note: Correction to the 1997 Tutorial on Reed-Solomon Coding" [2] Plank, James S. (September 1997). "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems" [3] https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/fs/zfs/vdev_raidz.c https://github.com/illumos/illumos-gate/blob/master/usr/src/...
  - omazurov 8y ago
    It turns out there is a simple, though not trivial, conversion from Cauchy to Vandermonde, so all error correction techniques apply.
    - akalin 8y ago
      Cool, what does the conversion look like? Do you have a reference?

deleted 8y ago

[deleted]