Remove UTXO cache entries when the tx they were added for is removed/does not enter mempool #6872

TheBlueMatt commented at 10:53 PM on October 22, 2015: member

No description provided.

in src/coins.cpp:None in 2882815e3b outdated

 196 | @@ -192,6 +197,13 @@ bool CCoinsViewCache::Flush() {
 197 |      return fOk;
 198 |  }
 199 |  
 200 | +void CCoinsViewCache::Uncache(const uint256& hash)
 201 | +{
 202 | +    CCoinsMap::iterator it = cacheCoins.find(hash);
 203 | +    if (it != cacheCoins.end() && it->second.flags == 0)

sipa commented at 2:38 AM on October 26, 2015:

You can do slightly better: if (it != cacheCoins.end() && (((it->second.flags & CCoinsCacheEntry::DIRTY) == 0) || ((it->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned())))

This will also allow removing entries that were created and spent entirely within a cache.

TheBlueMatt commented at 2:45 AM on October 26, 2015:

Such an entry should probably be removed without a call to Uncache, no?

sipa commented at 2:46 AM on October 26, 2015:

Uh, right, and it already is... never mind!

in src/main.cpp:None in 2882815e3b outdated

 864 |              if (!view.HaveCoins(txin.prevout.hash)) {
 865 |                  if (pfMissingInputs)
 866 |                      *pfMissingInputs = true;
 867 |                  return false; // fMissingInputs and !state.IsInvalid() is used to detect this condition, don't set state.Invalid()
 868 | -            }
 869 | +            } else if (fMaybeUncache)

sipa commented at 2:51 AM on October 26, 2015:

Even if HaveCoins returns false, the entry may have been pulled into the cache (the parent cache may have a pruned entry), so this probably works better outside of the else branch.

in src/main.cpp:None in 2882815e3b outdated

 746 | +        LogPrint("mempool", "Expired %i transactions from the memory pool\n", expired);
 747 | +
 748 | +    size_t mempoolUsage = pool.DynamicMemoryUsage();
 749 | +    size_t coinsUsage = pcoinsTip->DynamicMemoryUsage();
 750 | +
 751 | +    while (mempoolUsage > limit || coinsUsage + mempoolUsage > nCoinCacheUsage + limit) {

sipa commented at 3:00 AM on October 26, 2015:

If coinsUsage is larger than nCoinCacheUsage + limit, this results in an infinite loop?

TheBlueMatt commented at 3:04 AM on October 26, 2015:

Huh? I could have sworn I deleted the loop as it is too easy for an attacker to fuck with your mempool, even if it did work.

sipa commented at 3:32 AM on October 26, 2015:

Yeah, I think that loop and the link with coincache size should go away. The coincache size shouldn't exceed its own limit, and the mempool shouldn't exceed its own limit. We may want to move to a model where the size for both is set using a single limit, but that will require other changes elsewhere too.

sipa commented at 3:24 AM on October 26, 2015: member

Do you feel like pulling in https://github.com/sipa/bitcoin/commit/4186ac95f8283206874af50f9754e894823df66d ?

TheBlueMatt commented at 5:03 AM on October 26, 2015: member

https://github.com/sipa/bitcoin/commit/4186ac95f8283206874af50f9754e894823df66d seems pretty nasty to me....completely clearing the cache when we add a transaction that pushes our cache over 90% usage seems like a really bad idea.

sipa commented at 5:08 AM on October 26, 2015: member

@TheBlueMatt it's a last resort. If the cache size can grow outside of its set bounds, we have to do something or there is no limit. Furthermore, it's the same as what will happen anyway after the next block.

I considered it unacceptable on its own, as it would makr transaction spamming result in more or less synchronized wiping of the cache across the network, which could interfere with relay. Hopefully the rest of your patch should reduce the risk of that.

TheBlueMatt commented at 5:10 AM on October 26, 2015: member

Wiping the cache sounds like a dirty hack to me. I'd rather evict random elements until the cache is reasonably-sized than that.

TheBlueMatt commented at 5:11 AM on October 26, 2015: member

Also, we should fix it to not dump the entire cache after each new block.

sipa commented at 5:13 AM on October 26, 2015: member

That, or some for of LRU or priority tracking in the coin cache would be a significant improvement for sure.

But we need a means to limit memory usage at all costs IMHO, and this solution is simple and doesn't worsen things on average, I think, as the cache would be flushed anyway at the next block - potentially even in between blocks in a reorg if the usage passed 100% by that time.

TheBlueMatt commented at 5:15 AM on October 26, 2015: member

Sure, making the cache smarter would be nice, but lets not rush to fix it with a dirty hack when we're not even gonna ship the fix for a few months anyway.

sipa commented at 5:17 AM on October 26, 2015: member

It's orthogonal. We need to enforce memory usage limits after each transaction, so let's call the function to do that at that time.

How that function works is a different matter, and can be arbitrarily improved later.

I don't understand your resistance here. I think it's the only solution.

morcos commented at 1:49 PM on October 26, 2015: member

Have you guys looked into how expensive all this work is? @sipa Once we've made it so that you can't bloat memory usage with txs that aren't accepted (as accomplished by this pull) then it seems to me the right approach is to just set your maxmempool size low enough that the unknown and variable multiple of that that is the size of your cache is also small enough for you. IMHO, the default dbcache size is too small. I'm with @TheBlueMatt that it seems bad to randomly wipe it unless we think that'll be very rare.

I'd actually argue we might not even need to remove cache entries that are due to evicted tx's, because there is a relay cost that is paid to create those.

in src/main.cpp:None in d5b4e90270 outdated

 841 | @@ -830,13 +842,17 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
 842 |          view.SetBackend(viewMemPool);
 843 |  
 844 |          // do we already have it?
 845 | -        if (view.HaveCoins(hash))
 846 | +        if (view.HaveCoins(hash)) {
 847 | +            vHashTxnToUncache.push_back(hash);

sdaftuar commented at 1:55 PM on October 26, 2015:

If I understand correctly, then we might remove this transaction from the cache even though there may be in-mempool spends of it, right? I think we want some kind of check like you have in TrimToSize, where you only uncache if there's nothing in the mempool that spends it.

(Alternatively, if HaveCoins somehow reported whether any new caching happened, that might be helpful, but that seems like a harder change to make.)

TheBlueMatt commented at 12:31 AM on October 27, 2015: member

Sure, if the eventual solution is to tweak FlushStateToDisk to be smarter (LRU or some priority metric based on what's in mempool), then that would be reasonable. I am, however, worried we'd merge it and forget to tweak the coins cache, making it even easier (maybe, though maybe there are easier ways anyway) for an attacker to cause lots of random disk I/O.

On 10/26/15 05:17, Pieter Wuille wrote:

It's orthogonal. We need to enforce memory usage limits after each transaction, so let's call the function to do that at that time.

How that function works is a different matter, and can be arbitrarily improved later.

I don't understand your resistance here. I think it's the only solution.

— Reply to this email directly or view it on GitHub #6872 (comment).

sipa commented at 12:34 AM on October 27, 2015: member

I don't think it's worse than what we have. The cache will already be flushed on the next block.

TheBlueMatt commented at 12:38 AM on October 27, 2015: member

Depends on which you find worse, memory usage or DB I/O. Because its easy to optimize for loading lots of crap into the cache, an attacker can obviously tickle the cache to make it do more DB I/O with https://github.com/sipa/bitcoin/commit/4186ac95f8283206874af50f9754e894823df66d, but can cause an equivalent increase in memory usage without.

sipa commented at 1:11 AM on October 27, 2015: member

I think we should move to a model of thinking where exceeding some reasonable but fixed memory limit is equivalent in badness to crashing. People need to be able to rely on the memory usage to remain bounded. So if it's a choice between more I/O and that, I think the first is far better.

TheBlueMatt commented at 1:40 AM on October 27, 2015: member

I think thats a fine idea...except that we're so far away from it, it seems a bit premature to be optimizing for it now.

dcousens commented at 3:15 AM on October 27, 2015: contributor

concept ACK

sipa commented at 8:50 PM on October 27, 2015: member

Observation:

2015-10-27 20:49:07 dd310afee248d4699e462e5d3826e879cc19d1d2d34e9de0070811d1d5f6e64a from peer=15 was not accepted: rate limited free transaction (code 66)
2015-10-27 20:49:07 ATMT increases coincache by 159 (to 614694) KiB

So when ATMT rejects due to rate limiting, the coincache entries pulled in don't seem to be removed.

sipa commented at 8:55 PM on October 27, 2015: member

Observation:

2015-10-27 20:52:57 a94894230e8c647d11dc67c2f7d56e91913aab8c6b3f7257f36d2cea30ddfbeb from peer=5 was not accepted: non-mandatory-script-verify-flag (No error) (code 64)
2015-10-27 20:52:57 ATMT increases coincache by 329 (to 991099) KiB

sipa commented at 9:07 PM on October 27, 2015: member

My observations are likely explained by this patch not updating coinsCachedUsage, so the pcoinsTip->DynamicMemoryUsage() going off the charts.

sipa commented at 9:29 PM on October 27, 2015: member

New observation:

2015-10-27 21:27:43 cd55b134090117cc7fbf4ad8d1039642f1dd63460daa27c59d1c0ae2aba3e582 from peer=14 was not accepted: mempool min fee not met, 15000 < 24788 (code 66)
2015-10-27 21:27:43 ATMT decreases coincache by 105 (to 67916) KiB

laanwj added the label Mempool on Oct 29, 2015

sipa commented at 8:54 PM on October 30, 2015: member

Tested ACK.

morcos commented at 9:28 PM on October 30, 2015: member

I'm a bit hesitant to merge this instead of a cleaner way of smart flushing and I'd still like to see some performance analysis.

gmaxwell added this to the milestone 0.12.0 on Nov 5, 2015

gmaxwell commented at 12:13 AM on November 8, 2015: contributor

Without this, my mining node with an elevated relay fee (and running mempool limiting) and default dbcache is at 4GB RES. We do need to do more to control the size of the coins cache, if not precisely this change.

morcos commented at 9:40 PM on November 9, 2015: member

I did some benchmarking on this pull. I built it on top of all the other improvements in #6976 except I tried it with and without the hot cache. It caused a significant performance boost to ConnectBlock. Unfortunately on my test days, 10/6 and 10/7 and using 100 M mempool and 200 M dbcache, the total cpu time shot up by over 10%. This seems to be entirely due to the 15kb very low fee transaction spam and increased time to reject these txs. I did not break down where the time was spent, but my guess is that it is not all in the uncaching code and that part of the problem is that these large txs often spent from the same prev hashes. So by uncaching them we cause more time to be spent just calculating the fee of new txs before we can reject them.
It also had the desired effect of reducing cache size, and reduced cache flushes from 38 to 16 over the 2 days.

Here is a summary of the results. I haven't fully reviewed the code yet, but I think this might be a performance hit we could tolerate.

Code	Avg time for tx rejected by ATMP (ms)	Avg time to connect block (ms)
baseline (#6976 except #6936)	1.7	134
baseline + #6936	1.7	128
baseline + this PR	2.9	109
baseline + this PR + #6936	2.9	104

sipa commented at 1:23 PM on November 28, 2015: member

Needs rebase.

laanwj commented at 8:42 AM on December 1, 2015: member

Still needs rebase

TheBlueMatt commented at 9:19 AM on December 1, 2015: member

Yes, sorry, I thought the plan was to go forward with #6936 and skip this one entirely, but it seems there is some consensus to do this as an intermediate until #6936 is fully ready to replace it (probably 0.13). Will try to rebase this tomorrow.

TheBlueMatt force-pushed on Dec 1, 2015

TheBlueMatt commented at 10:22 AM on December 1, 2015: member

Rebased, squashed, pulled in https://github.com/sipa/bitcoin/commit/4186ac95f8283206874af50f9754e894823df66d for 0.12.

TheBlueMatt force-pushed on Dec 1, 2015

MarcoFalke commented at 12:30 PM on December 1, 2015: member

@TheBlueMatt Needs rebase. (Travis fail is unrelated: #6540)

Add method to remove a tx from CCoinsViewCache if it is unchanged 74d0f90262

Get the set of now-uncacheable-txn from CTxMemPool::TrimToSize b2e74bd292

Discard txn cache entries that were loaded for removed mempool txn 677aa3d88c

Add CCoinsViewCache::HaveCoinsInCache to check if a tx is cached 97bf377bd1

Uncache input txn in utxo cache if a tx is not accepted to mempool bde953e281

Flush coins cache also after transaction processing dd5862c4cd

TheBlueMatt force-pushed on Dec 1, 2015

TheBlueMatt commented at 12:03 AM on December 2, 2015: member

Rebased. Again.

laanwj merged this on Dec 2, 2015

laanwj closed this on Dec 2, 2015

laanwj referenced this in commit bdda4d567e on Dec 2, 2015

laanwj commented at 9:19 AM on December 2, 2015: member

Merged this because I want to branch off 0.12 soon, ~~not happy it has no ACKs at all though~~ (oh it does, sorry @sipa). Would still be nice if some reviewers could poshumously ACK this

morcos commented at 2:53 PM on December 2, 2015: member

code review and tested for performance only ACK

(I think most of us tested this before #5967 was merged, but I can't think why that should cause any problems)

arielgabizon commented at 7:23 AM on December 27, 2017: none

What was the justification for pulling in the flush commit? It seemed from the conversation that there was agreement of @TheBlueMatt and @morcos that it was not a good idea.

TheBlueMatt commented at 7:28 AM on December 27, 2017: member

It's important to limit cache at some point during normal operation, see gmaxwell's comment.

On December 27, 2017 8:24:06 AM GMT+01:00, Ariel notifications@github.com wrote:

What was the justification for pulling in the flush commit? It seemed from the conversation that there was agreement of @TheBlueMatt and @morcos that it was not a good idea.

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/bitcoin/bitcoin/pull/6872#issuecomment-354066853

random-zebra referenced this in commit fcb546ad05 on Aug 12, 2020

markblundeberg referenced this in commit 216482dec5 on Sep 5, 2020

markblundeberg referenced this in commit 374c5d3117 on Sep 5, 2020

ftrader referenced this in commit f60a16c581 on Oct 16, 2020

MarcoFalke locked this on Sep 8, 2021