Years 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.
Erasure Coding for Distributed Systems
21–30 of 61 posts
Re: Erasure Coding for Distributed Systems
#22Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive
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.
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 B were missing, Parity#1 XOR A XOR Z can back-calculate B.
Parity#2 can be a random set of all previous entries (including Parity#1). Etc. etc. etc.
Keep adding XOR parity codes until your probability of reconstruction is high enough to please you.
I believe this concept is called a Fountain Code.
Re: Erasure Coding for Distributed Systems
#23Re: Erasure Coding for Distributed Systems
#24This does not come without trade-offs though, you cannot update the coding parameters (k, m) afterwards, so you either have to be very sure that those parameters are going to work in a long time, or you have to start from scratch. This inelasticity is also the reason why replicas are still the dominant choice for HA fault tolerant data storage.
Re: Erasure Coding for Distributed Systems
#25Yep, this is the key tech behind Ceph's Erasure Code pool: https://docs.ceph.com/en/latest/rados/operations/erasure-cod... This does not come without trade-offs though, you cannot update the coding parameters (k, m) afterwards, so you either have to be very sure that those parameters are going to work in a long time, or you have to start from scratch. This inelasticity is also the reason why replicas are still the do…
Re: Erasure Coding for Distributed Systems
#26Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive
Re: Erasure Coding for Distributed Systems
#27Earlier 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.
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…
Arithmetic wouldn’t be a good implementation due to integer overflow (a problem XOR doesn’t have) but it’s helpful if you ever have to explain it to the less technical business person who you need to sign off on the purchasing decision.
Re: Erasure Coding for Distributed Systems
#28Re: Erasure Coding for Distributed Systems
#29This 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-editor.org/rfc/rfc6330
Re: Erasure Coding for Distributed Systems
#30I'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…