bitcoin/bitcoin — pull request #4700 by laanwj (2014-08-14 11:04:07+00:00)
Title: CCoinsCache: Split read and write caches, MRU cache for read, add stats to RPC

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.