cluster mempool: add txgraph diagrams/mining/eviction

sipa commented at 2:50 pm on December 8, 2024: member

Part of cluster mempool: #30289

This builds on #31363, adding more functionality to the txgraph module, specifically:

TxGraph::GetMainStagingDiagrams(), a function to obtain feerate diagrams for both the main graph and the staged changes to it, including only the clusters that differ between the two.
TxGraph::GetBlockBuilder(), a function to obtain an object which can efficiently iterate the chunks of the (main) graph from high to low chunk feerate, allowing each to be skipped or included.
TxGraph::GetWorstMainChunk(), a function to obtain the last chunk that would be returned by GetBlockBuilder()’s returned object, intended for eviction.

DrahtBot commented at 2:50 pm on December 8, 2024: contributor

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

Reviews

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.

sipa force-pushed on Dec 8, 2024

DrahtBot added the label CI failed on Dec 8, 2024

DrahtBot commented at 2:59 pm on December 8, 2024: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/34093447174

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 Dec 8, 2024

DrahtBot removed the label CI failed on Dec 8, 2024

glozow added the label Mempool on Dec 17, 2024

sipa force-pushed on Dec 20, 2024

sipa force-pushed on Dec 22, 2024

sipa force-pushed on Jan 8, 2025

sipa commented at 11:30 pm on January 8, 2025: member

I have simplified the eviction interface. Instead of getting a TxGraph::Evictor object through TxGraph::GetEvictor(), there is now a simpler TxGraph::GetWorstMainChunk() function, which is a pure inspector.

DrahtBot added the label CI failed on Jan 9, 2025

DrahtBot commented at 0:51 am on January 9, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/35343422864

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

DrahtBot commented at 11:40 pm on January 9, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/35398305833

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 9, 2025

sipa force-pushed on Jan 10, 2025

DrahtBot removed the label CI failed on Jan 10, 2025

sipa force-pushed on Jan 10, 2025

sipa force-pushed on Jan 16, 2025

sipa force-pushed on Jan 22, 2025

sipa commented at 8:01 pm on January 22, 2025: member

I modified TxGraph::GetWorstMainChunk() to return the chunk feerate in addition to the list of transaction Refs.

sipa force-pushed on Jan 24, 2025

DrahtBot commented at 11:48 pm on January 24, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/36148920396

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 24, 2025

sipa force-pushed on Jan 26, 2025

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 added the label CI failed on Jan 31, 2025

DrahtBot commented at 1:16 am on January 31, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/36451236768

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 31, 2025

DrahtBot removed the label CI failed on Jan 31, 2025

sipa force-pushed on Jan 31, 2025

DrahtBot added the label CI failed on Jan 31, 2025

DrahtBot commented at 11:33 pm on January 31, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/36505832220

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 Feb 1, 2025

DrahtBot removed the label CI failed on Feb 1, 2025

sipa force-pushed 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

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/37128497464

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.

87fed74a9a

clusterlin: (refactor) ClusterIndex -> DepGraphIndex

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 rates 2637908a18

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 graphs def212b423

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.

fc98be3add

txgraph: (feature) Add CountDistinctClusters function 0e4b3943f3

txgraph: (preparation) multiple inputs to Get{Ancestors,Descendant}Refs

This is a preparation for the next commit, which adds a feature to request
the Refs to multiple ancestors/descendants at once.

225a360797

txgraph: (feature) Get{Ancestors,Descendants}Union d5abb86439

txgraph: (feature) Add GetMainStagingDiagrams function

This allows determining whether the changes in a staging diagram unambiguously improve
the graph, through CompareChunks().

cdaf4f8519

txgraph: (preparation) maintain chunk index

This is preparation for exposing mining and eviction functionality in
TxGraph.

369448552a

txgraph: (feature) introduce BlockBuilder interface

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).

6c275c62b2

txgraph: (feature) introduce TxGraph::GetWorstMainChunk

It returns the last chunk that would be suggested for mining by BlockBuilder
objects. This is intended for eviction.

67b69301c9

txgraph: (optimization) reuse discarded chunkindex entries 80ab8682b0

txgraph: (optimization) skipping end of cluster has no impact 31be1466a8

txgraph: (optimization) special-case singletons in chunk index efad48b239

sipa force-pushed on Feb 21, 2025

cluster mempool: add txgraph diagrams/mining/eviction #31444

Code Coverage & Benchmarks

Reviews

Conflicts