zebrad/components/mempool/storage/
eviction_list.rs

Help
1//! [`EvictionList`] represents the transaction eviction list with
2//! efficient operations.
3use std::{
4    collections::{HashMap, VecDeque},
5    time::{Duration, Instant},
6};
7
8use zebra_chain::transaction;
9
10/// An eviction list that allows Zebra to efficiently add entries, get entries,
11/// and remove older entries in the order they were inserted.
12pub struct EvictionList {
13    // Maps each TXID in the list to the most recent instant they were added.
14    unique_entries: HashMap<transaction::Hash, Instant>,
15    // The same as `unique_entries` but in the order they were inserted.
16    ordered_entries: VecDeque<transaction::Hash>,
17    // The maximum size of `unique_entries`.
18    max_size: usize,
19    /// The mempool transaction eviction age limit.
20    /// Same as [`Config::eviction_memory_time`][1].
21    ///
22    /// [1]: super::super::Config::eviction_memory_time
23    eviction_memory_time: Duration,
24}
25
26impl EvictionList {
27    /// Create a new [`EvictionList`] with the given maximum size and
28    /// eviction time.
29    pub fn new(max_size: usize, eviction_memory_time: Duration) -> Self {
30        Self {
31            unique_entries: Default::default(),
32            ordered_entries: Default::default(),
33            max_size,
34            eviction_memory_time,
35        }
36    }
37
38    /// Inserts a TXID in the list, keeping track of the time it was inserted.
39    ///
40    /// All entries older than [`EvictionList::eviction_memory_time`] will be removed.
41    ///
42    /// # Panics
43    ///
44    /// If the TXID is already in the list.
45    ///
46    pub fn insert(&mut self, key: transaction::Hash) {
47        // From https://zips.z.cash/zip-0401#specification:
48        // > Nodes SHOULD remove transactions from RecentlyEvicted that were evicted more than
49        // > mempoolevictionmemoryminutes minutes ago. This MAY be done periodically,
50        // > and/or just before RecentlyEvicted is accessed when receiving a transaction.
51        self.prune_old();
52        // > Add the txid and the current time to RecentlyEvicted, dropping the oldest entry
53        // > in RecentlyEvicted if necessary to keep it to at most eviction_memory_entries entries.
54        if self.len() >= self.max_size {
55            self.pop_front();
56        }
57        let value = Instant::now();
58        let old_value = self.unique_entries.insert(key, value);
59        // It should be impossible for an already-evicted transaction to be evicted
60        // again since transactions are not added to the mempool if they are evicted,
61        // and the mempool doesn't allow inserting two transactions with the same
62        // hash (they would conflict).
63        assert_eq!(
64            old_value, None,
65            "an already-evicted transaction should not be evicted again"
66        );
67        self.ordered_entries.push_back(key)
68    }
69
70    /// Checks if the given TXID is in the list.
71    pub fn contains_key(&self, txid: &transaction::Hash) -> bool {
72        if let Some(evicted_at) = self.unique_entries.get(txid) {
73            // Since the list is pruned only in mutable functions, make sure
74            // we take expired items into account.
75            if !self.has_expired(evicted_at) {
76                return true;
77            }
78        }
79        false
80    }
81
82    /// Get the size of the list.
83    //
84    // Note: if this method being mutable becomes an issue, it's possible
85    // to compute the number of expired transactions and subtract,
86    // at the cost of `O(len + expired)` performance each time the method is called.
87    //
88    // Currently the performance is `O(expired)` for the first call, then `O(1)` until the next expiry.
89    pub fn len(&mut self) -> usize {
90        self.prune_old();
91        self.unique_entries.len()
92    }
93
94    /// Clear the list.
95    #[allow(dead_code)]
96    pub fn clear(&mut self) {
97        self.unique_entries.clear();
98        self.ordered_entries.clear();
99    }
100
101    /// Prune TXIDs that are older than `eviction_time` ago.
102    ///
103    // This method is public because ZIP-401 states about pruning:
104    // > This MAY be done periodically,
105    pub fn prune_old(&mut self) {
106        while let Some(txid) = self.front() {
107            let evicted_at = self
108                .unique_entries
109                .get(txid)
110                .unwrap_or_else(|| panic!("all entries should exist in both ordered_entries and unique_entries, missing {txid:?} in unique_entries"));
111            if self.has_expired(evicted_at) {
112                self.pop_front();
113            } else {
114                break;
115            }
116        }
117    }
118
119    /// Get the oldest TXID in the list.
120    fn front(&self) -> Option<&transaction::Hash> {
121        self.ordered_entries.front()
122    }
123
124    /// Removes the first element and returns it, or `None` if the `EvictionList`
125    /// is empty.
126    fn pop_front(&mut self) -> Option<transaction::Hash> {
127        if let Some(key) = self.ordered_entries.pop_front() {
128            let removed = self.unique_entries.remove(&key);
129            assert!(
130                removed.is_some(),
131                "all entries should exist in both ordered_entries and unique_entries, missing {key:?} in unique_entries"
132            );
133            Some(key)
134        } else {
135            None
136        }
137    }
138
139    /// Returns if `evicted_at` is considered expired considering the current
140    /// time and the configured eviction time.
141    fn has_expired(&self, evicted_at: &Instant) -> bool {
142        let now = Instant::now();
143        (now - *evicted_at) > self.eviction_memory_time
144    }
145}
zebrad/components/mempool/storage/eviction_list.rs

zebrad/components/mempool/storage/
eviction_list.rs
