As suggested in the main cluster mempool PR (https://github.com/bitcoin/bitcoin/pull/28676#pullrequestreview-3177119367), I've pulled out some of the non-essential optimizations and cleanups into this separate PR.
Will continue to add more commits here to address non-blocking suggestions/improvements as they come up.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33591.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | instagibbs, sipa |
If your review is incorrectly listed, please copy-paste <code><!--meta-tag:bot-skip--></code> into the comment that the bot should ignore.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, 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.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
1077 | @@ -1078,6 +1078,17 @@ void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPool 1078 | } 1079 | } 1080 | 1081 | +bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx) 1082 | +{ 1083 | + LOCK(cs); 1084 | + // Use ChangeSet interface to check whether the chain 1085 | + // limits would be violated. Note that the changeset will be destroyed 1086 | + // when it goes out of scope.
// Use ChangeSet interface to check whether the cluster count
// limits would be violated. Note that the changeset will be destroyed
// when it goes out of scope.
Fixed in 9e7410479.
424 | @@ -425,9 +425,15 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei 425 | 426 | CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip)); 427 | 428 | + const auto score_with_topo{GetSortedScoreWithTopology()}; 429 | + 430 | + // Number of chunks is bounded by number of transactions. 431 | + const auto diagram{GetFeerateDiagram()}; 432 | + Assume(diagram.size() <= score_with_topo.size() + 1);
Now that the feerate diagram outputs weight, the sanity check can be stronger:
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 472ed581145..0be261ad964 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -418,6 +418,8 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
uint64_t checkTotal = 0;
CAmount check_total_fee{0};
+ CAmount check_total_modified_fee{0};
+ int32_t check_total_adjusted_weight{0};
uint64_t innerUsage = 0;
assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
@@ -430,12 +432,21 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
// Number of chunks is bounded by number of transactions.
const auto diagram{GetFeerateDiagram()};
Assume(diagram.size() <= score_with_topo.size() + 1);
+ Assume(diagram.size() >= 1);
std::optional<Wtxid> last_wtxid = std::nullopt;
+ auto diagram_iter = diagram.cbegin();
for (const auto& it : score_with_topo) {
+ // GetSortedScoreWithTopology() contains the same chunks as the feerate diagram. We do not know where the chunk
+ // boundaries are, but we can check that there are points at which they match the cumulative fee and weight.
+ if (diagram_iter->fee == check_total_modified_fee && diagram_iter->size == check_total_adjusted_weight) {
+ diagram_iter++;
+ }
checkTotal += it->GetTxSize();
+ check_total_adjusted_weight += it->GetAdjustedWeight();
check_total_fee += it->GetFee();
+ check_total_modified_fee += it->GetModifiedFee();
innerUsage += it->DynamicMemoryUsage();
const CTransaction& tx = it->GetTx();
@@ -502,8 +513,13 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
assert(it2 != mapTx.end());
}
+ // If mempool is empty, we have the 1 diagram chunk of (0, 0).
+ Assume(diagram_iter == diagram.cend());
+
assert(totalTxSize == checkTotal);
assert(m_total_fee == check_total_fee);
+ Assume(diagram.back().fee == check_total_modified_fee);
+ Assume(diagram.back().size == check_total_adjusted_weight);
assert(innerUsage == cachedInnerUsage);
}
Took this (with one small fix) in 375682ec
677 | @@ -678,11 +678,11 @@ class ChainImpl : public Chain 678 | // that Chain clients do not need to know about. 679 | return TransactionError::OK == err; 680 | } 681 | - void getTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& descendants, size_t* ancestorsize, CAmount* ancestorfees) override 682 | + void getTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* ancestorsize, CAmount* ancestorfees) override
cec26203732ce3883e7e014f954ccd73c3c0099d: The function signature in chain.h still calls this descendants
Fixed in 472e3e16
165 | @@ -166,6 +166,7 @@ std::optional<std::pair<std::string, CTransactionRef>> SingleTRUCChecks(const CT 166 | const std::set<Txid>& direct_conflicts, 167 | int64_t vsize) 168 | { 169 | + LOCK(pool.cs);
I think these functions should actually require the lock to already be held. They are only called from MemPoolAccept so this is always true.
Replaced this with AssertLockHeld(pool.cs), and added lock annotations to both the single and package TRUC checks in 70893b6b
260 | @@ -261,14 +261,14 @@ static RPCHelpMan testmempoolaccept() 261 | static std::vector<RPCResult> ClusterDescription() 262 | { 263 | return { 264 | - RPCResult{RPCResult::Type::NUM, "vsize", "virtual transaction size as defined in BIP 141. This is different from actual serialized size for witness transactions as witness data is discounted."}, 265 | + RPCResult{RPCResult::Type::NUM, "weight", "total sigops-adjusted weight (as defined in BIP 141 and modified by '-bytespersigop'"},
nit: missing parens
Also, I wonder if it would be confusing that an RPC result named "weight" is adjusted in some RPCs but not in others... should we be calling this "adjusted_weight" ? Or perhaps "clusterweight" and "chunkweight" are enough to indicate that this is in the mempool context and thus not just BIP 141 weight.
Some documentation that could be worth having in doc/policy/ ?
Each transaction has a weight and virtual size as defined in BIP 141 (different from serialized size for witness transactions as witness data is discounted and virtual size is rounded up to the nearest integer).
A transaction has a sigops size, defined as its sigop cost multiplied by the node's -bytespersigop, an adjustable policy.
A transaction's virtual size (vsize) refers to its sigops-adjusted virtual size: the maximum of its BIP 141 size and sigops size. This virtual size is used in order to simplify the process of building blocks that satisfy both the maximum weight limit and sigop limit.
In the RPCs, "vsize" refers to sigops-adjusted virtual size.
Mempool entry information with the suffix "size" ("clustersize") refer to the cumulative virtual size of the transactions in the group.
A transaction can also have a sigops-adjusted weight, defined similarly (using the BIP 141 weight without dividing by the witness scaling factor). This value is used in most internal processes because using virtual size can result in loss of precision.
A transaction's base fee is the difference between its input and output values.
A transaction's modified fee is its base fee added to any fee delta introduced using the prioritisetransaction RPC.
Modified fee is used internally for all fee-related mempool policies and block building.
I'm going with chunkweight and clusterweight for now. Not sure what to do for the output of getmempoolfeeratediagram() though?
I also took your doc suggestion and created a new file in doc/policy/ that explains the terminology. Would it better to consolidate some of those files into one?
The docs look great. I agree they could be consolidated. Maybe even just one file, since the rules are becoming simpler and more consistent across package and single tx.
The getmempoolfeeratediagram RPC is hidden/experimental, so maybe it's fine? We could rename it to "adjusted_weight" to not invalidate 'In the RPCs, "weight" refers to the weight as defined in BIP 141.'
660 | + HelpExampleCli("getmempoolcluster", "txid") 661 | + + HelpExampleRpc("getmempoolcluster", "txid") 662 | + }, 663 | + [&](const RPCHelpMan& self, const JSONRPCRequest& request) -> UniValue 664 | +{ 665 | + uint256 hash = ParseHashV(request.params[0], "parameter 1");
Is this supposed to be the name of the param?
uint256 hash = ParseHashV(request.params[0], "txid");
Oops, fixed in 62b2f2144
998 | + std::vector<CTxMemPool::txiter> ret; 999 | + std::set<const CTxMemPoolEntry*> unique_cluster_representatives; 1000 | + for (auto txid : txids) { 1001 | + auto it = mapTx.find(txid); 1002 | + if (it != mapTx.end()) { 1003 | + auto cluster = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN);
57cb99c82504693601709eeb47eba9cd7ab7e387 requires that GetCluster output txns in a deterministic order, which could be worth documenting.
Added a comment in 875f1b98fcc
Needs rebase!
319 | @@ -320,6 +320,7 @@ class CTxMemPool 320 | */ 321 | void check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main); 322 | 323 | + void removeRecursive(txiter to_remove, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
f1cfc07b8af90d9c80c84e9db56d61c56f50d6c2
Are we using this elsewhere or could this be private?
Made private in 6797c71ef9323efd2db9dc07d6c1156d077b38cc
342 | + txiter origit = mapTx.find(origTx.GetHash()); 343 | + if (origit != mapTx.end()) { 344 | + removeRecursive(origit, reason); 345 | + } else { 346 | + // When recursively removing but origTx isn't in the mempool 347 | + // be sure to remove any children that are in the pool. This can
f1cfc07b8af90d9c80c84e9db56d61c56f50d6c2
// be sure to remove any descendants that are in the pool. This can
Done.
339 | - txiter nextit = it->second; 340 | - assert(nextit != mapTx.end()); 341 | - txToRemove.insert(nextit); 342 | + txiter origit = mapTx.find(origTx.GetHash()); 343 | + if (origit != mapTx.end()) { 344 | + removeRecursive(origit, reason);
f1cfc07b8af90d9c80c84e9db56d61c56f50d6c2
From a cursory glance I could not figure out when this happens. I believe behavior matches, but I'm still curious.
In removeConflicts(), we'd invoke removeRecursive() with a transaction that is in the mempool, and then this code would trigger. However I realize now that we already have the iterator that we're trying to remove, so I can save a map lookup by invoking the helper directly. (Prior to #33629 there were more places we'd invoke removeRecursive() on transactions in the mempool.)
Otherwise, I think this code will now only trigger in tests.
384 | - CalculateDescendants(it, setAllRemoves); 385 | + removeUnchecked(it, MemPoolRemovalReason::REORG); 386 | } 387 | - RemoveStaged(setAllRemoves, MemPoolRemovalReason::REORG); 388 | for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { 389 | assert(TestLockPointValidity(chain, it->GetLockPoints()));
05a7b963c93501939ec0523fe0182af87ee40056
not related to cluster mempool, but doesn't this seem pretty expensive, wondering if we can make this an Assume() instead
I agree that this seems expensive, but an Assume() wouldn't save us anything, would it? I believe the code would still get invoked (unless the compiler is somehow smart enough to optimize it out).
Given the new implementation that doesn't even use visited(), I think can be removed anyway (in another followup)
edit: Actually not sure removal is worth it. If check_final_and_mature introduces a bug it may be hard to catch the issue.
365 | - if (check_final_and_mature(it)) txToRemove.insert(it); 366 | + std::vector<CTxMemPool::txiter> txToRemove; 367 | + { 368 | + WITH_FRESH_EPOCH(m_epoch); 369 | + for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { 370 | + if (check_final_and_mature(it) && !visited(it)) {
05a7b963c93501939ec0523fe0182af87ee40056
Light preference for splitting out the checks to make the visited() mutation more obvious
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 5efdfbf133..7765f27b79 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -365,5 +365,6 @@ void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check
WITH_FRESH_EPOCH(m_epoch);
for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
- if (check_final_and_mature(it) && !visited(it)) {
+ if (check_final_and_mature(it)) {
+ if (visited(it)) continue;
txToRemove.emplace_back(it);
auto descendants = m_txgraph->GetDescendants(*it, TxGraph::Level::MAIN);
This is now re-written to not use epochs; I also added a test that would have caught the previous bug (when the call to visited() came before the call to check_final_an_mature().
31 | -// defaults reflect this constraint. 32 | -static_assert(DEFAULT_DESCENDANT_LIMIT >= MAX_PACKAGE_COUNT); 33 | -static_assert(DEFAULT_ANCESTOR_LIMIT >= MAX_PACKAGE_COUNT); 34 | -static_assert(MAX_PACKAGE_WEIGHT >= DEFAULT_ANCESTOR_SIZE_LIMIT_KVB * WITNESS_SCALE_FACTOR * 1000); 35 | -static_assert(MAX_PACKAGE_WEIGHT >= DEFAULT_DESCENDANT_SIZE_LIMIT_KVB * WITNESS_SCALE_FACTOR * 1000); 36 | +// Packages are part of a single cluster, so ensure that the package limits are
d2b0872461158e69675985e8c9e2eb929d904683
seems like these checks are backwards now compared to before, but seems right after these changes... @glozow ?
Agree the previous checks can be removed. Rationale is "transactions that would be individually accepted may be rejected in a package erroneously" which is addressed more comprehensively by trying individual transactions if they don't need to be grouped with others and calculating precise cluster limits through the staging txgraph.
251 | @@ -252,7 +252,7 @@ void BlockAssembler::addChunks() 252 | 253 | while (selected_transactions.size() > 0) { 254 | // Check to see if min fee rate is still respected. 255 | - if (chunk_feerate.fee < m_options.blockMinFeeRate.GetFee(chunk_feerate_vsize.size)) { 256 | + if (chunk_feerate_vsize < m_options.blockMinFeeRate.GetFeePerVSize()) {
ff2a16af040ac0906b4ebd488b1125b6ea25fa14
I don't think we should be tie-breaking based on size here?
if (chunk_feerate_vsize << m_options.blockMinFeeRate.GetFeePerVSize()) {
Fixed in 6129b8ecb77aafdc4d80ffdc3e85eb05889917f7
66 | - 67 | -1. The descendant count limit is temporarily increased by 1. 68 | - 69 | -2. The descendant size limit temporarily is increased by the virtual size of the to-be-replaced 70 | - directly conflicting transaction. 71 | +Transactions submitted to the mempool must not exceed the cluster limits set by
c11faf779a1c415f8a04463bfb3febc990eb297b
maybe:
"Transactions submitted to the mempol must not result in clusters which would exceed cluster limits set by"
I ended up reworking the docs and merged the mempool-limits.md file (which was quite short and included a few definitions) in with the new mempool-design.md file (that also has a bunch of definitions and a brief overview of how cluster mempool works).
I took your language suggestion and incorporated in 9d25e2cbcd011b3046f9c3cd8de4e1b9112d0dfd.
349 | - auto feerate = pool.GetMainChunkFeerate(*tx); 350 | - txentry.pushKV("txid", tx->GetTx().GetHash().ToString()); 351 | - txentry.pushKV("chunkfee", ValueFromAmount((int)feerate.fee)); 352 | - txentry.pushKV("chunkweight", feerate.size); 353 | - txs.push_back(txentry); 354 | + if (current_chunk_feerate.size == 0) {
486b441971912bdc63921425d5e40a8c168186ea
pretty sure there's at least one bug here. f.e., if you have three chunks in one cluster, I think the conditional here is only hit the first time, as current_chunk_feerate is never reset to the next chunk's size, so it'll just start going negative.
Wrote a test which I think covers it
diff --git a/test/functional/mempool_cluster.py b/test/functional/mempool_cluster.py
index 4b4812e619..a7eabef039 100755
--- a/test/functional/mempool_cluster.py
+++ b/test/functional/mempool_cluster.py
@@ -299,4 +299,73 @@ class MempoolClusterTest(BitcoinTestFramework):
assert_equal(node.getmempoolcluster(tx_replacer["txid"])['txcount'], 2)
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+ def test_getmempoolcluster(self):
+ node = self.nodes[0]
+
+ self.log.info("Testing getmempoolcluster")
+
+ assert_equal(node.getrawmempool(), [])
+
+ # Not in-mempool
+ not_mempool_tx = self.wallet.create_self_transfer()
+ assert_raises_rpc_error(-5, "Transaction not in mempool", node.getmempoolcluster, not_mempool_tx["txid"])
+
+ # Test that chunks are being recomputed properly
+
+ # One chunk with one tx
+ first_chunk_tx = self.wallet.send_self_transfer(from_node=node)
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ assert_equal(first_chunk_info, {'weight': first_chunk_tx["tx"].get_weight(), 'txcount': 1, 'chunks': [{'chunkfee': first_chunk_tx["fee"], 'chunkweight': first_chunk_tx["tx"].get_weight(), 'txs': [first_chunk_tx["txid"]]}]})
+
+ # Another unconnected tx, nothing should change
+ other_chunk_tx = self.wallet.send_self_transfer(from_node=node)
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ assert_equal(first_chunk_info, {'weight': first_chunk_tx["tx"].get_weight(), 'txcount': 1, 'chunks': [{'chunkfee': first_chunk_tx["fee"], 'chunkweight': first_chunk_tx["tx"].get_weight(), 'txs': [first_chunk_tx["txid"]]}]})
+
+ # Second connected tx, makes one chunk still with high enough fee
+ second_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=first_chunk_tx["new_utxo"], fee_rate=Decimal("0.01"))
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ # output is same across same cluster transactions
+ assert_equal(first_chunk_info, node.getmempoolcluster(second_chunk_tx["txid"]))
+ chunkweight = first_chunk_tx["tx"].get_weight() + second_chunk_tx["tx"].get_weight()
+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"]
+ assert_equal(first_chunk_info, {'weight': chunkweight, 'txcount': 2, 'chunks': [{'chunkfee': chunkfee, 'chunkweight': chunkweight, 'txs': [first_chunk_tx["txid"], second_chunk_tx["txid"]]}]})
+
+ # Third connected tx, makes one chunk still with high enough fee
+ third_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=second_chunk_tx["new_utxo"], fee_rate=Decimal("0.1"))
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ # output is same across same cluster transactions
+ assert_equal(first_chunk_info, node.getmempoolcluster(third_chunk_tx["txid"]))
+ chunkweight = first_chunk_tx["tx"].get_weight() + second_chunk_tx["tx"].get_weight() + third_chunk_tx["tx"].get_weight()
+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"] + third_chunk_tx["fee"]
+ assert_equal(first_chunk_info, {'weight': chunkweight, 'txcount': 3, 'chunks': [{'chunkfee': chunkfee, 'chunkweight': chunkweight, 'txs': [first_chunk_tx["txid"], second_chunk_tx["txid"], third_chunk_tx["txid"]]}]})
+
+ # Now test single cluster with each tx being its own chunk
+
+ # One chunk with one tx
+ first_chunk_tx = self.wallet.send_self_transfer(from_node=node)
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ assert_equal(first_chunk_info, {'weight': first_chunk_tx["tx"].get_weight(), 'txcount': 1, 'chunks': [{'chunkfee': first_chunk_tx["fee"], 'chunkweight': first_chunk_tx["tx"].get_weight(), 'txs': [first_chunk_tx["txid"]]}]})
+
+ # Second connected tx, lower fee
+ second_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=first_chunk_tx["new_utxo"], fee_rate=Decimal("0.000002"))
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ # output is same across same cluster transactions
+ assert_equal(first_chunk_info, node.getmempoolcluster(second_chunk_tx["txid"]))
+ first_chunkweight = first_chunk_tx["tx"].get_weight()
+ second_chunkweight = second_chunk_tx["tx"].get_weight()
+ assert_equal(first_chunk_info, {'weight': first_chunkweight + second_chunkweight, 'txcount': 2, 'chunks': [{'chunkfee': first_chunk_tx["fee"], 'chunkweight': first_chunkweight, 'txs': [first_chunk_tx["txid"]]}, {'chunkfee': second_chunk_tx["fee"], 'chunkweight': second_chunkweight, 'txs': [second_chunk_tx["txid"]]}]})
+
+ # Third connected tx, even lower fee
+ third_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=second_chunk_tx["new_utxo"], fee_rate=Decimal("0.000001"))
+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
+ # output is same across same cluster transactions
+ assert_equal(first_chunk_info, node.getmempoolcluster(third_chunk_tx["txid"]))
+ first_chunkweight = first_chunk_tx["tx"].get_weight()
+ second_chunkweight = second_chunk_tx["tx"].get_weight()
+ third_chunkweight = third_chunk_tx["tx"].get_weight()
+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"] + third_chunk_tx["fee"]
+ # FIXME I think there's a big consolidating the second and third tx into one chunk
+ assert_equal(first_chunk_info, {'weight': first_chunkweight + second_chunkweight + third_chunkweight, 'txcount': 3, 'chunks': [{'chunkfee': first_chunk_tx["fee"], 'chunkweight': first_chunkweight, 'txs': [first_chunk_tx["txid"]]}, {'chunkfee': second_chunk_tx["fee"], 'chunkweight': second_chunkweight, 'txs': [second_chunk_tx["txid"]]}, {'chunkfee': third_chunk_tx["fee"], 'chunkweight': third_chunkweight, 'txs': [third_chunk_tx["txid"]]}]})
def run_test(self):
@@ -305,4 +374,6 @@ class MempoolClusterTest(BitcoinTestFramework):
self.generate(self.wallet, 400)
+ self.test_getmempoolcluster()
+
self.test_cluster_limit_rbf(DEFAULT_CLUSTER_LIMIT)
I think it was just a single bug, a missing line in the if block:
current_chunk_feerate = pool.GetMainChunkFeerate(*tx);
Please let me know if you spot anything else wrong. Your test passes with that fix, and I incorporated your code in that same commit. (Also, I deleted the "FIXME" comment you left in your python test, and added an additional test that 2nd and 3rd chunks get merged after a prioritisetransaction call.)
reviewed through 875f1b98fcc9a992a3280bf32edc2d30c1fb034d
347 | + // be sure to remove any children that are in the pool. This can 348 | + // happen during chain re-orgs if origTx isn't re-accepted into 349 | + // the mempool for any reason. 350 | + auto iter = mapNextTx.lower_bound(COutPoint(origTx.GetHash(), 0)); 351 | + std::vector<CTxMemPool::txiter> to_remove; 352 | + WITH_FRESH_EPOCH(m_epoch);
In commit "Simplify removeRecursive"
A possibility here, and below in removeForReorg, is to only add the child transactions themselves (not all their descendants) to a vector, in TxGraph::Ref* format, and then call TxGraph::GetDescendantsUnion once to find all their children to remove.
As a further simplification (but not performance improvement), I think it would be acceptable to forego the epoch/visited check and just add everything, as GetDescendantsUnion will deduplicate anyway.
This vastly simplifies the logic, thanks!
7 | @@ -8,58 +8,12 @@ Tx0 is a *parent* of Tx1 and Tx1 is a *child* of Tx0. 8 | A transaction's *ancestors* include, recursively, its parents, the parents of its parents, etc. 9 | A transaction's *descendants* include, recursively, its children, the children of its children, etc. 10 | 11 | -A mempool entry's *ancestor count* is the total number of in-mempool (unconfirmed) transactions in 12 | -its ancestor set, including itself. 13 | -A mempool entry's *descendant count* is the total number of in-mempool (unconfirmed) transactions in 14 | -its descendant set, including itself. 15 | +A transaction's *cluster* is the set of all transactions that can be reached 16 | +from that transaction by following all parent or child relationships. For
In commit "doc: Update mempool-limits.md for cluster mempool".
Perhaps worth elaborating that it is not just parents and children, but also any combination thereof:
A transaction's cluster is the set of all transactions that can be reached by following any combination of parent or child relationships. This includes all ancestors and descendants, but also any descendants of those ancestors and ancestors of those descendants, and so on.
Please take a look at the new mempool-design.md docs and let me know what you think -- in the course of many edits, I incorporated your suggestion with some modifications.
13 | +explanation of how we use feerate diagrams for mining, eviction, and evaluating 14 | +transaction replacements. 15 | + 16 | +## Definitions and theorems 17 | + 18 | +See https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202 for
In commit "doc: add design notes for cluster mempool"
I think the theory thread is outdated now. Merging and postlinearization won't be very relevant post SFL, and the existence of optimal linearizations can probably be shown much more concisely when using results from the GGT paper.
It's probably worth creating a trimmed-down version with just definitions of clusters, chunks, and fee-size diagams, possibly to include directly in the document here, but that can be done as a follow-up I think.
Might be useful to specifically include something that describes it in the literature terms, like:
"Producing an optimal linearization of a cluster is an instance of the parametric maximal weight closure problem as found in the field of mineral extraction for open pit mining."
-- just to give future researchers a hook to the literature that contributors here initially lacked.
Made an attempt at this in 9d25e2cbcd011b3046f9c3cd8de4e1b9112d0dfd
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed.
<sub>Task lint: https://github.com/bitcoin/bitcoin/actions/runs/19778009649/job/56673707344</sub>
<sub>LLM reason (✨ experimental): Lint failure: Ruff found unused-variable errors in Python tests, causing the CI to fail.</sub>
<details><summary>Hints</summary>
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.
</details>
I believe I've responded to all the previous review comments, so this should be ready for re-review.
Also fyi, I do have some additional changes to propose beyond what's included here already, but I think I'll stop adding additional scope so that this PR can make forward progress with the improvements already suggested.
385 | @@ -386,13 +386,14 @@ void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigne 386 | std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block; 387 | if (mapTx.size() || mapNextTx.size() || mapDeltas.size()) { 388 | txs_removed_for_block.reserve(vtx.size()); 389 | - for (const auto& tx : vtx) { 390 | + for (const auto& tx : vtx) 391 | + {
In commit "Remove unused argument to RemoveStaged"
Nit: strange and unrelated style change.
Removed.
351 | @@ -352,15 +352,21 @@ void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check 352 | AssertLockHeld(::cs_main); 353 | Assume(!m_have_changeset); 354 | 355 | - setEntries txToRemove; 356 | - for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { 357 | - if (check_final_and_mature(it)) txToRemove.insert(it); 358 | + std::vector<const TxGraph::Ref*> txToRemove; 359 | + {
In commit "Rewrite removeForReorg to avoid using sets"
Nit: it seems this scope level is unnecessary.
Removed.
351 | @@ -352,15 +352,21 @@ void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check 352 | AssertLockHeld(::cs_main); 353 | Assume(!m_have_changeset); 354 | 355 | - setEntries txToRemove; 356 | - for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { 357 | - if (check_final_and_mature(it)) txToRemove.insert(it); 358 | + std::vector<const TxGraph::Ref*> txToRemove;
In commit "Rewrite removeForReorg to avoid using sets"
Nit: given that you're rewriting most of this function anyway, make this variable name match style?
Done.
903 | @@ -901,6 +904,12 @@ bool AppInitParameterInteraction(const ArgsManager& args) 904 | if (args.IsArgSet("-checkpoints")) { 905 | InitWarning(_("Option '-checkpoints' is set but checkpoints were removed. This option has no effect.")); 906 | } 907 | + if (args.IsArgSet("-limitancestorsize")) { 908 | + InitWarning(_("Option '-limitancestorsize' is given but ancestor size limits have been replaced with cluster size limits. This option has no effect."));
In commit " Warn user if using -limitancestorsize/-limitdescendantsize that the options have no effect"
Perhaps mention the relevant corresponding option names (-limitclustercount and -limitclustersize).
Added a reference to -limitclustersize since it's analogous.
0 | @@ -0,0 +1,105 @@ 1 | +# Mempool design and limits 2 | + 3 | +## Definitions 4 | + 5 | +We view the unconfirmed transactions in the mempool as a directed graph, 6 | +with an edge from transaction B to transaction A if B spends an output created 7 | +by A (ie, B is a **child** of A, and A is a **parent** of B).
In commit "doc: Add design notes for cluster mempool and explain new mempool limits"
Writing nit: ie, -> i.e.,
Also in two other places below.
Fixed.
70 | +## Mempool limits 71 | + 72 | +### Motivation 73 | + 74 | +Selecting chunks in decreasing feerate order when building a block template 75 | +will be close to optimal when the maximize size of a chunk is small compared to
In commit "doc: Add design notes for cluster mempool and explain new mempool limits"
The word "maximize" seems out of place here.
EDIT: DrahtBot LLM figured it out, you mean "maximum"?
Yep, that is what I meant! Fixed.
0 | @@ -0,0 +1,105 @@ 1 | +# Mempool design and limits
In commit "doc: Add design notes for cluster mempool and explain new mempool limits"
Nice write-up, enough to understand the terminology used in the codebase, but not going too detailed into the rationale.
0 | @@ -0,0 +1,41 @@ 1 | +Mempool 2 | +======= 3 | + 4 | +The mempool has been reimplemented with a new design ("cluster mempool"), to 5 | +facilitate better performance when constructing block templates, evicting
In commit "doc: add release notes snippet for cluster mempool"
I wouldn't say "better performance". While it's true many things are more performant now, that's not the motivation, and in many cases, not really critical anyway. How about "better decision-making"?
Agreed, "performance" is misleading. I was thinking "better behavior" myself, but took your language.
10 | +- The mempool no longer enforces ancestor or descendant size/count limits. 11 | + Instead, two new limits are introduced: `-limitclustercount` (default 64) and 12 | + `-limitclustersize` (default 101kvB). These limits govern the size of 13 | + connected components, or clusters, in the mempool. Transactions are 14 | + considered to be in the same cluster if they are connected to each other via 15 | + parent/child relationships in the mempool.
In commit "doc: add release notes snippet for cluster mempool"
Add "any combination of"? It's noted elsewhere, but the release notes are likely read by far more people.
Done.
14 | + considered to be in the same cluster if they are connected to each other via 15 | + parent/child relationships in the mempool. 16 | + 17 | +- Within the mempool, transactions are ordered based on the fee rate at which 18 | + they are expected to be mined, which takes into account the full set, or 19 | + "chunk", of transactions that would be included together (eg a parent and its
In commit "doc: add release notes snippet for cluster mempool"
Writing nit: eg -> e.g.,.
Fixed.
441 | @@ -440,12 +442,27 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei 442 | // Number of chunks is bounded by number of transactions. 443 | const auto diagram{GetFeerateDiagram()}; 444 | Assume(diagram.size() <= score_with_topo.size() + 1); 445 | + Assume(diagram.size() >= 1);
In commit "Sanity check feerate diagram in CTxMemPool::check()"
In a check function like CTxMempool::check(), I think we should always use assert/Assert, not Assume, as we want the checks to always be enabled.
Agreed, fixed.
-BEGIN VERIFY SCRIPT-
find src/test -type f -exec sed -i 's/AddToMempool/TryAddToMempool/g' {} +
find src/bench -type f -exec sed -i 's/AddToMempool/TryAddToMempool/g' {} +
-END VERIFY SCRIPT-
Also improve test coverage for removeForReorg by creating a scenario where
there are in-mempool descendants that are only invalidated due to an in-mempool
parent no longer spending a mature coin.
@sipa Thanks for the review!
I noticed a few things:
-limitclustercount and -limitclustersize are both debug options at the moment. Is that the right place for them? It seems slightly unusual to me that we'd reference command line options in our general docs that are hidden away like this...?
While -limitancestorsize and -limitdescendantsize have nice warnings now, I don't think I've updated any of the help text for -limitancestorcount and -limitdescendantcount. I believe those limits are now only used by the wallet for coin selection. Guessing I should include something in the release notes and in the help text for those options to explain this?
In the release notes, would it be worth mentioning the switch from vsize-accounting to weight-accounting in the mempool and block building logic? Or is that too in the weeds?
Yeah, there is an inconsistency here. Either (1) we treat it as a debug-only option, and don't refer to it in documentation and help texts, or (2) we make it a fully fledged option that has a normal config category. I'd prefer (1).
In the release notes for 0.12.0, we referenced that there was a way to change the descendant limits without calling out what the command line argument was, and instead referred users to using --help -help-debug for more info. I could do that in the release note snippet here as well, and perhaps leave the documentation in doc/policy/mempool-design.md as written, as that is more developer facing than user facing?
Also, I guess -limitancestorcount and -limitdescendantcount are both debug-only options anyway, so perhaps no need to mention their presence in the release notes either. I'll update the help text for both to indicate the options are deprecated and only used by the wallet for coin selection.
Also update the help text for -limitancestorcount/-limitdescendantcount to
explain they no longer affect the mempool, and are only used by the wallet for
coin selection.
This makes the terminology consistent with other parts of the codebase, as part
of the cluster mempool implementation.
85 | +(ideally, optimal) linearizations in a reasonable amount of time. 86 | + 87 | +### Limits 88 | + 89 | +Transactions submitted to the mempool must not result in clusters that would 90 | +exceed the cluster limits set by the node (see `-limitclustercount` and
In commit "doc: Add design notes for cluster mempool and explain new mempool limits"
With these options made debug-only, maybe it's better to list the defaults?
Transactions submitted to the mempool must not result in clusters that would exceed the cluster limits (64 transactions and 101 kvB total per cluster).
Done
28 | +union by simply merge sorting the chunks of each cluster by feerate. 29 | + 30 | +For any set of linearized clusters, then, we can define the **feerate diagram** 31 | +of the set by plotting the cumulative fee (y-axis) against the cumulative size 32 | +(x-axis) as we progress from chunk to chunk. Given two linearizations for the 33 | +same set of transactions, we can can compare their feerate diagrams by
doc: Add design notes for cluster mempool and explain new mempool limits
Grammar: "we can can compare" -> "we can compare"
(thanks DrahtBot LLM)
Fixed!
10 | +- The mempool no longer enforces ancestor or descendant size/count limits. 11 | + Instead, two new default policy limits are introduced governing connected 12 | + components, or clusters, in the mempool, limiting clusters to 64 transactions 13 | + and up to 101kB in virtual size. Transactions are considered to be in the 14 | + same cluster if they are connected to each other via any combination of 15 | + parent/child relationships in the mempool. These limits can be overriden
In commit "doc: add release notes snippet for cluster mempool"
"overriden" -> "overridden"
(thanks to DrahtBot LLM)
Fixed, and made a few other small style edits as well.
320 | + UniValue chunk_txids(UniValue::VARR); 321 | + for (const auto& chunk_tx : chunk_txs) { 322 | + chunk_txids.push_back(chunk_tx->GetTx().GetHash().ToString()); 323 | + } 324 | + chunk.pushKV("txs", std::move(chunk_txids)); 325 | + all_chunks.push_back(chunk);
In commit "rpc: improve getmempoolcluster output"
all_chunks.push_back(std::move(chunk)) will avoid a copy
Done.
ACK 48c29fbe0974664e28564af07fbfd753cf125c36
See nits above.
Now that the mempool no longer keeps any feerate-based indices, we can modify
feerates in mempool entries directly.
Also switch Assume()'s to assert()'s, so that failures in this function are
always caught.
Co-authored-by: glozow <gloriajzhao@gmail.com>
ACK b8d279a81c16fe9f5b6d422e518c77344e217d4f
Milestone
31.0