Super Duper MemPool Limiter

morcos commented at 11:08 pm on July 23, 2015: member

@sipa @sdaftuar @jtimon @petertodd OK, this is the best combination of approaches I could put together.

I took #6455 and I removed the floating relay fee commit. I really like that idea, but it needs to be much slower acting I think and not subject to potential abuse. That can be a later improvement.

I added 3 things:

Reserved space between the soft cap and hard cap. The soft cap is currently set to 70% of the hard cap. Once the soft cap is hit, you first try to evict as in 6455, but if you fail, you have another chance to get in if you are still under the hard cap. There are 10 “rate zones” between the hard cap and soft cap and the effective minRelayRate to get into the mempool doubles for each additional zone.
Any required minRelayFee for your transaction alone is considered inside the StageTrimToSize loop.
Periodically (once a second) we use the knowledge that surplus fees over the minRelayRate must have been paid if the size of the mempool is over the soft cap. We use these fees in aggregate to try to trim from the bottom of the mempool. This allows us to aggregate many small high fee transactions to evict a low paying large transaction or long chain.

The reject rates in my test setup have dropped to 0.3% for 30k feerate tx’s and 0.05% for 60k feerate tx’s. (See other results in #6455).

I made an attempt to tweak the looping parameters in StageTrimToSize to something that I think made sense, but with the contrived test setup, and only one set of simulation data, they are probably best evaluated on the basis of intuition and not relying entirely on the resulting rejection rates.

It turns out the slowest part of StageTrimToSize was GetRand() by a long shot, so I hacked it out, but I’m sure @sipa will want to replace my hack with something nicer.

The code works as is, but could still use some work, but I think its time to get more eyes on this suggestion for a plan forward.

in src/main.cpp: in 6b4af964ff outdated

876@@ -852,6 +877,12 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
877                                    hash.ToString(), nSigOps, MAX_STANDARD_TX_SIGOPS),
878                              REJECT_NONSTANDARD, "bad-txns-too-many-sigops");
879 
880+        // Expire old transactions before trying to replace low-priority ones.
881+        int expired = pool.Expire(GetTime() - GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY) * 60 * 60);

jtimon commented at 11:16 pm on July 23, 2015:

Can’t - GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY) * 60 * 60 be inside pool.Expire?, it may become an attribute of the txmempool in the future or something.

sipa commented at 2:39 pm on July 27, 2015:

I would prefer not doing that, and keeping CTxMempool as much as possible a dumb data structure - the decisions about what happens to it (policy?) should stay out of it, IMHO.

EDIT: We’re already failing at that pretty badly anyway, it seems, with the feerate index and the trim code inside CTxMempool. Too bad, but disregard this comment.

jtimon commented at 10:37 am on July 29, 2015:

It is just as easy to move things from txmempool to the policy dir than it is from main (if not easier, given that main is always the part with more development conflicts [unrelated things in theory conflict in code there]). But whatever, I guess it will be a new global in main…

in src/main.cpp: in 6b4af964ff outdated

921+        size_t hardcap = GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000;
922+        size_t capstep = (hardcap - softcap) / 10;
923+        std::set<uint256> stagedelete;
924+        CAmount nFeesDeleted = 0;
925+
926+        if (!mempool.StageTrimToSize(softcap, entry, stagedelete, nFeesRequired, nFeesDeleted)) {

jtimon commented at 11:18 pm on July 23, 2015:

s/mempool/pool don’t use the global when you have the parameter

sipa commented at 2:50 pm on July 27, 2015:

Agree.

sipa commented at 3:53 pm on July 27, 2015:

@morcos If this method call returns false, do we need to wipe stagedelete/nFeesDeleted, or are they guaranteed to be empty/zero?

morcos commented at 4:18 pm on July 27, 2015:

@sipa Neither is the answer. Perhaps it needs commenting though. If the transaction is accepted into the reserve space and stagedelete is non-empty then it is both safe and desirable to evict any transactions that were staged. If the transaction is not accepted into the reserve space, then as before we return failure from ATMP before we have a chance to evict anything.

The one slight caveat is in the case where you pass entry into the reserve space, but then you fail the rate limiter code directly below it. In that case, it probably wasn’t very fair that your feesDeleted were causing you to be counted as a free transaction. It’s overly conservative and rare behavior though. I was planning on suggesting a fix but I wanted to see if there were any thoughts on the free relay code remaining in place here before I complicated it. The suggested fix is that if the transaction is entering the mempool via the reserve space, and then it fails the rate limiter code, you let it in anyway but just wipe stagedelete. Note that if stagedelete were empty then the tx by definition wouldn’t have been subject to the rate limit test because it has a multiple of the minRelayFee.

sipa commented at 4:22 pm on July 27, 2015:

ACK, understood. That seems fine, but could probably use a comment.

in src/main.cpp: in 6b4af964ff outdated

980@@ -921,8 +981,38 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
981             return error("AcceptToMemoryPool: BUG! PLEASE REPORT THIS! ConnectInputs failed against MANDATORY but not STANDARD flags %s", hash.ToString());
982         }
983 
984+        // Make actually space

jtimon commented at 11:29 pm on July 23, 2015:

Can’t all this code around pool.addUnchecked be moved to a new mempool method that internally calls pool.addUnchecked ? You could go further. stagedelete and nFeesDeleted could just be ctxmempool attributes so that you don’t need to pass it to pool.RemoveStagedAndAddUnchecked (or whatever you want to call the method) and pool.StageTrimToSize (or whatever you want to call the method)

sipa commented at 2:53 pm on July 27, 2015:

Storing attributes inside CTxMempool just to avoid passing them around seems ugly. It would be incompatible with some multithreaded modifications, for example.

A cleaner way to do this is having a separate TxMempoolStagedChange class for example that is calculated from an add/delete, kept by AcceptToMemoryPool during validation, and finally applied to the mempool or thrown away.

jtimon commented at 10:42 am on July 29, 2015:

With or without attributes, this code could be just a single-line call to a method in the pool (for example, a modified version of addUnchecked):

 0+        // Delete staged transactions to actually make space in mempool
 1+        if (!stagedelete.empty()) {
 2+            LogPrint("mempool", "Removing %u transactions (%d fees) from the mempool to make space for %s\n", stagedelete.size(), nFeesDeleted, tx.GetHash().ToString());
 3+            pool.RemoveStaged(stagedelete);
 4+        }
 5+
 6         // Store transaction in memory
 7         pool.addUnchecked(hash, entry, !IsInitialBlockDownload());
 8+
 9+        // Try to use excess relay fees paid by txs above the soft cap to trim in aggregate
10+        int64_t timeNow = GetTime();
11+        size_t curUsage = pool.DynamicMemoryUsage();
12+        size_t trimGoal = 1000000; //Try to trim up to 1MB worth of transactions at a time
13+        if (curUsage > softcap + trimGoal && timeNow > lastSurplusTrimTime) {
14+            // Require at least 1M at highest fee rate we'll try to trim at, and try to trim 1MB
15+            lastSurplusTrimTime = timeNow;
16+            int rateZone = (curUsage - softcap - trimGoal)/capstep + 1;
17+            int rateMultForTrim = 1 << rateZone;
18+            std::set<uint256> stageTrimDelete;
19+            if (pool.SurplusTrim(rateMultForTrim-1, minRelayTxFee, trimGoal, stageTrimDelete)) {
20+                size_t oldUsage = curUsage;
21+                size_t txsToDelete = stageTrimDelete.size();
22+                pool.RemoveStaged(stageTrimDelete);
23+                curUsage = pool.DynamicMemoryUsage();
24+                LogPrint("mempool", "Removing %u transactions (%ld total usage) using periodic trim from reserve size\n", txsToDelete, oldUsage - curUsage);
25+            }
26+        }

in src/main.cpp: in 6b4af964ff outdated

898-                             REJECT_INSUFFICIENTFEE, "insufficient fee");
899-
900-        // Require that free transactions have sufficient priority to be mined in the next block.
901-        if (GetBoolArg("-relaypriority", true) && nFees < ::minRelayTxFee.GetFee(nSize) && !AllowFree(view.GetPriority(tx, chainActive.Height() + 1))) {
902-            return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "insufficient priority");
903+        // The fees required to accept this transaction start with the fees required to accept it on its own

jtimon commented at 11:51 pm on July 23, 2015:

Can’t all this new code be part of mempool.StageTrimToSize ? In fact, I would go further and take anything that depends on nFeesDeleted to txmempool as well (including csFreeLimiter GetBoolArg("-relaypriority", true) and GetMinRelayFee). I would also move https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L785 there and have all mempool-replacement-related things in one place: txmempool. We could also move some things directly to policy/fees but I’m not going to ask for that much.

I’m sorry but I won’t push my nits as branches with fixup! commits anymore on this subject. I guess I’ll have to wait the ages that will take to move the code later and accept that nobody else but me cares about the movement being better-than-free right now. I won’t miss the chance to beg you though. Please, try some of my movement suggestions and if takes you too long to adapt the parameter too recompile or you don’t like what my suggestions are doing to the number of parameters in pool.StageTrimToSize just stop it. And I guess I can just add/maintain all those things in my tomove list. It seems I’m the only one that doesn’t love the fact that most of our changes conflict with each other in main.cpp. But I understand, moving things out of main so that things don’t need to conflict and don’t need to be prioritized is not a priority. @sipa I must be getting something wrong or I’ve been communicating poorly around this. Maybe code doesn’t talk as much as I thought after all.

sipa commented at 2:43 pm on July 27, 2015:

@jtimon Let’s first find a solution to the problem at hand.

Code movement that goes into the master branch conflicts with everything, so complicates changes that we want in backports too.

jtimon commented at 10:46 am on July 29, 2015:

Ok, moving existing code is one thing. But putting new code in txmempool instead of main doesn’t make things harder to backport. It feels like I’m always trying to control main.cpp’s diet, but when I look somewhere else everybody gives him candy in high quantity. If we keep doing this, main.cpp is always going to be fat no matter how many things I move out of it.

morcos force-pushed on Jul 24, 2015

laanwj added the label Mempool on Jul 24, 2015

laanwj commented at 7:56 am on July 24, 2015: member

re: GetRand slowness, wouldn’t insecure_rand() be good enough here? If you need both fast and cryptographic randomness you’d have to wait for #5885

sipa commented at 5:53 pm on July 24, 2015: member

I like the approach; I’ll review the code in detail soon.

dgenr8 commented at 4:26 pm on July 25, 2015: contributor

The idea that a transaction must be “paid for” when evicted by an unrelated transaction is mistaken. It creates zero incentive for the evicted author to pay more fees in the future. He got what he wanted – his tx was relayed.

If the decision does not affect the cost, the cost should not affect the decision.

sipa commented at 4:35 pm on July 25, 2015: member

The assumption is that when a transaction is evicted, it won’t be mined, thus it won’t have paid anything at all.

dgenr8 commented at 4:55 pm on July 25, 2015: contributor

@sipa In that case, it also received no benefit.

sipa commented at 5:09 pm on July 25, 2015: member

It got relayed, which has network costs.

The purpose of this payment requirement is to prevent someone from spamming the network by constantly replacing the lowest priority one, and only paying once.

dgenr8 commented at 5:24 pm on July 25, 2015: contributor

For DoS protection, all that’s needed is (new fee/kb) - (old fee/kb) >= (minimum fee/kb).

sipa commented at 2:36 pm on July 27, 2015: member

@dgenr8 No, that would let a small transaction erase a large transaction, making space for several new transactions to be cheaply relayed.

in src/main.cpp: in c4d87ae115 outdated

923+        std::set<uint256> stagedelete;
924+        CAmount nFeesDeleted = 0;
925+
926+        if (!mempool.StageTrimToSize(softcap, entry, stagedelete, nFeesRequired, nFeesDeleted)) {
927+            size_t expsize = mempool.DynamicMemoryUsage() + mempool.GuessDynamicMemoryUsage(entry);
928+            if (expsize > hardcap)

sipa commented at 2:55 pm on July 27, 2015:

Please use { } around the then block.

morcos commented at 8:18 pm on July 27, 2015:

No objection to changing, but just want to understand what the style request is related to this. All then blocks should have braces or only because the else block is multi-line? A single-line then block without braces appears as example code in developer-notes.md.

sipa commented at 8:25 pm on July 27, 2015:

Oh, I thought we changed that. Never mind then.

I personally dislike those, as they easily lead to mistakes when merging different patches (see the OSX SSL bug that was likely the result of it), but I shouldn’t ask that as long as our notes use it.

jtimon commented at 10:03 am on July 29, 2015:

The fact is that braces are not necessary in our clang style. And btw, when they’re used, the shouldn’t be in the next line but in the same line as the if/for/while. I’m happy changing the style, but that’s in clang-format.

in src/txmempool.cpp: in c4d87ae115 outdated

495+            // If the transaction is already staged for deletion, we know its descendants are already processed, so skip it.
496+            it++;
497+            continue;
498+        }
499+        if ((double)it->GetFee() * sizeToUse > (double)feeToUse * it->GetTxSize()) {
500+            // If the transaction's feerate is worse than what we're looking for, we have processed everything in the mempool

sipa commented at 3:08 pm on July 27, 2015:

This comment is technically no longer true since the majority of transactions are being skipped. Maybe the code should be removed altogether now, or does it still offer a benefit? In any case, the comment needs addressing.

morcos commented at 3:20 pm on July 27, 2015:

Agree the comment needs changing, but the check is still valuable. No reason to continue checking further transactions at this point, even if we haven’t used up all of our fails.

in src/txmempool.cpp: in c4d87ae115 outdated

552+            nFeesRemoved += nowfee;
553+            usageRemoved += nowusage;
554+        } else {
555+            fails++;
556+            if (fails > failmax) {
557+                // Bail out after traversing 32 transactions that are not acceptable.

sipa commented at 3:10 pm on July 27, 2015:

Comment should say 10, not 32 - or just refer to the failmax variable.

morcos commented at 3:40 pm on July 27, 2015: member

@jtimon I’d like to add some sanity checking for the command line arguments that are passed in. I assume that should go in init.cpp? Where is the appropriate place for me to store variables such as hard cap, mempool expiry time, etc.. so they aren’t recalculated every time.

in src/txmempool.cpp: in c4d87ae115 outdated

476+                             std::set<uint256>& stage, CAmount &nFeesRemoved, bool mustTrimAllSize) {
477+    size_t usageRemoved = 0;
478+    indexed_transaction_set::nth_index<1>::type::reverse_iterator it = mapTx.get<1>().rbegin();
479+    int fails = 0; // Number of mempool transactions iterated over that were not included in the stage.
480+    int itertotal = 0;
481+    int iterextra = mustTrimAllSize ? 10 : 100; //Allow many more iterations to find large size during SurplusTrim

sipa commented at 4:25 pm on July 27, 2015:

Do you mind turning these into arguments, that get passed from the 2 callsites instead?

sipa commented at 4:28 pm on July 27, 2015: member

Needs rebase.

dgenr8 commented at 6:31 pm on July 27, 2015: contributor

that would let a small transaction erase a large transaction, making space for several new transactions to be cheaply relayed @sipa That is good. You don’t want a 500KB spam-monster tx paying (minimum fee/kb) to require a regular-sized tx to pay 1001 * (minimum fee/kb) to dislodge it. Bad guy could get 1000 little txes relayed anyway by sending them first – the pay-for-evicted rule creates a race to be first or pay double.

sdaftuar commented at 6:37 pm on July 27, 2015: member

@dgenr8 While that is a potential problem for optimizing what gets into the mempool, note that this PR is attempting to provide a solution so that many small transactions can be used to evict large transaction packages.

morcos commented at 7:51 pm on July 27, 2015: member

@dgenr8 This conversation has been spread over a couple of PR’s and IRC, so I apologize if I’m repeating a prior argument, but I think it would be good to explain the reasoning behind the logic in this pull.

Prior to limiting the mempool (or having RBF implemented), we had protection against bandwidth spamming attacks by requiring all transactions that were relayed to be accepted into the mempool and have either fee or priority. Since those transactions are now in the mempool and can’t be recalled, those fees are now at risk for being consumed by being included in a block. This pull isn’t meant to provide some new protection against that attack, but is only meant to protect against OOM attacks by ever expanding mempools. However, it must be sure not to break that pre-existing protection.

Once we create a way for transactions to be removed from the mempool, we have to realize that the fees placed on those transactions are no longer at risk. The approach we’ve been using is to say that (modulo transactions that have already been mined) the mempool must contain enough fees to pay for the relay cost of all transactions that have been historically broadcast whether they are still in the mempool or not. What this prevents is someone replacing or evicting their own transactions “cheaply” and thereby achieving free relay of their original transactions. The fact that there might be a race to get into the mempool before it fills up is a slight aberration that occurs as a one off. We still need a mechanism by which to adjust the minimum relay fee over time in the event that it is too small to dissuade spam.

Your concern about a monster transaction of low fees preventing a small transaction from getting in the mempool is addressed in 4 separate ways in this pull.

Multiple attempts are made to evict transactions, so being unlucky and trying against one large transaction is insufficient to block you.
Some portion of the mempool space is reserved for higher and higher fee transactions. That space is not cheaply fillable with spam and should serve to act as a temporarily higher min relay rate which will keep the relay path open for high fee paying tx’s (large or small).
Any tx’s occupying the reserve space are periodically looked at in aggregate and used to remove large tx’s or chains of tx’s from the bottom of the mempool that would otherwise be unevictable.
There is a time based eviction mechanism as a last fall back.

No doubt further improvements are possible, but I think this is a good step in the right direction.

dgenr8 commented at 0:43 am on July 28, 2015: contributor

@morcos Thanks. I feel the capping part of this pull is too complex, and could be simplifed (a little) by removing the “pay for eviction” idea, which has no good incentive effect.

The person paid is the miner, who doesn’t need to be paid ~double to mine the evictor tx. The person who pays is the unlucky evictor. Evictee gets a chance at cheap fees, and others who come after eviction could pay even less, since there might then be extra space for them.

The case where evictor == evictee could be handled explicitly, if it were actually possible to target this kind of replacement with all the factors that affect the selection of the evictees, such as propagation variation, node start time variation, mining, and nodes having different mempool size limits.

morcos force-pushed on Jul 28, 2015

morcos commented at 9:23 pm on July 28, 2015: member

I rebased, addressed many of the comments and did some various cleanups in place.

Please note I changed the defaults for -maxmempool and -mempoolexpiry to 500MB and 1 week respectively.

jtimon commented at 10:34 am on July 29, 2015: contributor

@morcos everybody is creating new globals in main, but I hate that. I would at the very least move them to globals/server ot something, but whatever… It would be much nicer if you make them an attribute of an existing class that is used as a global (say, mempool or globalPolicy). Here’s a commit in which you can see what I would like to move towards: https://github.com/jtimon/bitcoin/commit/5a42e278c64468e1e0f3ee24e10710b91c754082 I’ve been trying to do something like that since 2014 but unfortunately there’s still no right place for introducing new policy options and people keep doing everything in main. Next step is #6068 (still without the preparations in util that you could reuse, let me know if you want me to separate those preparations).

Even if you don’t do it “the right way” ( @luke-jr wanted to create a dynamic GUI form for command line options using something like https://github.com/jtimon/bitcoin/commit/5a42e278c64468e1e0f3ee24e10710b91c754082#diff-01e64f27a2a21a3116825fa22aee0537R30 ), for the case of -maxmempool and -mempoolexpiry, you could at least put them in CTxMempool. If we want them in policy (no strong opinion), the easiest thing IMO is leaving them as locals for now (even though that’s not very efficient) and hide them in CStandardPolicy or the policy estimator later.

But, whatever, there’s many things to cleanup already and everybody is doing it wrong, even for new policy options (like fRequireStandard), so why would you spend any “mental power” on putting new things in the right place when you’re actually solving an urgent problem? Do everything in main like everybody else and hopefully it will be cleaned up eventually.

morcos commented at 2:23 pm on July 29, 2015: member

@jtimon OK thanks. Yes I’m going to leave them as locals for now and if we end up adding sanity checking it can just be done separately in init.cpp for now. But I do like your idea of moving them to a policy class. It puts all the logic of what are the reasonable parameters for these arguments in the same place..

ABISprotocol commented at 2:35 am on July 30, 2015: none

I have a few questions,

I noted that @morcos stated that he “removed the floating relay fee commit,” but is there another commit added that provides some (roughly) equivalent function? It strikes me that having a floating relay fee added has a necessary dynamic effect ~ the purpose of the floating relay, as discussed in #6455, is to dampen the effect of the limited memory pool, and make it more constant over time.
Noted from prior remarks I have made in #6455 that a mempool is not necessarily needed (e.g., relay nodes would not need to be using a mempool; the wallet nodes, would be using a mempool, as was indicated).
It was my understanding that there was a resolution that “Mempool limiting and dynamic fee determination are superior to a static parameter change” at the end of #6201, which when closed led to #6455 and now, to this pull request.

0So, why not time based expiration as well as a floating relay fee?  Just curious.

sipa commented at 1:05 pm on July 30, 2015: member

Testing & benchmarking.

morcos commented at 4:31 pm on July 30, 2015: member

@ABISprotocol, I still believe we need a floating relay fee. I just think it needs to act over a much longer time horizon and be less abusable than the one implemented in the commit I removed.

ABISprotocol commented at 7:44 am on August 3, 2015: none

@morcos @sipa In what pull request or issue should I look for the floating relay fee, or is that TBD?

morcos commented at 3:32 pm on August 3, 2015: member

@ABISprotocol This was the commit I removed, https://github.com/sipa/bitcoin/commit/6498673f99da9976df170052648ff2f0026210d2. But I think the correct answer is TBD.

ABISprotocol commented at 1:01 am on August 5, 2015: none

@morcos @sipa Please refer to the number of the pull request for the the floating relay fee in this one at such time when it is created so that the discussion / progress on this can be followed. So far I have been following this as follows: #6201 #6455 I’m assuming there will be another pullreq (with a floating relay fee) TBD, my request is that when it is created, please refer to the number of that pullreq here. Thank you in advance.

morcos force-pushed on Aug 5, 2015

morcos commented at 3:54 pm on August 5, 2015: member

Rebased now that #6498 has been merged

TxMemPool: Change mapTx to a boost::multi_index_container

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

bb93e2cb5d

Move orphan tx handling to a separate log class 9dc4e7051c

Implement on-the-fly mempool size limitation. 04cf4baeae

Mempool expiry dac6496703

Add a notion of reserved space.

The mempool will now have a soft cap set below its hard cap.  After it fills up to the soft cap, transactions much first try using StageTrimToSize to evict the amount of size they are adding.  If they fail they can still be let into the mempool if they pass a higher relay minimum.  It doubles 10 times between the soft cap and hard cap.

9297953cde

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.

9881316466

Refactor STTS to be usable for surplus trimming as well 2dd1b4ddd9

Implement Surplus Trim.

Use reserve space between soft cap and hard cap as a reservoir of surplus fees that have been paid above the minRelayTxFee and occasionally use the aggregate usage there to trim from the bottom of the mempool.

40c38f8958

Various improvements.

Improve logging
Use insecure_rand in TrimMempool
Tweak logic of TrimMempool
Add occasional larger SurplusTrim.
Bypass eviction on disconnected block txs
Additional SurplusTrim for bypassed size
Acquire locks appropriately

6e8d3dd36c

morcos force-pushed on Aug 14, 2015

morcos commented at 7:03 pm on August 14, 2015: member

Rebased and squashed various cleanups and small changes into the last commit.

morcos commented at 5:20 pm on September 2, 2015: member

Closing in lieu of #6557, will reopen if we decide for some reason we want the mempool limiting without the descendant package tracking…

morcos closed this on Sep 2, 2015

ABISprotocol commented at 6:08 am on September 3, 2015: none

I’m beginning to wonder just how far down the rabbit hole this all goes. And what happened to the floating relay fee bit?

MarcoFalke locked this on Sep 8, 2021

Super Duper MemPool Limiter #6470