cluster mempool: add TxGraph reorg functionality#31553
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31553. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. ConflictsReviewers, this pull request conflicts with the following ones:
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. LLM Linter (✨ experimental)Possible typos and grammar issues:
drahtbot_id_4_m |
d84455d to
3e809fa
Compare
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
3e809fa to
75c6757
Compare
75c6757 to
5a6550f
Compare
theuni
left a comment
There was a problem hiding this comment.
Very quick and shallow pass through the initial impl commit. This PR is a lot to get through :)
5a6550f to
fa14d06
Compare
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
fa14d06 to
ab08987
Compare
fbd6568 to
9046cbf
Compare
9046cbf to
e4a2fd9
Compare
e4a2fd9 to
a312648
Compare
|
Some changes:
|
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
a312648 to
52c4105
Compare
|
df71855 to
265ad9e
Compare
There was a problem hiding this comment.
if anyone has ideas for tests that exercise the improved quality UF brings, I'm all ears
Maybe a starting point, I wrote a unit test to see the difference in trimming with 0b59916271c43cbedd14aafe88e5baf2dec2d97d: https://github.com/glozow/bitcoin/commits/2025-06-31553-test/
One test is a bunch of singleton transactions (e.g. from disconnected blocks) connected by 1 transaction (e.g. in the mempool).
- Initial
Trimimplementation: trims all but the topmax_cluster_counttransactions of the parents - With union-find tracking multiple: just trims the child, which leaves everything as singleton clusters
The other test is a trellis (e.g. parents all from disconnected blocks, children all already in mempool)
- Initial
Trimimplementation: trims half of the trellis (top and bottom), leaving just the prefix that is withinmax_cluster_countsize - With union-find tracking multiple: just trims the middle transaction, splitting it into 2 trellises
There was a bug in the second Trim commit
I haven't fully grokked this commit (there's something wrong with my eyesight whenever I look at the code), but before the last push, the trellis test was evicting 1/4 of the transactions: https://github.com/glozow/bitcoin/commits/2025-06-31553-trellis/
|
@glozow Awesome, thanks. I've included your commit (with minor changes) in this PR, and added my own 64000-transactions-merged-together test to it. |
|
@sipa to be clear, was the issue In that the optimization means we should keep on going in case we're going to create/add to undersized clusters, but this |
|
@instagibbs Yes, exactly. The commit was still an improvement, as it would only stop once an aggregate-of-clusters-so-far would exceed the limit, rather than stopping when the sum of all-clusters-so-far would exceed the limit (the behavior in the initial Trim commit). But with the |
instagibbs
left a comment
There was a problem hiding this comment.
reACK 643fffafdc70da5fbaf1992c36965595b9e63f84
and the UF structure purely for included or rejected transactions
i.e. rejected here means "things with no unmet deps yet never included"
Validated in my mental model that bug fix and heap logic changes are correct. Reviewed new unit tests and makes sense that it would have caught the bug. It's a bit further non-black-box, but they're simple.
git range-diff master e1f501cab224608004e3a1eee7a48eec3cea25fc 643fffafdc70da5fbaf1992c36965595b9e63f84
There was a problem hiding this comment.
nit: can just assert this number rather than put in comment
There was a problem hiding this comment.
I've added a computation for it, and assertion.
|
@instagibbs Done. Also expanded comments slightly, made unit test constant names a bit more consistent, and sprinkled some |
|
reACK 2b2df98747fdb6380588991167ce2e8cb92f3bfb |
|
Would there be interest in adding a benchmark for the Trim() operation here, or rather in a follow-up? |
|
@sipa linked here, added to follow-up potentially? |
|
@instagibbs @ismaelsadeeq See sipa@0a8e1d6 It's the same scenario as the |
|
@sipa one order of magnitude more for me on my wimpy laptop but well within acceptable bounds I suspect for a reorg. IIUC this is one of the more pessimistic mempool topologies for this since you're going to have to go through the ~entire mempool before finishing |
That will be nice, I don't mind adding it here. I plan to do another round of review of the added tests and diff after my last review so if added will review it as well. I try running the bench on the linked commit.
|
|
@ismaelsadeeq Yeah, the benchmark is in my "all txgraph" branch which also includes #32263. Removing the |
There was a problem hiding this comment.
ACK 2b2df98747fdb6380588991167ce2e8cb92f3bfb
Reviewed the code and the tests. I ran the bench to see that we spend a lot longer on the last commit since we are able to consider more potential clusters.
Before:
| ns/op | op/s | err% | total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
| 55,112,375.00 | 18.14 | 0.0% | 0.06 | `TxGraphTrim`
After:
| ns/op | op/s | err% | total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
| 71,068,959.00 | 14.07 | 0.0% | 0.07 | `TxGraphTrim`
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.
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.
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>
Co-Authored-By: Pieter Wuille <pieter@wuille.net>
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>
|
Addressed nits, and also incorporated the benchmark in this PR. |
…ent) 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().
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
instagibbs
left a comment
There was a problem hiding this comment.
reACK 1632fc1
Includes the benchmark and unit test for trimming singletons, and a text cleanup
git range-diff master 2b2df98747fdb6380588991167ce2e8cb92f3bfb 1632fc104be8f171f59a023800b2f9f20d0a3cff
| graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i + 1], /*child=*/refs[i]); | ||
| } | ||
|
|
||
| // Check that the graph is now oversized. This also forces the graph to |
There was a problem hiding this comment.
fwiw I commented out the IsOversized check and the test passes still as expected, with singletons
There was a problem hiding this comment.
True, there isn't actually anything to group in this test. Just copied from the other tests.
| // Create the zigzag dependency structure. | ||
| // Each transaction in the bottom row depends on two adjacent transactions from the top row. | ||
| graph->SanityCheck(); | ||
| for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) { |
There was a problem hiding this comment.
We start being oversized at i = 24 iteration.
Part of cluster mempool (#30289).
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 theTxGraphfunctionality added in previous PRs, in thatTrim()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 otherTxGraphmutators 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).