Cluster mempool: add txgraph diagrams/mining/eviction (mempool)

https://github.com/bitcoin/bitcoin/pull/31444

Host: glozow  -  PR author: sipa

Notes

Motivations and Background

  • Block building (done by the BlockAssembler) is the process of selecting ~4MWU worth of mempool transactions while trying to maximize the total fees.
  • Non-mining nodes might never use the block builder, but are still interested in comparing the incentive compatibility of transactions as a metric for whether it is worth keeping: if the mempool exceeds its maximum memory allowance, it should evict the transactions that are least likely to be mined soon.
  • The block building algorithm on master uses ancestor set-based sort to dynamically linearize mempool transactions by including ancestor sets in order of highest ancestor score (minimum between ancestor feerate and individual feerate). As transactions are included, their descendants’ ancestor scores can change; the BlockAssembler keeps a copy of mempool entries with their updated ancestor information in a separate map, which avoids modifying the mempool itself. We covered this algorithm in more detail in a previous meeting.
  • Ancestor set-based sorting can be used to linearize the entire mempool to find the “worst” transaction for eviction, but this algorithm would be too slow to use in practice.
  • Instead, eviction runs a similar algorithm with ascending descendant score (maximum between descendant feerate and individual feerate). This also linearizes transactions in an approximate order of least to most likely to be mined, but the linearization is not exactly opposite to the result of ancestor set-based sorting. This asymmetry is problematic:
    • What if the first transaction selected for eviction is also the transaction that would be selected first for mining?
    • Similarly, what if we have transactions that are “junk” (e.g. fall below the node’s configured -blockmintxfee and would thus never be selected for mining) but can’t be kicked out because they have a high descendant score? This mempool limitation necessitated the requirement that package transactions be above the minimum relay feerate (see PR #26933).
  • Due to similar limitations, Replace-by-Fee code cannot properly determine whether the proposed replacement(s) are more incentive compatible, so it uses approximations like individual feerate comparisons. These imperfect heuristics are a major cause of pinning problems and fee-bumping inefficiencies.
  • The main motivations for cluster mempool are to address these problems.

TxGraph

  • We have reviewed TxGraph basic functionality in a previous meeting. If TxGraph is new to you, the host recommends reading some of those notes and getting a feel for TxGraph by reviewing SimTxGraph in the fuzzer, which has similar functionality but a far simpler design:
    • It uses a single DepGraph to represent all transactions across all clusters, which means it doesn’t need to implement merges or track much information about the set of clusters.
    • It implements the staging level by creating a copy of main and deleting either the main or the staging to commit or abort staged changes. This approach is much more memory and CPU-intensive, but doesn’t need to track the differences between the levels.
  • A cluster mempool essentially keeps the entire mempool linearized at all times (lazily using TxGraph), which makes it easy to quickly determine a transaction’s linearization position (including what the highest and lowest transactions are) and compare the current mempool with a potential one.
  • PR #31444 adds TxGraph functionality for these purposes:
    • TxGraph adds a chunk index, a total ordering of all chunks in the graph across all clusters. A ChunkOrder comparator defines the order in which chunks would be mined.
    • BlockBuilder can just iterate through the chunks in order. Also, since a total orderering of all graph entries exists, we can get the “least likely to be mined” transaction without building a full mempool worth of block templates: simply take the last chunk in the index.
    • TxGraph exposes a BlockBuilder to iterate over the chunks from best to worst. BlockBuilder can Skip chunks (i.e. if they are too large to fit in the remaining block space), and those chunks’ descendants will be subsequently skipped as well.
    • TxGraph also exposes a GetWorstMainChunk method to identify the transactions that would be included in a block last.
  • The PR also adds a GetMainStagingDiagrams method to make it possible to compare the feerate diagram of the TxGraph with and without its staged changes.
    • This Delving post discusses the theory behind evaluating replacements using feerate diagrams.
    • Feerate diagram comparison is already used in package RBF. Package RBF is limited to clusters of size 2, which are easy to linearize even without cluster mempool.

Questions

  1. Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK? What was your review approach?
  2. Why are block building and eviction relevant to each other? Wouldn’t it be easier to evict transactions by the order they entered the mempool?
  3. True / false: if all clusters are singletons (have 1 transaction each), m_main_chunkindex would just be sorting the transactions by feerate.
  4. In English, using the approach in this PR, what is the algorithm for selecting transactions in order for block building? And for eviction?
  5. How would a client of BlockBuilder use it to build a block? When would GetCurrentChunk, Include, and Skip be called?
  6. What is the expected lifetime of BlockBuilder (is it similar to CTxMemPool’s or very different)?
  7. Can you create a BlockBuilder when staging exists? Can you build a block using the TxGraph’s state with its staged changes?
  8. Does BlockBuilder modify TxGraph (a “yes and no”-style answer is ok)?
  9. Why does BlockBuilder need to remember the set of skipped transactions? Why can it be represented as a set of Clusters?
  10. This commit adds new fields in data structures that need to point to each other: Entry now contains an iterator to the transaction’s ChunkData in m_main_chunkindex, and ChunkData refrence Entrys by their position in m_entries. In your review, how did you check that these pointers are always kept up-to-date?
  11. Conceptually, what are all the ways that an entry’s chunk index can change?
  12. In the ChunkOrder comparator, when cmp_feerate != 0, why can it be returned directly without comparing position within the cluster?
  13. m_main_chunkindex_observers indicates the existence of aBlockBuilder. Why is it an integer instead of a boolean?
  14. This call to GetClusterRefs gets the vector of Refs corresponding to the chunk. Why are the arguments ret.first and start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count correct?
  15. Continuing from the last question, why is std::reverse called on the result?
  16. What is GetMainStagingDiagrams useful for? Why might we exclude the clusters that are identical in main and staging?

Meeting Log

  117:00 <glozow> #startmeeting
  217:00 <corebot> glozow: Meeting started at 2025-04-23T17:00+0000
  317:00 <corebot> glozow: Current chairs: glozow
  417:00 <corebot> glozow: Useful commands: #action #info #idea #link #topic #motion #vote #close #endmeeting
  517:00 <corebot> glozow: See also: https://hcoop-meetbot.readthedocs.io/en/stable/
  617:00 <corebot> glozow: Participants should now identify themselves with '#here' or with an alias like '#here FirstLast'
  717:00 <sipa> hello!
  817:01 <glozow> Welcome to PR review club! Today is txgraph round 2, notes are available here: https://bitcoincore.reviews/31444
  917:01 <glozow> Did anybody have a chance to review the PR or the notes?
 1017:02 <abubakarsadiq> I am in the process of reviewing the PR
 1117:02 <monlovesmango> I did review the best that I could
 1217:03 <glozow> Nice! What is your review approach/
 1317:03 <glozow> ?*
 1417:03 <monlovesmango> read PR review club notes, read through pr desc, read/skimmed through the commits, tried to answer pr review club questions
 1517:04 <abubakarsadiq> I like the approach, I am reviewing it commit by commit and running the fuzz test locally with modifications
 1617:04 <pseudoramdom> Hi! First time here. Did glance over the PR and the notes. Getting caught up on Cluster Mempool
 1717:04 <glozow> pseudoramdom: welcome!
 1817:04 <sipa> pseudoramdom: welcome to the (review) club!
 1917:04 <glozow> Let's start with the questions
 2017:04 <monlovesmango> oh yeah I also am runnign fuzz tests but it is taking forever and this is my first time so not sure what i'm doing
 2117:04 <glozow> Why are block building and eviction relevant to each other? Wouldn’t it be easier to evict transactions by the order they entered the mempool?
 2217:05 <glozow> Feel free to ask any of your own questions, whenever you like
 2317:05 <sipa> monlovesmango: just in case you're not aware - running fuzz tests generally runs indefinitely; it keeps trying to make randomized changes to the input, and seeing if those trigger code coverage change and (even better) assertion failures
 2417:06 <monlovesmango> they are both looking for the same data (ording of tx clusters by fee rate), just opposite goals. one wants the top fee rates, the other the lowest fee rate.
 2517:06 <abubakarsadiq> glozow: you would want to evict the worst transaction in the mempool, i.e the one very unlikely to be mined soon.
 2617:06 <abubakarsadiq> As such when you use the order they enter mempool you will likely evict a transaction that might be mined in the next block.
 2717:06 <monlovesmango> it would be easier to evict by order they entered, but this can also evict your highest paying tx
 2817:07 <pseudoramdom> Does block building and eviction need to be opposites? or not necessary?
 2917:07 <sipa> monlovesmango: just a tiny nit, it's not sorting the *clusters* by feerate, but something else
 3017:07 <monlovesmango> sipa: haha ok thank you for letting me know! will have to look into how to run that properly
 3117:07 <monlovesmango> sipa: not clusters, chunks right?
 3217:07 <sipa> monlovesmango: bingo
 3317:07 <glozow> monlovesmango: abubakarsadiq: yes exactly
 3417:08 <sipa> pseudoramdom: today, they are very much not each other's opposite; the question is why we'd like them to be opposities
 3517:08 <glozow> to be fair, today, eviction is an approximation of the opposite of block building, just not an accurate one
 3617:09 <sipa> glozow: right, that's phrased more clearly
 3717:09 <glozow> True / false: if all clusters are singletons (have 1 transaction each), m_main_chunkindex would just be sorting the transactions by feerate
 3817:09 <monlovesmango> I want to say true
 3917:09 <abubakarsadiq> True :)
 4017:10 <pseudoramdom> I see. Yeah, it makes sense to have them accurately ordered. Block building can select the "best" end of the list. And eviction removes from the "worst" end
 4117:10 <glozow> Great :) can you explain why true?
 4217:10 <abubakarsadiq> If there is tie it it will compare the sequence of the clusters (individual tx)
 4317:11 <monlovesmango> if all clusters are singletons, then each cluster will have one chunk, and the linearization orders by chunk fee rate
 4417:11 <sipa> Bonus question: imagine two singleton clusters, with the same feerate, but they have different vsize. What can you say about their order?
 4517:11 <glozow> for the people following at home, we are looking at https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/txgraph.cpp#L290-L306
 4617:12 <abubakarsadiq> sipa: thats a tie?
 4717:12 <sipa> abubakarsadiq: depends on your perspective :p
 4817:12 <glozow> monlovesmango: yes!
 4917:13 <abubakarsadiq> We have two comparators yes.
 5017:13 <pseudoramdom> m_sequence?
 5117:15 <abubakarsadiq> sipa: I think the one with higher vsize will come first in the order since the sorting uses the > operator not `FeeRateCompare`?
 5217:15 <sipa> abubakarsadiq: no it uses FeeRateCompare, sorry - I thought it didn't, so this was a very trick question
 5317:16 <sipa> they'll be sorted by cluster creation order (m_sequence)
 5417:16 <Murch[m]> monlovesmango: You can just interrupt fuzz tests any time, or you can set a `max_total_time` or `runs` limit. You can ping me later if you want
 5517:16 <glozow> does `FeeRateCompare` return 0 for same feerate different vsize?
 5617:16 <glozow> I suppose yes
 5717:17 <sipa> glozow: yes, FeeFrac::operator<=> (and derived operator<, ... etc) treat equal feerate objects as sorted by increasing size
 5817:17 <glozow> So it tie-breaks by sequence
 5917:17 <abubakarsadiq> ah, I've mentioned that as well above. and changed my mind :)
 6017:17 <sipa> but FeeRateCompare specifically just compares the feerate itself
 6117:17 <monlovesmango> Murch: ok sounds good thank you!
 6217:18 <glozow> here: https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/util/feefrac.h#L113
 6317:18 <glozow> Next question
 6417:18 <Murch[m]> (or rather, we can discuss here in this channel after the meeting, I think others might also chime in or want to read it)
 6517:18 <glozow> In English, using the approach in this PR, what is the algorithm for selecting transactions in order for block building? And for eviction?
 6617:19 <abubakarsadiq> @monlovesmango: I run the fuzz test to verify my understand that if I make modification to a commit I expect an assertion I added to be triggered which always do.
 6717:19 <glozow> You can discuss here, it's about the PR
 6817:19 <monlovesmango> glozow: I can't process too much at a time and would rather focus on questions :)
 6917:20 <monlovesmango> abubakarsa: that is a good idea!
 7017:21 <Murch[m]> glozow: Repeatedly pick from all clusters the chunk with the highest available chunk feerate until the block is full
 7117:21 <sipa> glozow: is your question more about what BlockBuildImpl does internally, or how you imagine high-level code would use BlockBuilder based on its interface?
 7217:22 <sipa> (because the actual block building code isn't inside this PR)
 7317:22 <glozow> let's start with: how would higher level code use BlockBuilder?
 7417:22 <abubakarsadiq> In English?
 7517:22 <glozow> (Oh oops, that's the next question)
 7617:22 <pseudoramdom> @glozow picking chunks in the order of highest to lowest feerate
 7717:22 <Murch[m]> abubakarsadiq: Hausa would be confusing to most of us :~
 7817:22 <sipa> Murch[m]: :D
 7917:22 <abubakarsadiq> :P
 8017:24 <glozow> so let's start with: How would a client of BlockBuilder use it to build a block? When would GetCurrentChunk, Include, and Skip be called?
 8117:24 <monlovesmango> the algorithm for selecting transactions is to group related tx into clusters, and then linearize each cluster into chunks by their fee rate (this part i'm still fuzzy on), and then order all chunks by fee rate, and then pick chunks by decreasing fee rate (skipping chunks from clusters that have had a chunk skipped)
 8217:24 <glozow> monlovesmango: yes!
 8317:24 <monlovesmango> eviction is the same but starting from lowest fee rate
 8417:25 <abubakarsadiq> It's a linear algorithm that just get the current chunk recommended by block builder and include it when it satisfy a condition or skip it when it didn't
 8517:25 <abubakarsadiq> Not sure why a chunk will be skipped is it because of blockmintxfee?
 8617:25 <pseudoramdom> GetCurrentChunk would give the "best" chunk available?
 8717:25 <monlovesmango> i think if the cluster can't fit in a block?
 8817:26 <glozow> abubakarsadiq; can you think of a nother reason?
 8917:26 <glozow> monlovesmango; yes! but s/cluster/chunk
 9017:26 <glozow> What is the expected lifetime of BlockBuilder (is it similar to CTxMemPool’s or very different)?
 9117:26 <abubakarsadiq> thanks @monlovesmango
 9217:27 <monlovesmango> oh, but then why does it remember what to skip by cluster?
 9317:27 <glozow> monlovesmango: what happens if it doesn't?
 9417:27 <sipa> monlovesmango: once any chunk in a cluster has been skipped, nothing else from the cluster can't be included anymore, because the later transactions in the cluster may depend on transactions from the skipped chunk
 9517:27 <sipa> oh, sorry, spoiler
 9617:28 <abubakarsadiq> It is different, you should discard it immediately you are done building a block template.
 9717:28 <abubakarsadiq> TxGraph mutation methods can't be triggered when we have a block builder instance;
 9817:28 <monlovesmango> it will evaluate a chunk fromt he same cluster, which likely has missing dependencies! hah yeah what you said
 9917:28 <glozow> is it necessarily true that nothing else from the cluster can be included/
10017:28 <glozow> ?* ugh my shift key
10117:28 <sipa> glozow: you used it correctly for "English"
10217:28 <monlovesmango> glozow: cool that makes a lot of sense thanks!
10317:30 <abubakarsadiq> @sipa also if you skip a chunk in a cluster then that cluster linearization is incorrect yeah?
10417:30 <sipa> abubakarsadiq: maybe
10517:30 <monlovesmango> expected lifetime of BlockBuilder is short, as you can't make updates to txgraph if there is an observer right?
10617:30 <glozow> If you skip something, you could still include its sibling, no?
10717:31 <monlovesmango> should always be contained within CTxMemPool's lifetime
10817:31 <sipa> abubakarsadiq: depends what you mean with correct; it won't be a linearization for the full cluster anymore as some transactions will clearly be missing, but it may still be a valid linearization for what remains of the cluster after removing the skipped chunk
10917:31 <sipa> but BlockBuilderImpl (currently) doesn't try to reason about that because it's hard, and breaks the abstraction offered by linearizations/chunks
11017:32 <glozow> monlovesmango: yes!
11117:32 <sipa> so as soon as you skip anything of a cluster, it conservatively assumes nothing more from that cluster can be included
11217:32 <abubakarsadiq> then if it is valid and topological even with the skipped chunk, arent miners losing on fees by skipping everything in the cluster?
11317:32 <glozow> Why should `TxGraph` disallow changes while an observer exists?
11417:32 <sipa> abubakarsadiq: yes, it is neccessarily an approximation, like block building always is
11517:33 <sipa> abubakarsadiq: even the fact that we're only considering transactions in just a single order (the linearization) may result in small amounts of lost fees
11617:33 <sipa> or the fact that it's an eager algorithm to begin with
11717:34 <glozow> Can you create a BlockBuilder when staging exists? Can you build a block using the TxGraph’s state with its staged changes?
11817:35 <monlovesmango> bc everytime TxGraph is updated it will need re-linearization, which you don't want to do while something is actively observing the ordering
11917:35 <glozow> monlovesmango: exactly, it'll invalidate the chunk ordering that the observer is using
12017:35 <pseudoramdom> Why should `TxGraph` disallow changes while an observer exists? - the ordering mught change, possibility of missing a tx if the underlying graph changed?
12117:35 <abubakarsadiq> I think this case will likely happen towards the tail end of the block building process when we are close to the 4M `WU` limit.
12217:35 <abubakarsadiq> And also I think majority of tx are single clusters so it is fine?
12317:36 <monlovesmango> yes I think you can't create a BlockBuilder when staging exists, but you can't build a block using staging
12417:36 <sipa> monlovesmango: correct
12517:36 <monlovesmango> you can* create a BlockBuiler
12617:36 <sipa> oh, *can*, indeed
12717:36 <monlovesmango> haha
12817:37 <abubakarsadiq> @glozow: I think you can create a block builder while we have staging; but the recommended chunks will always be from main
12917:37 <glozow> yep yep
13017:37 <sipa> specifically, if you were making changes to main while a block builder exists, what would go wrong (ignoring the fact that it's not allowed, and might trigger Assume failes)
13117:38 <sipa> glozow: tell me to shut up if my extra questions make us move too slowly
13217:38 <monlovesmango> sipa: I would imagine things like double including a tx, or missing txs all together
13317:38 <glozow> sipa: all good
13417:39 <abubakarsadiq> @sipa; I think you will mess up with chunk order and invalidate the chunk index iterators?
13517:39 <sipa> abubakarsadiq: yep, that's it
13617:39 <sipa> the m_current_chunk iterator in BlockBuilderImpl may end up referring to a chunk index entry that no longer exists
13717:39 <sipa> which would be undefined behavior in C++
13817:39 <abubakarsadiq> yeah
13917:40 <monlovesmango> ok interesting. is there no way that it would point to an inaccurate index, but one that does exist?
14017:41 <sipa> monlovesmango: that is definitely possible, the point of undefined behavior is that it makes the behavior of the entire program undefined
14117:41 <sipa> so it might do that
14217:41 <glozow> Does `BlockBuilder` modify `TxGraph`?
14317:41 <sipa> it might also result in sending all your BTC away
14417:42 <abubakarsadiq> yep in constructor and destructor, while incrementing and decrementing block builder observer
14517:42 <monlovesmango> yes, it modifies observer count
14617:43 <sipa> might it make any other changes in the constructor?
14717:43 <abubakarsadiq> peeping at the constructor.......
14817:44 <monlovesmango> MakeAllAcceptable
14917:44 <sipa>
15017:44 <glozow> tada https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/txgraph.cpp#L2394
15117:45 <monlovesmango> which looks like it does ApplyDependencies, which will mutate txgraph
15217:45 <sipa> indeed
15317:45 <abubakarsadiq> I second :)
15417:45 <sipa> but it doesn't make any *observable* changes to the graph, as in, ApplyDependencies would have been called anyway, but possibly later
15517:45 <glozow> In some ways, "no," because the observable contents of the graph don't change - BlockBuilder doesn't remove transactions for exampl
15617:45 <abubakarsadiq> It might not though when their is nothing to apply
15717:47 <glozow> We already answered Q9 before, so moving on to Q10
15817:47 <glozow> looking at this commit https://github.com/bitcoin-core-review-club/bitcoin/commit/3429e9d79df1336cf1d0a61cb5f9bf028aa860b2
15917:47 <glozow> This commit adds new fields in data structures that need to point to each other: Entry now contains an iterator to the transaction’s ChunkData in m_main_chunkindex, and ChunkData refrence Entrys by their position in m_entries. In your review, how did you check that these pointers are always kept up-to-date?
16017:49 <monlovesmango> wasn't able to finish trying to answer this question, but I would imagine that you want to check all the places where txgraph mutates (ApplyDependencies and Relinearize)
16117:51 <glozow> Yeah, this is more of a "how do you review stuff?" question. I counted up the pointers and checked that there were assertions for them in `SanityCheck()`
16217:51 <glozow> Conceptually, what are all the ways that an entry’s chunk index can change?
16317:52 <pseudoramdom> when child tx is added/removed?
16417:52 <monlovesmango> glozow: can you explain more about SanityCheck()?
16517:52 <monlovesmango> when a tx is added or removed from that entry's cluster?
16617:53 <monlovesmango> i guess also if any tx is added/removed from mempool
16717:53 <pseudoramdom> oops, there could be more scenarios - maybe when feerate changes by RBF
16817:54 <glozow> monlovesmango: sure. generally I think that if pointer consistency is checked in `SanityCheck` and the fuzzer is good at finding possible (mis)uses of `TxGraph`, I can feel reasonably confident that `TxGraph` is updating those pointers correctly
16917:54 <sipa> pseudoramdom: that's the same thing... chunk feerates are a function of the linearization of a cluster, so anything that changes the linearization can affect it... and that includes RBF, but that is effectively through the cluster changes by adding/removing transactions from it
17017:55 <sipa> glozow: and as abubakarsadiq already mentioned, to get confidence that the fuzzer is indeed capable of finding such problems, it's often good to just try introducing a bug you expect SanityCheck (or other assertion) to find, and see if it actually does
17117:55 <pseudoramdom> gotcha yeah, thanks for claryfying. (For a sec I was wondering my messages were not going thr')
17217:55 <glozow> monlovesmango: pseudoramdom: yeah, any of the mutators can change the chunk index
17317:56 <sipa> also CommitStaging
17417:56 <pseudoramdom> can clusters merge?
17517:56 <monlovesmango> glozow: interesting thank you!
17617:56 <glozow> pseudoramdom: yep!
17717:56 <sipa> pseudoramdom: yes, by adding a dependency between transactions that are in distinct clusters
17817:56 <sipa> also, invoking the ~Ref destructor can change clusters
17917:56 <sipa> because it causes the corresponding transaction to be removed
18017:57 <glozow> In the ChunkOrder comparator, when cmp_feerate != 0, why can it be returned directly without comparing position within the cluster?
18117:58 <monlovesmango> bc fee rate is the first priority when determining order?
18217:58 <sipa> monlovesmango: but why is that ok?
18317:59 <glozow> monlovesmango: but why doesn't that violate any dependencies?
18418:00 <monlovesmango> bc we know they are from different clusters?
18518:00 <monlovesmango> hmm no
18618:00 <glozow> No, they can be within the same cluster
18718:01 <glozow> But chunks within a cluster are already in feerate order :)
18818:01 <glozow> Uh oh, we're already out of time!
18918:01 <glozow> We got through a lot today, thanks for coming everybody
19018:01 <glozow> #endmeeting