Struct Frontier 

pub struct Frontier { /* private fields */ }

Management of the transaction pool frontier, that is, the set of transactions in the transaction pool which have no mempool ancestors and are essentially ready to enter the next block template.

Implementations

impl Frontier

pub fn total_weight(&self) -> f64

pub fn total_mass(&self) -> u64

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn insert(&mut self, key: FeerateTransactionKey) -> bool

pub fn remove(&mut self, key: &FeerateTransactionKey) -> bool

pub fn sample_inplace<R>( &self, rng: &mut R, policy: &Policy, _collisions: &mut u64, ) -> SequenceSelectorInput

where R: Rng + ?Sized,

Samples the frontier in-place based on the provided policy and returns a SequenceSelector.

This sampling algorithm should be used when frontier total mass is high enough compared to policy mass limit so that the probability of sampling collisions remains low.

Convergence analysis: 1. Based on the above we can safely assume that k << n, where n is the total number of frontier items and k is the number of actual samples (since desired_mass << total_mass and mass per item is bounded) 2. Indeed, if the weight distribution is not too spread (i.e., max(weights) = O(min(weights))), k << n means that the probability of collisions is low enough and the sampling process will converge in O(k log(n)) w.h.p. 3. It remains to deal with the case where the weight distribution is highly biased. The process implemented below keeps track of the top-weight element. If the distribution is highly biased, this element will be sampled with sufficient probability (in constant time). Following each sampling collision we search for a consecutive range of top elements which were already sampled and narrow the sampling space to exclude them all. We do this by computing the prefix weight up to the top most item which wasn’t sampled yet (inclusive) and then continue the sampling process over the narrowed space. This process is repeated until acquiring the desired mass.
4. Numerical stability. Naively, one would simply subtract total_weight -= top.weight in order to narrow the sampling space. However, if top.weight is much larger than the remaining weight, the above f64 subtraction will yield a number close or equal to zero. We fix this by implementing a log(n) prefix weight operation. 5. Q. Why not just use u64 weights? A. The current weight calculation is feerate^alpha with alpha=3. Using u64 would mean that the feerate space is limited to a range of size (2^64)^(1/3) = ~2^21 = ~2M. Already with current usages, the feerate can vary from ~1/50 (2000 sompi for a transaction with 100K storage mass), to 5M (100 KAS fee for a transaction with 2000 mass = 100·100_000_000/2000), resulting in a range of size 250M (5M/(1/50)). By using floating point arithmetics we gain the adjustment of the probability space to the accuracy level required for current samples. And if the space is highly biased, the repeated elimination of top items and the prefix weight computation will readjust it.

pub fn build_selector( &self, policy: &Policy, ) -> Box<dyn TemplateTransactionSelector>

Dynamically builds a transaction selector based on the specific state of the ready transactions frontier.

The logic is divided into three cases: 1. The frontier is small and can fit entirely into a block: perform no sampling and return a TakeAllSelector 2. The frontier has at least ~4x the capacity of a block: expected collision rate is low, perform in-place k*log(n) sampling and return a SequenceSelector 3. The frontier has 1-4x capacity of a block. In this case we expect a high collision rate while the number of overall transactions is still low, so we take all of the transactions and use the rebalancing weighted selector (performing the actual sampling out of the mempool lock)

The above thresholds were selected based on benchmarks. Overall, this dynamic selection provides full transaction selection in less than 150 µs even if the frontier has 1M entries (!!). See mining/benches for more details.

pub fn build_selector_sample_inplace( &self, _collisions: &mut u64, ) -> Box<dyn TemplateTransactionSelector>

Exposed for benchmarking purposes

pub fn build_selector_take_all(&self) -> Box<dyn TemplateTransactionSelector>

Exposed for benchmarking purposes

pub fn build_rebalancing_selector(&self) -> Box<dyn TemplateTransactionSelector>

Exposed for benchmarking purposes

pub fn build_feerate_estimator( &self, args: FeerateEstimatorArgs, ) -> FeerateEstimator

Builds a feerate estimator based on internal state of the ready transactions frontier

pub fn ascending_iter( &self, ) -> impl DoubleEndedIterator<Item = &Arc<Transaction>> + ExactSizeIterator + FusedIterator

Returns an iterator to the transactions in the frontier in increasing feerate order

Trait Implementations

impl Default for Frontier

fn default() -> Frontier

Returns the “default value” for a type.