Order and buffer data shreds

Order only data indices

After authentication and optional recovery, send data shreds into a per-slot ordering buffer. Coding shreds never enter this stream. Order by the data-shred index field, not arrival time, FEC-set index, or coding position.

UDP can duplicate and reorder packets. FEC recovery can produce an earlier missing data index after later indices are already buffered. A BTreeMap<u32, DataShred> is an adequate first structure. A bounded sparse ring is faster when maximum reorder distance and slot limits are known.

Emit at completion boundaries

The DATA_COMPLETE_SHRED flag means the current data shred ends one serialized data unit. LAST_SHRED_IN_SLOT includes the data-complete bits and also marks the proposed slot end. Deshred a consecutive range as soon as its final member has data complete. Do not wait for the whole slot.

The next range begins at the following data index. A data-complete flag does not permit a gap before it. Missing indices must arrive or be recovered.

use std::{collections::BTreeMap, mem};

#[derive(Debug)]
struct Data { index: u32, data_complete: bool, bytes: Vec<u8> }

struct SlotOrder {
    next: u32,
    pending: BTreeMap<u32, Data>,
    current: Vec<Data>,
}

impl SlotOrder {
    fn insert(&mut self, item: Data) -> Result<Vec<Vec<Data>>, &'static str> {
        if item.index < self.next { return Ok(Vec::new()); }
        if self.pending.insert(item.index, item).is_some() {
            return Err("duplicate data index reached ordering stage");
        }
        let mut ready = Vec::new();
        while let Some(item) = self.pending.remove(&self.next) {
            self.next = self.next.checked_add(1).ok_or("data index overflow")?;
            let complete = item.data_complete;
            self.current.push(item);
            if complete { ready.push(mem::take(&mut self.current)); }
        }
        Ok(ready)
    }
}

fn main() {
    let mut s = SlotOrder { next: 0, pending: BTreeMap::new(), current: Vec::new() };
    let first = s.insert(Data { index: 1, data_complete: true, bytes: Vec::from([2]) }).unwrap();
    if first.is_empty() == false { std::process::exit(1); }
    let ready = s.insert(Data { index: 0, data_complete: false, bytes: Vec::from([1]) }).unwrap();
    if (ready[0].len() == 2 && ready[0][0].bytes == Vec::from([1])) == false {
        std::process::exit(1);
    }
}

The ordering stage should retain complete serialized shred payloads because Shredder::deshred validates indices and flags and uses the variant-correct data accessor. Do not concatenate bytes[88..] in this model.

Establish the first expected index

A receiver that observes a new slot from its beginning expects data index zero. If the process starts mid-slot and first sees index 40, it cannot know that index 40 begins a serialized unit. Buffering from 40 and decoding at the next completion flag may start inside a serialized value.

For a fresh process, wait for data index zero or wait for the next slot with index zero. You may also start after a trusted prior DATA_COMPLETE_SHRED boundary if the boundary member itself and following sequence are available. Do not guess a boundary from successful partial deserialization.

After emitting a range, next already points at the following index. Track the last emitted boundary so duplicate and late packets below it are discarded cheaply.

Coordinate FEC and ordering state

An FEC set and a serialized data range are not the same unit. A range can cross FEC-set boundaries, and one set can contain more than one completion boundary. Feed every complete or recovered data shred into the same per-slot index stream.

Mark whether an item was received or recovered for metrics, but its ordering semantics are identical after verification. If two recovery paths claim different content for one index, stop and report a conflict before ordering.

Bound the reorder window

Limit pending indices per slot, active slots, total bytes, and age. Also reject indices beyond protocol maximums from the pinned Agave release. A malformed high index must not force a vector to allocate gigabytes.

When a slot buffer expires with a gap, record the missing interval, highest observed index, last completion boundary, whether last-in-slot arrived, and related FEC outcomes. Evict the whole undecodable tail. Keeping later indices after their required prefix is permanently gone only consumes memory.

Forks can produce multiple authenticated proposals for a slot. A basic receiver can quarantine conflicting shred IDs. A fork-aware system needs a block identity or root path beyond numeric slot before combining data. Never merge members with different authenticated roots or duplicate evidence into one byte stream.

Preserve arrival timing

Carry the earliest receive timestamp for a completed range and per-shred timestamps if fine-grained latency attribution matters. Decode latency should be measured from first or relevant packet arrival, not from the moment ordering completed. A late missing member can dominate the range's time.

Test ordering

Generate a valid range and submit indices in order, reverse order, random order, with exact duplicates removed, and with one index supplied by recovery. Test multiple boundaries in one slot and one boundary crossing two FEC sets. Verify no range emits before every consecutive member is present.

Test receiver startup at a mid-range index, missing index zero, duplicate after emission, index overflow, large invalid index, slot expiry, and last-in-slot without a preceding gap filled. Entry decoding should receive exactly one ordered range per completion boundary.