reth_blockchain_tree/
block_buffer.rs

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

reth_blockchain_tree/
block_buffer.rs
