4 ms·

It is worth noting that this does not come for free, and it would have been nice for the article to mention the trade-off: reconstruction is not cheap on CPU, i

by ot 3y ago

It is worth noting that this does not come for free, and it would have been nice for the article to mention the trade-off: reconstruction is not cheap on CPU, if you use something like Reed-Solomon. Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data. If you get any other k-subset, you need to perform expensive reconstruction.

mjb 3y ago
It's true that Reed-Solomon isn't free. The first two codes (N of N+1 and N of N+2) are nearly trivial and can be done very fast indeed. On my hardware, the N of N+1 code (which is an XOR) can be arranged to be nearly as fast a memcpy (which obviously isn't free either). They can also be done in a streaming way which can save the memcpy if you're feeding a stream into a parser (e.g. JSON or something) or decryption. > Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data. Yeah, that's true. If you're CPU bound, it may be worth waiting a little longer for these 'diagonal' components to come back.
- pjdesno 3y ago
  There are new Intel instructions (GFNI) which accelerate things a lot, as well as various hacks to make it go fast. See https://www.reddit.com/r/ceph/comments/17z1w08/but_is_my_cpu_fast_enough_for_erasure_coding_a/ https://www.reddit.com/r/ceph/comments/17z1w08/but_is_my_cpu... for some quick and dirty benchmarks on jerasure, one of the EC plugins for Ceph, IIRC not using GFNI. (TLDR: 25GB/s on a Ryzen 7700X)
- dragontamer 3y ago
  Reed Solomon is closer to "perfect" but is unnecessary. IIRC, Turbo Codes and LDPCs are less-perfect (they cannot offer strict guarantees like Reed-Solomon can), but as XOR-based simple operations, they are extremely extremely fast to implement. LDPC has high-probabilities of fixing errors (near Reed-Solomon level), which is good enough in practice. Especially since LDPC's simple XOR-based operation is far faster and like O(n) instead of Reed-Solomon's matrix-multiplication (O(n^2)) algorithm. The state of the art has moved forward. Reed Solomon is great for proving the practice and providing strict assurances (likely better for storage where you have strict size limits and need strong guarantees for MTBF or other such statistics). But for a "faster" algorithm (ie: trying to prevent repeated packets in a communication stream like TCP or similar protocol), LDPC and/or Turbo codes are likely a better solution. ----- Reed Solomon is probably best for "smaller" codes where the matrix is smaller and O(n^2) hasn't gotten out of hand yet. But as codes increase in size, the O(n) "less than perfect" codes (such as Turbo codes or LDPC codes) become better-and-better ideas. That being said: I can imagine some crazy GPU / SIMD algorithm where we have such cheap compute and low bandwidth where the O(n^2) operation might serve as a better basis than the cheap XOR operation. The future of computers is going to be more compute and less relative memory bandwidth after all, so the pendulum may swing the other way depending on how future machines end up.
  - mjb 3y ago
    That's true too, this approach isn't limited to Reed-Solomon (or MDS codes). For non-MDS codes the fetch logic becomes a little more complicated (you need to wait for a subset you can reconstruct from rather than just the first k), but that's not a huge increase in complexity.
  - nsguy 3y ago
    I haven't heard about LDPCs before. Thanks! Do they serve the same use case though? With Reed-Solomon the idea is to recover from complete loss of a fragment of data (erasure coding), isn't LPDC strictly for error correction/"noise" (e.g. certain bits flipping but the data overall exists)?
    - dragontamer 3y ago
      I admit that I haven't thought it all the way through, but in general, all error-correction codes I'm aware of have a simpler erasure-code version available too. Reed Solomon traditionally is an error-correction code, for example. But has common implementations in its simplified erasure-only code. (Ex: fixing "lost data" is far easier than fixing "contradictory data"). I'm fairly certain that LDPC erasure codes is as simple as "Is there only one missing erasure in this particular code??" and "answer is LDPC XOR (other data) == missing-data". EDIT: The "hard part" is the exact composition of (other data), of which there's many styles and different methodologies with tons of different tradeoffs.
  - aero_code 3y ago
    I'm interested in using LDPC (or Turbo Codes) in software for error correction, but most of the resources I've found only cover soft-decision LDPC. When I've found LDPC papers, it's hard for me to know how efficient the algorithms are and whether it's worth spending time on them. Reed-Solomon has more learning resources that are often more approachable (plus open source libraries). Do you have more information on how to implement LDPC decoding using XOR-based operations?
    - dragontamer 3y ago
gizmo686 3y ago
That is true if you want a "perfect" algorithm, that can provide arbitrary M-of-N guarantees. But, if you are a bit more flexible in your requirements you can get some very cheep reconstruction. I worked on a system that uses a variant of parity packet encoding. Basic parity packet encoding is very simple. You divide you data into N blocks, then send the XOR of all the blocks as an extra packet. Both sender and receiver maintain a running XOR of packets. As soon as the Nth packet has been received, they immidietly reconstruct the N+1th packet without any additional work. This ammounts to 1 extra XOR operation per unit of data, which is a trivial amount of overhead in almost any workload. Of course, the above scheme is limited to N/N+1 recovery (and is probably as good as you can do for that particular use case). However, it has a fairly simple extension to N/N+M recovery. Arrange the data in an NxM grid, and construct M sets of "extra" packets". The first set is constructed row wise, (effectivly devolving into the above case). For the second set, rotate each of the columns by their column index. So if R(x,y) is a redundant packet, and D(x,y) is a data packet at location (x,y) in the grid, you would have * R(0,0) = D(0,0) ^ D(1,0) ^ D(2,0) ^ ... D(N,0) * R(0,1) = D(0,1) ^ D(1,1) ^ D(2,1) ^ ... D(N,1) ... * R(0,M-1) = D(0,M-1) ^ D(1,M-1) ^ D(2,M-1) ^ ... D(N,M-1) * R(1,0) = D(0,0) ^ D(1,1) ^ D(2,2) ^ ... D(N,N%M) * R(1,1) = D(0,1) ^ D(1,2) ^ D(2,3) ^ ... D(N,(N+1)%M) * R(1,M-1) = D(0,M-1) ^ D(1,0) ^ D(2,1) ^ ... D(N,(N+1)%M) ... * R(2,0) = D(0,0) ^ D(1,2) ^ D(2,4) ^ ... D(N,2N%M) * R(3,0) = D(0,0) ^ D(1,3) ^ D(2,6) ^ ... D(N,3N%M) Your overhead is now M XOR operations per unit of real data, which is still trivial for reasonable values of M. The downside of this scheme is that if the first redundancy packet is not enough to reconstruct the dropped packet, you need to wait for the entire NxM table to be sent, which could cause a significant long-tail spike in latency if you are not careful. (The upside of this downside, is it provides even stronger burst protection that a traditional K-of-M erasure coding. If you get even more creative with how you group packets for the extra redundancy packets, you can get even stronger burst protection). The other downside is you end up being less space efficient than Reed-Solomon error correction. Interestingly, the recovery algorithm I described is not optimal in the sense that there are times where it fails to recover data that is theoretically recoverable. Recovering data in all theoretically possible cases probably would be quite intensive.

by ot 3y ago

mjb 3y ago

It's true that Reed-Solomon isn't free. The first two codes (N of N+1 and N of N+2) are nearly trivial and can be done very fast indeed. On my hardware, the N of N+1 code (which is an XOR) can be arranged to be nearly as fast a memcpy (which obviously isn't free either). They can also be done in a streaming way which can save the memcpy if you're feeding a stream into a parser (e.g. JSON or something) or decryption. > Usually the codes used for erasure coding are in systematic form: there are k "preferential" parts out of M that are just literal fragments of the original blob, so if you get those you can just concatenate them to get the original data. Yeah, that's true. If you're CPU bound, it may be worth waiting a little longer for these 'diagonal' components to come back.

pjdesno 3y ago
There are new Intel instructions (GFNI) which accelerate things a lot, as well as various hacks to make it go fast. See https://www.reddit.com/r/ceph/comments/17z1w08/but_is_my_cpu_fast_enough_for_erasure_coding_a/ https://www.reddit.com/r/ceph/comments/17z1w08/but_is_my_cpu... for some quick and dirty benchmarks on jerasure, one of the EC plugins for Ceph, IIRC not using GFNI. (TLDR: 25GB/s on a Ryzen 7700X)
dragontamer 3y ago
Reed Solomon is closer to "perfect" but is unnecessary. IIRC, Turbo Codes and LDPCs are less-perfect (they cannot offer strict guarantees like Reed-Solomon can), but as XOR-based simple operations, they are extremely extremely fast to implement. LDPC has high-probabilities of fixing errors (near Reed-Solomon level), which is good enough in practice. Especially since LDPC's simple XOR-based operation is far faster and like O(n) instead of Reed-Solomon's matrix-multiplication (O(n^2)) algorithm. The state of the art has moved forward. Reed Solomon is great for proving the practice and providing strict assurances (likely better for storage where you have strict size limits and need strong guarantees for MTBF or other such statistics). But for a "faster" algorithm (ie: trying to prevent repeated packets in a communication stream like TCP or similar protocol), LDPC and/or Turbo codes are likely a better solution. ----- Reed Solomon is probably best for "smaller" codes where the matrix is smaller and O(n^2) hasn't gotten out of hand yet. But as codes increase in size, the O(n) "less than perfect" codes (such as Turbo codes or LDPC codes) become better-and-better ideas. That being said: I can imagine some crazy GPU / SIMD algorithm where we have such cheap compute and low bandwidth where the O(n^2) operation might serve as a better basis than the cheap XOR operation. The future of computers is going to be more compute and less relative memory bandwidth after all, so the pendulum may swing the other way depending on how future machines end up.
- mjb 3y ago
  That's true too, this approach isn't limited to Reed-Solomon (or MDS codes). For non-MDS codes the fetch logic becomes a little more complicated (you need to wait for a subset you can reconstruct from rather than just the first k), but that's not a huge increase in complexity.
- nsguy 3y ago
  I haven't heard about LDPCs before. Thanks! Do they serve the same use case though? With Reed-Solomon the idea is to recover from complete loss of a fragment of data (erasure coding), isn't LPDC strictly for error correction/"noise" (e.g. certain bits flipping but the data overall exists)?
  - dragontamer 3y ago
    I admit that I haven't thought it all the way through, but in general, all error-correction codes I'm aware of have a simpler erasure-code version available too. Reed Solomon traditionally is an error-correction code, for example. But has common implementations in its simplified erasure-only code. (Ex: fixing "lost data" is far easier than fixing "contradictory data"). I'm fairly certain that LDPC erasure codes is as simple as "Is there only one missing erasure in this particular code??" and "answer is LDPC XOR (other data) == missing-data". EDIT: The "hard part" is the exact composition of (other data), of which there's many styles and different methodologies with tons of different tradeoffs.
- aero_code 3y ago
  I'm interested in using LDPC (or Turbo Codes) in software for error correction, but most of the resources I've found only cover soft-decision LDPC. When I've found LDPC papers, it's hard for me to know how efficient the algorithms are and whether it's worth spending time on them. Reed-Solomon has more learning resources that are often more approachable (plus open source libraries). Do you have more information on how to implement LDPC decoding using XOR-based operations?
  - dragontamer 3y ago

gizmo686 3y ago

That is true if you want a "perfect" algorithm, that can provide arbitrary M-of-N guarantees. But, if you are a bit more flexible in your requirements you can get some very cheep reconstruction. I worked on a system that uses a variant of parity packet encoding. Basic parity packet encoding is very simple. You divide you data into N blocks, then send the XOR of all the blocks as an extra packet. Both sender and receiver maintain a running XOR of packets. As soon as the Nth packet has been received, they immidietly reconstruct the N+1th packet without any additional work. This ammounts to 1 extra XOR operation per unit of data, which is a trivial amount of overhead in almost any workload. Of course, the above scheme is limited to N/N+1 recovery (and is probably as good as you can do for that particular use case). However, it has a fairly simple extension to N/N+M recovery. Arrange the data in an NxM grid, and construct M sets of "extra" packets". The first set is constructed row wise, (effectivly devolving into the above case). For the second set, rotate each of the columns by their column index. So if R(x,y) is a redundant packet, and D(x,y) is a data packet at location (x,y) in the grid, you would have * R(0,0) = D(0,0) ^ D(1,0) ^ D(2,0) ^ ... D(N,0) * R(0,1) = D(0,1) ^ D(1,1) ^ D(2,1) ^ ... D(N,1) ... * R(0,M-1) = D(0,M-1) ^ D(1,M-1) ^ D(2,M-1) ^ ... D(N,M-1) * R(1,0) = D(0,0) ^ D(1,1) ^ D(2,2) ^ ... D(N,N%M) * R(1,1) = D(0,1) ^ D(1,2) ^ D(2,3) ^ ... D(N,(N+1)%M) * R(1,M-1) = D(0,M-1) ^ D(1,0) ^ D(2,1) ^ ... D(N,(N+1)%M) ... * R(2,0) = D(0,0) ^ D(1,2) ^ D(2,4) ^ ... D(N,2N%M) * R(3,0) = D(0,0) ^ D(1,3) ^ D(2,6) ^ ... D(N,3N%M) Your overhead is now M XOR operations per unit of real data, which is still trivial for reasonable values of M. The downside of this scheme is that if the first redundancy packet is not enough to reconstruct the dropped packet, you need to wait for the entire NxM table to be sent, which could cause a significant long-tail spike in latency if you are not careful. (The upside of this downside, is it provides even stronger burst protection that a traditional K-of-M erasure coding. If you get even more creative with how you group packets for the extra redundancy packets, you can get even stronger burst protection). The other downside is you end up being less space efficient than Reed-Solomon error correction. Interestingly, the recovery algorithm I described is not optimal in the sense that there are times where it fails to recover data that is theoretically recoverable. Recovering data in all theoretically possible cases probably would be quite intensive.