cfx_packing_pool/
sample.rs

1use cfx_types::U256;
2use heap_map::HeapMap;
3use rand::RngCore;
4use treap_map;
5
6use crate::{
7    transaction::PackingPoolTransaction, treapmap_config::PackingPoolMap,
8};
9
10/// Enum representing the phase in which a transaction was selected during the
11/// sampling process. See [`TxSampler`] for more details.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum SampleTag {
14    /// Transaction was picked during the Random Sampling Phase.
15    RandomPick,
16    /// Transaction was picked during the Candidate Queue Phase.
17    CandidateAddress,
18    /// Transaction was picked during the Remaining Transactions Phase.
19    PriceDesc,
20}
21
22/// An iterator for sampling transactions from a packing pool.
23///
24/// `TxSampler` iterates over addresses, returning lists of transactions that
25/// come from the same sender, have continuous nonces, and pass
26/// [`PackingBatch`][crate::PackingBatch] and readiness checks.
27///
28/// The iterator operates in three phases:
29/// 1. **Random Sampling Phase**: Based on the random packing algorithm,
30/// addresses are selected from high    to low gas prices of their first
31/// transaction. The probability of inclusion is determined by the algorithm.
32/// Transactions not selected    are placed in a candidate queue.
33/// 2. **Candidate Queue Phase**: Transactions from the candidate queue are
34/// output in a random order. Transactions    with a higher probability in the
35/// first phase have a greater chance of appearing earlier in this phase.
36/// 3. **Remaining Transactions Phase**: Remaining addresses are output in
37/// descending order of their first transaction gas prices.
38///
39/// If the block's gas limit can accommodate all transactions in the packing
40/// pool, the iterator directly enters the third phase.
41pub struct TxSampler<'a, 'b, TX: PackingPoolTransaction, R: RngCore> {
42    iter: treap_map::Iter<'a, PackingPoolMap<TX>>,
43    /// A intermediated variable, record the first node that not considered in
44    /// the Random Sampling Phase.
45    first_unsample: Option<&'a treap_map::Node<PackingPoolMap<TX>>>,
46    /// If the iterator in the Random Sampling Phase.
47    random_sample_phase: bool,
48    /// The candidate quese
49    candidate_queue: HeapMap<TX::Sender, CandidateAddress<'a, TX>>,
50    /// A parameter from packing algorithm
51    loss_base: U256,
52    /// Random source
53    rng: &'b mut R,
54}
55
56impl<'a, 'b, TX: PackingPoolTransaction, R: RngCore> TxSampler<'a, 'b, TX, R> {
57    pub(crate) fn new(
58        iter: treap_map::Iter<'a, PackingPoolMap<TX>>, loss_base: U256,
59        rng: &'b mut R,
60    ) -> Self {
61        Self {
62            iter,
63            random_sample_phase: true,
64            first_unsample: None,
65            candidate_queue: Default::default(),
66            loss_base,
67            rng,
68        }
69    }
70
71    /// Iter in the **Remaining Transactions Phase**
72    #[inline]
73    fn price_desc_next(&mut self) -> Option<(TX::Sender, &'a [TX], SampleTag)> {
74        if let Some(node) = self.first_unsample {
75            self.first_unsample = None;
76            return Some((node.key, &node.value.txs[..], SampleTag::PriceDesc));
77        }
78        self.iter
79            .next()
80            .map(|node| (node.key, &node.value.txs[..], SampleTag::PriceDesc))
81    }
82
83    /// Iter in the **Candidate Queue Phase**
84    #[inline]
85    fn candidate_next(&mut self) -> Option<(TX::Sender, &'a [TX], SampleTag)> {
86        self.candidate_queue.pop().map(|(addr, candidate)| {
87            (
88                addr,
89                &candidate.node.value.txs[..],
90                SampleTag::CandidateAddress,
91            )
92        })
93    }
94
95    /// Iter in the **Random Sampling Phase**
96    #[inline]
97    fn random_sample(&mut self) -> Option<(TX::Sender, &'a [TX], SampleTag)> {
98        while let Some(node) = self.iter.next() {
99            let loss_threshold = if let Some(x) =
100                self.loss_base.checked_mul(node.weight.max_loss_ratio)
101            {
102                (x >> 192).as_u64()
103            } else {
104                self.random_sample_phase = false;
105                self.first_unsample = Some(node);
106                return None;
107            };
108
109            let target_quality = (u64::MAX - loss_threshold).saturating_add(1);
110            let sampled = self.rng.next_u64();
111            if sampled < target_quality {
112                return Some((
113                    node.key,
114                    &node.value.txs,
115                    SampleTag::RandomPick,
116                ));
117            } else {
118                self.candidate_queue.insert(
119                    &node.key,
120                    CandidateAddress {
121                        node,
122                        priority: (target_quality as f64)
123                            / ((sampled + 1) as f64),
124                    },
125                );
126            }
127        }
128        None
129    }
130}
131
132impl<'a, 'b, TX: PackingPoolTransaction, R: RngCore> Iterator
133    for TxSampler<'a, 'b, TX, R>
134{
135    type Item = (TX::Sender, &'a [TX], SampleTag);
136
137    fn next(&mut self) -> Option<Self::Item> {
138        // Packing pool is not full
139        if self.loss_base.is_zero() {
140            return self.price_desc_next();
141        }
142
143        if self.random_sample_phase {
144            let res = self.random_sample();
145            if res.is_some() {
146                return res;
147            }
148        }
149
150        let res = self.candidate_next();
151        if res.is_some() {
152            return res;
153        }
154        self.price_desc_next()
155    }
156}
157
158#[derive(Clone)]
159pub struct CandidateAddress<'a, TX: PackingPoolTransaction> {
160    node: &'a treap_map::Node<PackingPoolMap<TX>>,
161    priority: f64,
162}
163
164impl<'a, TX: PackingPoolTransaction> std::cmp::PartialEq
165    for CandidateAddress<'a, TX>
166{
167    fn eq(&self, other: &Self) -> bool { self.priority.eq(&other.priority) }
168}
169
170impl<'a, TX: PackingPoolTransaction> std::cmp::PartialOrd
171    for CandidateAddress<'a, TX>
172{
173    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
174        Some(self.cmp(other))
175    }
176}
177
178impl<'a, TX: PackingPoolTransaction> std::cmp::Eq for CandidateAddress<'a, TX> {}
179
180impl<'a, TX: PackingPoolTransaction> std::cmp::Ord
181    for CandidateAddress<'a, TX>
182{
183    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
184        self.priority.partial_cmp(&other.priority).unwrap()
185    }
186}
cfx_packing_pool/sample.rs

cfx_packing_pool/
sample.rs
