Replace reed solomon implementation in turbine

[alexpyattaev]

Problem

Our reed-solomon impl is somewhat slow

Proposed Solution

Look at the available crates and bench them to make sure we have a decent impl

Also this is available https://github.com/firedancer-io/firedancer/blob/d7e947aa1049f66f3dcd23199bbcc48d81239110/src/ballet/reedsol/fd_reedsol_gfni_32.S#L16

[leafaar]

give me this issue

[alexpyattaev]

give me this issue

Thank you for looking into this!

[kskalski]

Looks like the library we are using right now is not maintained ("looking for new maintainers" explicitly stated in description), though I see rust-rse/reed-solomon-erasure#115 that was also mentioned in core-technology discord, but not sure there will be anyone to review and merge it.

There are some newer libraries like
https://crates.io/crates/reed-solomon-simd
and
https://crates.io/crates/reed_solomon_rs
it would be cool to benchmark against them.

[leafaar]

Indeed, my goal was to either use this reed-solomon-simd or try to use fd implementation, but first I want to benchmark and analyze in our network what is the time spent on the FEC and how many shreds get recovered.

[vkomenda]

https://github.com/vkomenda/rse-aes is my WIP using AVX512 GFNI instructions. At the moment it's using a different polynomial field to that of the Solana client though. The FFT butterfly can be implemented to return to the same field.

[vkomenda]

Indeed, my goal was to either use this reed-solomon-simd or try to use fd implementation, but first I want to benchmark and analyze in our network what is the time spent on the FEC and how many shreds get recovered.

I'm porting the fd C implementation to Rust. When it's ready, would you like to compare it as well?

One thing I I'm curious about: Would Anza prefer to

1. keep the same behaviour of the codec - same field, same encoder matrix computation, similar shred number and sizes, just more efficient, or
2. would you rather introduce a new shred version for a different codec if improving the old codec proves challenging? The parity shard content will be incompatible with the current codec and will require a new decoder.

Now the shredder works in GF_{2^8} modulo the polynomial 0x11d.

AVX512 GFNI instructions work over GF_(2^8) modulo the polynomial 0x11b (AES field). However there is a way to use them modulo 0x11d as the fd C implementation shows.

reed-solomon-simd works in GF_{2^16} and so is quite different.

There may be other tradeoffs such as deprecating certain platforms, for example.

[leafaar]

I'm porting the fd C implementation to Rust. When it's ready, would you like to compare it as well?

Absolutely.

I can't answer this one, but I assume if they would have such change it would impact and change a lot of the code (I am not sure how much tbh), and if that were to happen this would change from a low hanging fruit to something more complex that would take more time to merge. Again I don't know if that's the case but if it were I think it would be better to first change something that is compatible and after this one we could evaluate if its worth the other changes. What do you think, does it makes sense?

[vkomenda]

I can't answer this one, but I assume if they would have such change it would impact and change a lot of the code (I am not sure how much tbh), and if that were to happen this would change from a low hanging fruit to something more complex that would take more time to merge. Again I don't know if that's the case but if it were I think it would be better to first change something that is compatible and after this one we could evaluate if its worth the other changes. What do you think, does it makes sense?

I think this makes sense. This is my reasoning too for starting with a dependency upgrade and keeping the same interface.

Introducing multiple concurrent shred coding versions is a high-level architectural decision only possible for an insider.

[alexpyattaev]

Changing the code structure / polynomial in an incompatible way requires a SIMD to be filed. We are always open to such changes if they bring substantial performance benefits.

At this point I believe it is critical that we stop using the inefficient implementation. Once it is done, we can revisit the question of code structure and improve that as well. We may also consider increasing the RS block size to 128 at that point (as that improves packet loss resilience).

[vkomenda]

We may also consider increasing the RS block size to 128 at that point (as that improves packet loss resilience).

Do you mean a change to 64 data shreds + 64 parity shreds?

[alexpyattaev]

We may also consider increasing the RS block size to 128 at that point (as that improves packet loss resilience).

Do you mean a change to 64 data shreds + 64 parity shreds?

Yes. But for that we need to ~2x the average TPS on the cluster, else we end up with too much padding bytes and/or high latency. Gotta bring those users in.

[vkomenda]

Here is the FFT butterfly WIP https://github.com/vkomenda/buttrs. It's naive ATM. I'm going to add SIMD later on.

[alexpyattaev]

@leafaar do you have some preliminary benchmarking data/scripts that you can share? Would be nice to get a feel for how far off we are when compared to firedancer and e.g. whatever CEPH uses.

[leafaar]

I am not using any scripts/profiling at the moment, recently I was looking at InfluxDB to have a better image of what are the actual number of shreds that are recovered and how many get inserted, this is the data I got:

This week, I will start looking at changing crates and having a better view of what's actually going on with the recover, and I can share better data.