reth_engine_tree/tree/
block_buffer.rs

1use crate::tree::metrics::BlockBufferMetrics;
2use alloy_consensus::BlockHeader;
3use alloy_primitives::{BlockHash, BlockNumber};
4use indexmap::IndexSet;
5use reth_primitives_traits::{Block, SealedBlock};
6use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};
7
8/// Contains the tree of pending blocks that cannot be executed due to missing parent.
9/// It allows to store unconnected blocks for potential future inclusion.
10///
11/// The buffer has three main functionalities:
12/// * [`BlockBuffer::insert_block`] for inserting blocks inside the buffer.
13/// * [`BlockBuffer::remove_block_with_children`] for connecting blocks if the parent gets received
14///   and inserted.
15/// * [`BlockBuffer::remove_old_blocks`] to remove old blocks that precede the finalized number.
16///
17/// Note: Buffer is limited by number of blocks that it can contain and eviction of the block
18/// is done in FIFO order (oldest inserted block is evicted first).
19#[derive(Debug)]
20pub struct BlockBuffer<B: Block> {
21    /// All blocks in the buffer stored by their block hash.
22    pub(crate) blocks: HashMap<BlockHash, SealedBlock<B>>,
23    /// Map of any parent block hash (even the ones not currently in the buffer)
24    /// to the buffered children.
25    /// Allows connecting buffered blocks by parent.
26    pub(crate) parent_to_child: HashMap<BlockHash, IndexSet<BlockHash>>,
27    /// `BTreeMap` tracking the earliest blocks by block number.
28    /// Used for removal of old blocks that precede finalization.
29    pub(crate) earliest_blocks: BTreeMap<BlockNumber, HashSet<BlockHash>>,
30    /// FIFO queue tracking block insertion order for eviction.
31    /// When the buffer reaches its capacity limit, the oldest block is evicted first.
32    pub(crate) block_queue: VecDeque<BlockHash>,
33    /// Maximum number of blocks that can be stored in the buffer
34    pub(crate) max_blocks: usize,
35    /// Various metrics for the block buffer.
36    pub(crate) metrics: BlockBufferMetrics,
37}
38
39impl<B: Block> BlockBuffer<B> {
40    /// Create new buffer with max limit of blocks
41    pub fn new(limit: u32) -> Self {
42        Self {
43            blocks: Default::default(),
44            parent_to_child: Default::default(),
45            earliest_blocks: Default::default(),
46            block_queue: VecDeque::default(),
47            max_blocks: limit as usize,
48            metrics: Default::default(),
49        }
50    }
51
52    /// Return reference to the requested block.
53    pub fn block(&self, hash: &BlockHash) -> Option<&SealedBlock<B>> {
54        self.blocks.get(hash)
55    }
56
57    /// Return a reference to the lowest ancestor of the given block in the buffer.
58    pub fn lowest_ancestor(&self, hash: &BlockHash) -> Option<&SealedBlock<B>> {
59        let mut current_block = self.blocks.get(hash)?;
60        while let Some(parent) = self.blocks.get(&current_block.parent_hash()) {
61            current_block = parent;
62        }
63        Some(current_block)
64    }
65
66    /// Insert a correct block inside the buffer.
67    pub fn insert_block(&mut self, block: SealedBlock<B>) {
68        let hash = block.hash();
69
70        match self.blocks.entry(hash) {
71            std::collections::hash_map::Entry::Occupied(_) => return,
72            std::collections::hash_map::Entry::Vacant(entry) => {
73                self.parent_to_child.entry(block.parent_hash()).or_default().insert(hash);
74                self.earliest_blocks.entry(block.number()).or_default().insert(hash);
75                entry.insert(block);
76            }
77        };
78
79        // Add block to FIFO queue and handle eviction if needed
80        if self.block_queue.len() >= self.max_blocks {
81            // Evict oldest block if limit is hit
82            if let Some(evicted_hash) = self.block_queue.pop_front() {
83                self.remove_block(&evicted_hash);
84            }
85        }
86        self.block_queue.push_back(hash);
87        self.metrics.blocks.set(self.blocks.len() as f64);
88    }
89
90    /// Removes the given block from the buffer and also all the children of the block.
91    ///
92    /// This is used to get all the blocks that are dependent on the block that is included.
93    ///
94    /// Note: that order of returned blocks is important and the blocks with lower block number
95    /// in the chain will come first so that they can be executed in the correct order.
96    pub fn remove_block_with_children(&mut self, parent_hash: &BlockHash) -> Vec<SealedBlock<B>> {
97        let removed = self
98            .remove_block(parent_hash)
99            .into_iter()
100            .chain(self.remove_children(vec![*parent_hash]))
101            .collect();
102        self.metrics.blocks.set(self.blocks.len() as f64);
103        removed
104    }
105
106    /// Discard all blocks that precede block number from the buffer.
107    pub fn remove_old_blocks(&mut self, block_number: BlockNumber) {
108        let mut block_hashes_to_remove = Vec::new();
109
110        // discard all blocks that are before the finalized number.
111        while let Some(entry) = self.earliest_blocks.first_entry() {
112            if *entry.key() > block_number {
113                break
114            }
115            let block_hashes = entry.remove();
116            block_hashes_to_remove.extend(block_hashes);
117        }
118
119        // remove from other collections.
120        for block_hash in &block_hashes_to_remove {
121            // It's fine to call
122            self.remove_block(block_hash);
123        }
124
125        self.remove_children(block_hashes_to_remove);
126        self.metrics.blocks.set(self.blocks.len() as f64);
127    }
128
129    /// Remove block entry
130    fn remove_from_earliest_blocks(&mut self, number: BlockNumber, hash: &BlockHash) {
131        if let Some(entry) = self.earliest_blocks.get_mut(&number) {
132            entry.remove(hash);
133            if entry.is_empty() {
134                self.earliest_blocks.remove(&number);
135            }
136        }
137    }
138
139    /// Remove from parent child connection. This method does not remove children.
140    fn remove_from_parent(&mut self, parent_hash: BlockHash, hash: &BlockHash) {
141        // remove from parent to child connection, but only for this block parent.
142        if let Some(entry) = self.parent_to_child.get_mut(&parent_hash) {
143            entry.swap_remove(hash);
144            // if set is empty remove block entry.
145            if entry.is_empty() {
146                self.parent_to_child.remove(&parent_hash);
147            }
148        }
149    }
150
151    /// Removes block from inner collections.
152    /// This method will only remove the block if it's present inside `self.blocks`.
153    /// The block might be missing from other collections, the method will only ensure that it has
154    /// been removed.
155    fn remove_block(&mut self, hash: &BlockHash) -> Option<SealedBlock<B>> {
156        let block = self.blocks.remove(hash)?;
157        self.remove_from_earliest_blocks(block.number(), hash);
158        self.remove_from_parent(block.parent_hash(), hash);
159        self.block_queue.retain(|h| h != hash);
160        Some(block)
161    }
162
163    /// Remove all children and their descendants for the given blocks and return them.
164    fn remove_children(&mut self, parent_hashes: Vec<BlockHash>) -> Vec<SealedBlock<B>> {
165        // remove all parent child connection and all the child children blocks that are connected
166        // to the discarded parent blocks.
167        let mut remove_parent_children = parent_hashes;
168        let mut removed_blocks = Vec::new();
169        while let Some(parent_hash) = remove_parent_children.pop() {
170            // get this child blocks children and add them to the remove list.
171            if let Some(parent_children) = self.parent_to_child.remove(&parent_hash) {
172                // remove child from buffer
173                for child_hash in &parent_children {
174                    if let Some(block) = self.remove_block(child_hash) {
175                        removed_blocks.push(block);
176                    }
177                }
178                remove_parent_children.extend(parent_children);
179            }
180        }
181        removed_blocks
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188    use alloy_eips::BlockNumHash;
189    use alloy_primitives::BlockHash;
190    use reth_testing_utils::generators::{self, random_block, BlockParams, Rng};
191    use std::collections::HashMap;
192
193    /// Create random block with specified number and parent hash.
194    fn create_block<R: Rng>(
195        rng: &mut R,
196        number: u64,
197        parent: BlockHash,
198    ) -> SealedBlock<reth_ethereum_primitives::Block> {
199        random_block(rng, number, BlockParams { parent: Some(parent), ..Default::default() })
200    }
201
202    /// Assert that all buffer collections have the same data length.
203    fn assert_buffer_lengths<B: Block>(buffer: &BlockBuffer<B>, expected: usize) {
204        assert_eq!(buffer.blocks.len(), expected);
205        assert_eq!(buffer.block_queue.len(), expected);
206        assert_eq!(
207            buffer.parent_to_child.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
208            expected
209        );
210        assert_eq!(
211            buffer.earliest_blocks.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
212            expected
213        );
214    }
215
216    /// Assert that the block was removed from all buffer collections.
217    fn assert_block_removal<B: Block>(
218        buffer: &BlockBuffer<B>,
219        block: &SealedBlock<reth_ethereum_primitives::Block>,
220    ) {
221        assert!(!buffer.blocks.contains_key(&block.hash()));
222        assert!(buffer
223            .parent_to_child
224            .get(&block.parent_hash)
225            .and_then(|p| p.get(&block.hash()))
226            .is_none());
227        assert!(buffer
228            .earliest_blocks
229            .get(&block.number)
230            .and_then(|hashes| hashes.get(&block.hash()))
231            .is_none());
232    }
233
234    #[test]
235    fn simple_insertion() {
236        let mut rng = generators::rng();
237        let parent = rng.random();
238        let block1 = create_block(&mut rng, 10, parent);
239        let mut buffer = BlockBuffer::new(3);
240
241        buffer.insert_block(block1.clone());
242        assert_buffer_lengths(&buffer, 1);
243        assert_eq!(buffer.block(&block1.hash()), Some(&block1));
244    }
245
246    #[test]
247    fn take_entire_chain_of_children() {
248        let mut rng = generators::rng();
249
250        let main_parent_hash = rng.random();
251        let block1 = create_block(&mut rng, 10, main_parent_hash);
252        let block2 = create_block(&mut rng, 11, block1.hash());
253        let block3 = create_block(&mut rng, 12, block2.hash());
254        let parent4 = rng.random();
255        let block4 = create_block(&mut rng, 14, parent4);
256
257        let mut buffer = BlockBuffer::new(5);
258
259        buffer.insert_block(block1.clone());
260        buffer.insert_block(block2.clone());
261        buffer.insert_block(block3.clone());
262        buffer.insert_block(block4.clone());
263
264        assert_buffer_lengths(&buffer, 4);
265        assert_eq!(buffer.block(&block4.hash()), Some(&block4));
266        assert_eq!(buffer.block(&block2.hash()), Some(&block2));
267        assert_eq!(buffer.block(&main_parent_hash), None);
268
269        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
270        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
271        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
272        assert_eq!(
273            buffer.remove_block_with_children(&main_parent_hash),
274            vec![block1, block2, block3]
275        );
276        assert_buffer_lengths(&buffer, 1);
277    }
278
279    #[test]
280    fn take_all_multi_level_children() {
281        let mut rng = generators::rng();
282
283        let main_parent_hash = rng.random();
284        let block1 = create_block(&mut rng, 10, main_parent_hash);
285        let block2 = create_block(&mut rng, 11, block1.hash());
286        let block3 = create_block(&mut rng, 11, block1.hash());
287        let block4 = create_block(&mut rng, 12, block2.hash());
288
289        let mut buffer = BlockBuffer::new(5);
290
291        buffer.insert_block(block1.clone());
292        buffer.insert_block(block2.clone());
293        buffer.insert_block(block3.clone());
294        buffer.insert_block(block4.clone());
295
296        assert_buffer_lengths(&buffer, 4);
297        assert_eq!(
298            buffer
299                .remove_block_with_children(&main_parent_hash)
300                .into_iter()
301                .map(|b| (b.hash(), b))
302                .collect::<HashMap<_, _>>(),
303            HashMap::from([
304                (block1.hash(), block1),
305                (block2.hash(), block2),
306                (block3.hash(), block3),
307                (block4.hash(), block4)
308            ])
309        );
310        assert_buffer_lengths(&buffer, 0);
311    }
312
313    #[test]
314    fn take_block_with_children() {
315        let mut rng = generators::rng();
316
317        let main_parent = BlockNumHash::new(9, rng.random());
318        let block1 = create_block(&mut rng, 10, main_parent.hash);
319        let block2 = create_block(&mut rng, 11, block1.hash());
320        let block3 = create_block(&mut rng, 11, block1.hash());
321        let block4 = create_block(&mut rng, 12, block2.hash());
322
323        let mut buffer = BlockBuffer::new(5);
324
325        buffer.insert_block(block1.clone());
326        buffer.insert_block(block2.clone());
327        buffer.insert_block(block3.clone());
328        buffer.insert_block(block4.clone());
329
330        assert_buffer_lengths(&buffer, 4);
331        assert_eq!(
332            buffer
333                .remove_block_with_children(&block1.hash())
334                .into_iter()
335                .map(|b| (b.hash(), b))
336                .collect::<HashMap<_, _>>(),
337            HashMap::from([
338                (block1.hash(), block1),
339                (block2.hash(), block2),
340                (block3.hash(), block3),
341                (block4.hash(), block4)
342            ])
343        );
344        assert_buffer_lengths(&buffer, 0);
345    }
346
347    #[test]
348    fn remove_chain_of_children() {
349        let mut rng = generators::rng();
350
351        let main_parent = BlockNumHash::new(9, rng.random());
352        let block1 = create_block(&mut rng, 10, main_parent.hash);
353        let block2 = create_block(&mut rng, 11, block1.hash());
354        let block3 = create_block(&mut rng, 12, block2.hash());
355        let parent4 = rng.random();
356        let block4 = create_block(&mut rng, 14, parent4);
357
358        let mut buffer = BlockBuffer::new(5);
359
360        buffer.insert_block(block1.clone());
361        buffer.insert_block(block2);
362        buffer.insert_block(block3);
363        buffer.insert_block(block4);
364
365        assert_buffer_lengths(&buffer, 4);
366        buffer.remove_old_blocks(block1.number);
367        assert_buffer_lengths(&buffer, 1);
368    }
369
370    #[test]
371    fn remove_all_multi_level_children() {
372        let mut rng = generators::rng();
373
374        let main_parent = BlockNumHash::new(9, rng.random());
375        let block1 = create_block(&mut rng, 10, main_parent.hash);
376        let block2 = create_block(&mut rng, 11, block1.hash());
377        let block3 = create_block(&mut rng, 11, block1.hash());
378        let block4 = create_block(&mut rng, 12, block2.hash());
379
380        let mut buffer = BlockBuffer::new(5);
381
382        buffer.insert_block(block1.clone());
383        buffer.insert_block(block2);
384        buffer.insert_block(block3);
385        buffer.insert_block(block4);
386
387        assert_buffer_lengths(&buffer, 4);
388        buffer.remove_old_blocks(block1.number);
389        assert_buffer_lengths(&buffer, 0);
390    }
391
392    #[test]
393    fn remove_multi_chains() {
394        let mut rng = generators::rng();
395
396        let main_parent = BlockNumHash::new(9, rng.random());
397        let block1 = create_block(&mut rng, 10, main_parent.hash);
398        let block1a = create_block(&mut rng, 10, main_parent.hash);
399        let block2 = create_block(&mut rng, 11, block1.hash());
400        let block2a = create_block(&mut rng, 11, block1.hash());
401        let random_parent1 = rng.random();
402        let random_block1 = create_block(&mut rng, 10, random_parent1);
403        let random_parent2 = rng.random();
404        let random_block2 = create_block(&mut rng, 11, random_parent2);
405        let random_parent3 = rng.random();
406        let random_block3 = create_block(&mut rng, 12, random_parent3);
407
408        let mut buffer = BlockBuffer::new(10);
409
410        buffer.insert_block(block1.clone());
411        buffer.insert_block(block1a.clone());
412        buffer.insert_block(block2.clone());
413        buffer.insert_block(block2a.clone());
414        buffer.insert_block(random_block1.clone());
415        buffer.insert_block(random_block2.clone());
416        buffer.insert_block(random_block3.clone());
417
418        // check that random blocks are their own ancestor, and that chains have proper ancestors
419        assert_eq!(buffer.lowest_ancestor(&random_block1.hash()), Some(&random_block1));
420        assert_eq!(buffer.lowest_ancestor(&random_block2.hash()), Some(&random_block2));
421        assert_eq!(buffer.lowest_ancestor(&random_block3.hash()), Some(&random_block3));
422
423        // descendants have ancestors
424        assert_eq!(buffer.lowest_ancestor(&block2a.hash()), Some(&block1));
425        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
426
427        // roots are themselves
428        assert_eq!(buffer.lowest_ancestor(&block1a.hash()), Some(&block1a));
429        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
430
431        assert_buffer_lengths(&buffer, 7);
432        buffer.remove_old_blocks(10);
433        assert_buffer_lengths(&buffer, 2);
434    }
435
436    #[test]
437    fn evict_with_gap() {
438        let mut rng = generators::rng();
439
440        let main_parent = BlockNumHash::new(9, rng.random());
441        let block1 = create_block(&mut rng, 10, main_parent.hash);
442        let block2 = create_block(&mut rng, 11, block1.hash());
443        let block3 = create_block(&mut rng, 12, block2.hash());
444        let parent4 = rng.random();
445        let block4 = create_block(&mut rng, 13, parent4);
446
447        let mut buffer = BlockBuffer::new(3);
448
449        buffer.insert_block(block1.clone());
450        buffer.insert_block(block2.clone());
451        buffer.insert_block(block3.clone());
452
453        // pre-eviction block1 is the root
454        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
455        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
456        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
457
458        buffer.insert_block(block4.clone());
459
460        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
461
462        // block1 gets evicted
463        assert_block_removal(&buffer, &block1);
464
465        // check lowest ancestor results post eviction
466        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block2));
467        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
468        assert_eq!(buffer.lowest_ancestor(&block1.hash()), None);
469
470        assert_buffer_lengths(&buffer, 3);
471    }
472
473    #[test]
474    fn simple_eviction() {
475        let mut rng = generators::rng();
476
477        let main_parent = BlockNumHash::new(9, rng.random());
478        let block1 = create_block(&mut rng, 10, main_parent.hash);
479        let block2 = create_block(&mut rng, 11, block1.hash());
480        let block3 = create_block(&mut rng, 12, block2.hash());
481        let parent4 = rng.random();
482        let block4 = create_block(&mut rng, 13, parent4);
483
484        let mut buffer = BlockBuffer::new(3);
485
486        buffer.insert_block(block1.clone());
487        buffer.insert_block(block2);
488        buffer.insert_block(block3);
489        buffer.insert_block(block4);
490
491        // block3 gets evicted
492        assert_block_removal(&buffer, &block1);
493
494        assert_buffer_lengths(&buffer, 3);
495    }
496
497    #[test]
498    fn eviction_parent_child_cleanup() {
499        let mut rng = generators::rng();
500
501        let main_parent = BlockNumHash::new(9, rng.random());
502        let block1 = create_block(&mut rng, 10, main_parent.hash);
503        let block2 = create_block(&mut rng, 11, block1.hash());
504        // Unrelated block to trigger eviction
505        let unrelated_parent = rng.random();
506        let unrelated_block = create_block(&mut rng, 12, unrelated_parent);
507
508        // Capacity 2 so third insert evicts the oldest (block1)
509        let mut buffer = BlockBuffer::new(2);
510
511        buffer.insert_block(block1.clone());
512        buffer.insert_block(block2.clone());
513
514        // Pre-eviction: parent_to_child contains main_parent -> {block1}, block1 -> {block2}
515        assert!(buffer
516            .parent_to_child
517            .get(&main_parent.hash)
518            .and_then(|s| s.get(&block1.hash()))
519            .is_some());
520        assert!(buffer
521            .parent_to_child
522            .get(&block1.hash())
523            .and_then(|s| s.get(&block2.hash()))
524            .is_some());
525
526        // Insert unrelated block to evict block1
527        buffer.insert_block(unrelated_block);
528
529        // Evicted block1 should be fully removed from collections
530        assert_block_removal(&buffer, &block1);
531
532        // Cleanup: parent_to_child must no longer have (main_parent -> block1)
533        assert!(buffer
534            .parent_to_child
535            .get(&main_parent.hash)
536            .and_then(|s| s.get(&block1.hash()))
537            .is_none());
538
539        // But the mapping (block1 -> block2) must remain so descendants can still be tracked
540        assert!(buffer
541            .parent_to_child
542            .get(&block1.hash())
543            .and_then(|s| s.get(&block2.hash()))
544            .is_some());
545
546        // And lowest ancestor for block2 becomes itself after its parent is evicted
547        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
548    }
549}
reth_engine_tree/tree/block_buffer.rs

reth_engine_tree/tree/
block_buffer.rs
