cluster mempool: add TxGraph work controls

sipa commented at 9:29 pm on April 13, 2025: member

Part of #30289. Builds on top of #31553.

So far, the TxGraph::DoWork() function took no parameters, and just made all clusters reach the “acceptable” internal quality level by performing a minimum number of improvement iterations on it, but:

Did not attempt to go beyond that.
Was broken, as the QualityLevel of optimal clusters that merge together was not being reset.

Fix this by adding an argument to DoWork() to control how much work it is allowed to do right now, which will first be used to get all clusters to the acceptable level, and if more budget remains, use it to try to get some or all clusters optimal. The function will now return true if all clusters are known to be optimal (and thus no further work remains). This is verified in the tests, by remembering whether the graph is optimal, and if it is at the end of the simulation run, verify that the overall linearization cannot be improved further.

txgraph: compare sequence numbers instead of Cluster* (bugfix)

This makes fuzz testing more deterministic, by avoiding the (arbitrary) pointer
value ordering in comparing transactions.

905361424b

txgraph: make GroupClusters use partition numbers directly (optimization) 777e742826

txgraph: Add GetMainStagingDiagrams function (feature)

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

a658341f06

txgraph: Maintain chunk index (preparation)

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

cdc487befe

txgraph: Introduce TxGraphImpl observer tracking (preparation)

This is preparation for a next commit which will introduce a class whose
objects hold references to internals in TxGraphImpl, which disallows
modifications to the graph while such objects exist.

58a2a743cd

txgraph: Generalize GetClusterRefs to support subsections (preparation)

This is preparation for a next commit which will need a way to extract Refs
for just individual chunks from a cluster.

87b009b9db

txgraph: Introduce BlockBuilder interface (feature)

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).

fd51a29392

txgraph: Introduce TxGraph::GetWorstMainChunk (feature)

It returns the last chunk that would be suggested for mining by BlockBuilder
objects. This is intended for eviction.

c61b202855

txgraph: Reuse discarded chunkindex entries (optimization) d0a916f932

txgraph: Skipping end of cluster has no impact (optimization) 9c81318e2a

txgraph: Special-case singletons in chunk index (optimization) 58110899fd

txgraph: Add ability to configure maximum cluster size/weight (feature)

This is integrated with the oversized property: the graph is oversized when
any connected component within it contains more than the cluster count limit
many transactions, or when their combined size/weight exceeds the cluster size
limit.

It becomes disallowed to call AddTransaction with a size larger than this limit.
In addition, SetTransactionFeeRate becomes SetTransactionFee, so that we do not
need to deal with the case that a call to this function might affect the
oversizedness.

299a4d9718

txgraph: Permit transactions that exceed cluster size limit (feature) a8239edab3

txgraph: Add ability to trim oversized clusters (feature)

During reorganisations, it is possible that dependencies get add which
result in clusters that violate limits (count, size), when linking the
new from-block transactions to the old from-mempool transactions.

Unlike RBF scenarios, we cannot simply reject these policy violations
when they are due to received blocks. To accomodate this, add a Trim()
function to TxGraph, which removes transactions (including descendants)
in order to make all resulting clusters satisfy the limits.

65f1aaa738

txgraph: Track multiple potential would-be clusters in Trim (improvement)

In a Trim function, for any given would-be group of clusters, a (rudimentary)
linearization for the would-be cluster is constructed on the fly by adding
eligible transactions to a heap. This continues until the total count or
size of the transaction exists a configured limit. Any transactions which
appear later in this linearization are discarded.

However, given that transactions at the end are discarded, it is possible that
the would-be cluster splits apart into multiple clusters. And those clusters
may well permit far more transactions before their limits are reached.

Take this into account by using a union-find structure inside TrimTxData to
keep track of the count/size of all would-be clusters that would be formed
at any point.

This is not an optimization in terms of CPU usage or memory; it just
improves the quality of the transactions removed by Trim().

39586d51ef

txgraph: reset quality when merging clusters (bugfix) 77d5c0bdc2

DrahtBot commented at 9:29 pm on April 13, 2025: 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/32263.

Reviews

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#32191 (Make TxGraph fuzz tests more deterministic by sipa)
#31553 (cluster mempool: add TxGraph reorg functionality by sipa)
#31444 (cluster mempool: add txgraph diagrams/mining/eviction by sipa)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

sipa marked this as a draft on Apr 13, 2025

DrahtBot added the label CI failed on Apr 13, 2025

DrahtBot commented at 10:42 pm on April 13, 2025: contributor

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

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.

txgraph: singleton split-off clusters are optimal (optimization) 4e3f4b9eb6

txgraph: track amount of work done in linearization (preparation) e01e3925c7

txgraph: make number of acceptable iterations configurable (feature) 81a88311b5

txgraph: add work limit to DoWork(), try optimal (feature)

This adds an `iters` parameter to DoWork(), which controls how much work it is
allowed to do right now.

Additionally, DoWork() won't stop at just getting everything ACCEPTABLE, but if
there is work budget left, will also attempt to get every cluster linearized
optimally.

8e423fd0fc

sipa force-pushed on Apr 14, 2025

DrahtBot removed the label CI failed on Apr 14, 2025

cluster mempool: add TxGraph work controls #32263

Code Coverage & Benchmarks

Reviews

Conflicts