4 ms·

We've been using klauspost's Golang reedsolomon package in our distributed storage package. It runs approximately as fast (~1GB) because the hot paths are writt

We've been using klauspost's Golang reedsolomon package in our distributed storage package. It runs approximately as fast (~1GB) because the hot paths are written in asm: https://github.com/klauspost/reedsolomon https://github.com/klauspost/reedsolomon Erasure codes are pretty magical.

zokier 9y ago
I'm not sure if they are quite in the same class. Or maybe I'm misunderstanding, but the Go implementation says "Note that the maximum number of data shards is 256" while FastECC says "Current implementation is limited to 2^20 blocks, removing this limit is the main priority [...]". Or are shards and blocks different things here?
- acrefoot 9y ago
  They are pretty different. Blocks are like blocks in a filesystem or on a disk, while shards are like RAID stripes/mirrors. 2^20 blocks would make for a pretty small datastore, depending on what your needs are, and seems a more serious limitation than the 256 shards. Not an exact description, but a hopefully workable analogy.
  - acrefoot 9y ago
    Actually, it's not clear to me if FastECC is saying that it works on 1M blocks together as a unit, in which case they would be the same as the shards. If that's the case, it does make this a totally different class of thing--what are the use cases?
    - sliken 9y ago
      I think it's mostly simplicity. Say your ECC code is only fast with say 17 shards/blocks of data and 3 shards/blocks of parity. I hear numbers like that used for hadoop, backblaze, microsoft and facebook object storage, etc. So sure you can split large files into groups of 20 pieces (17 data + 3 parity). But the real world often has low error rates, but the errors that do happen can happen in bursts. Say adjacent nodes dying, power strips/circuits blowing, complete loss of network connectivity for 30 seconds, etc. BTW, yes I'm aware you can tell hadoop to keep 2 copies in rack and 1 copy outside the rack, that's basically crude interleaving. If your code can handle a larger number of blocks/shards you can average your parity over a larger number shards/blocks so you can plan for the average error rate, but still handle substantial bursts of error. So maybe instead of 17+3 (17% overhead, survives 3 lost) you switch to 2048+192 (9.4% parity). That way you can survive a 9.4% error rate, even if that's 4 errors in a row. Granted updates become much more expensive, but for some cases it would be well justified by being more durable.
      - Bulat-Ziganshin 9y ago
        if they will need that, they will find a method long ago. but they try to minimize amount of data read/written for every transaction. look up for example "pyramid codes" - it's a way to use 20 disks in raid system but read/write only 5-6 for any operation. and MS use that in azure afaik with 2000 data blocks you will need to read back all those datya blocks to generate new parity when any of these data blocks was changed. and this decreases overall perfromance 2000 times. so you should see why they need those pyrammid codes rather than something on opposite side
  - Bulat-Ziganshin 9y ago
    Well, it's MY code so i use term "block" in the same meaning as they use term "shard" :)
- Bulat-Ziganshin 9y ago
  by block i mean the same thing as they mean by shard. it just doesn't make sense to count entire amount of data processed - only amount of data processed TOGETHER make a sense and yeah, it's quite hard to believe that some new approach may work 1000 times faster than existing ones. that said, i'm not alone - there are a few academic paper/code which is only ~10x slower than my code. i just developed better math scheme and made accurate low-level implementation
Bulat-Ziganshin 9y ago
Speed of RS coder depends on the amount of data/parity blocks. From the URL you mentioned, speed with 50+20 blocks is 713 MB/s. This algorithms is O(N^2) that means the speed is proportional to 1/N. So if it will support 500000+200000 blocks, the speed in this configuration will be 70 KB/s My algorithm is the only open-source one that has O(N*Log(N)) speed so it runs 500000+200000 blocks at 1.2 GB/s. Overall, FastECC should be faster than existing libraries starting from ~32 parity blocks It's like bublle sort vs quick sort - for small datasets they may be comparable, for larger ones they are just different worlds. It's all FFT magic, after all. I have added descriptions of method used, but will try to make a longer version since the math behind is is really wonderful
- nemo1618 9y ago
  Thanks for clarifying. What is the use case for 500000+200000 blocks/shards though? I can't imagine a real-world scenario that requires more than ~100 parity blocks. Even still, it would be a big deal if FastECC is 10x+ faster at something like 20+60 blocks.
  - Bulat-Ziganshin 9y ago
    Well, i don't know :) When you want to protect files on disk, f.e. 30 GB video, you may want to use as much RAM as possible to increase protection level. So if you have 8 GB RAM, and use 4 KB data blocks, you can fit one million blocks into RAM easily. That's one possible usecase, and dream of some data protection geeks But aside of that, it's exactly what i'm looking for - possible usecases. Today i've checked speed with small n/k and found that fastecc should be faster than MultiPar starting from 16-32 parity blocks. So sorry, with 20+60 blocks speed will be pretty the same, and i hope that Intel's isa-l is even faster than MultiPar. Moreover, fastecc doesn't work in GF(2^n) fields, it requires GF(p) or GF(p^2) instead, which means extra problems what you don't want to solve for a small speed increase So, overall, fastecc territory starts where GF(256) territory ends. Also, there is no soft decoder, so it's not interesting for any hardware (ssd, lte and so on)

zokier 9y ago

I'm not sure if they are quite in the same class. Or maybe I'm misunderstanding, but the Go implementation says "Note that the maximum number of data shards is 256" while FastECC says "Current implementation is limited to 2^20 blocks, removing this limit is the main priority [...]". Or are shards and blocks different things here?

acrefoot 9y ago
They are pretty different. Blocks are like blocks in a filesystem or on a disk, while shards are like RAID stripes/mirrors. 2^20 blocks would make for a pretty small datastore, depending on what your needs are, and seems a more serious limitation than the 256 shards. Not an exact description, but a hopefully workable analogy.
- acrefoot 9y ago
  Actually, it's not clear to me if FastECC is saying that it works on 1M blocks together as a unit, in which case they would be the same as the shards. If that's the case, it does make this a totally different class of thing--what are the use cases?
  - sliken 9y ago
    I think it's mostly simplicity. Say your ECC code is only fast with say 17 shards/blocks of data and 3 shards/blocks of parity. I hear numbers like that used for hadoop, backblaze, microsoft and facebook object storage, etc. So sure you can split large files into groups of 20 pieces (17 data + 3 parity). But the real world often has low error rates, but the errors that do happen can happen in bursts. Say adjacent nodes dying, power strips/circuits blowing, complete loss of network connectivity for 30 seconds, etc. BTW, yes I'm aware you can tell hadoop to keep 2 copies in rack and 1 copy outside the rack, that's basically crude interleaving. If your code can handle a larger number of blocks/shards you can average your parity over a larger number shards/blocks so you can plan for the average error rate, but still handle substantial bursts of error. So maybe instead of 17+3 (17% overhead, survives 3 lost) you switch to 2048+192 (9.4% parity). That way you can survive a 9.4% error rate, even if that's 4 errors in a row. Granted updates become much more expensive, but for some cases it would be well justified by being more durable.
    - Bulat-Ziganshin 9y ago
      if they will need that, they will find a method long ago. but they try to minimize amount of data read/written for every transaction. look up for example "pyramid codes" - it's a way to use 20 disks in raid system but read/write only 5-6 for any operation. and MS use that in azure afaik with 2000 data blocks you will need to read back all those datya blocks to generate new parity when any of these data blocks was changed. and this decreases overall perfromance 2000 times. so you should see why they need those pyrammid codes rather than something on opposite side
- Bulat-Ziganshin 9y ago
  Well, it's MY code so i use term "block" in the same meaning as they use term "shard" :)
Bulat-Ziganshin 9y ago
by block i mean the same thing as they mean by shard. it just doesn't make sense to count entire amount of data processed - only amount of data processed TOGETHER make a sense and yeah, it's quite hard to believe that some new approach may work 1000 times faster than existing ones. that said, i'm not alone - there are a few academic paper/code which is only ~10x slower than my code. i just developed better math scheme and made accurate low-level implementation

Bulat-Ziganshin 9y ago

Speed of RS coder depends on the amount of data/parity blocks. From the URL you mentioned, speed with 50+20 blocks is 713 MB/s. This algorithms is O(N^2) that means the speed is proportional to 1/N. So if it will support 500000+200000 blocks, the speed in this configuration will be 70 KB/s My algorithm is the only open-source one that has O(N*Log(N)) speed so it runs 500000+200000 blocks at 1.2 GB/s. Overall, FastECC should be faster than existing libraries starting from ~32 parity blocks It's like bublle sort vs quick sort - for small datasets they may be comparable, for larger ones they are just different worlds. It's all FFT magic, after all. I have added descriptions of method used, but will try to make a longer version since the math behind is is really wonderful

nemo1618 9y ago
Thanks for clarifying. What is the use case for 500000+200000 blocks/shards though? I can't imagine a real-world scenario that requires more than ~100 parity blocks. Even still, it would be a big deal if FastECC is 10x+ faster at something like 20+60 blocks.
- Bulat-Ziganshin 9y ago
  Well, i don't know :) When you want to protect files on disk, f.e. 30 GB video, you may want to use as much RAM as possible to increase protection level. So if you have 8 GB RAM, and use 4 KB data blocks, you can fit one million blocks into RAM easily. That's one possible usecase, and dream of some data protection geeks But aside of that, it's exactly what i'm looking for - possible usecases. Today i've checked speed with small n/k and found that fastecc should be faster than MultiPar starting from 16-32 parity blocks. So sorry, with 20+60 blocks speed will be pretty the same, and i hope that Intel's isa-l is even faster than MultiPar. Moreover, fastecc doesn't work in GF(2^n) fields, it requires GF(p) or GF(p^2) instead, which means extra problems what you don't want to solve for a small speed increase So, overall, fastecc territory starts where GF(256) territory ends. Also, there is no soft decoder, so it's not interesting for any hardware (ssd, lte and so on)