Index packets by priority to evict packet_batch when buffer reaches max limit

[tao-stones]

Problem

When buffer in banking_stage reaches its max limit, instead of poping the oldest packet_batch which may contain high priority packets, it should drop low priority packets first.

For context, by default the buffer has max limit of 2000 packet_batches, each packet_batch could have 128 packets. A buffer therefore can have up to 256_000 packets. In order to drop low priority packets first, they need to be somehow indexed.

The issue is when (and how) to index them.

Proposed Solution

There are two approaches, and maybe some combinations in between:

1. Eagerly indexing packets - packet_index is maintained for every packet_batch added or removed from buffer. So it is ready identify low priority packets when buffer reaches its limit;
2. lazily indexing packets - only when buffer reaches max limit, it'll scan the entire buffer to build index; index is disposed after use.

The choice would depend on how frequently buffer reaches its limit. Metrics indicates spikes in dropped packets during IDO/NFT, example

Purple is received packets count, Blue is dropped number of packets.

There are maybe other approaches, welcome inputs.

[tao-stones]

#23841 implemented approach#2, I am bench testing it with differently scenarios, will report back the results.

[tao-stones]

@carllin has a neat suggestion about approach#1 at #23841 (comment), essentially to update index (a min-max heap) for every received packets.

[tao-stones]

#23841 implemented approach#2, I am bench testing it with differently scenarios, will report back the results.

the bench tests here test the performance of insert_batch to an buffer below and beyond its capacity, the latter case invokes the overhead of indexing packets in buffer by fee priority and search of batch to drop. If the packets priority is randomized, the overhead is averaged to 12% by inserting 100 batches to saturated buffer.

Incorporated Carl's bench scenario, where packets have uniformly distributed priority in each batch. It is the worst possible scenario for dropping batch by priority, cause algo has to iterated through n_batchs * m_packets before finding a batch that contains no more unprocessed packets. In that test, inserting 100 more batches to saturated buffer has overhead of 80%!

[tao-stones]

@carllin has a neat suggestion about approach#1 at #23841 (comment), essentially to update index (a min-max heap) for every received packets.

here is a poc for approach 1: eagerly maintain an active per-packet priority index (as MinMaxHeap). Few design notes:

• Buffer will no longer a collection of Batch, but defined as pub struct Buffer(VecDeque<Rc<RefCell<Batch>>>);. This allows batch also be weakly referenced by unprocessed_packets it holds, as below:
• struct Batch owns a HashMap of unprocessed packets on top of whatever it needs to have (which is nil in this poc); these unprocessed packet hold a ref back to their owner - Batch, like this

#[derive(Debug, Default)]
pub struct Batch {
    packets: HashMap<usize, Rc<Packet>>, // batch owns packet strongly
}

// Packet has week ref to its owner
#[derive(Debug, Default)]
pub struct Packet {
    priority: u64,
    index: usize, // same usize used in HashMap key in batch
    owner: Weak<RefCell<Batch>>, // packet ref to batch weakly
}

• So the per-packet priority index pub type Index = MinMaxHeap<Rc<Packet>>; allows quickly pop low priority packet from index, then directly ref back to its Batch to remove that packet from buffer and other necessary ops without additional lookup, like this.
• this test demonstrates use site code

[tao-stones]

After applying the PoC to UnprocessPacketsBatches, the results of same bench tests are:

• with randomized priority, the overhead is 8.1% (compare to 12%)
• with uniformly distributed priority (eg. the worst scenario), the overhead is now 12.1% (compare to 80%)

This indicates that MinMaxHeap based index over PacketBatch is a viable option.