CCoinsCache: Split read and write caches, MRU cache for read, add stats to RPC #4700

Most of these changes depend on each other, but are in separate commits and can be split off into separate pulls if this is deemed too high-impact to apply at once.

Track cache statistics in getblockchaininfo

This makes it possible to measure and compare caching strategies.

"coinscache" : {
    "positive_hits" : 9186,
    "negative_hits" : 7579,
    "positive_misses" : 50791,
    "negative_misses" : 43200,
    "writes" : 8569,
    "cache_size" : 93722,
    "rcache_size" : 91207,
    "wcache_size" : 2515,
    "cache_limit" : 171267
}

Currently this is part of getblockchaininfo. I'm not sure about that, it probably should get its own RPC.

Separate read and write cache

Keep track of entries that are read-only or r/w in separate caches. This is an optimization that avoids writing back all accessed entries back to the database on a flush.

The read and write cache can be flushed separately. Only the write entries will be written back.

This also opens the door to using a different data structure for the read and write cache later on.

Cache negative hits

Currently the cache doesn't remember when a coin was not found. It could cache negative results as well.

Looking at the statistics this can make a difference in number of database queries almost as large as positive caching during normal node operation.

The implementation makes use of the fact that a a CCoins with 'pcoins->vout.empty()' is regarded as non-existent.

Change read cache to MRU cache

Changes the read cache to a MRU cache implemented using boost::bimap. This allows cleaning up the cache to a fixed size instead of flushing the entire cache periodically, and should result in more effective caching. Write cache flushes are done with the same frequency as before, and are still all-or-nothing.

Flush write cache into read cache

After writing the entries to the underlying store, move them to the read cache. It is likely that they will be accessed again soon. If not, the entries will be evicted eventually.

Memory usage

Peak memory usage hasn't changed compared to before. However, the evolution of memory usage in time has changed. Before, the cache was flushed completely every 10 minutes (when not in initial block sync) or when the cache was full (when initial block sync). Now, instead of alternating between empty and full it will plateau.

Testing

I did quite a bit of testing with these changes, amongst others various reindexes of the mainnet and testnet block chains as well as tests with -checkblocks and running a node for a while. Still, especially the MRU cache switch needs to be tested much more extensively before it can be merged.

I think the largest benefit of this will come later, from being able to track in-cache-created entries and removing them in-memory if they are fully spent, preventing them from ever needing to be serialized/written. I'm sure that tuning things like how frequently and when to write what can bring additional benefits.

I'll look at the code in more detail later. Perhaps we can try to first implement such optimizations as further commits on top of this, to see whether there are actual benefits before merging.

Indeed, there are a few other things we could try. But basically the MRU read cache seems to be useless at the moment:

• During checkblocks: everything enters the write cache of the child cache (coins), so there is no use to the read cache in pcoinsTip
• During initial sync: the read cache does have a lot of hits, but it appears that misses don't figure much into the overall timings (probably as leveldb has its own caching). So using the CCoinsCache as we do now, as a 'write buffer/batcher' is OK performance-wise
• During normal node use: the cache gets lots of hits during transaction and block validation, but performance consequences of this are hard to measure. At least with current transaction volumes maybe it's just not so bad to query the underlying database. Especially as leveldb does caching of its own

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p4700_1648f256f7104e7164f8aa81ae81b82bc68918e3/ 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.