Live data from Hacker News

Erasure Coding for Distributed Systems

transactional.blog

51–60 of 61 posts

Re: Erasure Coding for Distributed Systems

#51
post #39
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 th…

I think something about the test methodology in that article is severely flawed.

Re: Erasure Coding for Distributed Systems

#52
post #28

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

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.

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.

Re: Erasure Coding for Distributed Systems

#53
post #39
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 th…

> ecause bit rot scares me.

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.

Re: Erasure Coding for Distributed Systems

#54
post #8
post #4

Has 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 outsi…

> Bitcoin Fibre

Wow, been a long time since I've heard that project named. What ever happened with that?

Re: Erasure Coding for Distributed Systems

#55
post #8

Earlier quoted context omitted.

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

> Bitcoin Fibre Wow, been a long time since I've heard that project named. What ever happened with that?

The bitcoin satellite broadcast stuff uses a fork of the fibre codebase with changes to the FEC to better adapt it to recovering from signal disruptions. Otherwise it's not maintained anymore.

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

Re: Erasure Coding for Distributed Systems

#56
post #55

Earlier quoted context omitted.

> Bitcoin Fibre Wow, been a long time since I've heard that project named. What ever happened with that?

The bitcoin satellite broadcast stuff uses a fork of the fibre codebase with changes to the FEC to better adapt it to recovering from signal disruptions. Otherwise it's not maintained anymore. 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 includi…

Great answer @nullc, thank you for the context details. I always felt like having a subnetwork that was super fast optimized for sending transactions around the mempool would be really useful.

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

Re: Erasure Coding for Distributed Systems

#57
post #52

Earlier quoted context omitted.

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.

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

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.

Re: Erasure Coding for Distributed Systems

#58
post #52

Earlier quoted context omitted.

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

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…

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.

Re: Erasure Coding for Distributed Systems

#59
post #52

Earlier quoted context omitted.

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.

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

In my experience, the hybrid approach is practically better due to cache locality anyway, so I don't think even native GF16 or GF32 would be of much help.

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.

Re: Erasure Coding for Distributed Systems

#60
post #58

Earlier quoted context omitted.

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…

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

In those cases, I know that ARM has PMULL / PMULL2 and x86 has PCLMULQDQ, which go up to 64x64 == 128-bit multiplication.

There is even an AVX512 version of PCLMULQDQ.

Post reply on HN