Repository: paradigmxyz/reth (language: rust)

Issue:
Replace LRU with simple FIFO queue for block tracking
### Describe the feature

in the https://github.com/paradigmxyz/reth/blob/main/crates/engine/tree/src/tree/block_buffer.rs currently the:
The BlockBuffer uses an LRU map (LruMap<BlockHash, ()>) to track block hashes with 
a maximum size limit. Since this is for tracking pending unconnected blocks, the 
limit is likely small. For small limits (a hundred blocks), a simple Vec 
could work just as well:

but the thing is I want to benchmark this first, but I don't want to assume the limit
any help with the limit @mattsse 

### Additional context

_No response_


Discussion / hints:
that makes sense,
no need to benchmark this one, this should indeed be simplified as suggested

the expected max limit is ~2epoch so around 100 blocks, usually much smaller
This issue is stale because it has been open for 21 days with no activity.
@malik672 do you wanna do this?
else I can take this up :)
> [@malik672](https://github.com/malik672) do you wanna do this? else I can take this up :)

do it if you want to
I'm quite hooked

Fix patch:
diff --git a/crates/engine/tree/src/tree/block_buffer.rs b/crates/engine/tree/src/tree/block_buffer.rs
index 4a0fede28f78..8c421430ad6e 100644
--- a/crates/engine/tree/src/tree/block_buffer.rs
+++ b/crates/engine/tree/src/tree/block_buffer.rs
@@ -2,8 +2,7 @@ use crate::tree::metrics::BlockBufferMetrics;
 use alloy_consensus::BlockHeader;
 use alloy_primitives::{BlockHash, BlockNumber};
 use reth_primitives_traits::{Block, RecoveredBlock};
-use schnellru::{ByLength, LruMap};
-use std::collections::{BTreeMap, HashMap, HashSet};
+use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};
 
 /// Contains the tree of pending blocks that cannot be executed due to missing parent.
 /// It allows to store unconnected blocks for potential future inclusion.
@@ -27,11 +26,11 @@ pub struct BlockBuffer<B: Block> {
     /// `BTreeMap` tracking the earliest blocks by block number.
     /// Used for removal of old blocks that precede finalization.
     pub(crate) earliest_blocks: BTreeMap<BlockNumber, HashSet<BlockHash>>,
-    /// LRU used for tracing oldest inserted blocks that are going to be
-    /// first in line for evicting if `max_blocks` limit is hit.
-    ///
-    /// Used as counter of amount of blocks inside buffer.
-    pub(crate) lru: LruMap<BlockHash, ()>,
+    /// FIFO queue tracking block insertion order for eviction.
+    /// When the buffer reaches its capacity limit, the oldest block is evicted first.
+    pub(crate) block_queue: VecDeque<BlockHash>,
+    /// Maximum number of blocks that can be stored in the buffer
+    pub(crate) max_blocks: usize,
     /// Various metrics for the block buffer.
     pub(crate) metrics: BlockBufferMetrics,
 }
@@ -43,7 +42,8 @@ impl<B: Block> BlockBuffer<B> {
             blocks: Default::default(),
             parent_to_child: Default::default(),
             earliest_blocks: Default::default(),
-            lru: LruMap::new(ByLength::new(limit)),
+            block_queue: VecDeque::default(),
+            max_blocks: limit as usize,
             metrics: Default::default(),
         }
     }
@@ -70,28 +70,19 @@ impl<B: Block> BlockBuffer<B> {
         self.earliest_blocks.entry(block.number()).or_default().insert(hash);
         self.blocks.insert(hash, block);
 
-        if let Some(evicted_hash) = self.insert_hash_and_get_evicted(hash) {
-            // evict the block if limit is hit
-            if let Some(evicted_block) = self.remove_block(&evicted_hash) {
-                // evict the block if limit is hit
-                self.remove_from_parent(evicted_block.parent_hash(), &evicted_hash);
+        // Add block to FIFO queue and handle eviction if needed
+        if self.block_queue.len() >= self.max_blocks {
+            // Evict oldest block if limit is hit
+            if let Some(evicted_hash) = self.block_queue.pop_front() {
+                if let Some(evicted_block) = self.remove_block(&evicted_hash) {
+                    self.remove_from_parent(evicted_block.parent_hash(), &evicted_hash);
+                }
             }
         }
+        self.block_queue.push_back(hash);
         self.metrics.blocks.set(self.blocks.len() as f64);
     }
 
-    /// Inserts the hash and returns the oldest evicted hash if any.
-    fn insert_hash_and_get_evicted(&mut self, entry: BlockHash) -> Option<BlockHash> {
-        let new = self.lru.peek(&entry).is_none();
-        let evicted = if new && self.lru.limiter().max_length() as usize <= self.lru.len() {
-            self.lru.pop_oldest().map(|(k, ())| k)
-        } else {
-            None
-        };
-        self.lru.get_or_insert(entry, || ());
-        evicted
-    }
-
     /// Removes the given block from the buffer and also all the children of the block.
     ///
     /// This is used to get all the blocks that are dependent on the block that is included.
@@ -164,7 +155,7 @@ impl<B: Block> BlockBuffer<B> {
         let block = self.blocks.remove(hash)?;
         self.remove_from_earliest_blocks(block.number(), hash);
         self.remove_from_parent(block.parent_hash(), hash);
-        self.lru.remove(hash);
+        self.block_queue.retain(|h| h != hash);
         Some(block)
     }
 
@@ -213,7 +204,7 @@ mod tests {
     /// Assert that all buffer collections have the same data length.
     fn assert_buffer_lengths<B: Block>(buffer: &BlockBuffer<B>, expected: usize) {
         assert_eq!(buffer.blocks.len(), expected);
-        assert_eq!(buffer.lru.len(), expected);
+        assert_eq!(buffer.block_queue.len(), expected);
         assert_eq!(
             buffer.parent_to_child.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
             expected


Test patch: