Cluster mempool tracking issue #30289

1. 
   sipa commented at 1:21 pm on June 14, 2024: member

   What to review next:

   • #31363

   ---

   High-level structure:

    0graph BT;
    1
    2vecdeque["VecDeque"];
    3feefrac["FeeFrac"];
    4bitset["BitSet<N>"];
    5depgraph["DepGraph"];
    6txgraph["TxGraph"];
    7changeset["Mempool changesets"];
    8clm["Cluster mempool"];
    9
   10depgraph --> feefrac;
   11depgraph --> bitset;
   12depgraph --> vecdeque;
   13txgraph --> depgraph;
   14clm --> txgraph;
   15clm --> changeset;
   

   ---

   Plan:

   • Lowest level: generic utilities:
     • #29242 FeeFrac type
       • #30535 Add FeeFrac::EvaluateFee
     • #30160 BitSet type
     • #30161 VecDeque type
   • Low level: operations on DepGraph type (dependencies/linearizations for a single cluster)
     • #30126 Base linearization algorithm
       • #30605 Split tests from tests-of-tests
       • #30857 Extend DepGraph functionality
     • #30285 Merging and postprocessing of linearizations
     • #30286 Optimized candidate search
   • Intermediate level: operations on TxGraph type (dependencies/linearizations for the entire mempool)
     • #31363 TxGraph basics
     • #31444 TxGraph mining/eviction
     • #31553 TxGraph reorgs
     • TxGraph memory usage logic: TODO
   • High level: changes to mempool/validation
     • #31122 Changesets for mempool
     • #28676 Full implementation
2. glozow referenced this in commit 37bd70a225 on Jul 26, 2024
3. glozow referenced this in commit bba01ba18d on Aug 5, 2024
4. glozow referenced this in commit c38e9993de on Sep 16, 2024
5. glozow referenced this in commit 489e5aa3a2 on Oct 10, 2024
6. glozow referenced this in commit f34fe0806a on Nov 20, 2024
7. 
   summraznboi commented at 8:00 am on December 4, 2024: none

   Wow, no ancestor/descendant limit would be great for unblocking UX hurdles in creating transactions! (Commenting to watch, also curious how someone like myself could help out here).

   Edit: I see, this is going to be replaced with a cluster size limitation instead. What’s the order of magnitude in which this number could be increased up to?

8. 
   sipa commented at 3:04 pm on December 12, 2024: member

   @summraznboi We are thinking of a cluster size limit of 50 or 64, depending on benchmarks when the full code is done. The limit is set by how fast we can run the basic cluster linearization algorithm (ancestor sort, chunking, post-processing, …) quickly enough to run it at transaction relay time (taking into account that a single transaction may affect many clusters).

Contributors
sipa summraznboi