Part of cluster mempool: #30289.
1. Overview
This introduces the TxGraph class, which encapsulates knowledge about the fees, sizes, and dependencies between all mempool transactions, but nothing else. In particular, it lacks knowledge about CTransaction, inputs, outputs, txids, wtxids, prioritization, validatity, policy rules, and a lot more. Being restricted to just those aspects of the mempool makes the behavior very easy to fully specify (ignoring the actual linearizations produced), and write simulation-based tests for (which are included in this PR).
2. Interface
The interface can be largely categorized into:
- Mutation functions:
AddTransaction(add a new transaction with specified feerate, and get aRefobject back to identify it).RemoveTransaction(given aRefobject, remove the transaction).AddDependency(given twoRefobjects, add a dependency between them).SetTransactionFeerate(modify the feerate associated with a Ref object).
- Inspector functions:
GetAncestors(get the ancestor set in the form ofRef*pointers)GetDescendants(get the descendant set in the form ofRef*pointers)GetCluster(get the connected component set in the form ofRef*pointers, in the order they would be mined).GetIndividualFeerate(get the feerate of a tranaction)GetChunkFeerate(get the mining score of a transaction)CountDistinctClusters(count the number of distinct clusters a list ofRefs belong to)
- Staging functions:
StartStaging(make all future mutations operate on a proposed transaction graph)CommitStaging(apply all the changes that are staged)AbortStaging(discard all the changes that are staged)
- Miscellaneous functions:
DoWork(do queued-up computations now, so that future operations are fast)
This TxGraph::Ref type used as a “handle” on transactions in the graph can be inherited from, and the idea is that in the full cluster mempool implementation (#28676, after it is rebased on this), CTxMempoolEntry will inherit from it, and all actually used Ref objects will be CTxMempoolEntrys. With that, the mempool code can just cast any Ref* returned by txgraph to CTxMempoolEntry*.
3. Implementation
Internally the graph data is kept in clustered form (partitioned into connected components), for which linearizations are maintained and updated as needed using the cluster_linearize.h algorithms under the hood, but this is hidden from the users of this class. Implementation-wise, mutations are generally applied lazily, appending to queues of to-be-removed transactions and to-be-added dependencies, so they can be batched for higher performance. Inspectors will generally only evaluate as much as is needed to answer queries, with roughly 5 levels of processing to go to fully instantiated and acceptable cluster linearizations, in order:
ApplyRemovals(take batches of to-be-removed transactions and translate them to “holes” in the corresponding Clusters/DepGraphs).SplitAll(creating holes in Clusters may cause them to break apart into smaller connected components, so make turn them into separate Clusters/linearizations).GroupClusters(figure out which Clusters will need to be combined in order to add requested to-be-added dependencies, as these may span clusters).ApplyDependencies(actually merge Clusters as precomputed byGroupClusters, and add the dependencies between them).MakeAcceptable(perform the LIMO linearization algorithm on Clusters to make sure their linearizations are acceptable).
4. Future work
This is only an initial version of TxGraph, and some functionality is missing before #28676 can be rebased on top of it:
- The ability to get comparative feerate diagrams before/after for the set of staged changes (to evaluate RBF incentive-compatibility).
- Mining interface (ability to iterate transactions quickly in mining score order) (see #31444).
- Eviction interface (reverse of mining order, plus memory usage accounting) (see #31444).
- Ability to inspect the would-be-constructed clusters (so they can be “fixed” if they violate policy rules, as opposed to just accepted/rejected, before applying - this is needed for reorgs which are not optional).
- Interface for controlling how much effort is spent on LIMO. In this PR it is hardcoded.
Then there are further improvements possible which would not block other work:
- Making Cluster a virtual class with different implementations based on transaction count (which could dramatically reduce memory usage, as most Clusters are just a single transaction, for which the current implementation is overkill).
- The ability to have background thread(s) for improving cluster linearizations.
