transaction_pool/
lib.rs

1// Copyright 2020 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! Generic Transaction Pool
10//!
11//! An extensible and performant implementation of Ethereum Transaction Pool.
12//! The pool stores ordered, verified transactions according to some pluggable
13//! `Scoring` implementation.
14//! The pool also allows you to construct a set of `pending` transactions according
15//! to some notion of `Readiness` (pluggable).
16//!
17//! The pool is generic over transactions and should make no assumptions about them.
18//! The only thing we can rely on is the `Scoring` that defines:
19//!  - the ordering of transactions from a single sender
20//!  - the priority of the transaction compared to other transactions from different senders
21//!
22//! NOTE: the transactions from a single sender are not ordered by priority,
23//! but still when constructing pending set we always need to maintain the ordering
24//! (i.e. `txs[1]` always needs to be included after `txs[0]` even if it has higher priority)
25//!
26//! ### Design Details
27//!
28//! Performance assumptions:
29//! - Possibility to handle tens of thousands of transactions
30//! - Fast insertions and replacements `O(per-sender + log(senders))`
31//! - Reasonably fast removal of stalled transactions `O(per-sender)`
32//! - Reasonably fast construction of pending set `O(txs * (log(senders) + log(per-sender))`
33//!
34//! The removal performance could be improved by trading some memory. Currently `SmallVec` is used
35//! to store senders transactions, instead we could use `VecDeque` and efficiently `pop_front`
36//! the best transactions.
37//!
38//! The pending set construction and insertion complexity could be reduced by introducing
39//! a notion of `nonce` - an absolute, numeric ordering of transactions.
40//! We don't do that because of possible implications of EIP208 where nonce might not be
41//! explicitly available.
42//!
43//! 1. The pool groups transactions from particular sender together
44//!    and stores them ordered by `Scoring` within that group
45//!    i.e. `HashMap<Sender, Vec<Transaction>>`.
46//! 2. Additionally we maintain the best and the worst transaction from each sender
47//!    (by `Scoring` not `priority`) ordered by `priority`.
48//!    It means that we can easily identify the best transaction inside the entire pool
49//!    and the worst transaction.
50//! 3. Whenever new transaction is inserted to the queue:
51//!    - first check all the limits (overall, memory, per-sender)
52//!    - retrieve all transactions from a sender
53//!    - binary search for position to insert the transaction
54//!    - decide if we are replacing existing transaction (3 outcomes: drop, replace, insert)
55//!    - update best and worst transaction from that sender if affected
56//! 4. Pending List construction:
57//!    - Take the best transaction (by priority) from all senders to the List
58//!    - Replace the transaction with next transaction (by ordering) from that sender (if any)
59//!    - Repeat
60
61#![warn(missing_docs)]
62
63#[cfg(test)]
64mod tests;
65
66mod error;
67mod listener;
68mod options;
69mod pool;
70mod ready;
71mod replace;
72mod status;
73mod transactions;
74mod verifier;
75
76pub mod scoring;
77
78pub use self::error::Error;
79pub use self::listener::{Listener, NoopListener};
80pub use self::options::Options;
81pub use self::pool::{PendingIterator, Pool, Transaction, UnorderedIterator};
82pub use self::ready::{Readiness, Ready};
83pub use self::replace::{ReplaceTransaction, ShouldReplace};
84pub use self::scoring::Scoring;
85pub use self::status::{LightStatus, Status};
86pub use self::verifier::Verifier;
87
88use std::fmt;
89use std::hash::Hash;
90
91/// Already verified transaction that can be safely queued.
92pub trait VerifiedTransaction: fmt::Debug {
93	/// Transaction hash type.
94	type Hash: fmt::Debug + fmt::LowerHex + Eq + Clone + Hash;
95
96	/// Transaction sender type.
97	type Sender: fmt::Debug + Eq + Clone + Hash + Send;
98
99	/// Transaction hash
100	fn hash(&self) -> &Self::Hash;
101
102	/// Memory usage
103	fn mem_usage(&self) -> usize;
104
105	/// Transaction sender
106	fn sender(&self) -> &Self::Sender;
107}
transaction_pool/lib.rs

transaction_pool/
lib.rs
