sipa
commented at 7:06 pm on December 22, 2024:
member
Part of cluster mempool (#30289). Builds on top of #31444.
During reorganisations, it is possible that dependencies get added which would result in clusters that violate policy limits (cluster count, cluster weight), when linking the new from-block transactions to the old from-mempool transactions. Unlike RBF scenarios, we cannot simply reject the changes when they are due to received blocks. To accommodate this, add a TxGraph::Trim(), which removes some subset of transactions (including descendants) in order to make all resulting clusters satisfy the limits.
Conceptually, the way this is done is by defining a rudimentary linearization for the entire would-be too-large cluster, iterating it from beginning to end, and reasoning about the counts and weights of the clusters that would be reached using transactions up to that point. If a transaction is encountered whose addition would violate the limit, it is removed, together with all its descendants.
This rudimentary linearization is like a merge sort of the chunks of the clusters being combined, but respecting topology. More specifically, it is continuously picking the highest-chunk-feerate remaining transaction among those which have no unmet dependencies left. For efficiency, this rudimentary linearization is computed lazily, by putting all viable transactions in a heap, sorted by chunk feerate, and adding new transactions to it as they become viable.
The Trim() function is rather unusual compared to the TxGraph functionality added in previous PRs, in that Trim() makes it own decisions about what the resulting graph contents will be, without good specification of how it makes that decision - it is just a best-effort attempt (which is improved in the last commit). All other TxGraph mutators are simply to inform the graph about changes the calling mempool code decided on; this one lets the decision be made by txgraph.
As part of this, the “oversized” property is expanded to also encompass a configurable cluster weight limit (in addition to cluster count limit).
DrahtBot
commented at 7:06 pm on December 22, 2024:
contributor
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
See the guideline for information on the review process.
A summary of reviews will appear here.
Conflicts
Reviewers, this pull request conflicts with the following ones:
#31519 (refactor: Use std::span over Span by maflcko)
#30605 (Cluster linearization: separate tests from tests-of-tests by sipa)
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.
glozow added the label
Mempool
on Jan 2, 2025
sipa force-pushed
on Jan 8, 2025
DrahtBot added the label
CI failed
on Jan 9, 2025
DrahtBot
commented at 0:52 am on January 9, 2025:
contributor
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.
sipa force-pushed
on Jan 9, 2025
DrahtBot removed the label
CI failed
on Jan 9, 2025
sipa force-pushed
on Jan 9, 2025
in
src/txgraph.cpp:1653
in
0c8dc2323eoutdated
948+ Ref ret;
949+ // Construct a new Entry, and link it with the Ref.
950+ auto idx = m_entries.size();
951+ m_entries.emplace_back();
952+ auto& entry = m_entries.back();
953+ entry.m_ref = &ret;
I’m not sure how this is intended to be used, but storing a stack address seems like a problem? RVO may help but that seems brittle. I imagine the caller should be passing in their own Ref instead?
Ah, right, I missed that the move ctor would handle the update. Thanks for explaining.
in
src/txgraph.cpp:1172
in
0c8dc2323eoutdated
1167+ }
1168+}
1169+
1170+TxGraph::Ref& TxGraph::Ref::operator=(Ref&& other) noexcept
1171+{
1172+ // Inform both TxGraphs about the Refs being swapped.
Why is this doing an effective swap? I would expect this to call UnlinkRef on the moved-from value and reset its m_graph and m_index. Otherwise it wouldn’t be unlinked until the moved-from variable goes out of scope, no?
The vector now holds the old ref and UnlinkRef will not be called until that element is removed. I realize it’s allowed to be a “valid but unspecified state”, but I wouldn’t expect a ref to be hanging around.
in
src/txgraph.cpp:188
in
0c8dc2323eoutdated
183+ /** A class of objects held internally in TxGraphImpl, with information about a single
184+ * transaction. */
185+ struct Entry
186+ {
187+ /** Pointer to the corresponding Ref object, if any. */
188+ Ref* m_ref;
292+ LinearizationIndex lin_idx{0};
293+ // Iterate over the chunks.
294+ for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
295+ auto chunk = chunking.GetChunk(chunk_idx);
296+ // Iterate over the transactions in the linearization, which must match those in chunk.
297+ while (true) {
Trying to convince myself this is guaranteed to terminate…
do{} while (!chunk.transactions.None()) rather than the break for readability? Or just while() if we need to guard against an empty linearization (presumably not?)
Every chunk contains at least one element (added an Assume for that)
In the inner loop, one element from that chunk is Reset() (added an Assume that it indeed resets a bit that was previously set).
I’ve changed it to a do {} while(chunk.transactions.Any()); loop in the first commits, though it reverts back to a while (true) { ... } loop later, when the loop becomes a bit more complex.
in
src/txgraph.cpp:778
in
0c8dc2323eoutdated
306+}
307+
308+void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept
309+{
310+ // Iterate over the prefix of to_remove that applies to this cluster.
311+ SetType todo;
Done. I’ve also added a comment to the Cluster::ApplyRemovals() function definition stating that at least one element from the front of to_remove must belong to this Cluster (which is really why that requirement exists).
in
src/txgraph.cpp:1662
in
0c8dc2323eoutdated
1002+ // Make sure the transaction isn't scheduled for removal.
1003+ ApplyRemovals();
1004+ return m_entries[GetRefIndex(arg)].m_locator.IsPresent();
1005+}
1006+
1007+std::vector<TxGraph::Ref*> Cluster::GetAncestorRefs(const TxGraphImpl& graph, ClusterIndex idx) noexcept
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.
sipa force-pushed
on Jan 10, 2025
DrahtBot removed the label
CI failed
on Jan 10, 2025
sdaftuar
commented at 2:10 pm on January 24, 2025:
FYI – in my rebase of #28676, I’m seeing tx_pool fuzz test failures due to this line. Not clear to me whether we should require the caller to enforce the policy requirement that a single tx be below the cluster size limit, or just let the caller discover a changeset is oversized and then reject?
Right. That rule exists because the alternative requires existing clusters to be oversized as AddTransaction constructs a singleton cluster instantly. All other forms of oversizedness happen as a result of applying dependencies, which are done lazily.
Done, it is now allowed to have individually oversized transactions.
sipa force-pushed
on Jan 24, 2025
sipa
commented at 10:14 pm on January 24, 2025:
member
Some changes:
As a result of dropping Cleanup in the base PR, Trim now reports which transactions it removed, as it becomes the caller’s responsibility of destroying Refs.
DrahtBot added the label
CI failed
on Jan 24, 2025
DrahtBot
commented at 11:23 pm on January 24, 2025:
contributor
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.
sipa force-pushed
on Jan 26, 2025
sipa
commented at 4:42 am on January 26, 2025:
member
Add support for calling AddTransaction with a feerate whose size already violates the cluster size limit.
DrahtBot removed the label
CI failed
on Jan 26, 2025
sipa force-pushed
on Jan 26, 2025
sipa force-pushed
on Jan 30, 2025
DrahtBot
commented at 1:01 am on January 31, 2025:
contributor
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.
DrahtBot added the label
CI failed
on Jan 31, 2025
sipa force-pushed
on Jan 31, 2025
DrahtBot removed the label
CI failed
on Jan 31, 2025
sipa force-pushed
on Jan 31, 2025
sipa force-pushed
on Feb 1, 2025
sipa force-pushed
on Feb 4, 2025
DrahtBot added the label
CI failed
on Feb 4, 2025
DrahtBot removed the label
CI failed
on Feb 4, 2025
sipa force-pushed
on Feb 6, 2025
sipa force-pushed
on Feb 11, 2025
sipa force-pushed
on Feb 12, 2025
DrahtBot
commented at 11:49 pm on February 12, 2025:
contributor
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.
DrahtBot added the label
CI failed
on Feb 12, 2025
sipa force-pushed
on Feb 13, 2025
DrahtBot removed the label
CI failed
on Feb 13, 2025
sipa force-pushed
on Feb 14, 2025
sipa force-pushed
on Feb 20, 2025
clusterlin: add FixLinearization function + fuzz test
This function takes an existing ordering for transactions in a DepGraph, and
makes it a valid linearization for it (i.e., topological). Any topological
prefix of the input remains untouched.
b6a7238ec3
clusterlin: make IsAcyclic() a DepGraph member function
... instead of being a separate test-only function.
Also add a fuzz test for it returning false.
Since cluster_linearize.h does not actually have a Cluster type anymore, it is more
appropriate to rename the index type to DepGraphIndex.
9363105246
feefrac: introduce tagged wrappers to distinguish vsize/WU rates2637908a18
txgraph: (feature) add initial version
This adds an initial version of the txgraph module, with the TxGraph class.
It encapsulates knowledge about the fees, sizes, and dependencies between all
mempool transactions, but nothing else.
In particular, it lacks knowledge about txids, inputs, outputs, CTransactions,
... and so on. Instead, it exposes a generic TxGraph::Ref type to reference
nodes in the TxGraph, which can be passed around and stored by layers on top.
cba16ead84
txgraph: (tests) add simulation fuzz test
This adds a simulation fuzz test for txgraph, by comparing with a naive
reimplementation that models the entire graph as a single DepGraph, and
clusters in TxGraph as connected components within that DepGraph.
98ab5afb84
txgraph: (tests) add internal sanity check function
To make testing more powerful, expose a function to perform an internal sanity
check on the state of a TxGraph. This is especially important as TxGraphImpl
contains many redundantly represented pieces of information:
* graph contains clusters, which refer to entries, but the entries refer back
* graph maintains pointers to Ref objects, which point back to the graph.
This lets us make sure they are always in sync.
8813222308
txgraph: (optimization) avoid per-group vectors for clusters & dependencies
Instead construct a single vector with the list of all clusters in all groups,
and then store per-group offset/range in that list.
For dependencies, reuse m_deps_to_add, and store offset/range into that.
43d746b27e
txgraph: (feature) make max cluster count configurable and "oversize" state
Instead of leaving the responsibility on higher layers to guarantee that
no connected component within TxGraph (a barely exposed concept, except through
GetCluster()) exceeds the cluster count limit, move this responsibility to
TxGraph itself:
* TxGraph retains a cluster count limit, but it becomes configurable at construction
time (this primarily helps with testing that it is properly enforced).
* It is always allowed to perform mutators on TxGraph, even if they would cause the
cluster count limit to be exceeded. Instead, TxGraph exposes an IsOversized()
function, which queries whether it is in a special "oversize" state.
* During oversize state, many inspectors are unavailable, but mutators remain valid,
so the higher layer can "fix" the oversize state before continuing.
acc230d2f5
txgraph: (optimization) avoid representative lookup for each dependency
The m_deps_to_add vector is sorted by child Cluster*, which matches the
order of an_clusters. This means we can walk through m_deps_to_add while
doing the representative lookups for an_clusters, and reuse them.
b54fd58008
txgraph: (optimization) avoid looking up the same child cluster repeatedly
Since m_deps_to_add has been sorted by child Cluster* already, all dependencies
with the same child will be processed consecutively. Take advantage of this by
remember the last partition merged with, and reusing that if applicable.
fa9aff881d
txgraph: (optimization) delay chunking while sub-acceptable
Chunk-based information (primarily, chunk feerates) are never accessed without
first bringing the relevant Clusters to an "acceptable" quality level. Thus,
while operations are ongoing and Clusters are not acceptable, we can omit
computing the chunkings and chunk feerates for Clusters.
d63cee9251
txgraph: (optimization) special-case removal of tail of cluster
When transactions are removed from the tail of a cluster, we know the existing
linearization remains acceptable/optimal (if it already was), but may just need
splitting, so special case these into separate quality levels.
849317dd55
txgraph: (refactor) group per-graph data in ClusterSet
This is a preparation for a next commit where a TxGraph will start representing
potentially two distinct graphs (a main one, and a staging one with proposed
changes).
b4885a2d12
txgraph: (refactor) abstract out ClearLocator
Move a number of related modifications to TxGraphImpl into a separate
function for removal of transactions. This is preparation for a later
commit where this will be useful in more than one place.
7fa108d67b
txgraph: (feature) add staging support
In order to make it easy to evaluate proposed changes to a TxGraph, introduce a
"staging" mode, where mutators (AddTransaction, AddDependency, RemoveTransaction)
do not modify the actual graph, but just a staging version of it. That staging
graph can then be commited (replacing the main one with it), or aborted (discarding
the staging).
7017e89ab8
txgraph: (optimization) cache oversizedness of graphsdef212b423
txgraph: (feature) destroying Ref means removing transaction
Before this commit, if a TxGraph::Ref object is destroyed, it becomes impossible
to refer to, but the actual corresponding transaction node in the TxGraph remains,
and remains indefinitely as there is no way to remove it.
Fix this by making the destruction of TxGraph::Ref trigger immediate removal of
the corresponding transaction in TxGraph, both in main and staging if it exists.
d885ae1a94
txgraph: (feature) expose ability to compare transactions
In order to make it possible for higher layers to compare transaction quality
(ordering within the implicit total ordering on the mempool), expose a comparison
function and test it.
11442cfc33
txgraph: (feature) Add DoWork function
This can be called when the caller has time to spend now, and wants future operations
to be fast.
This interface lets one iterate efficiently over the chunks of the main
graph in a TxGraph, in the same order as CompareMainOrder. Each chunk
can be marked as "included" or "skipped" (and in the latter case,
dependent chunks will be skipped).
txgraph: (optimization) skipping end of cluster has no impact31be1466a8
txgraph: (optimization) special-case singletons in chunk indexefad48b239
txgraph: (feature) Add ability to configure maximum cluster size (weight)
This is integrated with the oversized property: the graph is oversized when
any connected component within it contains more than the cluster count limit
many transactions, or when their combined size/weight exceeds the cluster size
limit.
It becomes disallowed to call AddTransaction with a size larger than this limit.
In addition, SetTransactionFeeRate becomes SetTransactionFee, so that we do not
need to deal with the case that a call to this function might affect the
oversizedness.
01f8623ee1
txgraph: (feature) permit transactions that exceed cluster size limit4ab8eea1c6
txgraph: (feature) Add ability to trim oversized clusters
During reorganisations, it is possible that dependencies get add which
result in clusters that violate limits (count, size), when linking the
new from-block transactions to the old from-mempool transactions.
Unlike RBF scenarios, we cannot simply reject these policy violations
when they are due to received blocks. To accomodate this, add a Trim()
function to TxGraph, which removes transactions (including descendants)
in order to make all resulting clusters satisfy the limits.
dd90502650
txgraph: (improvement) track multiple potential would-be clusters in Trim
In a Trim function, for any given would-be group of clusters, a (rudimentary)
linearization for the would-be cluster is constructed on the fly by adding
eligible transactions to a heap. This continues until the total count or
size of the transaction exists a configured limit. Any transactions which
appear later in this linearization are discarded.
However, given that transactions at the end are discarded, it is possible that
the would-be cluster splits apart into multiple clusters. And those clusters
may well permit far more transactions before their limits are reached.
Take this into account by using a union-find structure inside TrimTxData to
keep track of the count/size of all would-be clusters that would be formed
at any point.
This is not an optimization in terms of CPU usage or memory; it just
improves the quality of the transactions removed by Trim().
This is a metadata mirror of the GitHub repository
bitcoin/bitcoin.
This site is not affiliated with GitHub.
Content is generated from a GitHub metadata backup.
generated: 2025-02-22 15:12 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
