[WIP] Implement a UTXO cache

[Roasbeef]

This PR picks off where #1168 left off. I've back ported fixes from the gcash repo, ensuring all commits have their authors properly attributed. I've started to test this PR as is on both mainnet and testnet. We also need to examine the set of fixes and ensure they're absolutely necessary, as many of the back-ported gcash fixes didn't have accompanying unit tests that failed before the fix was applied.

Additionally, I plan to fix what I view as two design flaws in the current UTXO set cache:

1. When entries are added, we don't evict them in real time. As a result, the cache can grow very large beyond the targeted constrained sized. In the future, we'll likely also implement more advanced eviction logic, such as evicting the oldest present UTXO, as empirically, UTXOs die young.
2. When we flush the cache, we also remove all in memory entries from the cache. This causes additional G/C pressure, as the very next block, we then need to re-allocate the map. Additionally, this causes more cache hits, as we start with a cold cache for the next block which guarantees that we'll have a large set of cache misses. Instead, we should only seek to sync our in memory view with that what's on disk, only syncing the entires that have been modified.

Thanks to everyone that had a part in this including @stevenroose, @cfromknecht and @cpacia.

[Roasbeef]

Tests fail as is, they also failed before of the cherry-picked "fix" commits. The set of extra commits actually seem to introduce even more test failures than without them.

[Roasbeef]

Tests should be passing now after that lastest commit. I don't like the fix in ee0b302 though, it should be much more precise.

[Roasbeef]

Started the mainnet sync, ton of optimization to do, most of the time is spent in GC:

[Roasbeef]

Zooming in on the other hot area, we see the current bottle necks in block processing:

[maguayo]

Any reason why the cache is limited to 250MB, just curious :)

[jakesylvestre]

@jcvernaleo (as per #1530)

• Low priority
• Outdated

[jakesylvestre]

@Roasbeef can we make this a draft?

[Roasbeef]

Wouldn't say the PR is outdated since it runs as is, and delivers a massive speed up in IBD. As mentioned in the recently closed (older) version of this PR, in combination with some of the other optimizations, btcd sync the chain in under 24 hours. This includes full verification after the past checkpoint, unlike bitcoind's assumevalid which only does UTXO ingestion primarily.

[jcvernaleo]

@Roasbeef I think we may have been using outdated to mean more like a catch-all for either not up to date or just not ready. Not a great way to do it for sure, but we had a lot of triage to do :)

This PR is definitely super important so I'm really looking forward to when it can go in.

[jakesylvestre]

Yep, that was the case. Will go ahead and run this on a full sync today to benchmark

[kcalvinalvin]

Is the bug in dbSeekUtxoEntry() already known? In the tests, dbSeekUtxoEntry() will sometimes return a tx that's new. This causes checkBIP0030() to fail as seekAndCacheEntries() will return a tx that hasn't been committed with Commit() method on utxoCache. Using fetchAndCacheEntries() is a workaround to this.

[rstaudt2]

In case anyone is interested when picking up this work, we implemented a UTXO Cache in dcrd earlier this year, and portions of it could likely be pretty easily reused here. It accounts for the design flaws mentioned in this PR description as well. The PR that introduces it is https://github.com/decred/dcrd/pull/2591.