Part of cluster mempool (#30289). Builds on top of #31444.
During reorganisations, it is possible that dependencies get added which would result in clusters that violate policy limits (cluster count, cluster weight), when linking the new from-block transactions to the old from-mempool transactions. Unlike RBF scenarios, we cannot simply reject the changes when they are due to received blocks. To accommodate this, add a TxGraph::Trim()
, which removes some subset of transactions (including descendants) in order to make all resulting clusters satisfy the limits.
Conceptually, the way this is done is by defining a rudimentary linearization for the entire would-be too-large cluster, iterating it from beginning to end, and reasoning about the counts and weights of the clusters that would be reached using transactions up to that point. If a transaction is encountered whose addition would violate the limit, it is removed, together with all its descendants.
This rudimentary linearization is like a merge sort of the chunks of the clusters being combined, but respecting topology. More specifically, it is continuously picking the highest-chunk-feerate remaining transaction among those which have no unmet dependencies left. For efficiency, this rudimentary linearization is computed lazily, by putting all viable transactions in a heap, sorted by chunk feerate, and adding new transactions to it as they become viable.
The Trim()
function is rather unusual compared to the TxGraph
functionality added in previous PRs, in that Trim()
makes it own decisions about what the resulting graph contents will be, without good specification of how it makes that decision - it is just a best-effort attempt (which is improved in the last commit). All other TxGraph
mutators are simply to inform the graph about changes the calling mempool code decided on; this one lets the decision be made by txgraph.
As part of this, the “oversized” property is expanded to also encompass a configurable cluster weight limit (in addition to cluster count limit).