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

reth_engine_tree/tree/
block_buffer.rs
