Limited and sorted mempool #6449

1. 
   morcos commented at 7:32 pm on July 16, 2015: member

   Here are a couple of suggested improvements to #6421.

   Feel free to cherry-pick back into that pull if you want to maintain it. Or if you’d like this pull to take over, that’s fine too..

   I built them on a rebased #6421 and I lost a few comment changes that differed between that pull’s NO_QT_KEYWORDS commit and the one in master.

2. TxMemPool: Change mapTx to a boost::multi_index_container

   Indexes on:
   - Tx Hash
   - Fee Rate (fee-per-kb)

   5850a750da
3. Move orphan tx handling to a separate log class d223671fb3
4. Implement on-the-fly mempool size limitation. afba7994e4
5. Make StageTrimToSize aware of any minimum relay fee.

   StageTrimToSize will make several attempts to find a set of transactions it can evict from the mempool to make room for the new transaction.  It should be aware of any required minimum relay fee that needs to be paid for by the new transaction after accounting for the fees of the deleted transactions.

   56b67ba193
6. Modify StageTrimToSize logic

   Always be willing to try at least 5 different starting transactions so hitting a long chain you can't evict on your first try doesn't eliminate any chance of success.

   cea215cc28
7. Add a fast check to make sure tx could pay for some eviction bb4657a675
8. 
   morcos commented at 11:48 am on July 17, 2015: member

   Unfortunately this PR doesn’t actually improve performance. cea215c appears to be the culprit, and with some tweaks to allow more fails it can do better than #6421 but not so much better that I think this is the right approach. Some very high fee rate transactions up to 400k satoshis/kB get rejected by both pulls. Once you start cleaning stuff out from the mempool, there is a tendency for the bottom to become occupied by large transactions with very low fee rate. Small transactions then have no chance of evicting these even with much higher fee rates because they fail the total fee test. I believe some combination of one of these approaches is necessary:

   1. Allowing high fee rate transactions to exceed the mempool cap via a multiplier based on size.
   2. Aggregating the fees of small high fee rate transactions to collectively evict large low fee rate transactions
   3. Attempting to evict by lowest total fee transactions as well as lowest fee rate.
   4. Using a packaging approach which combines dependent chains of transactions for a total feerate (or fee) to sort on.

   Closing until something is actually materially better.

9. morcos closed this on Jul 17, 2015

   ---

10. DrahtBot locked this on Sep 8, 2021

Contributors
morcos