feat: save and load partial blocks from a cache

[bertmiller]

Often times in the process of building a block the top of the block will be the same as a previous block. In that case, we should be able to reload a previously built block's state instead of reconstructing it ourselves by reapplying however many orders. In turn, that will make the process of building faster - especially where we're just appending new transactions or something similar.

For an example of a cache, see simulation_cache.rs used in the parallel builder. We can use a similar idea, except we need to store the full partial block. A possible struct could be this:

#[derive(Debug)]
pub struct PartialBlockStateCache {
    pub partial_block: Arc<PartialBlock<GasUsedSimulationTracer>>,
    pub state: Arc<CachedSimulationState>,
    pub execution_results: Vec<ExecutionResult>,
}

/// An inner cache of partial blocks, keyed by a vector of order IDs.
#[derive(Debug, Default)]
struct PartialBlockCache {
    inner_cache: DashMap<Vec<OrderId>, Arc<PartialBlockStateCache>>,
}

Then we'd need to implement a new building helper to load/save from this cache.

In testing a design for this on the mempool I found a significant reduction in building times, from 11ms on average to just 2ms. The reason is that for many blocks we were just appending mempool txs at the end instead of rebuilding the whole thing. With loading from the cache that reduces the time to construct a new block with a new mempool tx to less than 1ms instead of 10+ms.

[bertmiller]

If you take this one up, make sure to get buy in on designs from the team.

[grasphoper]

Interested in taking this!

I've taken your suggestion from the comments and landed on the following design, please let me know what you and the team think about this one @bertmiller :

BlockBuildingResultAssembler runs in a single thread, and that is a big part of my design decisions.

BlockBuildingResultAssembler can hold a member var, partial_block_cache: PartialBlockCache,,

#[derive(Default)]
pub struct PartialBlockCache {
    index: HashMap<OrderId, usize>,
    nodes: Vec<Node>,
    cursor: Cursor,
}

struct Node {
    children_index: HashMap<OrderId, usize>,
    data: Box<PartialBlockStateCache>
}

#[derive(Debug)]
pub struct PartialBlockStateCache {
    pub partial_block: PartialBlock<GasUsedSimulationTracer>,
    pub state: CachedSimulationState,
    pub execution_result: ExecutionResult,
}

PartialBlockCache is a Trie-like data structure using index mappings to a single Vec<Node> of data instead of recursive ownership.

Also, PartialBlockStateCache in my impl is a little different, holding a single ExecutionResult as opposed to the vec.

There's one more element to the suggested design:

pub struct BBHFPWithCache<'a, P, DB> 
where
    DB: Database + Clone + 'static,
    P: DatabaseProviderFactory<DB> + StateProviderFactory + Clone + 'static,
{
    block_builder: BlockBuildingHelperFromProvider<P, DB>,
    cache: &'a mut PartialBlockCache,
}

(name is a work in progress, but it stands for BlockBuildingHelperFromProviderWithCache)
which is used as a new entrypoint to .commit_order call.

Then the workflow is as follows:

• create cache on BlockBuildingResultAssembler::new()
• create BBHFPWithCache here, from BlockBuildingResultAssembler and &mut PartialBlockCache
• let BBHFPWithCache process all the .commit_order calls instead of BlockBuildingHelperFromProvider:
  • BBHFPWithCache works with sim_orders one-by-one, just like BlockBuildingHelperFromProvider
  • every time BBHFPWithCache receives a new sim_order, it tries to look it up in cache by OrderId and if found, return the cached result and move cache cursor deeper into the trie (a single HashMap lookup)
  • when we run out of cached OrderIds, we just forward execution to BlockBuildingHelperFromProvider, putting interim exec results into cache after each sim_order is processed. Here, we need to call .clone() on each of the members of PartialBlockStateCache in order to save them into cache
  • After we're done with .commit_order calls, we call .into_block_building_helper(self) on BBHFPWithCache, consuming the object and releasing the BlockBuildingHelperFromProvider object and the &mut reference to cache
  • After, the pipeline is the same as currently

A couple of main things about this design:

• relies on single-threadedness of the blockbuilding loop
• does a lot of .clones on interim block building results. How slow are they? Should we use some heuristic like (not saving very long sequences) or (not saving to cache near the end of slot)?
• have no decision on when to clear the cache. Theoretically, we can do it every slot. Do you have suggestions for this one? From what I understand, SimulationCache.inner_cache is never cleaned?