reth_engine_tree/tree/
block_buffer.rs

1use crate::tree::metrics::BlockBufferMetrics;
2use alloy_consensus::BlockHeader;
3use alloy_primitives::{BlockHash, BlockNumber};
4use reth_primitives_traits::{Block, RecoveredBlock};
5use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};
6
7/// Contains the tree of pending blocks that cannot be executed due to missing parent.
8/// It allows to store unconnected blocks for potential future inclusion.
9///
10/// The buffer has three main functionalities:
11/// * [`BlockBuffer::insert_block`] for inserting blocks inside the buffer.
12/// * [`BlockBuffer::remove_block_with_children`] for connecting blocks if the parent gets received
13///   and inserted.
14/// * [`BlockBuffer::remove_old_blocks`] to remove old blocks that precede the finalized number.
15///
16/// Note: Buffer is limited by number of blocks that it can contain and eviction of the block
17/// is done by last recently used block.
18#[derive(Debug)]
19pub struct BlockBuffer<B: Block> {
20    /// All blocks in the buffer stored by their block hash.
21    pub(crate) blocks: HashMap<BlockHash, RecoveredBlock<B>>,
22    /// Map of any parent block hash (even the ones not currently in the buffer)
23    /// to the buffered children.
24    /// Allows connecting buffered blocks by parent.
25    pub(crate) parent_to_child: HashMap<BlockHash, HashSet<BlockHash>>,
26    /// `BTreeMap` tracking the earliest blocks by block number.
27    /// Used for removal of old blocks that precede finalization.
28    pub(crate) earliest_blocks: BTreeMap<BlockNumber, HashSet<BlockHash>>,
29    /// FIFO queue tracking block insertion order for eviction.
30    /// When the buffer reaches its capacity limit, the oldest block is evicted first.
31    pub(crate) block_queue: VecDeque<BlockHash>,
32    /// Maximum number of blocks that can be stored in the buffer
33    pub(crate) max_blocks: usize,
34    /// Various metrics for the block buffer.
35    pub(crate) metrics: BlockBufferMetrics,
36}
37
38impl<B: Block> BlockBuffer<B> {
39    /// Create new buffer with max limit of blocks
40    pub fn new(limit: u32) -> Self {
41        Self {
42            blocks: Default::default(),
43            parent_to_child: Default::default(),
44            earliest_blocks: Default::default(),
45            block_queue: VecDeque::default(),
46            max_blocks: limit as usize,
47            metrics: Default::default(),
48        }
49    }
50
51    /// Return reference to the requested block.
52    pub fn block(&self, hash: &BlockHash) -> Option<&RecoveredBlock<B>> {
53        self.blocks.get(hash)
54    }
55
56    /// Return a reference to the lowest ancestor of the given block in the buffer.
57    pub fn lowest_ancestor(&self, hash: &BlockHash) -> Option<&RecoveredBlock<B>> {
58        let mut current_block = self.blocks.get(hash)?;
59        while let Some(parent) = self.blocks.get(&current_block.parent_hash()) {
60            current_block = parent;
61        }
62        Some(current_block)
63    }
64
65    /// Insert a correct block inside the buffer.
66    pub fn insert_block(&mut self, block: RecoveredBlock<B>) {
67        let hash = block.hash();
68
69        self.parent_to_child.entry(block.parent_hash()).or_default().insert(hash);
70        self.earliest_blocks.entry(block.number()).or_default().insert(hash);
71        self.blocks.insert(hash, block);
72
73        // Add block to FIFO queue and handle eviction if needed
74        if self.block_queue.len() >= self.max_blocks {
75            // Evict oldest block if limit is hit
76            if let Some(evicted_hash) = self.block_queue.pop_front() {
77                self.remove_block(&evicted_hash);
78            }
79        }
80        self.block_queue.push_back(hash);
81        self.metrics.blocks.set(self.blocks.len() as f64);
82    }
83
84    /// Removes the given block from the buffer and also all the children of the block.
85    ///
86    /// This is used to get all the blocks that are dependent on the block that is included.
87    ///
88    /// Note: that order of returned blocks is important and the blocks with lower block number
89    /// in the chain will come first so that they can be executed in the correct order.
90    pub fn remove_block_with_children(
91        &mut self,
92        parent_hash: &BlockHash,
93    ) -> Vec<RecoveredBlock<B>> {
94        let removed = self
95            .remove_block(parent_hash)
96            .into_iter()
97            .chain(self.remove_children(vec![*parent_hash]))
98            .collect();
99        self.metrics.blocks.set(self.blocks.len() as f64);
100        removed
101    }
102
103    /// Discard all blocks that precede block number from the buffer.
104    pub fn remove_old_blocks(&mut self, block_number: BlockNumber) {
105        let mut block_hashes_to_remove = Vec::new();
106
107        // discard all blocks that are before the finalized number.
108        while let Some(entry) = self.earliest_blocks.first_entry() {
109            if *entry.key() > block_number {
110                break
111            }
112            let block_hashes = entry.remove();
113            block_hashes_to_remove.extend(block_hashes);
114        }
115
116        // remove from other collections.
117        for block_hash in &block_hashes_to_remove {
118            // It's fine to call
119            self.remove_block(block_hash);
120        }
121
122        self.remove_children(block_hashes_to_remove);
123        self.metrics.blocks.set(self.blocks.len() as f64);
124    }
125
126    /// Remove block entry
127    fn remove_from_earliest_blocks(&mut self, number: BlockNumber, hash: &BlockHash) {
128        if let Some(entry) = self.earliest_blocks.get_mut(&number) {
129            entry.remove(hash);
130            if entry.is_empty() {
131                self.earliest_blocks.remove(&number);
132            }
133        }
134    }
135
136    /// Remove from parent child connection. This method does not remove children.
137    fn remove_from_parent(&mut self, parent_hash: BlockHash, hash: &BlockHash) {
138        // remove from parent to child connection, but only for this block parent.
139        if let Some(entry) = self.parent_to_child.get_mut(&parent_hash) {
140            entry.remove(hash);
141            // if set is empty remove block entry.
142            if entry.is_empty() {
143                self.parent_to_child.remove(&parent_hash);
144            }
145        }
146    }
147
148    /// Removes block from inner collections.
149    /// This method will only remove the block if it's present inside `self.blocks`.
150    /// The block might be missing from other collections, the method will only ensure that it has
151    /// been removed.
152    fn remove_block(&mut self, hash: &BlockHash) -> Option<RecoveredBlock<B>> {
153        let block = self.blocks.remove(hash)?;
154        self.remove_from_earliest_blocks(block.number(), hash);
155        self.remove_from_parent(block.parent_hash(), hash);
156        self.block_queue.retain(|h| h != hash);
157        Some(block)
158    }
159
160    /// Remove all children and their descendants for the given blocks and return them.
161    fn remove_children(&mut self, parent_hashes: Vec<BlockHash>) -> Vec<RecoveredBlock<B>> {
162        // remove all parent child connection and all the child children blocks that are connected
163        // to the discarded parent blocks.
164        let mut remove_parent_children = parent_hashes;
165        let mut removed_blocks = Vec::new();
166        while let Some(parent_hash) = remove_parent_children.pop() {
167            // get this child blocks children and add them to the remove list.
168            if let Some(parent_children) = self.parent_to_child.remove(&parent_hash) {
169                // remove child from buffer
170                for child_hash in &parent_children {
171                    if let Some(block) = self.remove_block(child_hash) {
172                        removed_blocks.push(block);
173                    }
174                }
175                remove_parent_children.extend(parent_children);
176            }
177        }
178        removed_blocks
179    }
180}
181
182#[cfg(test)]
183mod tests {
184    use super::*;
185    use alloy_eips::BlockNumHash;
186    use alloy_primitives::BlockHash;
187    use reth_primitives_traits::RecoveredBlock;
188    use reth_testing_utils::generators::{self, random_block, BlockParams, Rng};
189    use std::collections::HashMap;
190
191    /// Create random block with specified number and parent hash.
192    fn create_block<R: Rng>(
193        rng: &mut R,
194        number: u64,
195        parent: BlockHash,
196    ) -> RecoveredBlock<reth_ethereum_primitives::Block> {
197        let block =
198            random_block(rng, number, BlockParams { parent: Some(parent), ..Default::default() });
199        block.try_recover().unwrap()
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: &RecoveredBlock<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
