Skip to content

mempool: Add topological index, enforce consistency, updated reorg logic

Note: This is the second MR in the series, built on top of !1127 (merged). It is basically MR !1114 (closed), broken up into a multi-MR series.


Summary:

In order to ween ourselves off of the quadratic stats, we must first make a few changes. Future commits will remove the quadratic stats completely, but this is a critical step along the way.

  • Introduced a new topological index, based off a new property of CTxMemPoolEntry, entryId. This is a monotonically increasing and unique value (much how NodeId works in the network layer).
    • Reviewers: Initial implementation tried to use boost's sequenced indices but they are less convenient than this technique.
  • This index paves the way for us to remove the quadratic ancestor stats.
  • This index is now used for relay (and the ancestor score sorter which was used for this purpose was removed).
  • Reorg logic has been redone and simplified -- the performance gains from this are not yet fully realized but will be fully realized in future commits.
    • No more inconsistent mempools on reorg!
      • Invariants are never violated -- the mempool is consistent at all times.
    • To accomplish this we leverage the DisconnectedBlockTransactions pool as a topological sorter and we toss all mempool tx's into it on reorg, temporarily clearing the mempool.
    • Unwound blocks get added to this disconnected tx pool as before.
    • Unwinding farther than 10 blocks does not resurrect block tx's >10 blocks ago (same as before).
    • When unwinding is done, the tx's in the disconnect pool are added back to the mempool via the central and well tested ATMP code path, in topological order (care is taken to preserve any original entry timestamps and fee deltas that we know of).
    • Note that the disconnect pool has a default size limit that's 20x excessive block size, or 640MB (this behavior is unchanged by this MR).
    • Previously the mempool was being "updated for reorg" with each unwound block using a very expensive scan of the entire mempool, re-checking each tx against the tip. On very long reorgs this could get very costly. There is no need to do this for each unwound block, each time. It can be done once at the end "naturally" by calling ATMP. On top of having a performance benefit -- this has the benefit that code that checks tx sanity for mempool now lives in only 1 place, rather than two (note how we were able to delete a bunch of redundant code).
    • This change ensures:
      • That the topological index "entry id" is always correct
      • That the mempool is always consistent
      • Allowed us to delete expensive cleanup/reconciliation code that existed in CTxMemPool (which was used on reorg only).

Misc:

  • Implemented a "TODO" that was left in addUnchecked from Core.
  • A nit here and there
  • Updated comments

Test Plan:

  • ninja all check check-all
  • ninja bench_bitcoin && src/bench/bench_bitcoin -filter='Reorg.*' <-- you won't see too significant a speedup yet this commit, but in future commits the work we do here will ensure this gets faster.

For the cautiously paranoid:

  • Run a node and observe it run for a while. perhaps do some reorgs with tx's in the mempool, reorg back 5 or 10 blocks (invalidateblock), observe unwound block tx's end up in the mempool, do reconsiderblock, observe mempool clear of those tx's that were from unwound blocks, etc.
Edited by Calin Culianu

Merge request reports