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.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33591.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | instagibbs, sipa |
If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.
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.
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.
0 // Use ChangeSet interface to check whether the cluster count
1 // limits would be violated. Note that the changeset will be destroyed
2 // when it goes out of scope.
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:
0diff --git a/src/txmempool.cpp b/src/txmempool.cpp
1index 472ed581145..0be261ad964 100644
2--- a/src/txmempool.cpp
3+++ b/src/txmempool.cpp
4@@ -418,6 +418,8 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
5
6 uint64_t checkTotal = 0;
7 CAmount check_total_fee{0};
8+ CAmount check_total_modified_fee{0};
9+ int32_t check_total_adjusted_weight{0};
10 uint64_t innerUsage = 0;
11
12 assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
13@@ -430,12 +432,21 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
14 // Number of chunks is bounded by number of transactions.
15 const auto diagram{GetFeerateDiagram()};
16 Assume(diagram.size() <= score_with_topo.size() + 1);
17+ Assume(diagram.size() >= 1);
18
19 std::optional<Wtxid> last_wtxid = std::nullopt;
20+ auto diagram_iter = diagram.cbegin();
21
22 for (const auto& it : score_with_topo) {
23+ // GetSortedScoreWithTopology() contains the same chunks as the feerate diagram. We do not know where the chunk
24+ // boundaries are, but we can check that there are points at which they match the cumulative fee and weight.
25+ if (diagram_iter->fee == check_total_modified_fee && diagram_iter->size == check_total_adjusted_weight) {
26+ diagram_iter++;
27+ }
28 checkTotal += it->GetTxSize();
29+ check_total_adjusted_weight += it->GetAdjustedWeight();
30 check_total_fee += it->GetFee();
31+ check_total_modified_fee += it->GetModifiedFee();
32 innerUsage += it->DynamicMemoryUsage();
33 const CTransaction& tx = it->GetTx();
34
35@@ -502,8 +513,13 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
36 assert(it2 != mapTx.end());
37 }
38
39+ // If mempool is empty, we have the 1 diagram chunk of (0, 0).
40+ Assume(diagram_iter == diagram.cend());
41+
42 assert(totalTxSize == checkTotal);
43 assert(m_total_fee == check_total_fee);
44+ Assume(diagram.back().fee == check_total_modified_fee);
45+ Assume(diagram.back().size == check_total_adjusted_weight);
46 assert(innerUsage == cachedInnerUsage);
47 }
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
descendants
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);
MemPoolAccept so this is always true.
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?
0 uint256 hash = ParseHashV(request.params[0], "txid");
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);
GetCluster output txns in a deterministic order, which could be worth documenting.
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?
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
0 // be sure to remove any descendants that are in the pool. This can
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
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
0diff --git a/src/txmempool.cpp b/src/txmempool.cpp
1index 5efdfbf133..7765f27b79 100644
2--- a/src/txmempool.cpp
3+++ b/src/txmempool.cpp
4@@ -365,5 +365,6 @@ void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check
5 WITH_FRESH_EPOCH(m_epoch);
6 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
7- if (check_final_and_mature(it) && !visited(it)) {
8+ if (check_final_and_mature(it)) {
9+ if (visited(it)) continue;
10 txToRemove.emplace_back(it);
11 auto descendants = m_txgraph->GetDescendants(*it, TxGraph::Level::MAIN);
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 ?
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?
0 if (chunk_feerate_vsize << m_options.blockMinFeeRate.GetFeePerVSize()) {
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
0diff --git a/test/functional/mempool_cluster.py b/test/functional/mempool_cluster.py
1index 4b4812e619..a7eabef039 100755
2--- a/test/functional/mempool_cluster.py
3+++ b/test/functional/mempool_cluster.py
4@@ -299,4 +299,73 @@ class MempoolClusterTest(BitcoinTestFramework):
5 assert_equal(node.getmempoolcluster(tx_replacer["txid"])['txcount'], 2)
6
7+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
8+ def test_getmempoolcluster(self):
9+ node = self.nodes[0]
10+
11+ self.log.info("Testing getmempoolcluster")
12+
13+ assert_equal(node.getrawmempool(), [])
14+
15+ # Not in-mempool
16+ not_mempool_tx = self.wallet.create_self_transfer()
17+ assert_raises_rpc_error(-5, "Transaction not in mempool", node.getmempoolcluster, not_mempool_tx["txid"])
18+
19+ # Test that chunks are being recomputed properly
20+
21+ # One chunk with one tx
22+ first_chunk_tx = self.wallet.send_self_transfer(from_node=node)
23+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
24+ 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"]]}]})
25+
26+ # Another unconnected tx, nothing should change
27+ other_chunk_tx = self.wallet.send_self_transfer(from_node=node)
28+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
29+ 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"]]}]})
30+
31+ # Second connected tx, makes one chunk still with high enough fee
32+ second_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=first_chunk_tx["new_utxo"], fee_rate=Decimal("0.01"))
33+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
34+ # output is same across same cluster transactions
35+ assert_equal(first_chunk_info, node.getmempoolcluster(second_chunk_tx["txid"]))
36+ chunkweight = first_chunk_tx["tx"].get_weight() + second_chunk_tx["tx"].get_weight()
37+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"]
38+ assert_equal(first_chunk_info, {'weight': chunkweight, 'txcount': 2, 'chunks': [{'chunkfee': chunkfee, 'chunkweight': chunkweight, 'txs': [first_chunk_tx["txid"], second_chunk_tx["txid"]]}]})
39+
40+ # Third connected tx, makes one chunk still with high enough fee
41+ third_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=second_chunk_tx["new_utxo"], fee_rate=Decimal("0.1"))
42+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
43+ # output is same across same cluster transactions
44+ assert_equal(first_chunk_info, node.getmempoolcluster(third_chunk_tx["txid"]))
45+ chunkweight = first_chunk_tx["tx"].get_weight() + second_chunk_tx["tx"].get_weight() + third_chunk_tx["tx"].get_weight()
46+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"] + third_chunk_tx["fee"]
47+ 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"]]}]})
48+
49+ # Now test single cluster with each tx being its own chunk
50+
51+ # One chunk with one tx
52+ first_chunk_tx = self.wallet.send_self_transfer(from_node=node)
53+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
54+ 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"]]}]})
55+
56+ # Second connected tx, lower fee
57+ second_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=first_chunk_tx["new_utxo"], fee_rate=Decimal("0.000002"))
58+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
59+ # output is same across same cluster transactions
60+ assert_equal(first_chunk_info, node.getmempoolcluster(second_chunk_tx["txid"]))
61+ first_chunkweight = first_chunk_tx["tx"].get_weight()
62+ second_chunkweight = second_chunk_tx["tx"].get_weight()
63+ 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"]]}]})
64+
65+ # Third connected tx, even lower fee
66+ third_chunk_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=second_chunk_tx["new_utxo"], fee_rate=Decimal("0.000001"))
67+ first_chunk_info = node.getmempoolcluster(first_chunk_tx["txid"])
68+ # output is same across same cluster transactions
69+ assert_equal(first_chunk_info, node.getmempoolcluster(third_chunk_tx["txid"]))
70+ first_chunkweight = first_chunk_tx["tx"].get_weight()
71+ second_chunkweight = second_chunk_tx["tx"].get_weight()
72+ third_chunkweight = third_chunk_tx["tx"].get_weight()
73+ chunkfee = first_chunk_tx["fee"] + second_chunk_tx["fee"] + third_chunk_tx["fee"]
74+ # FIXME I think there's a big consolidating the second and third tx into one chunk
75+ 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"]]}]})
76
77 def run_test(self):
78@@ -305,4 +374,6 @@ class MempoolClusterTest(BitcoinTestFramework):
79 self.generate(self.wallet, 400)
80
81+ self.test_getmempoolcluster()
82+
83 self.test_cluster_limit_rbf(DEFAULT_CLUSTER_LIMIT)
I think it was just a single bug, a missing line in the if block:
0current_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.)
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.
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.
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.
🚧 At least one of the CI tasks failed.
Task lint: https://github.com/bitcoin/bitcoin/actions/runs/19778009649/job/56673707344
LLM reason (✨ experimental): Lint failure: Ruff found unused-variable errors in Python tests, causing the CI to fail.
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.
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.
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.
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?
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).
-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.
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”?
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”?
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.
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.,.
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.
-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).
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)
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)
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
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>