cluster mempool: Implement changeset interface for mempool by sdaftuar · Pull Request #31122 · bitcoin/bitcoin

sdaftuar · 2024-10-20T17:46:28Z

part of cluster mempool: #30289

It became clear while working on cluster mempool that it would be helpful for transaction validation if we could consider a full set of proposed changes to the mempool -- consisting of a set of transactions to add, and a set of transactions (ie conflicts) to simultaneously remove -- and perform calculations on what the mempool would look like if the proposed changes were to be applied. Two specific examples of where we'd like to do this:

Determining if ancestor/descendant/TRUC limits would be violated (in the future, cluster limits) if either a single transaction or a package of transactions were to be accepted
Determining if an RBF would make the mempool "better", however that idea is defined, both in the single transaction and package of transaction cases

In preparation for cluster mempool, I have pulled this reworking of the mempool interface out of #28676 so it can be reviewed on its own. I have not re-implemented ancestor/descendant limits to be run through the changeset, since with cluster mempool those limits will be going away, so this seems like wasted effort. However, I have rebased #28676 on top of this branch so reviewers can see what the new mempool interface could look like in the cluster mempool setting.

There are some minor behavior changes here, which I believe are inconsequential:

In the package validation setting, transactions would be added to the mempool before the ConsensusScriptChecks() are run. In theory, ConsensusScriptChecks() should always pass if the PolicyScriptChecks() have passed and it's just a belt-and-suspenders for us, but if somehow they were to diverge then there could be some small behavior change from adding transactions and then removing them, versus never adding them at all.
The error reporting on CheckConflictTopology() has slightly changed due to no longer distinguishing between direct conflicts and indirect conflicts. I believe this should be entirely inconsequential because there shouldn't be a logical difference between those two ideas from the perspective of this function, but I did have to update some error strings in some tests.
Because, in a package setting, RBFs now happen as part of the entire package being accepted, the logging has changed slightly because we do not know which transaction specifically evicted a given removed transaction.
- Specifically, the "package hash" is now used to reference the set of transactions that are being accepted, rather than any single txid. The log message relating to package RBF that happen in the TXPACKAGES category has been updated as well to include the package hash, so that it's possible to see which specific set of transactions are being referenced by that package hash.
- Relatedly, the tracepoint logging in the package rbf case has been updated as well to reference the package hash, rather than a transaction hash.

DrahtBot · 2024-10-20T17:46:31Z

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/31122.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	instagibbs, ismaelsadeeq, naumenkogs, glozow

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31318 (Drop script_pub_key arg from createNewBlock by Sjors)
#31283 (Add waitNext() to BlockTemplate interface by Sjors)
#30964 (Disable RBF Rule 2 by arik-so)
#30391 (BlockAssembler: return selected packages virtual size and fee by ismaelsadeeq)
#30157 (Fee Estimation via Fee rate Forecasters by ismaelsadeeq)
#29680 (wallet: fix unrelated parent conflict doesn't cause child tx to be marked as conflict by Eunovo)

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.

DrahtBot · 2024-10-20T19:19:59Z

🚧 At least one of the CI tasks failed.
_{Debug: https://github.com/bitcoin/bitcoin/runs/31793556861}

Hints

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.

glozow

Concept ACK, did a first pass

ismaelsadeeq

Concept ACK

The changes are straightforward to understand, and the large diff is primarily due to changes in the error message and the removal of addUnchecked.

sdaftuar · 2024-10-22T17:01:08Z

Thanks @glozow and @ismaelsadeeq for the review; I've incorporated some of the comments. If you have suggestions for how the logging can be improved in the package RBF case (and how the USDT tracing messages can be improved, similarly) please let me know your thoughts.

Also, I wanted to flag that the locking is a bit of a mess in this branch. Initially, I tried to add lock annotations to the CTxMemPoolChangeSet functions to guarantee that the mempool itself was locked whenever any of those functions were invoked. I had mixed results with the compiler understanding those annotations, and ran into a roadblock at some point with a unit test which was taking the mempool lock and should have satisfied the annotations, but the compiler wasn't recognizing the lock as being the same one that needed to be held. I assume the complication is mostly that the changeset is a different object than the mempool, so one thing I could try is moving all the changeset methods to instead be methods of the mempool itself (which take a changeset as an argument, potentially) -- but that also seems like a little bit of a mess to me, so wasn't sure if that was worth doing.

DrahtBot · 2024-10-23T17:12:20Z

🚧 At least one of the CI tasks failed.
_{Debug: https://github.com/bitcoin/bitcoin/runs/31962210262}

Hints

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.

instagibbs

first pass through, concept ACK

sdaftuar · 2024-11-13T18:33:10Z

Just rebased this on master -- @0xB10C thanks for the note on the tracepoint change. @instagibbs I think I could rewrite the CheckEphemeralSpends() code to take advantage of the changesets for package validation (since we will now be maintaining a map of package transactions that we can query), but maybe that can be done in a separate PR? Just left that code as-is for now.

@naumenkogs Thanks for looking at the validation change relating to consensus-invalid packages. Someone should probably test that logic by changing the policy checks to NOT be a strict superset of the consensus checks and verify that the logic I'm introducing here actually does what I think it does. I intend to do that myself but haven't gotten to it yet.

EDIT: I hacked up the validation logic to trigger this currently unreachable block of code -- ie to make the ConsensusScriptChecks() fail in a package validation context -- and verified that logic to remove the newly added transactions seems to work. Would be great for others to verify this as well!

instagibbs

ACK 5736d1d

Picks up TRACEPOINT and ephemeral dust stuff.

via git range-diff master 0ca1e05d8bcbc42892156c15f128a5f829e9e48e 5736d1ddacc4019101e7a5170dd25efbc63b622a

naumenkogs · 2024-11-14T07:48:55Z

@sdaftuar

EDIT: I hacked up the validation logic to trigger this currently unreachable block of code -- ie to make the ConsensusScriptChecks() fail in a package validation context -- and verified that logic to remove the newly added transactions seems to work. Would be great for others to verify this as well!

I had a little doubt that it will remove the transactions... Instead I was worried about evictions (i can't think of other side effects) of add/remove invalid stuff. Doesn't this allow to clear the victims mempool for free?

sdaftuar · 2024-11-14T11:18:22Z

Instead I was worried about evictions (i can't think of other side effects) of add/remove invalid stuff. Doesn't this allow to clear the victims mempool for free?

Just to be clear, in case anyone has lost track: we're specifically talking about a codepath we believe is not possible to trigger, namely one where the PolicyScriptChecks pass yet the ConsensusScriptChecks fail for some transaction, and someone is able to submit such a transaction as part of a package to our node.

In this event, I actually don't think the mempool could be directly drained, because we don't call LimitMempoolSize() until after this condition is detected and the new transactions are removed. However, I did observe that any RBF's that take place would not be fully reverted (ie the replaced transactions aren't being added back).

If it were simple to just re-add the just-removed transactions, I'd try to include that here as well, but it would take some additional work to topologically sort the removed transactions so they can be re-added. Given that this logic is unreachable and already difficult-to-test as a result, I don't think it makes sense to add any significant complexity, at least for now -- this may be simpler to think about post-cluster-mempool.

ismaelsadeeq

reACK 5736d1d

naumenkogs · 2024-11-18T08:32:27Z

ACK 5736d1d

My concern above was related to LimitMempoolSize(), but indeed it's easy to see it doesn't happen between the two m_changeset->Apply() calls.

For the RBF transactions i agree it's probably not worth complicating the code.

glozow

Still working on review. I've skimmed through the commits and reviewed the end state of MemPoolAccept so far.

glozow · 2024-11-18T13:40:45Z

+            // If not found, try to have the mempool calculate it, and cache
+            // for later.
+            LOCK(m_pool->cs);
+            auto ret{m_pool->CalculateMemPoolAncestors(*tx, limits)};
+            if (ret) m_ancestors.try_emplace(tx, *ret);
+            return ret;


This is maybe a TxGraph question, but will we get to the point where CMPA and CheckPackageLimits can do the calculations using all staged changes? For example, if it looks like I would bust cluster limits using current mempool, but my parent's RBF is breaking up the cluster / removing things from it.

I'm wondering if we could easily align our multi-testmempoolaccept interface with the ProcessNewPackage interface to support package CPFP and RBF by pointing testmempoolaccept down the same codepath, with some if (test_accept) conditions to skip submission and retain changeset + coinsview state.

TxGraph will be able reason about cluster count limits using arbitrary staged changes (so any combination of transaction deletions, transaction additions, and added dependencies).

These operations are always ordered as (1) tx additions (2) tx deletions (3) dep additions, even if they are invoked in a different order. So if you first add dependencies which - if applied - would violate the limit, and then delete some transactions in the cluster such that the result breaks up again and stays below the limit, that is fine.

I also have a goal of eliminating the need to invoke CMPA on a changeset anyway. In #28676, I believe the only place that CMPA is used in a changeset is for determining whether an RBF might be replacing something it depends on. I think it should be straightforward to have the changeset logic directly test for that condition and return failure if a dependency is being added to something that is slated for removal, which would then allow us to remove the method altogether.

glozow

ACK 5736d1d

I really like how ChangeSet codifies the concept of an atomic changeset of additions and removals, and how CalculateChunksForRBF and ImprovesFeerateDiagram operate on changesets. It's like the mempool interface is moving towards it being more responsible for itself.

glozow · 2024-11-20T11:27:31Z

+        }
+
+        size_t GetTxCount() const { return m_entry_vec.size(); }
+        const CTransaction& GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetTx(); }


nitty, but I wondered why not CTransactionRef here?

Suggested change

const CTransaction& GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetTx(); }

CTransactionRef GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetSharedTx(); }

glozow · 2024-11-20T11:43:13Z

+    // to track size/count of descendant transactions.  First version of
+    // addNewTransaction can be used to have it call CalculateMemPoolAncestors(), and
+    // then invoke the second version.


I misunderstood this comment initially, thinking it meant that you would call both addNewTransactions, but it actually means that one is a wrapper for the other, with a prepended CMPA. Callers should use one or the other.

glozow · 2024-11-20T12:06:13Z


 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
    AssertLockHeld(cs);
+    Assume(!m_have_changeset);


b447416 is nice!

glozow · 2024-11-20T12:28:16Z

    const auto tx2_size = entry2->GetTxSize();

+    // conflicting transactions
+    const auto tx1_conflict = make_tx(/*inputs=*/ {m_coinbase_txns[0], m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});


nit: these changes were perhaps meant for d7dc9fd instead of 284a1d3?

laanwj added the Mempool label Oct 20, 2024

sipa mentioned this pull request Oct 20, 2024

Cluster mempool tracking issue #30289

Closed

33 tasks

DrahtBot added the CI failed label Oct 20, 2024

sdaftuar force-pushed the 2024-10-mempool-changeset branch from c04c3bd to bb7b43b Compare October 20, 2024 23:38

DrahtBot removed the CI failed label Oct 21, 2024

sdaftuar force-pushed the 2024-10-mempool-changeset branch from bb7b43b to aeefd31 Compare October 21, 2024 12:30

glozow reviewed Oct 22, 2024

View reviewed changes

Comment thread src/txmempool.h Outdated

Comment thread src/txmempool.h Outdated

Comment thread src/txmempool.h Outdated

Comment thread src/validation.cpp Outdated

ismaelsadeeq reviewed Oct 22, 2024

View reviewed changes

Comment thread src/validation.cpp Outdated

ismaelsadeeq reviewed Oct 22, 2024

View reviewed changes

Comment thread src/validation.cpp Outdated

ismaelsadeeq reviewed Oct 22, 2024

View reviewed changes

sdaftuar force-pushed the 2024-10-mempool-changeset branch from aeefd31 to a4d0275 Compare October 22, 2024 16:55

sdaftuar force-pushed the 2024-10-mempool-changeset branch 4 times, most recently from 32ac5cd to a981f07 Compare October 23, 2024 16:46

DrahtBot added the CI failed label Oct 23, 2024

instagibbs reviewed Oct 23, 2024

View reviewed changes

DrahtBot removed the CI failed label Oct 23, 2024

sdaftuar mentioned this pull request Oct 23, 2024

validation: fix coins disappearing mid-package evaluation #28251

Merged

sdaftuar force-pushed the 2024-10-mempool-changeset branch 2 times, most recently from c85990d to 57a0356 Compare October 24, 2024 09:58

DrahtBot removed the Needs rebase label Nov 13, 2024

instagibbs approved these changes Nov 13, 2024

View reviewed changes

DrahtBot requested a review from naumenkogs November 13, 2024 19:29

DrahtBot mentioned this pull request Nov 14, 2024

Add waitNext() to BlockTemplate interface #31283

Merged

ismaelsadeeq reviewed Nov 15, 2024

View reviewed changes

glozow reviewed Nov 18, 2024

View reviewed changes

DrahtBot requested a review from glozow November 18, 2024 14:08

DrahtBot mentioned this pull request Nov 18, 2024

Drop script_pub_key arg from createNewBlock #31318

Merged

glozow reviewed Nov 20, 2024

View reviewed changes

glozow merged commit f34fe08 into bitcoin:master Nov 20, 2024

btsea mentioned this pull request Jan 20, 2025

DC BitDevs 011 Topic Suggestion dcbitdevs/dcbitdevs.github.io#13

Closed

0xB10C mentioned this pull request Feb 12, 2025

tracing: network connection tracepoints #25832

Merged

glozow mentioned this pull request Jul 14, 2025

validation: docs and cleanups for MemPoolAccept coins views #32973

Merged

bitcoin locked and limited conversation to collaborators Nov 20, 2025

	const CTransaction& GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetTx(); }
	CTransactionRef GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetSharedTx(); }

Uh oh!

Conversation

sdaftuar commented Oct 20, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Oct 20, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

DrahtBot commented Oct 20, 2024

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ismaelsadeeq left a comment

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Oct 22, 2024

Uh oh!

DrahtBot commented Oct 23, 2024

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sdaftuar commented Nov 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

naumenkogs commented Nov 14, 2024

Uh oh!

sdaftuar commented Nov 14, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ismaelsadeeq left a comment

Choose a reason for hiding this comment

Uh oh!

naumenkogs commented Nov 18, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

glozow Nov 18, 2024

Choose a reason for hiding this comment

Uh oh!

sipa Nov 18, 2024

Choose a reason for hiding this comment

Uh oh!

sdaftuar Nov 19, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

glozow Nov 20, 2024

Choose a reason for hiding this comment

Uh oh!

glozow Nov 20, 2024

sdaftuar commented Oct 20, 2024 •

edited

Loading

DrahtBot commented Oct 20, 2024 •

edited

Loading

sdaftuar commented Nov 13, 2024 •

edited

Loading

sdaftuar commented Nov 14, 2024 •

edited

Loading

naumenkogs commented Nov 18, 2024 •

edited

Loading