Mempool: Add tracking of ancestor packages #7594

1. 
   sdaftuar commented at 10:30 pm on February 24, 2016: member

   This implements caching of count, size, (modified) fee, and sigops of each mempool entry with its unconfirmed ancestors.

   This is in preparation for adding support to CreateNewBlock for transaction selection based on fees-with-ancestors, for which I’ll open another pull request soon.

   Note that in order to keep accurate ancestor state, CTxMemPool::removeForBlock has to walk the descendants of each in-block transaction (so that it’s ancestor state can be reflected for the ancestor which was confirmed). The performance hit appears to be relatively insignificant (at least on the mempools I was looking at from 10/1/15 - 10/10/15): it amounted to an average 0.3ms, from 10.9ms to 11.2ms, on my almost 2 year old hardware. Moreover, I think if this performance was ever an issue we could do a bigger re-engineering of ConnectBlock so that block relay isn’t held up by updating the mempool state.

   I would like to also expose this ancestor information via RPC, but will hold off until after #7292, so I might do that in a future PR rather than in this one. Also, the unit tests in this PR will be improved somewhat after #7539.

2. jonasschnelli added the label Mempool on Feb 25, 2016
3. sdaftuar force-pushed on Feb 25, 2016
4. sdaftuar force-pushed on Feb 25, 2016
5. sdaftuar force-pushed on Mar 5, 2016
6. 
   sdaftuar commented at 11:58 am on March 5, 2016: member

   Needed rebase. @sipa Regarding your comment about adding exact ancestor state checking to CTxMemPool::check() (https://github.com/bitcoin/bitcoin/pull/7600#issuecomment-192487265), my only concern with adding that was slowing down the test suite to a potentially unacceptable level. I’m timing that now…
7. 
   sdaftuar commented at 8:55 pm on March 8, 2016: member

   I tried adding complete ancestor-state checks to CTxMemPool::check() and timed the rpc tests (with -extended), and I saw negligible difference in times (<5%), so I’ve gone ahead and pushed that commit here.

   I do expect this to be substantially slower, but I assume that since we can now run on mainnet with -checkmempool=<N> with N > 1 that we can just use bigger values of N if necessary.

8. 
   sipa commented at 8:38 pm on March 9, 2016: member

   Untested ACK
9. 
   dgenr8 commented at 2:25 am on March 12, 2016: contributor

   In CalculateMempoolAncestors, how about wrapping the limit checks in if (fSearchForParents)? These checks should be unnecessary if entry is already in the mempool.
10. 
    sdaftuar commented at 4:09 pm on March 14, 2016: member

    @dgenr8 I agree that refactoring that code would make that function clearer, but as the content of CalculateMemPoolAncestors() hasn’t changed in this PR, I’d like to defer that refactor to a separate pull, to avoid making this PR any more difficult to review than it already is.
11. CTxMemPool::removeForBlock now uses RemoveStaged 7659438a63
12. Rename CTxMemPool::remove -> removeRecursive

    remove is no longer called non-recursively, so simplify the logic
    and eliminate an unnecessary parameter

    5de2baa138
13. Remove work limit in UpdateForDescendants()

    The work limit served to prevent the descendant walking algorithm from doing
    too much work by marking the parent transaction as dirty.  However to implement
    ancestor tracking, it's not possible to similarly mark those descendant
    transactions as dirty without having to calculate them to begin with.
    
    This commit removes the work limit altogether.  With appropriate
    chain limits (-limitdescendantcount) the concern about doing too much
    work inside this function should be mitigated.

    76a76321d2
14. Add ancestor tracking to mempool

    This implements caching of ancestor state to each mempool entry, similar to
    descendant tracking, but also including caching sigops-with-ancestors (as that
    metric will be helpful to future code that implements better transaction
    selection in CreatenewBlock).

    72abd2ce3c
15. Add ancestor feerate index to mempool e2eeb5dda7
16. Check all ancestor state in CTxMemPool::check() ce019bf90f
17. sdaftuar force-pushed on Mar 14, 2016
18. 
    sdaftuar commented at 5:15 pm on March 14, 2016: member

    Needed rebase.
19. 
    dgenr8 commented at 5:26 pm on March 14, 2016: contributor

    Ok. Looking closer I see there’s no real performance hit. I thought otherwise at first glance.
20. 
    sipa commented at 4:46 pm on March 16, 2016: member

    ACK.

    Tested by running with -checkmempool=400 for a few days.

21. laanwj merged this on Mar 17, 2016
22. laanwj closed this on Mar 17, 2016

    ---

23. laanwj referenced this in commit 01f4267623 on Mar 17, 2016
24. 
    laanwj commented at 1:22 pm on March 17, 2016: member

    utACK ce019bf
25. codablock referenced this in commit b146718417 on Sep 16, 2017
26. codablock referenced this in commit 869465fb87 on Sep 19, 2017
27. codablock referenced this in commit aae430ac3a on Dec 9, 2017
28. codablock referenced this in commit 29d2633897 on Dec 19, 2017
29. MarkLTZ referenced this in commit c2255fd83d on Apr 28, 2019
30. furszy referenced this in commit 1f010c0969 on Jan 23, 2021
31. DrahtBot locked this on Sep 8, 2021

Contributors
sdaftuar sipa dgenr8 laanwj

Labels
Mempool