Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Erasure Coding for Distributed Systems

transactional.blog

Post reply on HN
Print view View original

31–40 of 61 posts

Re: Erasure Coding for Distributed Systems

#31

Post by jcalvinowens »

AYBABTME wrote: post #30
jcalvinowens wrote: post #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-e…

Aren't there patent problems with fountain codes?

Luby's original paper was published in 2002. Not sure about RaptorQ though...

Re: Erasure Coding for Distributed Systems

#32

Post by preisschild »

epistasis wrote: post #19
hinkley wrote: 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.

This has been used in Ceph for a long time: https://docs.ceph.com/en/latest/rados/operations/erasure-cod... I would not be surprised if there was a lot of stuff like this behind S3 and other cloud storage systems too, at least in the lower-access tiers of storage, but I have no actual knowledge of AWS or GCP systems.

Yeah, I use it in my homelab and it is really awesome to have "RAID(5/6)" basically work over the network.

Re: Erasure Coding for Distributed Systems

#33

Post by exikyut »

dragontamer wrote: post #22
jeremycarter wrote: post #6

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…

Is that introduction https://ntrs.nasa.gov/citations/19900019023 -> https://ntrs.nasa.gov/api/citations/19900019023/downloads/19... [PDF]?

Re: Erasure Coding for Distributed Systems

#34

Post by kqr »

cdumler wrote: post #13
jeremycarter wrote: post #6

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.

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

> "Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke

"If anything seems like magic you're not asking enough questions." -- Mario Romero Vega

Re: Erasure Coding for Distributed Systems

#35

Post by genewitch »

halfcat wrote: post #27
dragontamer wrote: post #22

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

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.

that's how i used to explain what a nonce was to explain what all the computers were doing to "mine" bitcoin. and then explain "they're instead trying to get a number that has a certain number of zeros in a specific place"

Re: Erasure Coding for Distributed Systems

#36

Post by jsolson »

stevefan1999 wrote: post #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 do…

Funny story, if you're using Rook Ceph and say "I'm going to try to update these parameters to see if it will let me (and trigger a re-encoding)" it absolutely will let you change them, but it does not trigger anything to re-encode.

It just uses --force and leaves you with a corrupt filesystem.

I suppose that's only really funny in a "you had to be there, and not be me" sense.

Re: Erasure Coding for Distributed Systems

#37

Post by kayg04 »

supertrope wrote: post #21
sva_ wrote: post #14

Earlier quoted context omitted.

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

can you explain? I tried looking it up but I didn't quite understand how it is called SD-WAN.

Re: Erasure Coding for Distributed Systems

#38

Post by londons_explore »

donavanm wrote: post #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...

You also need to take into account other constraints, like recovery time. If one of your companies datacenters gets destroyed, then it's great to be able to recover from the other 6 using clever erasure codes, but if that recovery requires reading every byte of data in every other DC and sending it over the network, it's gonna take 6 months+ to transfer all that data over a cross ocean fiber which might only be 1 Tbps.

Re: Erasure Coding for Distributed Systems

#39

Post by masspro »

otterley wrote: post #5

Erasure 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 those larger than 1 GB.

I assumed 10% PAR file size == resistance to 10% of the input file being corrupted, but that’s not how it works. The article shows some nonlinear and non-obvious relationships between input file size, par file size, and maximum number of recoverable errors.

Re: Erasure Coding for Distributed Systems

#40

Post by Luker88 »

jcalvinowens wrote: post #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-e…

I have implemented RaptorQ and RFC6330.

First, the rfc is pointlessly complex and optimized for files, not for streaming. if you want to play with it, manage blocks by yourself, ignore the asinine interleaving and block size management.

Second, the algorithm is actually split in two parts, and while the second (generation of repair blocks) is linear, the first is cubic on the number of messages that you put together in a block (~~ matrix gaussian elimination).

And while parts of both encoding and decoding can be cached, I think that "linear time" encoding for raptorq is actually just false marketing speak.

Post reply on HN