The PR branch HEAD was eebaca76 at the time of this review club meeting.
Notes
The UTXO cache is a critical data structure in Bitcoin for both correctness and
performance. It’s responsible for maintaining a view of the spendable coins
based upon the transactions in blocks. It is often a major bottleneck during
block validation, and incorrect behavior is almost certain to lead to consensus
failure.
Because the UTXO set is accessed so frequently, we would like its contents to be
available as quickly as possible. This amounts to having as much of the set
in memory as possible. The issue is that (at the moment) the in-memory
representation of the UTXO set is more than 8GB, and obviously not all hosts
running Bitcoin have that much memory.
For that reason, the UTXO cache is stratified across several
layers: some on-disk, and some in-memory. The
-dbcache parameter controls how much memory we allocate to the in-memory
portion. As we validate blocks, we pull unspent coins that we look up from disk
into memory until we run out of allocated memory (as indicated by this
logic).
At that point, we completely empty the UTXO cache by writing it to disk by
calling
CCoinsViewCache::Flush().
In master, this is the only way of reconciling the state of the cache
with the leveldb store on disk, even though sometimes we Flush() not because we
have exceeded our dbcache, but to ensure durability. For example, we
periodically
flush
the coins cache to avoid having to replay blocks if we shut down improperly.
Once we flush the cache, we are forced to read from and write to disk
for all UTXO operations, which can be notably slower depending on the
underlying disk. For this reason, separating the emptying of the cache
from the writing to disk might allow us to ensure durability without losing the
performance benefits of maintaining the cache.
A year ago, andrewtoth proposed in
PR #15218 that we flush the
UTXO set after completion of initial block download to avoid having to
reconstruct the entire set if an unclean shutdown happened before a periodic
flush, which basically amounts to a -reindex-chainstate. Other reviewers
criticized this idea because of the performance implications of emptying the
cache.
Another case that requires writing to disk without necessarily emptying the
cache can be found in the assumeutxo
project. When
loading a UTXO set from a serialized snapshot, it’s preferable to write out the
newly constructed chainstate immediately after load to avoid having to reload
the snapshot once again after a bad shutdown. Benchmarks have
shown
that some platforms benefit significantly from maintaining the contents of the
cache after writing them to disk.
What is the “shape” of the UTXO set? What is it keyed and valued by? What are
the operations it supports? Hint: try looking at
coins.h.
What are the different layers of the UTXO cache?
How does CCoinsView relate to CCoinsViewCache and CCoinsViewDB?
How does CCoinsViewDB relate to DBWrapper?
What do the flags associated with CCoinsCacheEntry objects mean?
What does DIRTY mean?
What does FRESH mean?
Why do we go to the trouble of maintaining these flags?
What happens when CCoinsViewCache::Flush() is called? How do the coins
in memory make their way to the disk?
When an unspent coin is flushed to disk and then spent in the next block, we
will have done (at least) two writes and a read for that coin. If a coin is
created and spent without a Flush() in between, no disk reads or writes are
done. Why is this?
Can you describe the consensus bug referenced
here?
<jamesob> "We usually start Bitcoin Core IRC meetings with a 'hi' so it's clear who's at keyboard. Feel free to say hi, even if you arrive in the middle of the meeting!" in the words of jonatak
<jamesob> You don't have to ask to ask a question (e.g. "I have a question about x but I don't know if it's on-topic?"). Just go ahead and ask. If it's off-topic we'll tell you.
<jamesob> In summary, the PR allows writing the contents of the UTXO set down to disk without wiping out the in-memory cache, which has some performance benefits.
<jamesob> that's great. Before we start talking about things like cache flushing, though, and in-memory vs. on disk we should probably get some things straight conceptually
<michaelfolkson> "The data structure used to refer to a particular transaction output, consisting of a 32-byte TXID and a 4-byte output index number (vout)."
<jamesob> instead of being valued by a Coin, which has the constituent data you've listed, it's actually valued by a CCoinsCacheEntry, which has some extra stuff
<jamesob> it's a CCoinsView implementation that says "I'm one layer of a cache, but there's another coins view that sits behind me, and I'll consult that view if the user of me asks for a coin I don't have."
<jamesob> nehan_: good question. It turns out (I think) that is because CCoinsViewDB doesn't have a cache behind it, and so it subclasses CCoinsView directly
<jamesob> so on the top of the cache is the in-memory store. If we try to fetch a coin from that view and it fails, it'll try the fetch from CCoinsViewCatcher. CCoinsViewCatcher doesn't store *anything*, so it will always fall back to CCoinsViewDB, which ultimately uses a class called DBWrapper to consult leveldb (which is the on-disk local database we use)
<jamesob> lightlike that's a good question and we're jumping ahead a little bit, but yes: CCoinsViewCache pulls any fetched coin into its cache after it fetches it from its parent cache
<nehan_> jamesob: "on the top of the cache is the in-memory store" --> do you mean on top of CCCoinsViewCatcher? Is there another in-memory store on top of CCoinsViewCache?
<jamesob> and beyond that, there are durability considerations: if we crash while everything is in memory, the UTXO set gets wipe out and we'd have to reindex on startup
<nehan_> jamesob: this seems like a really weird way to use what should be just an in-memory cache. it's sort of being used as a way of atomically applying updates?
<jamesob> nehan_: yeah, in the case I link to, we use the temporary CCoinsViewCache as a sort of "transaction" (in the database sense) to be able to easily "roll back" if any of the spends don't validate when connecting a block
<jamesob> so when to Flush() actually turns out to be pretty important because as you can probably guess, it not only amounts to writing to disk but (currently) it removes everything from the in-memory portion of the view structure
<jamesob> in order to make efficient use of the in-memory cache, we want to be able to avoid writing to and reading from disk if, say, a coin is created and spent without running low on memory
<jonatack> src/coins.h#L120 FRESH is a performance optimization with which we can erase coins that are fully spent if we know we do not need to flush the changes to the parent cache. It is always safe to not mark FRESH if that condition is not guaranteed.
<jamesob> jonatack: right. FRESH basically says "the cache that sits behind me has never seen this entry - I haven't flushed it yet. So if the entry gets removed, I can just remove it from my cache - no need to tell my parent."
<andrewtoth> this is basically an optimization to avoid writing a transient utxo. if the db hasn't seen it and it is spent, it never needs to be written
<jamesob> so there are certain cases where you may not know if leveldb has seen the entry or not, i.e. when we are recovering from a crash that happened during a Flush()
<jnewbery> Imagine we receive a block that has transaction A and transaction B, which spends one of A's outputs. We apply that block atomically and never need to apply that output to our UTXO set when we flush
<jnewbery> because we've marked A's output as FRESH, when we spend it, we can just remove it from our cache instead of flushing it at the end of block connection
<jnewbery> I think it's worth pointing out that the comment is a bit out of date (the words 'pruned' and 'fully spent' only made sense when the UTXO was tracking transactions instead of outputs
<jamesob> jnewbery: I initially thought that, but "pruned" does still have a relevant meaning: because parent caches can return null values for coins which have been spent in their caches, those null values are sometimes referred to as "pruned"
<jamesob> the way that fresh and dirty flags work, when they are set, and why is potentially the hardest thing to understand about the innerworkings of the UTXO view structure
<andrewtoth> if the utxo is brand new, it is DIRTY because the db doesn't have it, so it's different. It's also FRESH, since the db doesn't have it. If it gets spent before a write, it can just be removed
<jnewbery> huh, I'll need to look into that. I thought 'pruned' meant 'all the outputs of this tx have been spent, we can remove it from our (pre-0.15 per-transaction) UTXO set. No need to discuss here though!
<jamesob> but they allow us to fully leverage the in-memory cache by pruning coins which are created and spent in between disk flushes without ever touching the disk
<lightlike> could it be interesting idea for the future to try partial flushs (according to some heuristic) so that we free up some space but hopefully keep those coins in memory that we may need soon?
<jamesob> michaelfolkson: there aren't a ton of resources on that surprisingly, but I can recommend a very broad talk I did back in 2018: https://jameso.be/dev++2018/#1