Erasure Coding for Distributed Systems
transactional.blog
transactional.blog
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
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.
It's a great solution (fast, storage overhead of about 1.2%) iff your data is immutable.
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.
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.
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.
edit: I see immediately below while I was composing this, someone mentioned pararchive..
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.
> 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.
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).
Use WinRAR/RAR recovery record for the important things.
There is one site what still mandates 5% RR for the archives because before the ubiquitous HTTPS the trashed in transit archives were the norm.
But yeah if that's your data loss model then par2 isn't the right approach. (Not sure what is.)
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 of size X, there is one and only one solution to the polynomial's coefficients such that it will pass through those data points.
So, stripe the data into bands of arrays, compute the polynomial, and compute additional data points of the curve, and save it with the original data. If you have at least the array's size of data points ( original array and/or parity values) and know the place in the list for each data point (thus which data is missing), there is one and only one solution to the polynomial equation. Once you solve the polynomial again, you can compute any point, including the missing ones. Again, because there is one and only one solution for the curve.
The devil is the math necessary solve the polynomials, which is why it is so computationally intensive.
"If anything seems like magic you're not asking enough questions." -- Mario Romero Vega
For writable disk media, there is also dvdisaster:
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.
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.
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.
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.
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).
Wow, been a long time since I've heard that project named. What ever happened with that?
Fibre contained a number of complementary optimizations. A couple have been merged into popular node software-- that's what compact blocks (BIP152) is. The rest are still valuable particularly now with miners frequently including never-relayed transactions, CPUs having become ever more faster relative to latency, and some of the underlying number theory toys from proposed but not ever implemented further fibre enhancements having since been implemented for other purposes. Though the unmerged parts were the harder parts to upstream.
But with many of the contributors who worked on that sort of stuff driven out by vexatious litigation and other forms of harassment, I dunno if anyone will continue that work any time soon. Although, I think there has been some interest. The remaining contributors that I think are more likely to work on things like that have been busy developing an improved combinitoric optimizer for transaction selection, but that work is almost finished.
The two major things fibre had that are missing now is using a fountain code to fill in missing data from blocks and transmission over UDP. The two can be implemented independently but they're much more powerful together. Both are independently kind of complicated to implement in a non-yolo way: the error correcting code because it seems rocketsciency and so it narrows the pool of people willing to try working on it, and the UDP because it's a whole separate P2P protocol arguably, and has a lot of connection and resource management questions that have to be competently answered (some of which were just punted on in fibre).
The optimizer is a fascinating knapsack problem to me. A lot of work in ETH land went on with this, especially with the work on Flashbots/MEV. But we hear less and less about it in the public these days.
Cheers
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.
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.
I say that because I have seen some stuff which suggests when you grow the FS with new VDEV in ZFS there are circumstances where the balance is not fixed and you can have persisting unbalanced IO state.
ARM has NEON and SVE/SVE 2. They also operate very fast.
So not sure what you are thinking of.
(FWIW, it's possible to project elements from one field to another isomorphic field, though it takes enough operations that for fast code like RS decoding the conversion is probably performance limiting).
For hybrid codes GFNI should be sufficient, though for things like using RS at 16/32 bit sizes it's not.
As such, large ReedSolomon codes are impractical. If you need a larger code than what GF(2^8) can offer, you grow with 2-dimension codes, slicing or other features.
In practice, this sacrifices Minimum Distance property, meaning you should use a Turbo Code (or other XOR code) which are O(n) but imperfect.
---------
CRC32 can be implemented in GFNI. And AES is also GF(2^8).
----------
I don't think there are many algorithms where GF(2^16) or bigger are needed.
And if they did, it's possible to turn 8x8 into 16x16 or 32x32 anyway.
And sure, list decoding is slow. But I think there are two distinct groups of applications for good instruction sets: one is where you're trying to make a fast thing like an 8-bit RS code or something "free" by having it run at near memory, wire, or disk speeds (or make it consume little power). but the other is where you're doing something legitimately slow, including things that are O(N^2) (or worse). In those cases sometimes a small constant factor makes a big difference between usable and very much not usable.
There is even an AVX512 version of PCLMULQDQ.
FWIW, I've ported rs-leopard to Go and found it very effective, except in the "recover one" scenario, where it is only at 50% speed of the "recover all" scenario, since it has to do several reconstructions to get one output. But even so, I am not too sure it would be much better with plain GF16, since you would still need to touch most shards to get one shard out.