Reminds me also of Rabin’s Information Dispersal Algorithm, described in a paper here:
Erasure Coding for Distributed Systems
41–50 of 61 posts
Re: Erasure Coding for Distributed Systems
#42I'm surprised rateless fountain codes aren't mentioned! If you enjoy this sort of thing, you'll find the Luby Transform Code fascinating: https://en.wikipedia.org/wiki/Luby_transform_code This paper is a really nice overview with more detail: https://switzernet.com/people/emin-gabrielyan/060112-capilla... LT codes are used as the "outer code" in the linear time RaptorQ encoding specified in RFC6330: https://www.rfc-e…
Are rateless fountain codes the better solution and if are there any systems that are using them?
Re: Erasure Coding for Distributed Systems
#43Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive
I was unpleasantly surprised by but thankful to have found eclecticlight.co’s findings about PAR2. When I learned about PAR2 I immediately wanted to make par files for everything because bit rot scares me. But, from https://eclecticlight.co/2020/04/20/file-integrity-5-how-wel... : > This has serious implications for the use of Par2 with files much larger than 20 MB, and probably rules it out as a method of ECC for th…
It's my understanding that par2 is designed for missing files (parts of a multi part archive), not the uniform random bit rot corruption used in that article. I think it can recover a much larger corrupted or missing block, approaching the size of the parity files.
But yeah if that's your data loss model then par2 isn't the right approach. (Not sure what is.)
Re: Erasure Coding for Distributed Systems
#44unfortunately modern cpus are still pretty sparse on tools to make erasure codes extremely fast. E.g. no vector clmuls.
Almost all (x86) CPUs sold have GFNI. That can pretty much saturate memory bandwidth on a single core or two. You can use SSSE3 pshufb for the rest which is about half the speed.
ARM has NEON and SVE/SVE 2. They also operate very fast.
So not sure what you are thinking of.
Re: Erasure Coding for Distributed Systems
#45I'm surprised rateless fountain codes aren't mentioned! If you enjoy this sort of thing, you'll find the Luby Transform Code fascinating: https://en.wikipedia.org/wiki/Luby_transform_code This paper is a really nice overview with more detail: https://switzernet.com/people/emin-gabrielyan/060112-capilla... LT codes are used as the "outer code" in the linear time RaptorQ encoding specified in RFC6330: https://www.rfc-e…
Are rateless fountain codes the better solution and if are there any systems that are using them?
Amplidata did this https://en.wikipedia.org/wiki/Amplidata
It's a great solution (fast, storage overhead of about 1.2%) iff your data is immutable.
Re: Erasure Coding for Distributed Systems
#46Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive
I was unpleasantly surprised by but thankful to have found eclecticlight.co’s findings about PAR2. When I learned about PAR2 I immediately wanted to make par files for everything because bit rot scares me. But, from https://eclecticlight.co/2020/04/20/file-integrity-5-how-wel... : > This has serious implications for the use of Par2 with files much larger than 20 MB, and probably rules it out as a method of ECC for th…
Bitrot is reasonably handled by erasure codes by simply having CRC32 checksums (or similar) verifying the parts.
If a piece has bitrotted away, then you throw away the whole segment.
CRC32 is closely related to ReedSolomon / Galois Fields. It's basically a repeated division + remainders in Galois Field. And as we all know: Division is very good at mixing up bits (true in normal math as well as Galois Fields).
The real benefit of cyclical codes is the guarantee to catch any burst error of size 32 or less (for a CRC32). You only get a chance of false negatives if the error region is larger than the CRC size.
------
Indeed: the whole erasure code / correction code thing has complex math constructs so that these tight guarantees can be made. (Be it CRC32 or ReedSolomon, or any old school biterror algorithm).
Re: Erasure Coding for Distributed Systems
#47Earlier quoted context omitted.
PAR files use ReedSolomon error correction which IMO might as well be magic. Galois Fields are really awesome (and are related to CRC codes). The level of effort to learn is quite high. NASAs guide to ReedSolomon was amazing though ----------- XOR codes are easier and sloppier. But are actually what's used today despite being imperfect. Let's say you have A, B, C... Z as your data. Parity#1 could be XOR(A, B, Z). If…
Is that introduction https://ntrs.nasa.gov/citations/19900019023 -> https://ntrs.nasa.gov/api/citations/19900019023/downloads/19... [PDF]?
Yes, this is it.
It's a very shallow introduction to Galois Fields but it's just barely enough to reach Reed Solomon encoding and understand error correction codes.
As I said earlier: it's a lot of math, even in this simplified form. Abstract conceptual math. But I do find this kind of abstractness very fun.
Re: Erasure Coding for Distributed Systems
#48Years back someone proposed a cute algorithm for erasure codes that depended not on spinning rust but on multipath networking. I believe they called it network coding and the idea was in a network with multiple routes I might get a file faster by pulling an erasure code that used two parts of the file or even two files from one upstream instead of waiting for the entire file from the primary server.
I thought about something like that to make video calls more stable. For example I'll get completely different routes (sometimes noticeably lower/more predictable latency) when I use a VPN to connect to some peer in the US (from Europe.) Would be cool to combine different routes.
One difficulty with using multiple routes is you'll probably need to spend a lot of bytes on active probing, because the quality of a connection may change during the call and when the active connection loses quality it's not apparent what the other connections will do, so you need recent probing from them as well to make a smart change.
But in theory, you should have several routing options in a well supported calling service. I'll illustrate one direction, but the same options apply in the other direction, and there's no need for both peers to use the same connection to send (although WebRTC will)
Peer A -> Peer B
Peer A -> Relay near A -> Peer B
Peer A -> Relay near B -> Peer B
Peer A -> Relay near A -> Relay near B -> Peer B
If at least two of the four hosts mentioned have IPv4 and IPv6, you can also add those permutations. It's pretty typical to have different routing for v4 and v6.
Re: Erasure Coding for Distributed Systems
#49Re: Erasure Coding for Distributed Systems
#50Earlier quoted context omitted.
When I was younger, I literally thought PAR's were magic files. I had no idea how they worked, and from a distance it was magic.
"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke I thought the same thing when using PAR files. They're still useful today if you save things on media that can be damaged (CD, DVD, Blue-Ray) or across multiple multiple media. Eventually, I decided to dig into the math behind it. It is a surprisingly simple principle: Given polynomial of a degree X and an array of data points…
> They're still useful today if you save things on media that can be damaged (CD, DVD, Blue-Ray)
For writable disk media, there is also dvdisaster: