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, SealedBlock};
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, SealedBlock<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<&SealedBlock<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<&SealedBlock<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: SealedBlock<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(&mut self, parent_hash: &BlockHash) -> Vec<SealedBlock<B>> {
91        let removed = self
92            .remove_block(parent_hash)
93            .into_iter()
94            .chain(self.remove_children(vec![*parent_hash]))
95            .collect();
96        self.metrics.blocks.set(self.blocks.len() as f64);
97        removed
98    }
99
100    /// Discard all blocks that precede block number from the buffer.
101    pub fn remove_old_blocks(&mut self, block_number: BlockNumber) {
102        let mut block_hashes_to_remove = Vec::new();
103
104        // discard all blocks that are before the finalized number.
105        while let Some(entry) = self.earliest_blocks.first_entry() {
106            if *entry.key() > block_number {
107                break
108            }
109            let block_hashes = entry.remove();
110            block_hashes_to_remove.extend(block_hashes);
111        }
112
113        // remove from other collections.
114        for block_hash in &block_hashes_to_remove {
115            // It's fine to call
116            self.remove_block(block_hash);
117        }
118
119        self.remove_children(block_hashes_to_remove);
120        self.metrics.blocks.set(self.blocks.len() as f64);
121    }
122
123    /// Remove block entry
124    fn remove_from_earliest_blocks(&mut self, number: BlockNumber, hash: &BlockHash) {
125        if let Some(entry) = self.earliest_blocks.get_mut(&number) {
126            entry.remove(hash);
127            if entry.is_empty() {
128                self.earliest_blocks.remove(&number);
129            }
130        }
131    }
132
133    /// Remove from parent child connection. This method does not remove children.
134    fn remove_from_parent(&mut self, parent_hash: BlockHash, hash: &BlockHash) {
135        // remove from parent to child connection, but only for this block parent.
136        if let Some(entry) = self.parent_to_child.get_mut(&parent_hash) {
137            entry.remove(hash);
138            // if set is empty remove block entry.
139            if entry.is_empty() {
140                self.parent_to_child.remove(&parent_hash);
141            }
142        }
143    }
144
145    /// Removes block from inner collections.
146    /// This method will only remove the block if it's present inside `self.blocks`.
147    /// The block might be missing from other collections, the method will only ensure that it has
148    /// been removed.
149    fn remove_block(&mut self, hash: &BlockHash) -> Option<SealedBlock<B>> {
150        let block = self.blocks.remove(hash)?;
151        self.remove_from_earliest_blocks(block.number(), hash);
152        self.remove_from_parent(block.parent_hash(), hash);
153        self.block_queue.retain(|h| h != hash);
154        Some(block)
155    }
156
157    /// Remove all children and their descendants for the given blocks and return them.
158    fn remove_children(&mut self, parent_hashes: Vec<BlockHash>) -> Vec<SealedBlock<B>> {
159        // remove all parent child connection and all the child children blocks that are connected
160        // to the discarded parent blocks.
161        let mut remove_parent_children = parent_hashes;
162        let mut removed_blocks = Vec::new();
163        while let Some(parent_hash) = remove_parent_children.pop() {
164            // get this child blocks children and add them to the remove list.
165            if let Some(parent_children) = self.parent_to_child.remove(&parent_hash) {
166                // remove child from buffer
167                for child_hash in &parent_children {
168                    if let Some(block) = self.remove_block(child_hash) {
169                        removed_blocks.push(block);
170                    }
171                }
172                remove_parent_children.extend(parent_children);
173            }
174        }
175        removed_blocks
176    }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182    use alloy_eips::BlockNumHash;
183    use alloy_primitives::BlockHash;
184    use reth_testing_utils::generators::{self, random_block, BlockParams, Rng};
185    use std::collections::HashMap;
186
187    /// Create random block with specified number and parent hash.
188    fn create_block<R: Rng>(
189        rng: &mut R,
190        number: u64,
191        parent: BlockHash,
192    ) -> SealedBlock<reth_ethereum_primitives::Block> {
193        random_block(rng, number, BlockParams { parent: Some(parent), ..Default::default() })
194    }
195
196    /// Assert that all buffer collections have the same data length.
197    fn assert_buffer_lengths<B: Block>(buffer: &BlockBuffer<B>, expected: usize) {
198        assert_eq!(buffer.blocks.len(), expected);
199        assert_eq!(buffer.block_queue.len(), expected);
200        assert_eq!(
201            buffer.parent_to_child.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
202            expected
203        );
204        assert_eq!(
205            buffer.earliest_blocks.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
206            expected
207        );
208    }
209
210    /// Assert that the block was removed from all buffer collections.
211    fn assert_block_removal<B: Block>(
212        buffer: &BlockBuffer<B>,
213        block: &SealedBlock<reth_ethereum_primitives::Block>,
214    ) {
215        assert!(!buffer.blocks.contains_key(&block.hash()));
216        assert!(buffer
217            .parent_to_child
218            .get(&block.parent_hash)
219            .and_then(|p| p.get(&block.hash()))
220            .is_none());
221        assert!(buffer
222            .earliest_blocks
223            .get(&block.number)
224            .and_then(|hashes| hashes.get(&block.hash()))
225            .is_none());
226    }
227
228    #[test]
229    fn simple_insertion() {
230        let mut rng = generators::rng();
231        let parent = rng.random();
232        let block1 = create_block(&mut rng, 10, parent);
233        let mut buffer = BlockBuffer::new(3);
234
235        buffer.insert_block(block1.clone());
236        assert_buffer_lengths(&buffer, 1);
237        assert_eq!(buffer.block(&block1.hash()), Some(&block1));
238    }
239
240    #[test]
241    fn take_entire_chain_of_children() {
242        let mut rng = generators::rng();
243
244        let main_parent_hash = rng.random();
245        let block1 = create_block(&mut rng, 10, main_parent_hash);
246        let block2 = create_block(&mut rng, 11, block1.hash());
247        let block3 = create_block(&mut rng, 12, block2.hash());
248        let parent4 = rng.random();
249        let block4 = create_block(&mut rng, 14, parent4);
250
251        let mut buffer = BlockBuffer::new(5);
252
253        buffer.insert_block(block1.clone());
254        buffer.insert_block(block2.clone());
255        buffer.insert_block(block3.clone());
256        buffer.insert_block(block4.clone());
257
258        assert_buffer_lengths(&buffer, 4);
259        assert_eq!(buffer.block(&block4.hash()), Some(&block4));
260        assert_eq!(buffer.block(&block2.hash()), Some(&block2));
261        assert_eq!(buffer.block(&main_parent_hash), None);
262
263        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
264        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
265        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
266        assert_eq!(
267            buffer.remove_block_with_children(&main_parent_hash),
268            vec![block1, block2, block3]
269        );
270        assert_buffer_lengths(&buffer, 1);
271    }
272
273    #[test]
274    fn take_all_multi_level_children() {
275        let mut rng = generators::rng();
276
277        let main_parent_hash = rng.random();
278        let block1 = create_block(&mut rng, 10, main_parent_hash);
279        let block2 = create_block(&mut rng, 11, block1.hash());
280        let block3 = create_block(&mut rng, 11, block1.hash());
281        let block4 = create_block(&mut rng, 12, block2.hash());
282
283        let mut buffer = BlockBuffer::new(5);
284
285        buffer.insert_block(block1.clone());
286        buffer.insert_block(block2.clone());
287        buffer.insert_block(block3.clone());
288        buffer.insert_block(block4.clone());
289
290        assert_buffer_lengths(&buffer, 4);
291        assert_eq!(
292            buffer
293                .remove_block_with_children(&main_parent_hash)
294                .into_iter()
295                .map(|b| (b.hash(), b))
296                .collect::<HashMap<_, _>>(),
297            HashMap::from([
298                (block1.hash(), block1),
299                (block2.hash(), block2),
300                (block3.hash(), block3),
301                (block4.hash(), block4)
302            ])
303        );
304        assert_buffer_lengths(&buffer, 0);
305    }
306
307    #[test]
308    fn take_block_with_children() {
309        let mut rng = generators::rng();
310
311        let main_parent = BlockNumHash::new(9, rng.random());
312        let block1 = create_block(&mut rng, 10, main_parent.hash);
313        let block2 = create_block(&mut rng, 11, block1.hash());
314        let block3 = create_block(&mut rng, 11, block1.hash());
315        let block4 = create_block(&mut rng, 12, block2.hash());
316
317        let mut buffer = BlockBuffer::new(5);
318
319        buffer.insert_block(block1.clone());
320        buffer.insert_block(block2.clone());
321        buffer.insert_block(block3.clone());
322        buffer.insert_block(block4.clone());
323
324        assert_buffer_lengths(&buffer, 4);
325        assert_eq!(
326            buffer
327                .remove_block_with_children(&block1.hash())
328                .into_iter()
329                .map(|b| (b.hash(), b))
330                .collect::<HashMap<_, _>>(),
331            HashMap::from([
332                (block1.hash(), block1),
333                (block2.hash(), block2),
334                (block3.hash(), block3),
335                (block4.hash(), block4)
336            ])
337        );
338        assert_buffer_lengths(&buffer, 0);
339    }
340
341    #[test]
342    fn remove_chain_of_children() {
343        let mut rng = generators::rng();
344
345        let main_parent = BlockNumHash::new(9, rng.random());
346        let block1 = create_block(&mut rng, 10, main_parent.hash);
347        let block2 = create_block(&mut rng, 11, block1.hash());
348        let block3 = create_block(&mut rng, 12, block2.hash());
349        let parent4 = rng.random();
350        let block4 = create_block(&mut rng, 14, parent4);
351
352        let mut buffer = BlockBuffer::new(5);
353
354        buffer.insert_block(block1.clone());
355        buffer.insert_block(block2);
356        buffer.insert_block(block3);
357        buffer.insert_block(block4);
358
359        assert_buffer_lengths(&buffer, 4);
360        buffer.remove_old_blocks(block1.number);
361        assert_buffer_lengths(&buffer, 1);
362    }
363
364    #[test]
365    fn remove_all_multi_level_children() {
366        let mut rng = generators::rng();
367
368        let main_parent = BlockNumHash::new(9, rng.random());
369        let block1 = create_block(&mut rng, 10, main_parent.hash);
370        let block2 = create_block(&mut rng, 11, block1.hash());
371        let block3 = create_block(&mut rng, 11, block1.hash());
372        let block4 = create_block(&mut rng, 12, block2.hash());
373
374        let mut buffer = BlockBuffer::new(5);
375
376        buffer.insert_block(block1.clone());
377        buffer.insert_block(block2);
378        buffer.insert_block(block3);
379        buffer.insert_block(block4);
380
381        assert_buffer_lengths(&buffer, 4);
382        buffer.remove_old_blocks(block1.number);
383        assert_buffer_lengths(&buffer, 0);
384    }
385
386    #[test]
387    fn remove_multi_chains() {
388        let mut rng = generators::rng();
389
390        let main_parent = BlockNumHash::new(9, rng.random());
391        let block1 = create_block(&mut rng, 10, main_parent.hash);
392        let block1a = create_block(&mut rng, 10, main_parent.hash);
393        let block2 = create_block(&mut rng, 11, block1.hash());
394        let block2a = create_block(&mut rng, 11, block1.hash());
395        let random_parent1 = rng.random();
396        let random_block1 = create_block(&mut rng, 10, random_parent1);
397        let random_parent2 = rng.random();
398        let random_block2 = create_block(&mut rng, 11, random_parent2);
399        let random_parent3 = rng.random();
400        let random_block3 = create_block(&mut rng, 12, random_parent3);
401
402        let mut buffer = BlockBuffer::new(10);
403
404        buffer.insert_block(block1.clone());
405        buffer.insert_block(block1a.clone());
406        buffer.insert_block(block2.clone());
407        buffer.insert_block(block2a.clone());
408        buffer.insert_block(random_block1.clone());
409        buffer.insert_block(random_block2.clone());
410        buffer.insert_block(random_block3.clone());
411
412        // check that random blocks are their own ancestor, and that chains have proper ancestors
413        assert_eq!(buffer.lowest_ancestor(&random_block1.hash()), Some(&random_block1));
414        assert_eq!(buffer.lowest_ancestor(&random_block2.hash()), Some(&random_block2));
415        assert_eq!(buffer.lowest_ancestor(&random_block3.hash()), Some(&random_block3));
416
417        // descendants have ancestors
418        assert_eq!(buffer.lowest_ancestor(&block2a.hash()), Some(&block1));
419        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
420
421        // roots are themselves
422        assert_eq!(buffer.lowest_ancestor(&block1a.hash()), Some(&block1a));
423        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
424
425        assert_buffer_lengths(&buffer, 7);
426        buffer.remove_old_blocks(10);
427        assert_buffer_lengths(&buffer, 2);
428    }
429
430    #[test]
431    fn evict_with_gap() {
432        let mut rng = generators::rng();
433
434        let main_parent = BlockNumHash::new(9, rng.random());
435        let block1 = create_block(&mut rng, 10, main_parent.hash);
436        let block2 = create_block(&mut rng, 11, block1.hash());
437        let block3 = create_block(&mut rng, 12, block2.hash());
438        let parent4 = rng.random();
439        let block4 = create_block(&mut rng, 13, parent4);
440
441        let mut buffer = BlockBuffer::new(3);
442
443        buffer.insert_block(block1.clone());
444        buffer.insert_block(block2.clone());
445        buffer.insert_block(block3.clone());
446
447        // pre-eviction block1 is the root
448        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
449        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
450        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
451
452        buffer.insert_block(block4.clone());
453
454        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
455
456        // block1 gets evicted
457        assert_block_removal(&buffer, &block1);
458
459        // check lowest ancestor results post eviction
460        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block2));
461        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
462        assert_eq!(buffer.lowest_ancestor(&block1.hash()), None);
463
464        assert_buffer_lengths(&buffer, 3);
465    }
466
467    #[test]
468    fn simple_eviction() {
469        let mut rng = generators::rng();
470
471        let main_parent = BlockNumHash::new(9, rng.random());
472        let block1 = create_block(&mut rng, 10, main_parent.hash);
473        let block2 = create_block(&mut rng, 11, block1.hash());
474        let block3 = create_block(&mut rng, 12, block2.hash());
475        let parent4 = rng.random();
476        let block4 = create_block(&mut rng, 13, parent4);
477
478        let mut buffer = BlockBuffer::new(3);
479
480        buffer.insert_block(block1.clone());
481        buffer.insert_block(block2);
482        buffer.insert_block(block3);
483        buffer.insert_block(block4);
484
485        // block3 gets evicted
486        assert_block_removal(&buffer, &block1);
487
488        assert_buffer_lengths(&buffer, 3);
489    }
490
491    #[test]
492    fn eviction_parent_child_cleanup() {
493        let mut rng = generators::rng();
494
495        let main_parent = BlockNumHash::new(9, rng.random());
496        let block1 = create_block(&mut rng, 10, main_parent.hash);
497        let block2 = create_block(&mut rng, 11, block1.hash());
498        // Unrelated block to trigger eviction
499        let unrelated_parent = rng.random();
500        let unrelated_block = create_block(&mut rng, 12, unrelated_parent);
501
502        // Capacity 2 so third insert evicts the oldest (block1)
503        let mut buffer = BlockBuffer::new(2);
504
505        buffer.insert_block(block1.clone());
506        buffer.insert_block(block2.clone());
507
508        // Pre-eviction: parent_to_child contains main_parent -> {block1}, block1 -> {block2}
509        assert!(buffer
510            .parent_to_child
511            .get(&main_parent.hash)
512            .and_then(|s| s.get(&block1.hash()))
513            .is_some());
514        assert!(buffer
515            .parent_to_child
516            .get(&block1.hash())
517            .and_then(|s| s.get(&block2.hash()))
518            .is_some());
519
520        // Insert unrelated block to evict block1
521        buffer.insert_block(unrelated_block);
522
523        // Evicted block1 should be fully removed from collections
524        assert_block_removal(&buffer, &block1);
525
526        // Cleanup: parent_to_child must no longer have (main_parent -> block1)
527        assert!(buffer
528            .parent_to_child
529            .get(&main_parent.hash)
530            .and_then(|s| s.get(&block1.hash()))
531            .is_none());
532
533        // But the mapping (block1 -> block2) must remain so descendants can still be tracked
534        assert!(buffer
535            .parent_to_child
536            .get(&block1.hash())
537            .and_then(|s| s.get(&block2.hash()))
538            .is_some());
539
540        // And lowest ancestor for block2 becomes itself after its parent is evicted
541        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
542    }
543}
reth_engine_tree/tree/block_buffer.rs

reth_engine_tree/tree/
block_buffer.rs
