Mempool: Add tracking of ancestor packages #7594

pull sdaftuar wants to merge 6 commits into bitcoin:master from sdaftuar:ancestor-tracking changing 4 files +302 −124
  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 cross-referenced this on Feb 25, 2016 from issue Mining: Select transactions using feerate-with-ancestors by sdaftuar
  6. sdaftuar cross-referenced this on Mar 1, 2016 from issue Order CTxMemPool::queryHashes result by feerate including descendents. by pstratem
  7. sdaftuar force-pushed on Mar 5, 2016
  8. 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...

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

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

    Untested ACK

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

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

  13. CTxMemPool::removeForBlock now uses RemoveStaged 7659438a63
  14. Rename CTxMemPool::remove -> removeRecursive
    remove is no longer called non-recursively, so simplify the logic
and eliminate an unnecessary parameter
    5de2baa138
  15. 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
  16. 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
  17. Add ancestor feerate index to mempool e2eeb5dda7
  18. Check all ancestor state in CTxMemPool::check() ce019bf90f
  19. sdaftuar force-pushed on Mar 14, 2016
  20. sdaftuar commented at 5:15 PM on March 14, 2016: member

    Needed rebase.

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

  22. sipa commented at 4:46 PM on March 16, 2016: member

    ACK.

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

  23. laanwj merged this on Mar 17, 2016
  24. laanwj closed this on Mar 17, 2016
  25. laanwj referenced this in commit 01f4267623 on Mar 17, 2016
  26. laanwj commented at 1:22 PM on March 17, 2016: member

    utACK ce019bf

  27. sdaftuar cross-referenced this on May 17, 2016 from issue [RPC] Expose ancestor/descendant information over RPC by sdaftuar
  28. rebroad cross-referenced this on Aug 25, 2016 from issue nSequence-based Full-RBF opt-in by petertodd
  29. kyuupichan cross-referenced this on Apr 8, 2017 from issue [backport] [mempool] tracking of ancestor packages by kyuupichan
  30. madeo cross-referenced this on May 10, 2017 from issue [doc] Removing comments about dirty entries on txmempool by madeo
  31. codablock referenced this in commit b146718417 on Sep 16, 2017
  32. codablock referenced this in commit 869465fb87 on Sep 19, 2017
  33. codablock referenced this in commit aae430ac3a on Dec 9, 2017
  34. codablock referenced this in commit 29d2633897 on Dec 19, 2017
  35. MarkLTZ referenced this in commit c2255fd83d on Apr 28, 2019
  36. furszy cross-referenced this on Jul 3, 2020 from issue Up to CTransactionRef point back ports to do list. by furszy
  37. furszy cross-referenced this on Dec 31, 2020 from issue [NET] Inv, mempool and validation improvements by furszy
  38. furszy referenced this in commit 1f010c0969 on Jan 23, 2021
  39. bitcoin locked this on Sep 8, 2021
Contributors
sdaftuarsipadgenr8laanwj
Labels
Mempool
Linked (view graph)
#6871 nSequence-based Full-RBF opt-in#7292 [RPC] Expose ancestor/descendant information over RPC#7539 Add tags to mempool's mapTx indices#7600 Mining: Select transactions using feerate-with-ancestors#7629 Order CTxMemPool::queryHashes result by feerate including descendents.#10380 [doc] Removing comments about dirty entries on txmempool#23121 [policy] check ancestor feerate in RBF, remove BIP125 Rule2
github-metadata-mirror

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: 2026-05-20 06:55 UTC