Live data from Hacker News

Erasure Coding for Distributed Systems

transactional.blog

21–30 of 61 posts

Re: Erasure Coding for Distributed Systems

#21
post #14
post #3

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.

It’s called SD-WAN

Re: Erasure Coding for Distributed Systems

#22
post #5

Erasure 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.

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 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

#23
If youre interested in EC you might want to consider larger multi dimensional cases. Think of encoding not just across spindles, but another failure domain like rack, room, DC, or region. The goal being to tolerate common component failures, and larger system failures (or partitions) as well. A nice intro https://chameleoncloud.org/blog/2023/12/12/design-considerat...

Re: Erasure Coding for Distributed Systems

#24
Yep, 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 dominant choice for HA fault tolerant data storage.

Re: Erasure Coding for Distributed Systems

#25

Yep, 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…

[deleted]

Re: Erasure Coding for Distributed Systems

#27

Earlier 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…

Also I’ve found that while most people (non-tech) don’t have a concept of XOR, they probably took basic algebra and understand 1+?=3

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

#29
I'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-editor.org/rfc/rfc6330

Re: Erasure Coding for Distributed Systems

#30

I'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…

Aren't there patent problems with fountain codes?
Post reply on HN