Bulat-Ziganshin

I heard that BitTorrent is 40% traffic of today Internet

I personally prefer Nim. there is also Zig and D.

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

among the great answers that was already written here, i can suggest famous Plank tutorial: https://web.eecs.utk.edu/~plank/plank/papers/CS-96-332.html

i (FastECC author) learned everything from this great text. It contains anything required to understand RS coding from standard programmer knowledge base (i.e no Galois Fields or matrix arithmetic). it's longer than most other texts referenced here but it contains enough info to even make your own implementation if you want

note that it doesn't include info regarding my fast O(N*logN) implementation. If you need to learn that - read docs in my repository, although i'm not as good teacher as professor Plank

also note that there are several different approaches to RS implementation. While they all are called RS codes, they are pretty different. Plank describes the scheme that is easier to understand (and implement) than any other one

when encoding larger blocks, they are just split into multiple small words. f.e when GF(256) is used, each word is just a single byte. then you have f.e. 20 data blocks and encode corresponding words of each blocks as a single group, and each group generates a single word for each of parity blocks. you may consider it just as interleaving

overall, encoding in GF(2^n) is faster when n is smaller (since you need smaller multiplication tables that better fits into cpu cache). But OTOH encoding with K data+parity blocks require that 2^n>K, so for best speed n is choosen as small as possible among 8/16/32 depending on the K value

short answer: they all are suitable. i even has (unfinished) ldpc-based program that is pretty similar to par2

long answer: what you need is Forward Error Correction, that is implemented by any Error-Correcting Code (see wikipedia for both)

Reed-Solomon and BCH error-correcting codes are known since 60s. They are pretty slow (even my fastest implemenation is about 10x slower than good LDPC one with pretty close recovery ability), but well-studied and mostly free from patents

LDPC, fountain, Raptor and so on codes were started development in 90s as faster approach to FEC. They are preferred now in commercial environment due to their speed. But since they are so useful, they are patented all around

So, one advantage of my library is that while not as fast as best codes, it's still fast enough for any practical needs and absolutely patent-free. Well, i hope so :)

>from Reed-Solomon as it doesn't necessarily parallelize well.

i don't think so. RS erasure coding performs the same operation over all words in the block, that is perfectly vectorizable and parallelizable

SSDs goes from RS to LDPC probably because it's faster (and their controllers are already pretty hot!), in paricular LDPC allows faster soft decoders (i.e. ones that understand that 7 is more probably decoded as 8 rather than 2). Overall, classic RS encoder speed is O(1/N) where N is amount of parity blocks. Probably, modern media employs larger amount of parity blocks that slows down classic RS algorithms

OTOH, LDPC codecs afaik usually have fixed speed so with larger N they became faster than RS - sooner or later. So, as time goes and N increases, interest shifts from RS to LDPC algos. The same applies to other fast codes (fountain, raptor...) - they are also faster than classic RS for large enough N

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)

Let's see: in order to produce 32 parity blocks from 255 data blocks you are probably perform 32x255 multiplications, i.e. NxM operations where N,M is number of data/parity blocks. for a fixed N/M rate it is considered as O(N^2) algo

Once you fixed N and M, encoding speed will be fixed in both your and my algo. In mine, it's 1 GB/s for N=M=524288

And yes, it's doing the same as your algo - generate parity blocks from data blocks and then restore from any combination of N survived blocks

the math behind it is completely different. it doesn't even use GF(2^n) fields at all :)

as mentioned in RS.md, the encoding sheme is known since 2003 and even became a part of RFC

i (fastecc author) don't have isa-l benchmarks at hand, but i compared fastecc to the best O(N^2) implementation i know - MultiPar. My conclusion is that MultiPar will be slower than FastECC starting from ~32 ECC blocks

Well, it's MY code so i use term "block" in the same meaning as they use term "shard" :)

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

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