use crate::metrics::BlockBufferMetrics;
use alloy_consensus::BlockHeader;
use alloy_primitives::{BlockHash, BlockNumber};
use reth_network::cache::LruCache;
use reth_node_types::Block;
use reth_primitives::SealedBlockWithSenders;
use std::collections::{BTreeMap, HashMap, HashSet};
#[derive(Debug)]
pub struct BlockBuffer<B: Block = reth_primitives::Block> {
pub(crate) blocks: HashMap<BlockHash, SealedBlockWithSenders<B>>,
pub(crate) parent_to_child: HashMap<BlockHash, HashSet<BlockHash>>,
pub(crate) earliest_blocks: BTreeMap<BlockNumber, HashSet<BlockHash>>,
pub(crate) lru: LruCache<BlockHash>,
pub(crate) metrics: BlockBufferMetrics,
}
impl<B: Block> BlockBuffer<B> {
pub fn new(limit: u32) -> Self {
Self {
blocks: Default::default(),
parent_to_child: Default::default(),
earliest_blocks: Default::default(),
lru: LruCache::new(limit),
metrics: Default::default(),
}
}
pub const fn blocks(&self) -> &HashMap<BlockHash, SealedBlockWithSenders<B>> {
&self.blocks
}
pub fn block(&self, hash: &BlockHash) -> Option<&SealedBlockWithSenders<B>> {
self.blocks.get(hash)
}
pub fn lowest_ancestor(&self, hash: &BlockHash) -> Option<&SealedBlockWithSenders<B>> {
let mut current_block = self.blocks.get(hash)?;
while let Some(parent) = self.blocks.get(¤t_block.parent_hash()) {
current_block = parent;
}
Some(current_block)
}
pub fn insert_block(&mut self, block: SealedBlockWithSenders<B>) {
let hash = block.hash();
self.parent_to_child.entry(block.parent_hash()).or_default().insert(hash);
self.earliest_blocks.entry(block.number()).or_default().insert(hash);
self.blocks.insert(hash, block);
if let (_, Some(evicted_hash)) = self.lru.insert_and_get_evicted(hash) {
if let Some(evicted_block) = self.remove_block(&evicted_hash) {
self.remove_from_parent(evicted_block.parent_hash(), &evicted_hash);
}
}
self.metrics.blocks.set(self.blocks.len() as f64);
}
pub fn remove_block_with_children(
&mut self,
parent_hash: &BlockHash,
) -> Vec<SealedBlockWithSenders<B>> {
let removed = self
.remove_block(parent_hash)
.into_iter()
.chain(self.remove_children(vec![*parent_hash]))
.collect();
self.metrics.blocks.set(self.blocks.len() as f64);
removed
}
pub fn remove_old_blocks(&mut self, block_number: BlockNumber) {
let mut block_hashes_to_remove = Vec::new();
while let Some(entry) = self.earliest_blocks.first_entry() {
if *entry.key() > block_number {
break
}
let block_hashes = entry.remove();
block_hashes_to_remove.extend(block_hashes);
}
for block_hash in &block_hashes_to_remove {
self.remove_block(block_hash);
}
self.remove_children(block_hashes_to_remove);
self.metrics.blocks.set(self.blocks.len() as f64);
}
fn remove_from_earliest_blocks(&mut self, number: BlockNumber, hash: &BlockHash) {
if let Some(entry) = self.earliest_blocks.get_mut(&number) {
entry.remove(hash);
if entry.is_empty() {
self.earliest_blocks.remove(&number);
}
}
}
fn remove_from_parent(&mut self, parent_hash: BlockHash, hash: &BlockHash) {
if let Some(entry) = self.parent_to_child.get_mut(&parent_hash) {
entry.remove(hash);
if entry.is_empty() {
self.parent_to_child.remove(&parent_hash);
}
}
}
fn remove_block(&mut self, hash: &BlockHash) -> Option<SealedBlockWithSenders<B>> {
let block = self.blocks.remove(hash)?;
self.remove_from_earliest_blocks(block.number(), hash);
self.remove_from_parent(block.parent_hash(), hash);
self.lru.remove(hash);
Some(block)
}
fn remove_children(&mut self, parent_hashes: Vec<BlockHash>) -> Vec<SealedBlockWithSenders<B>> {
let mut remove_parent_children = parent_hashes;
let mut removed_blocks = Vec::new();
while let Some(parent_hash) = remove_parent_children.pop() {
if let Some(parent_children) = self.parent_to_child.remove(&parent_hash) {
for child_hash in &parent_children {
if let Some(block) = self.remove_block(child_hash) {
removed_blocks.push(block);
}
}
remove_parent_children.extend(parent_children);
}
}
removed_blocks
}
}
#[cfg(test)]
mod tests {
use crate::BlockBuffer;
use alloy_eips::BlockNumHash;
use alloy_primitives::BlockHash;
use reth_primitives::SealedBlockWithSenders;
use reth_testing_utils::generators::{self, random_block, BlockParams, Rng};
use std::collections::HashMap;
fn create_block<R: Rng>(rng: &mut R, number: u64, parent: BlockHash) -> SealedBlockWithSenders {
let block =
random_block(rng, number, BlockParams { parent: Some(parent), ..Default::default() });
block.seal_with_senders().unwrap()
}
fn assert_buffer_lengths(buffer: &BlockBuffer, expected: usize) {
assert_eq!(buffer.blocks.len(), expected);
assert_eq!(buffer.lru.len(), expected);
assert_eq!(
buffer.parent_to_child.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
expected
);
assert_eq!(
buffer.earliest_blocks.iter().fold(0, |acc, (_, hashes)| acc + hashes.len()),
expected
);
}
fn assert_block_removal(buffer: &BlockBuffer, block: &SealedBlockWithSenders) {
assert!(!buffer.blocks.contains_key(&block.hash()));
assert!(buffer
.parent_to_child
.get(&block.parent_hash)
.and_then(|p| p.get(&block.hash()))
.is_none());
assert!(buffer
.earliest_blocks
.get(&block.number)
.and_then(|hashes| hashes.get(&block.hash()))
.is_none());
}
#[test]
fn simple_insertion() {
let mut rng = generators::rng();
let parent = rng.gen();
let block1 = create_block(&mut rng, 10, parent);
let mut buffer = BlockBuffer::new(3);
buffer.insert_block(block1.clone());
assert_buffer_lengths(&buffer, 1);
assert_eq!(buffer.block(&block1.hash()), Some(&block1));
}
#[test]
fn take_entire_chain_of_children() {
let mut rng = generators::rng();
let main_parent_hash = rng.gen();
let block1 = create_block(&mut rng, 10, main_parent_hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 12, block2.hash());
let parent4 = rng.gen();
let block4 = create_block(&mut rng, 14, parent4);
let mut buffer = BlockBuffer::new(5);
buffer.insert_block(block1.clone());
buffer.insert_block(block2.clone());
buffer.insert_block(block3.clone());
buffer.insert_block(block4.clone());
assert_buffer_lengths(&buffer, 4);
assert_eq!(buffer.block(&block4.hash()), Some(&block4));
assert_eq!(buffer.block(&block2.hash()), Some(&block2));
assert_eq!(buffer.block(&main_parent_hash), None);
assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
assert_eq!(
buffer.remove_block_with_children(&main_parent_hash),
vec![block1, block2, block3]
);
assert_buffer_lengths(&buffer, 1);
}
#[test]
fn take_all_multi_level_children() {
let mut rng = generators::rng();
let main_parent_hash = rng.gen();
let block1 = create_block(&mut rng, 10, main_parent_hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 11, block1.hash());
let block4 = create_block(&mut rng, 12, block2.hash());
let mut buffer = BlockBuffer::new(5);
buffer.insert_block(block1.clone());
buffer.insert_block(block2.clone());
buffer.insert_block(block3.clone());
buffer.insert_block(block4.clone());
assert_buffer_lengths(&buffer, 4);
assert_eq!(
buffer
.remove_block_with_children(&main_parent_hash)
.into_iter()
.map(|b| (b.hash(), b))
.collect::<HashMap<_, _>>(),
HashMap::from([
(block1.hash(), block1),
(block2.hash(), block2),
(block3.hash(), block3),
(block4.hash(), block4)
])
);
assert_buffer_lengths(&buffer, 0);
}
#[test]
fn take_block_with_children() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 11, block1.hash());
let block4 = create_block(&mut rng, 12, block2.hash());
let mut buffer = BlockBuffer::new(5);
buffer.insert_block(block1.clone());
buffer.insert_block(block2.clone());
buffer.insert_block(block3.clone());
buffer.insert_block(block4.clone());
assert_buffer_lengths(&buffer, 4);
assert_eq!(
buffer
.remove_block_with_children(&block1.hash())
.into_iter()
.map(|b| (b.hash(), b))
.collect::<HashMap<_, _>>(),
HashMap::from([
(block1.hash(), block1),
(block2.hash(), block2),
(block3.hash(), block3),
(block4.hash(), block4)
])
);
assert_buffer_lengths(&buffer, 0);
}
#[test]
fn remove_chain_of_children() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 12, block2.hash());
let parent4 = rng.gen();
let block4 = create_block(&mut rng, 14, parent4);
let mut buffer = BlockBuffer::new(5);
buffer.insert_block(block1.clone());
buffer.insert_block(block2);
buffer.insert_block(block3);
buffer.insert_block(block4);
assert_buffer_lengths(&buffer, 4);
buffer.remove_old_blocks(block1.number);
assert_buffer_lengths(&buffer, 1);
}
#[test]
fn remove_all_multi_level_children() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 11, block1.hash());
let block4 = create_block(&mut rng, 12, block2.hash());
let mut buffer = BlockBuffer::new(5);
buffer.insert_block(block1.clone());
buffer.insert_block(block2);
buffer.insert_block(block3);
buffer.insert_block(block4);
assert_buffer_lengths(&buffer, 4);
buffer.remove_old_blocks(block1.number);
assert_buffer_lengths(&buffer, 0);
}
#[test]
fn remove_multi_chains() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block1a = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block2a = create_block(&mut rng, 11, block1.hash());
let random_parent1 = rng.gen();
let random_block1 = create_block(&mut rng, 10, random_parent1);
let random_parent2 = rng.gen();
let random_block2 = create_block(&mut rng, 11, random_parent2);
let random_parent3 = rng.gen();
let random_block3 = create_block(&mut rng, 12, random_parent3);
let mut buffer = BlockBuffer::new(10);
buffer.insert_block(block1.clone());
buffer.insert_block(block1a.clone());
buffer.insert_block(block2.clone());
buffer.insert_block(block2a.clone());
buffer.insert_block(random_block1.clone());
buffer.insert_block(random_block2.clone());
buffer.insert_block(random_block3.clone());
assert_eq!(buffer.lowest_ancestor(&random_block1.hash()), Some(&random_block1));
assert_eq!(buffer.lowest_ancestor(&random_block2.hash()), Some(&random_block2));
assert_eq!(buffer.lowest_ancestor(&random_block3.hash()), Some(&random_block3));
assert_eq!(buffer.lowest_ancestor(&block2a.hash()), Some(&block1));
assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
assert_eq!(buffer.lowest_ancestor(&block1a.hash()), Some(&block1a));
assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
assert_buffer_lengths(&buffer, 7);
buffer.remove_old_blocks(10);
assert_buffer_lengths(&buffer, 2);
}
#[test]
fn evict_with_gap() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 12, block2.hash());
let parent4 = rng.gen();
let block4 = create_block(&mut rng, 13, parent4);
let mut buffer = BlockBuffer::new(3);
buffer.insert_block(block1.clone());
buffer.insert_block(block2.clone());
buffer.insert_block(block3.clone());
assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block1));
assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block1));
assert_eq!(buffer.lowest_ancestor(&block1.hash()), Some(&block1));
buffer.insert_block(block4.clone());
assert_eq!(buffer.lowest_ancestor(&block4.hash()), Some(&block4));
assert_block_removal(&buffer, &block1);
assert_eq!(buffer.lowest_ancestor(&block3.hash()), Some(&block2));
assert_eq!(buffer.lowest_ancestor(&block2.hash()), Some(&block2));
assert_eq!(buffer.lowest_ancestor(&block1.hash()), None);
assert_buffer_lengths(&buffer, 3);
}
#[test]
fn simple_eviction() {
let mut rng = generators::rng();
let main_parent = BlockNumHash::new(9, rng.gen());
let block1 = create_block(&mut rng, 10, main_parent.hash);
let block2 = create_block(&mut rng, 11, block1.hash());
let block3 = create_block(&mut rng, 12, block2.hash());
let parent4 = rng.gen();
let block4 = create_block(&mut rng, 13, parent4);
let mut buffer = BlockBuffer::new(3);
buffer.insert_block(block1.clone());
buffer.insert_block(block2);
buffer.insert_block(block3);
buffer.insert_block(block4);
assert_block_removal(&buffer, &block1);
assert_buffer_lengths(&buffer, 3);
}
}