Cluster mempool implementation #28676

sdaftuar · 2023-10-18T18:59:37Z

This is a draft implementation of the cluster mempool design described in #27677. I'm opening this as a draft PR now to share the branch I'm working on with others, so that we can start to think about in-progress projects (like package relay, package validation, and package rbf) in the context of this design. Also, I can use some help from others for parts of this work, including the interaction between the mempool and the wallet, and also reworking some of our existing test cases to fit a cluster-mempool world.

Note that the design of this implementation is subject to change as I continue to iterate on the code (to make the code more hygienic and robust, in particular). At this point though I think the performance is pretty reasonable and I'm not currently aware of any bugs. There are some microbenchmarks added here, and some improved fuzz tests; it would be great if others ran both of those on their own hardware as well and reported back on any findings.

This branch implements the following observable behavior changes:

Maintains a partitioning of the mempool into connected clusters
Each cluster is sorted ("linearized") either using an optimal sort, or an ancestor-feerate-based one, depending on the size of the cluster (thanks to @sipa for this logic)
Transaction selection for mining is updated to use the cluster linearizations
Mempool eviction is updated to use the cluster linearizations
The RBF rules are updated to drop the requirement that no new inputs are introduced, and to change the feerate requirement to instead check that the mining score of a replacement transaction exceed the mining score of the conflicted transactions
The CPFP carveout rule is eliminated (it doesn't make sense in a cluster-limited mempool)
The ancestor and descendant limits are no longer enforced.
New cluster count/cluster vsize limits are now enforced instead.

Some less observable behavior changes:

The cached ancestor and descendant data are dropped from the mempool, along with the multi_index indices that were maintained to sort the mempool by ancestor and descendant feerates. For compatibility (eg with wallet behavior or RPCs exposing this), this information is now calculated dynamically instead.
The ancestor and descendant walking algorithms are now implemented using epochs (resulting in a significant performance improvement, according to the benchmarks I've looked at)

Still to do:

More comparisons between this branch and master on historical data to compare validation speed (accepting loose transactions, processing RBF transactions, validating a block/postprocessing, updating the mempool for a reorg).
More historical data analysis to try to evaluate the likely impact of setting the cluster size limits to varying values (to motivate what values we should ultimately pick). [DONE, see this post]
Updating wallet code to be cluster-aware (including mini_miner and coin selection)
Rework many of our functional tests to be cluster-aware
Figure out what package validation and package RBF rules should be in this design
Rework the partially_downloaded_block fuzz target to not add duplicate transactions to the mempool (fuzz: don't allow adding duplicate transactions to the mempool #29990).
Update RBF logic to ensure that replacements always strictly improve the mempool.
Figure out how we want to document our RBF policy (preserve historical references to BIP 125 or previous Bitcoin Core behaviors vs clean slate documentation?)

For discussion/feedback:

How significant is it to be dropping the CPFP carveout rule? Does that affect how we will ultimately want to stage new mempool deployment?
How well do the proposed RBF rules meet everyone's use cases?
What design improvements can we make to the cluster tracking implementation?
The ZMQ callbacks that occur when a block is found will happen in a slightly different order, because we now will fully remove all transactions occurring in a block from the mempool before removing any conflicts. Is this a problem?

DrahtBot · 2023-10-18T18:59:40Z

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

Reviews

See the guideline for information on the review process.

Type	Reviewers
Approach ACK	ismaelsadeeq

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:

#33616 (policy: don't CheckEphemeralSpends on reorg by instagibbs)
#33421 (node: add BlockTemplateCache by ismaelsadeeq)
#33335 (txgraph: randomize order of same-feerate distinct-cluster transactions by sipa)
#33214 (rpc: require integer verbosity; remove boolean 'verbose' by fqlx)
#33192 (refactor: unify container presence checks by l0rinc)
#33191 (net: Provide block templates to peers on request by ajtowns)
#33157 (cluster mempool: control/optimize TxGraph memory usage by sipa)
#33062 (truc: optimize the in package relation calculation by HowHsu)
#32587 (test: Fix reorg patterns in tests to use proper fork-based approach by yuvicc)
#31974 (Drop testnet3 by Sjors)
#31803 (fuzz: Extend mini_miner fuzz coverage to max block weight by fjahr)
#31682 ([IBD] specialize CheckBlock's input & coinbase checks by l0rinc)
#31382 (kernel: Flush in ChainstateManager destructor by TheCharlatan)
#30277 ([DO NOT MERGE] Erlay: bandwidth-efficient transaction relay protocol (Full implementation) by sr-gi)
#29641 (scripted-diff: Use LogInfo over LogPrintf [WIP, NOMERGE, DRAFT] by maflcko)
#28690 (build: Introduce internal kernel library by TheCharlatan)
#17783 (common: Disallow calling IsArgSet() on ALLOW_LIST options by ryanofsky)
#17581 (refactor: Remove settings merge reverse precedence code by ryanofsky)
#17580 (refactor: Add ALLOW_LIST flags and enforce usage in CheckArgFlags by ryanofsky)
#17493 (util: Forbid ambiguous multiple assignments in config file by ryanofsky)

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.

doc/policy/mempool-replacements.md

src/rpc/mempool.cpp

instagibbs · 2023-10-19T15:40:30Z

src/policy/rbf.cpp

-        for (const CTxIn& txin : mi->GetTx().vin) {
-            parents_of_conflicts.insert(txin.prevout.hash);
+        // Exit early if we're going to fail (see below)
+        if (all_conflicts.size() > MAX_REPLACEMENT_CANDIDATES) {


Note: this is sticking with the same rule#5 instead of number of effected clusters. It would be more ideal if it were number of clusters to allow for better usage of adversarial-ish batched CPFPs

There is room to relax this rule some, so if this is important we can do so. I think the requirement is a bound on the number of clusters that would have to be re-sorted in order to accept the new transaction. We can approximate that as the number of clusters that would be non-empty as a result of removing all the conflicting transactions from the mempool, and only process replacements for which that is below some target.

That would be a more complex logic though, so before implementing it I wanted to have some sense of whether we need to. Has the historical 100-transaction-conflict limit been problematic for use cases in the past? Note also that in the new code, we are calculating the number of conflicts exactly (the old code used an approximation, which could be gamed by an adversary).

~~Ah! I wrote a huge response to this, then looked up our previous discussions, and realized I didn't actually read the code: #27677 (comment)~~

~~IIUC now, this is only counting direct conflicts, and not the descendants that are booted.~~

~~I think that's fine.~~

Actually no, the existing code comments were just misleading, looks like the issue still exists, see: #27677 (comment)

Ah yes, in the new code I'm only counting direct conflicts right now, because every descendant of a direct conflict must be in the same cluster as that conflict. So this is already a relaxation of the existing rule.

I think the requirement is a bound on the number of clusters that would have to be re-sorted in order to accept the new transaction.

As an alternative, we drop the replacement limit to like, 10 or something, and then only count the direct conflicts, not the direct conflicts and all the descendants?

I believe I (finally) actually fixed this behavior to count the number of direct conflicts.

Will comment elsewhere as well, but I just updated this limit to be a limit on the number of distinct clusters that are conflicted.

instagibbs · 2023-10-19T20:48:36Z

src/validation.cpp

-    }
-
-    ws.m_ancestors = *ancestors;
+    // Calculate in-mempool ancestors


the check two conditionals above:

if (!bypass_limits && ws.m_modified_fees < m_pool.m_min_relay_feerate.GetFee(ws.m_vsize))

This is still needed for the same reason as before: transaction that is above minrelay, but would be in a chunk below minrelay. We could immediately evict below minrelay chunks post-re-linearization f.e. which would allow 0-fee parents then relax this maybe.

instagibbs · 2023-10-19T21:01:05Z

src/bench/mempool_stress.cpp

+    CTxMemPool& pool = *testing_setup.get()->m_node.mempool;
+
+    std::vector<CTransactionRef> transactions;
+    // Create 1000 clusters of 100 transactions each


numbers in comments are off

shower thought: Should we/can we bound the number of clusters in addition to total memory in TrimToSize? I can't think of a good way to do that that doesn't complicate things quite a bit, and perhaps practical mempool sizes make this moot. Just something to consider in case I missed something obvious.

The immediate downside to a cap on number of clusters is that singleton, high-feerate transactions would not be accepted. And I don't think we need to -- the only places where having more clusters makes us slower is in eviction and mining, and for both of those use cases we could improve performance (if we need to) by maintaining the relevant heap data structures (or something equivalent) as chunks are modified, rather than all at once.

For now in this branch I've created these from scratch each time, but if it turns out that performance is meaningfully impacted when the mempool is busy, then I can optimize this further by just using a bit more memory.

src/txmempool.cpp

instagibbs · 2023-10-20T19:46:25Z

src/node/miner.cpp

+        return a.first->fee*b.first->size < b.first->fee*a.first->size;
+    };
+    // TODO: replace the heap with a priority queue
+    std::make_heap(heap_chunks.begin(), heap_chunks.end(), cmp);


don't ask why but I'm getting significant performance improvement(>10%) just push_heaping everything from scratch, and similarly with priority_queue

Sjors · 2023-11-14T10:29:27Z

It would be useful to add a mempool_backwards_compatibility.py test to illustrate how the new rules interact with older nodes. It could have two modern nodes and one v25 (or v26) node. Some of the tests you deleted in this branch could be moved there. E.g. the test could demonstrate how RBF rule 2 is not enforced when relaying to the new node, but it is when relaying to the v25 node.

Benchmarks on a 2019 MacBook Pro (2,3 GHz 8-Core Intel Core i9), plugged in:

% src/bench/bench_bitcoin -filter=.*Mem.* -min-time=10000

|      330,557,188.67 |                3.03 |    1.5% |     10.77 | `ComplexMemPool`
|      451,529,273.50 |                2.21 |    2.8% |     10.01 | `MemPoolAddTransactions`
|            2,847.13 |          351,231.06 |    2.7% |     10.93 | `MemPoolAncestorsDescendants`
|           11,047.90 |           90,514.97 |    2.5% |     10.69 | `MemPoolMiningScoreCheck`
|        4,328,796.04 |              231.01 |    1.1% |     10.99 | `MempoolCheck`
|           36,268.80 |           27,571.91 |    2.9% |     11.17 | `MempoolEviction`
|        9,123,684.25 |              109.60 |    1.4% |     10.74 | `RpcMempool`

Update: added bench for master@c2d4e40e454ba0c7c836a849b6d15db4850079f2:

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|      302,677,055.25 |                3.30 |    3.5% |     10.76 | `ComplexMemPool`
|      100,167,478.00 |                9.98 |    2.5% |     11.08 | `MempoolCheck`
|           43,759.84 |           22,852.00 |    4.1% |     11.42 | `MempoolEviction`
|       10,235,913.25 |               97.70 |    3.5% |     10.66 | `RpcMempool`

Sjors · 2023-11-14T10:05:29Z

src/bench/mempool_stress.cpp

+}
+
+BENCHMARK(MemPoolAncestorsDescendants, benchmark::PriorityLevel::HIGH);
+BENCHMARK(MemPoolAddTransactions, benchmark::PriorityLevel::HIGH);


dd6684a: While you're touching this, can you rename MempoolCheck to MemPoolCheck, MempoolEviction to MemPoolEviction and ComplexMemPool to MempoolComplex? That makes -filter=MemPool.* work

As a workaround, -filter=.*Mem.* does work.

Sjors · 2023-11-14T10:34:19Z

src/init.cpp

    argsman.AddArg("-limitancestorsize=<n>", strprintf("Do not accept transactions whose size with all in-mempool ancestors exceeds <n> kilobytes (default: %u)", DEFAULT_ANCESTOR_SIZE_LIMIT_KVB), ArgsManager::ALLOW_ANY | ArgsManager::DEBUG_ONLY, OptionsCategory::DEBUG_TEST);
    argsman.AddArg("-limitdescendantcount=<n>", strprintf("Do not accept transactions if any ancestor would have <n> or more in-mempool descendants (default: %u)", DEFAULT_DESCENDANT_LIMIT), ArgsManager::ALLOW_ANY | ArgsManager::DEBUG_ONLY, OptionsCategory::DEBUG_TEST);
    argsman.AddArg("-limitdescendantsize=<n>", strprintf("Do not accept transactions if any ancestor would have more than <n> kilobytes of in-mempool descendants (default: %u).", DEFAULT_DESCENDANT_SIZE_LIMIT_KVB), ArgsManager::ALLOW_ANY | ArgsManager::DEBUG_ONLY, OptionsCategory::DEBUG_TEST);
+    argsman.AddArg("-limitclustercount=<n>", strprintf("Do not accept transactions connected to <n> or more existing in-mempool transactions (default: %u)", DEFAULT_CLUSTER_LIMIT), ArgsManager::ALLOW_ANY | ArgsManager::DEBUG_ONLY, OptionsCategory::DEBUG_TEST);


I made an attempt at dropping -limitdescendantsize and friends: https://github.com/Sjors/bitcoin/commits/2022/11/cluster-mempool

I (naively) replaced ancestor and descendent limits in coin selection with the new cluster limit. At least the tests pass *.

When we drop these settings anyone who uses them will get an error when starting the node. That's probably a good thing, since they should read about this change.

* = well, wallet_basic.py fails with:

Internal bug detected: Shared UTXOs among selection results wallet/coinselection.h:340 (InsertInputs)

I think we can do something similar to #32941 and just emit a warning (not error) for the first release, then remove it afterwards. We can't deprecate / continue supporting the options, but this is more user-friendly than dropping immediately.

InitWarning(_("Option '-limitdescendantcount' is set but no longer has any effect (see release notes about cluster limits). Please remove it from your configuration."));

Sjors

Couple more comments / questions. To be continued...

Sjors · 2023-11-14T13:15:36Z

src/txmempool.cpp

+{
+    m_chunks[entry.m_loc.first].txs.erase(entry.m_loc.second);
+
+    // Chunk (or cluster) may now be empty, but this will get cleaned up


54f39ca: what if the deleted transaction makes it so there are now two clusters? This is also safe to ignore?

I wouldn't say it's safe to ignore, but the idea is that we often want to be able to batch deletions, and then clean things up in one pass. So the call sites should all be dealing with this issue and ensuring that we always clean up at some point.

(This is definitely an area where I expect that we'll be re-engineering all this logic and trying to come up with a better abstraction layer so that this is more robust and easier to think about!)

Sjors · 2023-11-14T14:09:48Z

src/txmempool.cpp

+
+    for (auto txentry : txs) {
+        m_chunks.emplace_back(txentry.get().GetModifiedFee(), txentry.get().GetTxSize());
+        m_chunks.back().txs.emplace_back(txentry);


54f39ca: So you're creating a chunk for each new transaction and then erasing it if the fee rate goes down. Why not the other way around?

src/txmempool.cpp

Now that ancestor calculation never fails (due to ancestor/descendant limits being eliminated), we can eliminate the error handling from CalculateMemPoolAncestors.

…l entry

Changes AddToMempool() helper to only apply changes if the mempool limits are respected. Fix package_rbf fuzz target to handle mempool policy violations

Add benchmarks for: - mempool update time when blocks are found - adding a transaction - performing the mempool's RBF calculation - calculating mempool ancestors/descendants

Including test coverage for mempool eviction and expiry

Co-authored-by: glozow <gloriajzhao@gmail.com>

This is in preparation for eliminating the block template building happening in mini_miner, in favor of directly using the linearizations done in the mempool.

…ScoreWithTopology() We use CompareMiningScoreWithTopology() for sorting transaction announcements during tx relay, and we use GetSortedScoreWithTopology() in CTxMemPool::check().

Calculating mempool ancestors for a new transaction should not be done until after cluster size limits have been enforced, to limit CPU DoS potential. Achieve this by reworking TRUC and RBF validation logic: - TRUC policy enforcement is now done using only mempool parents of new transactions, not all mempool ancestors. - RBF replacement checks are performed earlier (which allows for checking cluster size limits earlier, because cluster size checks cannot happen until after all conflicts are staged for removal). - Verifying that a new transaction doesn't conflict with an ancestor now happens later, in AcceptSingleTransaction() rather than in PreChecks(). This means that the test is not performed at all in AcceptMultipleTransactions(), but in package acceptance we already disallow RBF in situations where a package transaction has in-mempool parents. Also to ensure that all RBF validation logic is applied in both the single transaction and multiple transaction cases, remove the optimization that skips the PackageMempoolChecks() in the case of a single transaction being validated in AcceptMultipleTransactions().

17cf9ff Use cluster size limit for -maxmempool bound, and allow -maxmempool=0 in general (Suhas Daftuar) 315e43e Sanity check `GetFeerateDiagram()` in CTxMemPool::check() (Suhas Daftuar) de2e9a2 test: extend package rbf functional test to larger clusters (Suhas Daftuar) 4ef4ddb doc: update policy/packages.md for new package acceptance logic (Suhas Daftuar) 79f73ad Add check that GetSortedScoreWithTopology() agrees with CompareMiningScoreWithTopology() (Suhas Daftuar) a86ac11 Update comments for CTxMemPool class (Suhas Daftuar) 9567eaa Invoke TxGraph::DoWork() at appropriate times (Suhas Daftuar) 6c5c44f test: add functional test for new cluster mempool RPCs (Suhas Daftuar) 72f60c8 doc: Update mempool_replacements.md to reflect feerate diagram checks (Suhas Daftuar) 21693f0 Expose cluster information via rpc (Suhas Daftuar) 72e74e0 fuzz: try to add more code coverage for mempool fuzzing (Suhas Daftuar) f107417 bench: add more mempool benchmarks (Suhas Daftuar) 7976eb1 Avoid violating mempool policy limits in tests (Suhas Daftuar) 84de685 Stop tracking parents/children outside of txgraph (Suhas Daftuar) 88672e2 Rewrite GatherClusters to use the txgraph implementation (Suhas Daftuar) 1ca4f01 Fix miniminer_tests to work with cluster limits (Suhas Daftuar) 1902111 Eliminate CheckPackageLimits, which no longer does anything (Suhas Daftuar) 3a646ec Rework RBF and TRUC validation (Suhas Daftuar) 19b8479 Make getting parents/children a function of the mempool, not a mempool entry (Suhas Daftuar) 5560913 Rework truc_policy to use descendants, not children (Suhas Daftuar) a4458d6 Use txgraph to calculate descendants (Suhas Daftuar) c8b6f70 Use txgraph to calculate ancestors (Suhas Daftuar) 241a3e6 Simplify ancestor calculation functions (Suhas Daftuar) b9cec7f Make removeConflicts private (Suhas Daftuar) 0402e6c Remove unused limits from CalculateMemPoolAncestors (Suhas Daftuar) 08be765 Remove mempool logic designed to maintain ancestor/descendant state (Suhas Daftuar) fc4e3e6 Remove unused members from CTxMemPoolEntry (Suhas Daftuar) ff3b398 mempool: eliminate accessors to mempool entry ancestor/descendant cached state (Suhas Daftuar) b9a2039 Eliminate use of cached ancestor data in miniminer_tests and truc_policy (Suhas Daftuar) ba09fc9 mempool: Remove unused function CalculateDescendantMaximum (Suhas Daftuar) 8e49477 wallet: Replace max descendant count with cluster_count (Suhas Daftuar) e031085 Eliminate Single-Conflict RBF Carve Out (Suhas Daftuar) cf3ab8e Stop enforcing descendant size/count limits (Suhas Daftuar) 89ae38f test: remove rbf carveout test from mempool_limit.py (Suhas Daftuar) c0bd04d Calculate descendant information for mempool RPC output on-the-fly (Suhas Daftuar) bdcefb8 Use mempool/txgraph to determine if a tx has descendants (Suhas Daftuar) 69e1eaa Add test case for cluster size limits to TRUC logic (Suhas Daftuar) 9cda64b Stop enforcing ancestor size/count limits (Suhas Daftuar) 1f93227 Remove dependency on cached ancestor data in mini-miner (Suhas Daftuar) 9fbe0a4 rpc: Calculate ancestor data from scratch for mempool rpc calls (Suhas Daftuar) 7961496 Reimplement GetTransactionAncestry() to not rely on cached data (Suhas Daftuar) feceaa4 Remove CTxMemPool::GetSortedDepthAndScore (Suhas Daftuar) 21b5cea Use cluster linearization for transaction relay sort order (Suhas Daftuar) 6445aa7 Remove the ancestor and descendant indices from the mempool (Suhas Daftuar) 216e693 Implement new RBF logic for cluster mempool (Suhas Daftuar) ff8f115 policy: Remove CPFP carveout rule (Suhas Daftuar) c3f1afc test: rewrite PopulateMempool to not violate mempool policy (cluster size) limits (Suhas Daftuar) 47ab32f Select transactions for blocks based on chunk feerate (Suhas Daftuar) dec138d fuzz: remove comparison between mini_miner block construction and miner (Suhas Daftuar) 6c2bceb bench: rewrite ComplexMemPool to not create oversized clusters (Suhas Daftuar) 1ad4590 Limit mempool size based on chunk feerate (Suhas Daftuar) b11c89c Rework miner_tests to not require large cluster limit (Suhas Daftuar) 95a8297 Check cluster limits when using -walletrejectlongchains (Suhas Daftuar) 95762e6 Do not allow mempool clusters to exceed configured limits (Suhas Daftuar) edb3e7c [test] rework/delete feature_rbf tests requiring large clusters (glozow) 435fd56 test: update feature_rbf.py replacement test (Suhas Daftuar) 34e3298 Add new (unused) limits for cluster size/count (Suhas Daftuar) 838d7e3 Add transactions to txgraph, but without cluster dependencies (Suhas Daftuar) d5ed9cb Add accessor for sigops-adjusted weight (Suhas Daftuar) 1bf3b51 Add sigops adjusted weight calculator (Suhas Daftuar) c18c68a Create a txgraph inside CTxMemPool (Suhas Daftuar) 29a94d5 Make CTxMemPoolEntry derive from TxGraph::Ref (Suhas Daftuar) 92b0079 Allow moving CTxMemPoolEntry objects, disallow copying (Suhas Daftuar) 6c73e47 mempool: Store iterators into mapTx in mapNextTx (Suhas Daftuar) 5143068 Allow moving an Epoch::Marker (Suhas Daftuar) Pull request description: [Reopening #28676 here as a new PR, because GitHub is slow to load the page making it hard to scroll through and see comments. Also, that PR was originally opened with a prototype implementation which has changed significantly with the introduction of `TxGraph`.] This is an implementation of the [cluster mempool proposal](https://delvingbitcoin.org/t/an-overview-of-the-cluster-mempool-proposal/393). This branch implements the following observable behavior changes: - Maintains a partitioning of the mempool into connected clusters (via the `txgraph` class), which are limited in vsize to 101 kvB by default, and limited in count to 64 by default. - Each cluster is sorted ("linearized") to try to optimize for selecting highest-feerate-subsets of a cluster first - Transaction selection for mining is updated to use the cluster linearizations, selecting highest feerate "chunks" first for inclusion in a block template. - Mempool eviction is updated to use the cluster linearizations, selecting lowest feerate "chunks" first for removal. - The RBF rules are updated to: (a) drop the requirement that no new inputs are introduced; (b) change the feerate requirement to instead check that the feerate diagram of the mempool will strictly improve; (c) replace the direct conflicts limit with a directly-conflicting-clusters limit. - The CPFP carveout rule is eliminated (it doesn't make sense in a cluster-limited mempool) - The ancestor and descendant limits are no longer enforced. - New cluster count/cluster vsize limits are now enforced instead. - Transaction relay now uses chunk feerate comparisons to determine the order that newly received transactions are announced to peers. Additionally, the cached ancestor and descendant data are dropped from the mempool, along with the multi_index indices that were maintained to sort the mempool by ancestor and descendant feerates. For compatibility (eg with wallet behavior or RPCs exposing this), this information is now calculated dynamically instead. ACKs for top commit: instagibbs: reACK 17cf9ff glozow: reACK 17cf9ff sipa: ACK 17cf9ff Tree-SHA512: bbde46d913d56f8d9c0426cb0a6c4fa80b01b0a4c2299500769921f886082fb4f51f1694e0ee1bc318c52e1976d7ebed8134a64eda0b8044f3a708c04938eee7

b8d279a doc: add comment to explain correctness of GatherClusters() (Suhas Daftuar) aba7500 Fix parameter name in getmempoolcluster rpc (Suhas Daftuar) 6c1325a Rename weight -> clusterweight in RPC output, and add doc explaining mempool terminology (Suhas Daftuar) bc2eb93 Require mempool lock to be held when invoking TRUC checks (Suhas Daftuar) 957ae23 Improve comments for getTransactionAncestry to reference cluster counts instead of descendants (Suhas Daftuar) d97d619 Fix comment to reference cluster limits, not chain limits (Suhas Daftuar) a1b341e Sanity check feerate diagram in CTxMemPool::check() (Suhas Daftuar) 23d6f45 rpc: improve getmempoolcluster output (Suhas Daftuar) d2dcd37 Avoid using mapTx.modify() to update modified fees (Suhas Daftuar) d84ffc2 doc: add release notes snippet for cluster mempool (Suhas Daftuar) b0417ba doc: Add design notes for cluster mempool and explain new mempool limits (Suhas Daftuar) 2d88966 miner: replace "package" with "chunk" (Suhas Daftuar) 6f3e8eb Add a GetFeePerVSize() accessor to CFeeRate, and use it in the BlockAssembler (Suhas Daftuar) b5f245f Remove unused DEFAULT_ANCESTOR_SIZE_LIMIT_KVB and DEFAULT_DESCENDANT_SIZE_LIMIT_KVB (Suhas Daftuar) 1dac54d Use cluster size limit instead of ancestor size limit in txpackage unit test (Suhas Daftuar) 04f6548 Use cluster size limit instead of ancestor/descendant size limits when sanity checking TRUC policy limits (Suhas Daftuar) 634291a Use cluster limits instead of ancestor/descendant limits when sanity checking package policy limits (Suhas Daftuar) fc18ef1 Remove ancestor and descendant vsize limits from MemPoolLimits (Suhas Daftuar) ed8e819 Warn user if using -limitancestorsize/-limitdescendantsize that the options have no effect (Suhas Daftuar) 80d8df2 Invoke removeUnchecked() directly in removeForBlock() (Suhas Daftuar) 9292570 Rewrite GetChildren without sets (Suhas Daftuar) 3e39ea8 Rewrite removeForReorg to avoid using sets (Suhas Daftuar) a3c31df scripted-diff: rename AddToMempool -> TryAddToMempool (Suhas Daftuar) a5a7905 Simplify removeRecursive (Suhas Daftuar) 01d8520 Remove unused argument to RemoveStaged (Suhas Daftuar) bc64013 Remove unused variable (cacheMap) in mempool (Suhas Daftuar) Pull request description: As suggested in the main cluster mempool PR (#28676 (review)), 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. ACKs for top commit: instagibbs: ACK b8d279a sipa: ACK b8d279a Tree-SHA512: 1a05e99eaf8db2e274a1801307fed5d82f8f917e75ccb9ab0e1b0eb2f9672b13c79d691d78ea7cd96900d0e7d5031a3dd582ebcccc9b1d66eb7455b1d3642235

DrahtBot added the CI failed label Oct 18, 2023

sdaftuar force-pushed the 2023-10-cluster-mempool branch from 9420af6 to a254fba Compare October 18, 2023 19:14

sdaftuar force-pushed the 2023-10-cluster-mempool branch from 190ada4 to b4f69c3 Compare October 19, 2023 18:28

DrahtBot mentioned this pull request Oct 19, 2023

C++20 std::views::reverse #28687

Merged

sdaftuar force-pushed the 2023-10-cluster-mempool branch from 033e7fe to 29f428f Compare October 19, 2023 23:46

glozow added the Mempool label Oct 20, 2023

DrahtBot mentioned this pull request Oct 20, 2023

build: Introduce internal kernel library #28690

Open

instagibbs reviewed Oct 24, 2023

View reviewed changes

DrahtBot mentioned this pull request Oct 26, 2023

doc: Fix bugprone-lambda-function-name errors #28737

Merged

DrahtBot added the Needs rebase label Oct 30, 2023

Sjors reviewed Nov 14, 2023

View reviewed changes

glozow mentioned this pull request Nov 14, 2023

Package Relay Project Tracking #27463

Open

57 tasks

Sjors mentioned this pull request Nov 17, 2023

wallet, mempool: propagete checkChainLimits error message to wallet #28863

Merged

sdaftuar and others added 24 commits October 14, 2025 14:03

==== END MEMPOOL CLEANUP ====

050ca80

==== BEGIN OPTIMIZATIONS ====

c6ad34c

Simplify ancestor calculation functions

5502a06

Now that ancestor calculation never fails (due to ancestor/descendant limits being eliminated), we can eliminate the error handling from CalculateMemPoolAncestors.

Use txgraph to calculate ancestors

f350915

Use txgraph to calculate descendants

d55f4eb

Rework truc_policy to use descendants, not children

e488cde

Make getting parents/children a function of the mempool, not a mempoo…

d85723a

…l entry

Eliminate CheckPackageLimits, which no longer does anything

b3c6b78

Fix miniminer_tests to work with cluster limits

517c734

Rewrite GatherClusters to use the txgraph implementation

cc6d55b

Stop tracking parents/children outside of txgraph

bdbe50e

==== END OPTIMIZATIONS ====

4c52a21

==== BEGIN DOCS/TESTING ====

233b886

Avoid violating mempool policy limits in tests

befe5c8

Changes AddToMempool() helper to only apply changes if the mempool limits are respected. Fix package_rbf fuzz target to handle mempool policy violations

bench: add more mempool benchmarks

dbb6e2b

Add benchmarks for: - mempool update time when blocks are found - adding a transaction - performing the mempool's RBF calculation - calculating mempool ancestors/descendants

fuzz: try to add more code coverage for mempool fuzzing

fb211f8

Including test coverage for mempool eviction and expiry

Expose cluster information via rpc

7ffd7c8

Co-authored-by: glozow <gloriajzhao@gmail.com>

doc: Update mempool_replacements.md to reflect feerate diagram checks

ac20c79

test: add functional test for new cluster mempool RPCs

aa30f26

fuzz: remove comparison between mini_miner block construction and miner

c88360c

This is in preparation for eliminating the block template building happening in mini_miner, in favor of directly using the linearizations done in the mempool.

Invoke TxGraph::DoWork() at appropriate times

b80c039

Update comments for CTxMemPool class

6bb3e4f

Add check that GetSortedScoreWithTopology() agrees with CompareMining…

92872a7

…ScoreWithTopology() We use CompareMiningScoreWithTopology() for sorting transaction announcements during tx relay, and we use GetSortedScoreWithTopology() in CTxMemPool::check().

sdaftuar force-pushed the 2023-10-cluster-mempool branch from 989827e to d3f8b63 Compare October 14, 2025 18:06

sdaftuar closed this Oct 14, 2025

sdaftuar mentioned this pull request Oct 14, 2025

Cluster mempool #33629

Merged

glozow mentioned this pull request Oct 28, 2025

Cluster mempool review and followups glozow/bitcoin#13

Open

Cluster mempool implementation #28676

Cluster mempool implementation #28676

Uh oh!

Conversation

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

Uh oh!

Uh oh!

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

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

instagibbs Oct 25, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Sjors left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

12 participants

sdaftuar commented Oct 18, 2023 •

edited

Loading

DrahtBot commented Oct 18, 2023 •

edited

Loading

instagibbs Oct 25, 2023 •

edited

Loading

Sjors commented Nov 14, 2023 •

edited

Loading

Sjors Nov 14, 2023 •

edited

Loading