Simplify cache interface and drop fully spent unwritten entries #4834

sipa commented at 12:44 PM on September 3, 2014: member

Replace the CCoinsViewCache interface with mostly just AccessCoins and ModifyCoins methods (see individual commits), and maintain metadata about cached entries.

This allows us to know when a transaction is fully spent before it is flushed, allowing us to forget about it entirely and never have it touch disk at all.

With this, I can -reindex the main chain until the last checkpoint with around 2GB (without any chainstate write to disk) of RSS. The final dump of the result to LevelDB takes 700MB extra.

Note that this is just a memory usage improvement, and not a performance optimization as such: it doesn't attempt to keep modified non-dirty entries in memory, or do negative caching.

This builds upon #4822, which may be simpler to review.

sipa force-pushed on Sep 3, 2014

sipa renamed this:
~~Simplify coins cache and drop fully spent unwritten entries~~
Simplify cache interface and drop fully spent unwritten entries
on Sep 3, 2014

laanwj added the label UTXO Db and Indexes on Sep 4, 2014

laanwj added the label Improvement on Sep 4, 2014

sipa commented at 1:04 PM on September 4, 2014: member

Strange, test_bitcoin works perfectly here - even under valgrind.

sipa force-pushed on Sep 4, 2014

sipa commented at 7:10 PM on September 4, 2014: member

Bug fixed.

Let it be known that

unordered_map::iterator it = mapA.find(x);
if (it != mapB.end()) {

works in recent Boost, but not in older Boost... (I assume that in newer ones, end() returns a map-independent constant).

in src/coins.cpp:None in 0cda129b67 outdated

  72 |  bool CCoinsViewBacked::GetStats(CCoinsStats &stats) const { return base->GetStats(stats); }
  73 |  
  74 |  CCoinsKeyHasher::CCoinsKeyHasher() : salt(GetRandHash()) {}
  75 |  
  76 | -CCoinsViewCache::CCoinsViewCache(CCoinsView &baseIn, bool fDummy) : CCoinsViewBacked(baseIn), hashBlock(0) { }
  77 | +CCoinsViewCache::CCoinsViewCache(CCoinsView &baseIn, bool fDummy) : CCoinsViewBacked(baseIn), hasModifier(false), hashBlock(0) { }

Diapolo commented at 5:41 PM on September 8, 2014:

Unrelated question, fDummy looks unused to me (even my compiler sais that ^^). Why is that flag there in the first place?

sipa commented at 5:42 PM on September 8, 2014:

That's the point of a dummy :).

The reason it's there is to avoid having the compiler think that this is a copy constructor, IIRC.

Diapolo commented at 5:44 PM on September 8, 2014:

Thanks for clarification ^^, is there a comment about that fact or is this common pratcise in C++ anyway?

laanwj commented at 9:51 AM on September 23, 2014:

Wouldn't "explicit" be enough to convince the compiler of that?

sipa force-pushed on Sep 10, 2014

sipa force-pushed on Sep 17, 2014

sipa commented at 12:03 AM on September 17, 2014: member

Added a large randomized test for CCoinsViewCache that hopefully triggers all edge cases.

sipa force-pushed on Sep 17, 2014

sipa force-pushed on Sep 20, 2014

sipa commented at 7:58 PM on September 22, 2014: member

@laanwj Can you have a look at this? Are the tests sufficient?

in src/main.cpp:None in 3067f33ec9 outdated

1357 | -            CCoins &coins = inputs.GetCoins(txin.prevout.hash);
1358 | +        BOOST_FOREACH(const CTxIn &txin, tx.vin) {
1359 |              txundo.vprevout.push_back(CTxInUndo());
1360 | -            ret = coins.Spend(txin.prevout, txundo.vprevout.back());
1361 | -            assert(ret);
1362 | +            inputs.ModifyCoins(txin.prevout.hash)->Spend(txin.prevout, txundo.vprevout.back());

laanwj commented at 10:02 AM on September 23, 2014:

We no longer check the result of Spend() here. Is this on purpose?

sipa commented at 8:12 PM on September 23, 2014:

Fixed.

in src/coins.cpp:None in 3067f33ec9 outdated

 123 |  
 124 | -CCoins &CCoinsViewCache::GetCoins(const uint256 &txid) {
 125 | -    CCoinsMap::iterator it = FetchCoins(txid);
 126 | -    assert(it != cacheCoins.end());
 127 | -    return it->second;
 128 | +CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) {

laanwj commented at 10:09 AM on September 23, 2014:

Do we need a flag/bitfield here to distinguish the cases

a) expect an entry to be already there for txid, creating a new one would be a mistake

b) expect to create a new entry for txid, having one there already would be a mistake

c) entry could be already there or be created anew, don't care

It appears we're slightly weakening the integrity checks in that regard.

sipa commented at 11:38 PM on September 23, 2014:

This really complicates things. We're in many cases already treating no-entry as empty-CCoins, and have had problems with incorrectly treating differences between them (on a reorg we may replace added entries with empties, for example).

Perhaps we already have problems in this space; I'm more in favor of an interface that explicitly treats them identically for this reason.

Are there any use sites where you think we reduced sanity checking?

in src/coins.h:None in 3067f33ec9 outdated

 363 | +    ~CCoinsModifier();
 364 | +    friend class CCoinsViewCache;
 365 | +};
 366 | +
 367 |  /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
 368 |  class CCoinsViewCache : public CCoinsViewBacked

laanwj commented at 10:19 AM on September 23, 2014:

We could add assert(!hasModifier); in the CCoinsViewCache destructor, to assert that the modifier never outlives the cache.

sipa commented at 9:58 PM on September 23, 2014:

Done.

in src/test/coins_tests.cpp:None in 3067f33ec9 outdated

  70 | +// It will randomly create/update/delete CCoins entries to a tip of caches, with
  71 | +// txids picked from a limited list of random 256-bit hashes. Occasionally, a
  72 | +// new tip is added to the stack of caches, or the tip is flushed and removed.
  73 | +//
  74 | +// During the process, booleans are kept to make sure that the randomized
  75 | +// operation hits all branches.

laanwj commented at 10:35 AM on September 23, 2014:

Does this mean that the test can randomly fail? (ie, if due to randomness it does not hit a branch?)

sipa commented at 9:59 PM on September 23, 2014:

Given that we're doing 40000 iterations of it, that should be exceedingly unlikely (plus the random numbers are deterministic, so it would only break after actual code changes).

sipa commented at 1:51 AM on September 24, 2014:

Just a 1000 iterations is enough to trigger all branches, by the way.

laanwj commented at 9:13 AM on September 24, 2014:

OK - good idea to make it determinisic, so at least in the case that it fails it will fail every time.

sipa force-pushed on Sep 23, 2014

Use ModifyCoins instead of mutable GetCoins.

Replace the mutable non-copying GetCoins method with a ModifyCoins, which
returns an encapsulated iterator, so we can keep track of concurrent
modifications (as iterators can be invalidated by those) and run cleanup
code after a modification is finished.

This also removes the overloading of the 'GetCoins' name.

f28aec014e

Get rid of CCoinsView's SetCoins and SetBestBlock.

All direct modifications are now done through ModifyCoins, and BatchWrite is
used for pushing batches of queued modifications up, so we don't need the
low-level SetCoins and SetBestBlock anymore in the top-level CCoinsView class.

c9d1a81ce7

Do not keep fully spent but unwritten CCoins entries cached.

Instead of storing CCoins entries directly in CCoinsMap, store a CCoinsCacheEntry
which additionally keeps track of whether a particular entry is:
* dirty: potentially different from its parent view.
* fresh: the parent view is known to not have a non-pruned version.

This allows us to skip non-dirty cache entries when pushing batches of changes up,
and to remove CCoins entries about transactions that are fully spent before the
parent cache learns about them.

058b08c147

Add coins_tests with a large randomized CCoinViewCache test. ed27e53c9b

sipa force-pushed on Sep 23, 2014

sipa commented at 11:25 PM on September 23, 2014: member

Replaced the dummy arg with an explicit constructor.

sipa force-pushed on Sep 24, 2014

Get rid of the dummy CCoinsViewCache constructor arg 7c70438dc6

sipa commented at 1:19 AM on September 24, 2014: member

Nope, that didn't work - the compiler still uses the explicit constructor for assignment (because the type is different). Solved it now by passing a pointer rather than a reference (in a separate commit).

BitcoinPullTester commented at 1:34 AM on September 24, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p4834_7c70438dc67547e83953ba0343a071fae304ce65/ for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

laanwj commented at 10:42 AM on September 24, 2014: member

Works for me, tested ACK

sipa commented at 6:47 PM on September 26, 2014: member

@gmaxwell @jgarzik Comments?

gmaxwell commented at 8:35 AM on October 8, 2014: contributor

ACK. (tested a previous version but moving my test hosts to the current version now)

sipa merged this on Oct 8, 2014

sipa closed this on Oct 8, 2014

sipa referenced this in commit d4a42334d4 on Oct 8, 2014

in src/main.cpp:None in 7c70438dc6

1796 | @@ -1804,10 +1797,10 @@ void static UpdateTip(CBlockIndex *pindexNew) {
1797 |      nTimeBestReceived = GetTime();
1798 |      mempool.AddTransactionsUpdated(1);
1799 |  
1800 | -    LogPrintf("UpdateTip: new best=%s  height=%d  log2_work=%.8g  tx=%lu  date=%s progress=%f\n",
1801 | +    LogPrintf("UpdateTip: new best=%s  height=%d  log2_work=%.8g  tx=%lu  date=%s progress=%f  cache=%u\n",

rebroad commented at 2:22 AM on December 10, 2014:

How useful is this extra debug info? Can it be made optional perhaps?

MarcoFalke locked this on Sep 8, 2021