HomePhabricator

mempool & mining: Use the topological ordering to break ties

Description

mempool & mining: Use the topological ordering to break ties

Summary:

This MR affects the "modified feerate" sorter used by mining code.

This MR makes it so that "ties" between entries are "broken" by their
topological ordering, such that parents come before children if their
fee rates are identical.  This allows mining code to be faster so that
it doesn't have to backtrack as much in CreateNewBlock.

Previous to this MR, GetTime() was used for this purpose which is a
rough approximation of topological ordering, but is not guaranteed for
this purpose (reorgs make it so that parents may have a later time than
their children in the case of resurrected block tx's showing up in the
mempool again!).

The original intent behind the mining code that we merged in !1078 and
!1079 was to sort by fee, but then by parent->child ordering, hence the
tie-breaker logic.

Using GetEntryId() for this purpose, rather than GetTime() accomplishes
this intent in a guaranteed way.

Port of bchn#1147.

Depends on D13141.

Test Plan:

ninja all check-all

Reviewers: #bitcoin_abc, PiRK

Reviewed By: #bitcoin_abc, PiRK

Differential Revision: https://reviews.bitcoinabc.org/D13147

Details

Provenance
CCulianuAuthored on Mar 29 2021, 10:55
FabienCommitted on Feb 21 2023, 10:36
FabienPushed on Feb 21 2023, 10:36
Reviewer
Restricted Project
Differential Revision
D13147: mempool & mining: Use the topological ordering to break ties
Parents
rABC12985ae1b027: mempool: Remove ancestor/descendant related stats from RPC
Branches
Unknown
Tags
Unknown