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.
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.
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:
#32545 (Replace cluster linearization algorithm with SFL 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
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 Apr 14, 2025
DrahtBot removed the label
CI failed
on Apr 14, 2025
in
src/test/fuzz/txgraph.cpp:320
in
81a88311b5outdated
268@@ -269,9 +269,11 @@ FUZZ_TARGET(txgraph)
269 auto max_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
270 // And the maximum combined size of transactions per cluster.
271 auto max_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT);
272+ // And the number of iterations to consider a cluster acceptably linearized.
273+ auto acceptable_iters = provider.ConsumeIntegralInRange<uint64_t>(0, 10000);
instagibbs
commented at 5:27 pm on April 14, 2025:
nice, this should allow some non-optimals to finally be created :+1:
DrahtBot added the label
Needs rebase
on Apr 17, 2025
sipa force-pushed
on Apr 17, 2025
DrahtBot removed the label
Needs rebase
on Apr 17, 2025
sipa force-pushed
on Apr 22, 2025
DrahtBot added the label
CI failed
on Apr 28, 2025
sipa force-pushed
on Apr 30, 2025
DrahtBot removed the label
CI failed
on Apr 30, 2025
sipa force-pushed
on May 12, 2025
sipa force-pushed
on May 13, 2025
sipa added the label
Mempool
on May 20, 2025
sipa force-pushed
on May 21, 2025
DrahtBot added the label
CI failed
on May 22, 2025
sipa force-pushed
on May 22, 2025
DrahtBot removed the label
CI failed
on May 22, 2025
sipa force-pushed
on May 22, 2025
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,
though this limit will be lifted in the next commit.
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.
416a8d16d0
txgraph: Permit transactions that exceed cluster size limit (feature)
This removes the restriction added in the previous commit that individual
transactions do not exceed the max cluster size limit.
With this change, the responsibility for enforcing cluster size limits can
be localized purely in TxGraph, without callers (and in particular, tests)
needing to duplicate the enforcement for individual transactions.
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.
In the initial version of the function added here, the following approach
is used:
- Lazily compute a naive linearization for the to-be-merged cluster (using
an O(n log n) algorithm, optimized for far larger groups of transactions
than the normal linearization code).
- Initialize a set of accepted transactions to {}
- Iterate over the transactions in this cluster one by one:
- If adding the transaction to the set makes it exceed the max cluster size
or count limit, stop.
- Add the transaction to the set.
- Remove all transactions from the cluster that were not included in the set
(note that this necessarily includes all descendants too, because they
appear later in the naive linearization).
Co-authored-by: Greg Sanders <gsanders87@gmail.com>
1664ec567f
txgraph: Track multiple potential would-be clusters in Trim (improvement)
In the existing Trim function, as soon as the set of accepted transactions
would exceed the max cluster size or count limit, the acceptance loop is
stopped, removing all later transactions. However, it is possible that by
excluding some of those transactions the would-be cluster splits apart into
multiple would-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, and only reject transactions which would cause these resulting
partitions to exceed their limits.
This is not an optimization in terms of CPU usage or memory; it just
improves the quality of the transactions removed by Trim().
45e3661d25
sipa force-pushed
on May 28, 2025
sipa force-pushed
on May 28, 2025
DrahtBot added the label
CI failed
on May 28, 2025
DrahtBot
commented at 3:32 am on May 28, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task macOS-cross, gui, no tests: https://github.com/bitcoin/bitcoin/runs/43009701810
LLM reason (✨ experimental): The CI failure is due to a compilation error caused by an incompatible call to std::max with mixed types in txgraph.cpp.
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.
DrahtBot removed the label
CI failed
on May 28, 2025
txgraph: add fuzz test scenario that avoids cycles inside Trim()
Trim internally builds an approximate dependency graph of the merged cluster,
replacing all existing dependencies within existing clusters with a simple
linear chain of dependencies. This helps keep the complexity of the merging
operation down, but may result in cycles to appear in the general case, even
though in real scenarios (where Trim is called for stitching re-added mempool
transactions after a reorg back to the existing mempool transactions) such
cycles are not possible.
Add a test that specifically targets Trim() but in scenarios where it is
guaranteed not to have any cycles. It is a special case, is much more a
whitebox test than a blackbox test, and relies on randomness rather than
fuzz input. The upside is that somewhat stronger properties can be tested.
Co-authored-by: Greg Sanders <gsanders87@gmail.com>
e1f501cab2
txgraph: reset quality when merging clusters (bugfix)1fb84bcb98
txgraph: singleton split-off clusters are optimal (optimization)b61d50c5b1
txgraph: track amount of work done in linearization (preparation)4ce878a8d1
txgraph: make number of acceptable iterations configurable (feature)e2fff46b00
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.
This is a metadata mirror of the GitHub repository
bitcoin/bitcoin.
This site is not affiliated with GitHub.
Content is generated from a GitHub metadata backup.
generated: 2025-05-31 00:12 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
