## Keyboard shortcuts Press `←` or `→` to navigate between chapters Press `S` or `/` to search in the book Press `?` to show this help Press `Esc` to hide this help - Auto - Light - Dark # Algorand Specifications The _Transaction Pool_ TxPoolTxPool is a Ledger component that maintains a queue of transactions received by the node. This section presents an implementor-oriented definition of TxPoolTxPool and is based on the [reference implementation](https://github.com/algorand/go-algorand/blob/b6e5bcadf0ad3861d4805c51cbf3f695c38a93b7/data/pools/transactionPool.go#L52) to clarify how it is constructed and operated by a node. The TxPoolTxPool implementation makes use of two distinct queues to aid the processes of pruning already observed transactions and block commitment: - The _remembered_ queue TxPoolrqTxPoolrq, - The _pending_ queue TxPoolpqTxPoolpq. The _pending queue_ TxPoolpqTxPoolpq is the main structure used to supply transactions to the active _pending_ BlockEvaluatorBlockEvaluator, which evaluates transactions for the next block. > Important > **IMPLEMENTATION:** > Pending block evaluator [reference implementation](https://github.com/algorand/go-algorand/blob/34deef26be34aebbdd7221dd2c55181e6f584bd2/data/pools/transactionPool.go#L557). > Important > **IMPLEMENTATION:** > Here we provide some implementation details about the _remembered_ queue TxPoolrqTxPoolrq and the _pending_ queue TxPoolpqTxPoolpq structures used in the TxPoolTxPool. > Whenever a new block is confirmed and committed to the Ledger, the node triggers `OnNewBlock`. > This function may rebuild the pending BlockEvaluatorBlockEvaluator (except for a future round’s pending BlockEvaluatorBlockEvaluator). As part of this process, the _pending queue_ TxPoolpqTxPoolpq is synchronized with the _remembered queue_ TxPoolrqTxPoolrq by replacing its contents entirely. > In contrast, when the `Remember` function is called, the verified transaction group is first appended to the _remembered queue_ TxPoolrqTxPoolrq. Then the entire TxPoolrqTxPoolrq is appended to TxPoolpqTxPoolpq rather than replacing it. This causes the two queues to diverge temporarily until the next `OnNewBlock` call resyncs them. > Example of `Remember` function used by the `txnHandler` to enqueue a verified transaction group in the [reference implementation](https://github.com/algorand/go-algorand/blob/34deef26be34aebbdd7221dd2c55181e6f584bd2/data/txHandler.go#L542). > For more detail, see the `rememberCommit(bool flush)` function, which controls how TxPoolpqTxPoolpq is updated from TxPoolrqTxPoolrq. > If `flush=true`, TxPoolpqTxPoolpq is completely overwritten; if `flush=false`, TxPoolrqTxPoolrq is appended. > In summary: > - `OnNewBlock` → calls `rememberCommit(true)` → replaces TxPoolpqTxPoolpq with TxPoolrqTxPoolrq. > - `Remember` → appends to TxPoolrqTxPoolrq, then calls `rememberCommit(false)` → appends TxPoolrqTxPoolrq to TxPoolpqTxPoolpq. > > Temporary queue divergence is expected and resolved at the next block confirmation. > Given a properly signed and _well-formed_ transaction group gtx∈TxPoolpqgtx∈TxPoolpq, we say that gtxgtx is _remembered_ when it is pushed into TxPoolrqTxPoolrq if: > - Its _aggregated fee_ is sufficiently high, > - Its state changes are consistent with the prior transactions in TxPoolrqTxPoolrq. > Note that a single transaction can be viewed as a group gtxgtx containing only one transaction. > TxPoolrqTxPoolrq is structured as a two-dimensional array. Each element in this array holds a list of _well-formed_, _signed_ transactions. > To improve efficiency, the node also uses a key-value mapping where the keys are [transaction IDs](https://specs.algorand.co/ledger/ledger-transactions) and the values are the corresponding signed transactions. This map duplicates the data in the queue, which adds a small computational cost when updating the queue (for insertions and deletions), but it enables fast, constant-time O(1)O(1) lookup of any enqueued transaction by its ID. > Additionally, TxPoolpqTxPoolpq serves as another layer of optimization. It stores transaction groups that are prepared in advance for the next _block assembly_ process. In a multithreaded system with strict timing constraints, this setup allows TxPoolrqTxPoolrq to be pruned as soon as a new block is committed, even while the next block is being assembled concurrently. The following is a list of _abstracted minimal functionalities_ that the TxPoolTxPool should provide. An algorithm that decides which transactions should be retained and which ones should be dropped, especially important when the TxPoolTxPool becomes congested (i.e., when transactions are arriving faster than they can be processed, de-enqueued in a block, or observed in a committed block and pruned). A simple approach could be a _“first-come, _first-served”_ policy. However, the `go-algorand` reference implementation uses a more selective method: a threshold-based _fee prioritization_ algorithm, which prioritizes transactions paying higher fees. This process is triggered when a new block is observed as committed. At this point, transactions are pruned if they meet either of the following conditions: - They have already been included in a committed block (as determined by the `OnNewBlock` function), or - Their `LastValid` [field](https://specs.algorand.co/ledger/ledger-transactions#first-and-last-valid-round) has expired. Specifically, if the current round r>TxLastValidr>TxLastValid. In addition to pruning outdated or committed transactions, this step also updates the internal variables used for the _prioritization_. This component handles the ingestion of new transaction groups (gtxgtx) that are to be remembered (enqueued to TxPoolrqTxPoolrq). Before enqueuing, it verifies that each transaction group is internally valid and consistent in the context of transactions already present in TxPoolrqTxPoolrq. Once transactions pass these checks, they are forwarded to any active _Block Evaluator_, so they can be considered for inclusion in blocks currently being assembled. This process builds a new block’s [`payset`](https://specs.algorand.co/ledger/ledger-block) (the body with block’s transactions) by selecting valid transaction groups gtxgtx dequeued from the TxPoolTxPool, all within a deadline. A (pending) _Block Evaluator_ is responsible for processing the transactions, while the `BlockAssembly` function coordinates with it. The assembly process halts as soon as the time constraints are reached.