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

Description

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

Summary:

In order to ween ourselves off of the quadratic stats, we must first
make a few changes.

- Introduce 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).
- 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 was removed).
- Reorg logic has been redone and simplified -- the performance gains
  from this are not yet fully realized but will be realized in future commits.
  - No more inconsistent mempools on reorg! 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
    - Invariants are never violated -- the mempool is consistent at all times.
    - Allowed us to delete expensive cleanup/reconciliation code that
      existed in `CTxMemPool` (which was used on reorg only).
- Implemented a "TODO" that was left in `addUnchecked` from Core.
- Updated comments

[..]

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.

Port of bchn#1128 and bchn#1158.

Depends on D13123.

This introduces 2 subtle changes that have not been catched by bchn due
to the lack of functional tests for these features:

The validation callback for tx removal is now called during a block disconnect (the mempool is cleared in DisconnectedBlock::importMemPool) which triggers new ZMQ messages. This is actually an improvement over the previous iteration because a transaction evicted from the mempool due to missing parent in the event of a reorg previously had no message. The test has been updated accordingly.
This removes an optimization that allowed the mempool descendant count to temporarily overflow during a reorg (see https://github.com/bitcoin/bitcoin/pull/21464#pullrequestreview-636049781). The mempool_updatefromblock.py test has been updated to increase the limit so that the test behavior remains the same but no overflow occurs(the descendant limit is not what is tested here).

Another difference is that we used to have a guard to prevent large
reorgs from causing an OOM due to the unbounded validation queue (see
D7213). However due to locking requirements we cannot apply this patch
anymore so it's left as a TODO.

Note that the mempool check() method has been updated to undo some of
the changes from D12173, since this diff breaks the ordering assumption.

Test Plan: