Erasure Coding for Distributed Systems
transactional.blog
Erasure Coding for Distributed Systems
1–10 of 61 posts
Re: Erasure Coding for Distributed Systems
#2[deleted]
Re: Erasure Coding for Distributed Systems
#3Years 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.
Re: Erasure Coding for Distributed Systems
#4Has anybody used Wirehair in a project? https://github.com/catid/wirehair
I'm curious if it's well-defined enough to base a standard around--informally if not formally--for building a large file archiving/data recovery project I've been mulling over for nearly 10 years. It's the only large block erasure code I've found that has both the ideal (or nearly ideal) algorithmic performance and API. That makes it a nice blackbox for my use case, unlike something like RaptorQ, which leaks little details all over the place, driving up the complexity and rigidness of the rest of the stack. But Wirehair isn't a spec, it's an (experimental?) implementation of an idea. It seems stable, but unless/until I try writing a second implementation, or it's seen substantial use (exposing any sharp edges in the algorithm) I worry how easily it would translate to a reliable specification or second implementation.
Re: Erasure Coding for Distributed Systems
#5Erasure 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
#6Erasure 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.
Re: Erasure Coding for Distributed Systems
#7This is one of the replication strategies that ceph uses for its distributed blob stores
Re: Erasure Coding for Distributed Systems
#8Has anybody used Wirehair in a project? https://github.com/catid/wirehair I'm curious if it's well-defined enough to base a standard around--informally if not formally--for building a large file archiving/data recovery project I've been mulling over for nearly 10 years. It's the only large block erasure code I've found that has both the ideal (or nearly ideal) algorithmic performance and API. That makes it a nice bla…
We previously used it in Bitcoin Fibre (a fork of the Bitcoin node software with special enhancements for block relay). It's extremely nice.
Be aware that Qualcomm might claim that its covered by RaptorQ patents (it is conceptually related), though the earliest of those are about to expire (or just expired, haven't checked the file wrapper lately) and QC has made some commitment to not apply the RaptorQ patents outside of wireless (but that might be only for conforming implementations, I don't recall).
I've looked at what it would take to specify it-- which would be something that we'd want to do if using it in the bitcoin protocol proper and wasn't super excited about doing it-- even though myself and several other bitcoin developers are quite comfortable with number theory and error correcting codes. It's just that wirehairs structure has a fair amount of adhoc-ish details and knowing us we might get sucked into a trap of improving it. :)
There might be some renewed interest in bitcoin land at getting a fountain code into wide use, if so waiting a while might result in someone else writing a spec.
Depending on your exact application you might find https://github.com/catid/fecal interesting too... if your expected erasures count is very low it could be faster than wirehair.
Leopard is mentioned in the article-- it's not a fountain code but it has a pretty big block size. It has a nice advantage for specification: it's merely a very fast implementation of a boring RS code (so a spec would arguably only need to document the field and generator choice).
Re: Erasure Coding for Distributed Systems
#9Years 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.
Network coding is more than that, participants in the graph can synthesize new parts on the fly from parts they just got without having the whole thing.
FWIW, freenet at least uses fec-coded files so that you can have some flexibility in what parts you get and durability against a file becoming broken just because a single part gets lost.
Re: Erasure Coding for Distributed Systems
#10Years 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.
With something like https://github.com/cberner/raptorq you can do several gbits/s over high latency/lossy UDP.