Often coding shred count in an FEC block is not maximum

[pgarg66]

Problem

Currently we are using 32:32 erasure ratio. This guarantees that for every 32 data shreds, there'll be 32 coding shreds.

However, the number of data shreds could be less than 32. For example, at end of a slot the last entries may not yield 32 data shreds. Or, in an idling cluster, we generate 64 ticks per 400ms slot. That'll yield 32 data shreds every 200ms. We do not wait to accumulate 32 data shreds to generate 32 coding shreds.

The current code cannot generate more coding shreds than data shreds in a given FEC block. This is because the coding shreds share the same indexing space as data shreds. The first coding shred in an FEC block has the same index as the first data shred in that block. If there were more coding shreds than data shreds in a block, that'll cause the coding shred index to overflow data shred index space. This will either cause the coding index in current block to overlap with the data index in the next FEC block, or leave holes in data index address space. Neither of these approach will work.

Due to this, maximum number of coding shreds = number of data shreds in the FEC block. So occasionally, there's only 1 coding shred is generated in a FEC block. This is not enough for erasure recovery for missing data. We need a mechanism through which we can still generate 32 coding shreds independent of number of data shreds in the block.

Proposed Solution

Considered following solutions.

1. Wait for 32 data shreds before generating coding shreds. Let data shreds be transmitted as they are created, but don't generate/transmit coding shreds until we have 32 data shreds. For the end of slot, generate padding data shreds to fill up 32 data shred limit.
2. Decouple index space for coding shreds from data shreds. Don't assume first coding shred index = first data shred index. Wait for certain time to accumulate 32 data shreds (e.g. N msec). If not enough data shreds are created, generate 32 coding shreds from current set of data shreds.

The 1st solution will trigger more repairs in an idling network with packet drops. As we'll wait almost half the slot before generating/transmitting coding shreds. Repair will kick in even before the coding shreds are transmitted. This will have adverse effect on overall network traffic and confirmation times.

At this point, 2nd seems a more comprehensive solution. It does have a design impact on shred data structure. Need to analyze it further.

tag: @aeyakovenko

[garious]

Beautifully written, thanks! More recon on option 2 sounds good to me. Seems worthy of a design proposal too. "Decoupled Coding Shreds"?

[aeyakovenko]

The odd side effects of this bug is that we have higher availability under load.

This is why we are seeing much larger than expected lost blocks when a small amount of stake is missing from the network. Any small batch of shreds like 2:2 fails in a block, that block will only succeed if repair succeeds.

[pgarg66]

Beautifully written, thanks! More recon on option 2 sounds good to me. Seems worthy of a design proposal too. "Decoupled Coding Shreds"?

Sounds good @garious

[pgarg66]

The issue was fixed with #7474