5 ms·

Erasure Coding for Distributed Systems

284 points by eatonphil 2y ago

deleted 2y ago
[deleted]
hinkley 2y ago
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.
- nullc 2y ago
  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.
  - StillBored 2y ago
    and usenet binaries with https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive and even earlier with RAR's recovery block, and probably even earlier with BBSes, but my memory is failing me what I was using before it in the 1990s. edit: I see immediately below while I was composing this, someone mentioned pararchive..
- phonon 2y ago
  With something like https://github.com/cberner/raptorq https://github.com/cberner/raptorq you can do several gbits/s over high latency/lossy UDP.
- sva_ 2y ago
  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.
  - supertrope 2y ago
    It’s called SD-WAN
    - kayg04 2y ago
      can you explain? I tried looking it up but I didn't quite understand how it is called SD-WAN.
  - toast0 2y ago
    One difficulty with using multiple routes is you'll probably need to spend a lot of bytes on active probing, because the quality of a connection may change during the call and when the active connection loses quality it's not apparent what the other connections will do, so you need recent probing from them as well to make a smart change. 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.
- epistasis 2y ago
  This has been used in Ceph for a long time: https://docs.ceph.com/en/latest/rados/operations/erasure-code/ 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.
  - preisschild 2y ago
    Yeah, I use it in my homelab and it is really awesome to have "RAID(5/6)" basically work over the network.
wahern 2y ago
Has anybody used Wirehair in a project? https://github.com/catid/wirehair 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.
- nullc 2y ago
  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 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).
otterley 2y ago
Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive
- jeremycarter 2y ago
  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.
  - cdumler 2y ago
    "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 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.
    - kqr 2y ago
      > "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
    - pwg 2y ago
      > They're still useful today if you save things on media that can be damaged (CD, DVD, Blue-Ray) For writable disk media, there is also dvdisaster: https://dvdisaster.jcea.es/ https://dvdisaster.jcea.es/
from-nibly 2y ago
This is one of the replication strategies that ceph uses for its distributed blob stores
ggm 2y ago
Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.
- jeffbee 2y ago
  Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
  - ggm 2y ago
    My point was specifically to new things created during the period. Resilvering happens on addition of a replacement drive in ZFS. I am less sure that otherwise valid, complete checksum states of files made during the loss period get uplifted to the wider stripe count when that is done. 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.
    - jeffbee 2y ago
      In distributed systems you don't need to be constrained to writing to a set of devices one of which is not available. You can just write anywhere, and remember where.
  - markhahn 2y ago
    just a suggestion: let the curator's activity be called "preening" rather than "grooming"...
anonymousDan 2y ago
Is it the case that it's really only practical for read-only or very read intensive workloads?
donavanm 2y ago
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-considerations-and-analysis-of-multi-level-erasure-coding-in-large-scale-data-centers/ https://chameleoncloud.org/blog/2023/12/12/design-considerat...
- londons_explore 2y ago
  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.
stevefan1999 2y ago
Yep, this is the key tech behind Ceph's Erasure Code pool: https://docs.ceph.com/en/latest/rados/operations/erasure-code/ 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.
- deleted 2y ago
  [deleted]
- jsolson 2y ago
  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.
nullc 2y ago
unfortunately modern cpus are still pretty sparse on tools to make erasure codes extremely fast. E.g. no vector clmuls.
- klauspost 2y ago
  Almost all (x86) CPUs sold have GFNI. That can pretty much saturate memory bandwidth on a single core or two. You can use SSSE3 pshufb for the rest which is about half the speed. ARM has NEON and SVE/SVE 2. They also operate very fast. So not sure what you are thinking of.
  - nullc 2y ago
    GFNI only does 8-bits and sticks you with a single modulus. But for some reason I'd forgotten it completely, you're totally right to give me a mystified response. (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.
    - dragontamer 2y ago
      The matrix multiplication needed to correct grows at n^2 despite the code only growing at n. There are asymptotic faster matrix multiplications in theory than O(n^2) but in practice every algorithm is O(n^2). 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.
      - nullc 2y ago
        RS codes can be done in N log N time for both encoding and erasure decoding, and sometimes achieving MDS is useful for attack resistance... e.g. that you can always decode with N blocks, vs with non-minimum distance codes you can have adversarial subsets that will fail to decode even when you have significantly more blocks than needed.. Larger word sizes for RS codes is also useful for list decoding even when the number of data blocks isn't that great. 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.
jcalvinowens 2y ago
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 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-capillary-references/ref/MacKay05.pdf 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 https://www.rfc-editor.org/rfc/rfc6330
- AYBABTME 2y ago
  Aren't there patent problems with fountain codes?
  - jcalvinowens 2y ago
    Luby's original paper was published in 2002. Not sure about RaptorQ though...
    - Sanzig 2y ago
      IIRC, Qualcomm still holds patents on RaptorQ. They do provide a blanket license exemption for implementing RFC6330.
- Luker88 2y ago
  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.
- jumperabg 2y ago
akww 2y ago
Reminds me also of Rabin’s Information Dispersal Algorithm, described in a paper here: https://dl.acm.org/doi/10.1145/62044.62050 https://dl.acm.org/doi/10.1145/62044.62050
sarahwoods 2y ago
[dead]

284 points by eatonphil 2y ago

deleted 2y ago

[deleted]

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.

nullc 2y ago
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.
- StillBored 2y ago
  and usenet binaries with https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive and even earlier with RAR's recovery block, and probably even earlier with BBSes, but my memory is failing me what I was using before it in the 1990s. edit: I see immediately below while I was composing this, someone mentioned pararchive..
phonon 2y ago
With something like https://github.com/cberner/raptorq https://github.com/cberner/raptorq you can do several gbits/s over high latency/lossy UDP.
sva_ 2y ago
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.
- supertrope 2y ago
  It’s called SD-WAN
  - kayg04 2y ago
    can you explain? I tried looking it up but I didn't quite understand how it is called SD-WAN.
- toast0 2y ago
  One difficulty with using multiple routes is you'll probably need to spend a lot of bytes on active probing, because the quality of a connection may change during the call and when the active connection loses quality it's not apparent what the other connections will do, so you need recent probing from them as well to make a smart change. 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.
epistasis 2y ago
This has been used in Ceph for a long time: https://docs.ceph.com/en/latest/rados/operations/erasure-code/ 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.
- preisschild 2y ago
  Yeah, I use it in my homelab and it is really awesome to have "RAID(5/6)" basically work over the network.

wahern 2y ago

Has anybody used Wirehair in a project? https://github.com/catid/wirehair 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.

nullc 2y ago
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 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).

otterley 2y ago

Erasure coding has been around for a very long time. Remember PAR2 files on Usenet? https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive

jeremycarter 2y ago
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.
- cdumler 2y ago
  "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 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.
  - kqr 2y ago
    > "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
  - pwg 2y ago
    > They're still useful today if you save things on media that can be damaged (CD, DVD, Blue-Ray) For writable disk media, there is also dvdisaster: https://dvdisaster.jcea.es/ https://dvdisaster.jcea.es/

from-nibly 2y ago

This is one of the replication strategies that ceph uses for its distributed blob stores

ggm 2y ago

Am I right in thinking that products made during an M of N incident are coded differently to when all N are available? If so, you might want a bitflag to denote "needs to be re-encoded when the N is restored" or else you have some files with less than stellar recovery for a random loss in the N set.

jeffbee 2y ago
Whenever you have a stripe with missing chunks they need to be re-encoded ASAP because those stripes will be lost if they lose enough chunks. Every distributed storage system needs some kind of librarian to go around grooming the stripes to keep them out of danger.
- ggm 2y ago
  My point was specifically to new things created during the period. Resilvering happens on addition of a replacement drive in ZFS. I am less sure that otherwise valid, complete checksum states of files made during the loss period get uplifted to the wider stripe count when that is done. 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.
  - jeffbee 2y ago
    In distributed systems you don't need to be constrained to writing to a set of devices one of which is not available. You can just write anywhere, and remember where.
- markhahn 2y ago
  just a suggestion: let the curator's activity be called "preening" rather than "grooming"...

anonymousDan 2y ago

Is it the case that it's really only practical for read-only or very read intensive workloads?

donavanm 2y ago

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-considerations-and-analysis-of-multi-level-erasure-coding-in-large-scale-data-centers/ https://chameleoncloud.org/blog/2023/12/12/design-considerat...

londons_explore 2y ago
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.

stevefan1999 2y ago

Yep, this is the key tech behind Ceph's Erasure Code pool: https://docs.ceph.com/en/latest/rados/operations/erasure-code/ 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.

deleted 2y ago
[deleted]
jsolson 2y ago
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.

nullc 2y ago

unfortunately modern cpus are still pretty sparse on tools to make erasure codes extremely fast. E.g. no vector clmuls.

klauspost 2y ago
Almost all (x86) CPUs sold have GFNI. That can pretty much saturate memory bandwidth on a single core or two. You can use SSSE3 pshufb for the rest which is about half the speed. ARM has NEON and SVE/SVE 2. They also operate very fast. So not sure what you are thinking of.
- nullc 2y ago
  GFNI only does 8-bits and sticks you with a single modulus. But for some reason I'd forgotten it completely, you're totally right to give me a mystified response. (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.
  - dragontamer 2y ago
    The matrix multiplication needed to correct grows at n^2 despite the code only growing at n. There are asymptotic faster matrix multiplications in theory than O(n^2) but in practice every algorithm is O(n^2). 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.
    - nullc 2y ago
      RS codes can be done in N log N time for both encoding and erasure decoding, and sometimes achieving MDS is useful for attack resistance... e.g. that you can always decode with N blocks, vs with non-minimum distance codes you can have adversarial subsets that will fail to decode even when you have significantly more blocks than needed.. Larger word sizes for RS codes is also useful for list decoding even when the number of data blocks isn't that great. 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.

jcalvinowens 2y ago

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 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-capillary-references/ref/MacKay05.pdf 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 https://www.rfc-editor.org/rfc/rfc6330

AYBABTME 2y ago
Aren't there patent problems with fountain codes?
- jcalvinowens 2y ago
  Luby's original paper was published in 2002. Not sure about RaptorQ though...
  - Sanzig 2y ago
    IIRC, Qualcomm still holds patents on RaptorQ. They do provide a blanket license exemption for implementing RFC6330.
Luker88 2y ago
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.
jumperabg 2y ago

akww 2y ago

Reminds me also of Rabin’s Information Dispersal Algorithm, described in a paper here: https://dl.acm.org/doi/10.1145/62044.62050 https://dl.acm.org/doi/10.1145/62044.62050

sarahwoods 2y ago

[dead]