collect min prioritization fees when replaying sanitized transactions

[tao-stones]

Problem

Users need to know the estimated minimum compute-unit price that their transactions should have in order to land in block.

In order to do so, a cache of block minimum prioritization fee is populated, transaction by transaction, during replay. RPC service can query it to provide user estimated min fee to land to block, or access particular write account.

Summary of Changes

• Add struct PrioritizationFee that captures block's minimum transaction fee and accounts' minimum fee.
• Add struct PrioritizationFeeCache that tracks up to 150 blocks for their PrioritizationFee, it implements two sets of public functions, one set for replay_stage to update with transactions, another set for RPC service to query cache.
  • it contains a service thread that does finalization and metrics reporting;
• blockstore_processor calls prioritization_fee_cache.update_transactions(bank.slot(), transactions.iter()) to update block's min fee, transaction by transaction.
• replay_stage calls prioritization_fee_cache.finalize_block(bank.slot()) when a bank is completed, to signal that block's min fee data is finalized, therefore can be made available for querying;

Fixes #26561

[tao-stones]

@CriesofCarrots I don't have actual RPC query use cases, I imagine user would construct a transaction, and know a list of write accounts. Then user would ask something like "what's estimated min block fee", and "what's estimated min account fee for account X".

I created BlockMinPrioritizationFeeCacheQuery trait to support that (ofc it can be changed to fit whatever need to be):

• available_block_count() returns number of available blocks in cache; it can't provide information if less than 1.
• get_block_min_prioritization_fees() -> Vec<u64> returns a vec of block min fee, one per each available blocks in cache. It can be used to calculate average, or top n%, before returning estimation to user;
• get_account_min_prioritization_fees(key) -> Vec<u64> is similar to above, except it is for each account. I am not sure if this trait should support querying a list of accounts, or maybe RPC service can break it down to account by account query.

Please let me know your thoughts.

[tao-stones]

One note: I can't decide whether to pluralize "fees" when referring to the collection struct. There might only be one value (what you call the block_fee, but I'd like to rename), or more likely, there will be many fees. Singular seems to make sense for the struct, but plural seems better in method and variable names referring to that struct and its data... thoughts?

Right, structure would be better is named in singular. Just in this case, the struct contains many min fees. Think it makes sense to be consistent by using singular in struct name. I'll make changes

[tao-stones]

A lot of this looks good, but the further I get into review, the more I think this implementation gets simpler and more performant if we use a fixed-size buffer for the cache. (Don't need sequence_number or finalization_thread or an eviction process, etc.) We can collect the PrioritizationFee on the Bank, and push it to the cache on freeze.

Thanks for reviewing and valuable feedbacks. The eviction process (which adds sequence_number and finalization handling) does add complexity and additional computing, its main motivation is to reduce fee cache's memory footprint - it keeps no more than 150 (currently) bank's PrioritizationFee in memory, somewhat a cpu/memory trade.

PrioritizationFee contains all relevant writable accounts prioritization fee, which could have as many as 4k entries, each entry is <pubkey, u64>, So memory usage can add up quickly.

Not sure how to release PrioritizationFee of old bank if it is collected on the bank. Perhaps still need to identify the old bank somehow (currently using sequence_numer), then drop the object.

fixed-size buffer will definitely be better than hash-map. Can get some details on that approach, helps to decide to do it on this PR, or a new one.

[tao-stones]

The PR is refreshed with all the pending changes, still need to nurse it through CI, but it is good for review. @CriesofCarrots @carllin @jdavis103

[CriesofCarrots]

I'm not sure what your CI failure is about...

[tao-stones]

I'm not sure what your CI failure is about...

Just force pushed a fix. Changes made to async update(...) resulted threads sync issue in a test. I went ok once on my workstation, but failed in CI. Glad COV Test being persistent on catching this bug.