reth_engine_tree/tree/
block_buffer.rs

Help
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                if let Some(evicted_block) = self.remove_block(&evicted_hash) {
78                    self.remove_from_parent(evicted_block.parent_hash(), &evicted_hash);
79                }
80            }
81        }
82        self.block_queue.push_back(hash);
83        self.metrics.blocks.set(self.blocks.len() as f64);
84    }
85
86    /// Removes the given block from the buffer and also all the children of the block.
87    ///
88    /// This is used to get all the blocks that are dependent on the block that is included.
89    ///
90    /// Note: that order of returned blocks is important and the blocks with lower block number
91    /// in the chain will come first so that they can be executed in the correct order.
92    pub fn remove_block_with_children(
93        &mut self,
94        parent_hash: &BlockHash,
95    ) -> Vec<RecoveredBlock<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<RecoveredBlock<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<RecoveredBlock<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_primitives_traits::RecoveredBlock;
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    ) -> RecoveredBlock<reth_ethereum_primitives::Block> {
199        let block =
200            random_block(rng, number, BlockParams { parent: Some(parent), ..Default::default() });
201        block.try_recover().unwrap()
202    }
203
204    /// Assert that all buffer collections have the same data length.
205    fn assert_buffer_lengths<B: Block>(buffer: &BlockBuffer<B>, expected: usize) {
206        assert_eq!(buffer.blocks.len(), expected);
207        assert_eq!(buffer.block_queue.len(), expected);
208        assert_eq!(
209            buffer.parent_to_child.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
210            expected
211        );
212        assert_eq!(
213            buffer.earliest_blocks.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
214            expected
215        );
216    }
217
218    /// Assert that the block was removed from all buffer collections.
219    fn assert_block_removal<B: Block>(
220        buffer: &BlockBuffer<B>,
221        block: &RecoveredBlock<reth_ethereum_primitives::Block>,
222    ) {
223        assert!(!buffer.blocks.contains_key(&block.hash()));
224        assert!(buffer
225            .parent_to_child
226            .get(&block.parent_hash)
227            .and_then(|p| p.get(&block.hash()))
228            .is_none());
229        assert!(buffer
230            .earliest_blocks
231            .get(&block.number)
232            .and_then(|hashes| hashes.get(&block.hash()))
233            .is_none());
234    }
235
236    #[test]
237    fn simple_insertion() {
238        let mut rng = generators::rng();
239        let parent = rng.gen();
240        let block1 = create_block(&mut rng, 10, parent);
241        let mut buffer = BlockBuffer::new(3);
242
243        buffer.insert_block(block1.clone());
244        assert_buffer_lengths(&buffer, 1);
245        assert_eq!(buffer.block(&block1.hash()), Some(&block1));
246    }
247
248    #[test]
249    fn take_entire_chain_of_children() {
250        let mut rng = generators::rng();
251
252        let main_parent_hash = rng.gen();
253        let block1 = create_block(&mut rng, 10, main_parent_hash);
254        let block2 = create_block(&mut rng, 11, block1.hash());
255        let block3 = create_block(&mut rng, 12, block2.hash());
256        let parent4 = rng.gen();
257        let block4 = create_block(&mut rng, 14, parent4);
258
259        let mut buffer = BlockBuffer::new(5);
260
261        buffer.insert_block(block1.clone());
262        buffer.insert_block(block2.clone());
263        buffer.insert_block(block3.clone());
264        buffer.insert_block(block4.clone());
265
266        assert_buffer_lengths(&buffer, 4);
267        assert_eq!(buffer.block(&block4.hash()), Some(&block4));
268        assert_eq!(buffer.block(&block2.hash()), Some(&block2));
269        assert_eq!(buffer.block(&main_parent_hash), None);
270
271        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
272        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
273        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
274        assert_eq!(
275            buffer.remove_block_with_children(&main_parent_hash),
276            vec![block1, block2, block3]
277        );
278        assert_buffer_lengths(&buffer, 1);
279    }
280
281    #[test]
282    fn take_all_multi_level_children() {
283        let mut rng = generators::rng();
284
285        let main_parent_hash = rng.gen();
286        let block1 = create_block(&mut rng, 10, main_parent_hash);
287        let block2 = create_block(&mut rng, 11, block1.hash());
288        let block3 = create_block(&mut rng, 11, block1.hash());
289        let block4 = create_block(&mut rng, 12, block2.hash());
290
291        let mut buffer = BlockBuffer::new(5);
292
293        buffer.insert_block(block1.clone());
294        buffer.insert_block(block2.clone());
295        buffer.insert_block(block3.clone());
296        buffer.insert_block(block4.clone());
297
298        assert_buffer_lengths(&buffer, 4);
299        assert_eq!(
300            buffer
301                .remove_block_with_children(&main_parent_hash)
302                .into_iter()
303                .map(|b| (b.hash(), b))
304                .collect::<HashMap<_, _>>(),
305            HashMap::from([
306                (block1.hash(), block1),
307                (block2.hash(), block2),
308                (block3.hash(), block3),
309                (block4.hash(), block4)
310            ])
311        );
312        assert_buffer_lengths(&buffer, 0);
313    }
314
315    #[test]
316    fn take_block_with_children() {
317        let mut rng = generators::rng();
318
319        let main_parent = BlockNumHash::new(9, rng.gen());
320        let block1 = create_block(&mut rng, 10, main_parent.hash);
321        let block2 = create_block(&mut rng, 11, block1.hash());
322        let block3 = create_block(&mut rng, 11, block1.hash());
323        let block4 = create_block(&mut rng, 12, block2.hash());
324
325        let mut buffer = BlockBuffer::new(5);
326
327        buffer.insert_block(block1.clone());
328        buffer.insert_block(block2.clone());
329        buffer.insert_block(block3.clone());
330        buffer.insert_block(block4.clone());
331
332        assert_buffer_lengths(&buffer, 4);
333        assert_eq!(
334            buffer
335                .remove_block_with_children(&block1.hash())
336                .into_iter()
337                .map(|b| (b.hash(), b))
338                .collect::<HashMap<_, _>>(),
339            HashMap::from([
340                (block1.hash(), block1),
341                (block2.hash(), block2),
342                (block3.hash(), block3),
343                (block4.hash(), block4)
344            ])
345        );
346        assert_buffer_lengths(&buffer, 0);
347    }
348
349    #[test]
350    fn remove_chain_of_children() {
351        let mut rng = generators::rng();
352
353        let main_parent = BlockNumHash::new(9, rng.gen());
354        let block1 = create_block(&mut rng, 10, main_parent.hash);
355        let block2 = create_block(&mut rng, 11, block1.hash());
356        let block3 = create_block(&mut rng, 12, block2.hash());
357        let parent4 = rng.gen();
358        let block4 = create_block(&mut rng, 14, parent4);
359
360        let mut buffer = BlockBuffer::new(5);
361
362        buffer.insert_block(block1.clone());
363        buffer.insert_block(block2);
364        buffer.insert_block(block3);
365        buffer.insert_block(block4);
366
367        assert_buffer_lengths(&buffer, 4);
368        buffer.remove_old_blocks(block1.number);
369        assert_buffer_lengths(&buffer, 1);
370    }
371
372    #[test]
373    fn remove_all_multi_level_children() {
374        let mut rng = generators::rng();
375
376        let main_parent = BlockNumHash::new(9, rng.gen());
377        let block1 = create_block(&mut rng, 10, main_parent.hash);
378        let block2 = create_block(&mut rng, 11, block1.hash());
379        let block3 = create_block(&mut rng, 11, block1.hash());
380        let block4 = create_block(&mut rng, 12, block2.hash());
381
382        let mut buffer = BlockBuffer::new(5);
383
384        buffer.insert_block(block1.clone());
385        buffer.insert_block(block2);
386        buffer.insert_block(block3);
387        buffer.insert_block(block4);
388
389        assert_buffer_lengths(&buffer, 4);
390        buffer.remove_old_blocks(block1.number);
391        assert_buffer_lengths(&buffer, 0);
392    }
393
394    #[test]
395    fn remove_multi_chains() {
396        let mut rng = generators::rng();
397
398        let main_parent = BlockNumHash::new(9, rng.gen());
399        let block1 = create_block(&mut rng, 10, main_parent.hash);
400        let block1a = create_block(&mut rng, 10, main_parent.hash);
401        let block2 = create_block(&mut rng, 11, block1.hash());
402        let block2a = create_block(&mut rng, 11, block1.hash());
403        let random_parent1 = rng.gen();
404        let random_block1 = create_block(&mut rng, 10, random_parent1);
405        let random_parent2 = rng.gen();
406        let random_block2 = create_block(&mut rng, 11, random_parent2);
407        let random_parent3 = rng.gen();
408        let random_block3 = create_block(&mut rng, 12, random_parent3);
409
410        let mut buffer = BlockBuffer::new(10);
411
412        buffer.insert_block(block1.clone());
413        buffer.insert_block(block1a.clone());
414        buffer.insert_block(block2.clone());
415        buffer.insert_block(block2a.clone());
416        buffer.insert_block(random_block1.clone());
417        buffer.insert_block(random_block2.clone());
418        buffer.insert_block(random_block3.clone());
419
420        // check that random blocks are their own ancestor, and that chains have proper ancestors
421        assert_eq!(buffer.lowest_ancestor(&random_block1.hash()), Some(&random_block1));
422        assert_eq!(buffer.lowest_ancestor(&random_block2.hash()), Some(&random_block2));
423        assert_eq!(buffer.lowest_ancestor(&random_block3.hash()), Some(&random_block3));
424
425        // descendants have ancestors
426        assert_eq!(buffer.lowest_ancestor(&block2a.hash()), Some(&block1));
427        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
428
429        // roots are themselves
430        assert_eq!(buffer.lowest_ancestor(&block1a.hash()), Some(&block1a));
431        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
432
433        assert_buffer_lengths(&buffer, 7);
434        buffer.remove_old_blocks(10);
435        assert_buffer_lengths(&buffer, 2);
436    }
437
438    #[test]
439    fn evict_with_gap() {
440        let mut rng = generators::rng();
441
442        let main_parent = BlockNumHash::new(9, rng.gen());
443        let block1 = create_block(&mut rng, 10, main_parent.hash);
444        let block2 = create_block(&mut rng, 11, block1.hash());
445        let block3 = create_block(&mut rng, 12, block2.hash());
446        let parent4 = rng.gen();
447        let block4 = create_block(&mut rng, 13, parent4);
448
449        let mut buffer = BlockBuffer::new(3);
450
451        buffer.insert_block(block1.clone());
452        buffer.insert_block(block2.clone());
453        buffer.insert_block(block3.clone());
454
455        // pre-eviction block1 is the root
456        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
457        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
458        assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
459
460        buffer.insert_block(block4.clone());
461
462        assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
463
464        // block1 gets evicted
465        assert_block_removal(&buffer, &block1);
466
467        // check lowest ancestor results post eviction
468        assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block2));
469        assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
470        assert_eq!(buffer.lowest_ancestor(&block1.hash()), None);
471
472        assert_buffer_lengths(&buffer, 3);
473    }
474
475    #[test]
476    fn simple_eviction() {
477        let mut rng = generators::rng();
478
479        let main_parent = BlockNumHash::new(9, rng.gen());
480        let block1 = create_block(&mut rng, 10, main_parent.hash);
481        let block2 = create_block(&mut rng, 11, block1.hash());
482        let block3 = create_block(&mut rng, 12, block2.hash());
483        let parent4 = rng.gen();
484        let block4 = create_block(&mut rng, 13, parent4);
485
486        let mut buffer = BlockBuffer::new(3);
487
488        buffer.insert_block(block1.clone());
489        buffer.insert_block(block2);
490        buffer.insert_block(block3);
491        buffer.insert_block(block4);
492
493        // block3 gets evicted
494        assert_block_removal(&buffer, &block1);
495
496        assert_buffer_lengths(&buffer, 3);
497    }
498}
reth_engine_tree/tree/block_buffer.rs

reth_engine_tree/tree/
block_buffer.rs
