cluster mempool: add txgraph diagrams/mining/eviction

sipa commented at 2:50 pm on December 8, 2024: member

Part of cluster mempool: #30289

This builds on #31363, adding more functionality to the txgraph module, specifically:

TxGraph::GetMainStagingDiagrams(), a function to obtain feerate diagrams for both the main graph and the staged changes to it, including only the clusters that differ between the two.
TxGraph::GetBlockBuilding(), a function to obtain an object which can efficiently iterate the chunks of the (main) graph from high to low chunk feerate, allowing each to be skipped or included.
TxGraph::GetEvictor(), a function to obtain an object which can efficiently iterate the chunks of the (main) graph from low to high chunk feerate, allowing each to be destroyed or not.

DrahtBot commented at 2:50 pm on December 8, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31444.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

sipa force-pushed on Dec 8, 2024

DrahtBot added the label CI failed on Dec 8, 2024

DrahtBot commented at 2:59 pm on December 8, 2024: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/34093447174

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

sipa force-pushed on Dec 8, 2024

DrahtBot removed the label CI failed on Dec 8, 2024

glozow added the label Mempool on Dec 17, 2024

clusterlin: add FixLinearization function + fuzz test

This function takes an existing ordering for transactions in a DepGraph, and
makes it a valid linearization for it (i.e., topological). Any topological
prefix of the input remains untouched.

a2d6beeb06

clusterlin: make IsAcyclic() a DepGraph member function

... instead of being a separate test-only function.

472be35af9

txgraph: (feature) add initial version

This adds an initial version of the txgraph module, with the TxGraph class.
It encapsulates knowledge about the fees, sizes, and dependencies between all
mempool transactions, but nothing else.

In particular, it lacks knowledge about txids, inputs, outputs, CTransactions,
... and so for. Instead, it exposes a generic TxGraph::Ref type to reference
nodes in the TxGraph, which can be passed around and stored by layers on top.

afc6a66577

txgraph: (tests) add simulation fuzz test

This adds a simulation fuzz test for txgraph, by comparing with a naive
reimplementation that models the entire graph as a single DepGraph, and
clusters in TxGraph as connected components within that DepGraph.

fe5cba8797

txgraph: (tests) add internal sanity check function

To make testing more powerful, expose a function to perform an internal sanity
check on the state of a TxGraph. This is especially important as TxGraphImpl
contains many redundantly represented pieces of information:

* graph contains clusters, which refer to entries, but the entries refer back
* graph maintains pointers to Ref objects, which point back to the graph.

This lets us make sure they are always in sync.

ee59e03d34

txgraph: (feature) make max cluster count configurable and "oversize" state

Instead of leaving the responsibility on higher layers to guarantee that
no connected component within TxGraph (a barely exposed concept, except through
GetCluster()) exceeds the cluster count limit, move this responsibility to
TxGraph itself:
* TxGraph retains a cluster count limit, but it becomes configurable at construction
  time (this primarily helps with testing that it is properly enforced).
* It is always allowed to perform mutators on TxGraph, even if they would cause the
  cluster count limit to be exceeded. Instead, TxGraph exposes an IsOversized()
  function, which queries whether it is in a special "oversize" state.
* During oversize state, many inspectors are unavailable, but mutators remain valid,
  so the higher layer can "fix" the oversize state before continuing.

acb199cce4

txgraph: (optimization) delay chunking while sub-acceptable

Chunk-based information (primarily, chunk feerates) are never accessed without
first bringing the relevant Clusters to an "acceptable" quality level. Thus,
while operations are ongoing and Clusters are not acceptable, we can omit
computing the chunkings and chunk feerates for Clusters.

557de5fffe

txgraph: (optimization) special-case removal of tail of cluster

When transactions are removed from the tail of a cluster, we know the existing
linearization remains acceptable/optimal (if it already was), but may just need
splitting, so special case these into separate quality levels.

d516224782

txgraph: (refactor) group per-graph data in ClusterSet

This is a preparation for a next commit where a TxGraph will start representing
potentially two distinct graphs (a main one, and a staging one with proposed
changes).

a88a10567a

txgraph: (refactor) abstract out ClearLocator

Move a number of related modifications to TxGraphImpl into a separate
function for removal of transactions. This is preparation for a later
commit where this will be useful in more than one place.

57d7e8db54

txgraph: (feature) add staging support

In order to make it easy to evaluate proposed changes to a TxGraph, introduce a
"staging" mode, where mutators (AddTransaction, AddDependency, RemoveTransaction)
do not modify the actual graph, but just a staging version of it. That staging
graph can then be commited (replacing the main one with it), or aborted (discarding
the staging).

4a2e383f5a

txgraph: (feature) destroying Ref means removing transaction

Before this commit, if a TxGraph::Ref object is destroyed, it becomes impossible
to refer to, but the actual corresponding transaction node in the TxGraph remains,
and remains indefinitely as there is no way to remove it.

Fix this by making the destruction of TxGraph::Ref trigger immediate removal of
the corresponding transaction in TxGraph, both in main and staging if it exists.

ef237a3c15

txgraph: (feature) expose ability to compare transactions

In order to make it possible for higher layers to compare transaction quality
(ordering within the implicit total ordering on the mempool), expose a comparison
function and test it.

19cd5a8c32

txgraph: (feature) Add GetMainStagingDiagrams function

This allows determining whether the changes in a staging diagram unambiguously improve
the graph, through CompareChunks().

f51d0afe2b

txgraph: (preparation) maintain chunk index

This is preparation for exposing mining and eviction functionality in
TxGraph.

67d39bfcae

txgraph: (feature) introduce BlockBuilder interface

This interface lets one iterate efficiently over the chunks of the main
graph in a TxGraph, in the same order as CompareMainOrder. Each chunk
can be marked as "included" or "skipped" (and in the latter case,
dependent chunks will be skipped).

d3c8a89252

txgraph: (feature) introduce Evictor interface

Similar to the BlockBuilder interface, this lets one iterate the set of
chunks in the entire graph. The iteration happens from low to high chunk
feerate however, does not permit skipping chunks, but does permit destroying
Refs of the chunks that are being iterated over.

5daa0238d8

txgraph: (optimization) reuse discarded chunkindex entries 04e077d975

txgraph: (optimization) skipping end of cluster has no impact f0a7490e0c

txgraph: (optimization) special-case singletons in chunk index b68bd663bf

sipa force-pushed on Dec 20, 2024

cluster mempool: add txgraph diagrams/mining/eviction #31444

Code Coverage & Benchmarks

Reviews

Conflicts