This PR is a follow-on to PR 25325,
which we reviewed March 8 of this year.
Please review at least the notes for that review club.
The -dbcache configuration option determines the amount of memory
(default 450 MiB)
used for the coins cache as well as other “database” uses of memory;
see CalculateCacheSizes().
Using less memory than allowed decreases the coins cache hit ratio (the
fraction of lookups that find the UTXO in the cache); using more memory
than specified risks crashing bitcoind on memory-restricted systems.
For this reason, it’s important to keep an accurate accounting of the amount
of memory used by the cache. It doesn’t have to be perfect but should be
fairly close.
When a program requests X bytes of dynamic memory from the C++ runtime
library, internally it allocates slightly more for the memory allocator’s
metadata (overhead). In other words, logical memory is not the same
as physical memory.
This memory allocator metadata is somewhat complex and depends on several
factors, such as the machine architecture and the
memory model.
When sizing the cache, we want to calculate physical memory usage, that is,
account for this extra allocation metadata. Unfortunately, there’s no
library function that maps logical memory size to physical size.
To deal with that, Bitcoin Core includes a function,
MallocUsage(),
that approximates this conversion. Its argument is an allocation size,
and it returns the corresponding physical size.
That source file, memusage.h,
includes many overloads of the function DynamicUsage() across
the various data types that we might be allocating somewhere
in the system. They all make use of MallocUsage().
The pool memory resource (added by PR #25325) adds a new
DynamicUsage()
overload (version) that computes the overall coins cache size. This allows us to stay
within the configured cache size.
In the master branch (without this PR), why does the
DynamicUsage()
overload have so many templated arguments?
(Hint: compare it to the overload immediately above it, on line 170.)
How did this DynamicUsage() overload work on master? What are the various
values being added together in this PR?
Specifically, why is m.bucket_count() part of the DynamicUsage() calculation?
Why isn’t the memory for the bucket allocation already accounted
for in the resource “chunks”?
In this PR, where is the DynamicUsage() calculation moved to, and why is m.bucket_count() no longer needed?
What is the advantage of not referencing m.bucket_count()?
<LarryRuane> IRC isn't the most interactive medium for these discussions, so feel free to bring up earlier topics or continue earlier conversations even if we've moved on!
<LarryRuane> So, after writing today's notes and questions, it occurred to me that some here might not be familiar with lower-level structures like `unordered_map` in c++, especially if you've come from higher-level languages like Ruby or Python
<LarryRuane> So in bitcoin core, a super important data structure is the "coins cache" ... this is a map (we use the standard library `unordered_map`) that lets us determine if a transaction's input refers to a valid, unspent output
<LarryRuane> and for each one, we look at all its inputs, and want to see if the output it references (the reference is called a `COutpoint`) is exists, and is unspent
<LarryRuane> I think of that name, COutpoint, as meaning it's a "pointer" to an earlier transaction's output ... but not in the usual sense of a memory pointer,
<LarryRuane> If the transaction is valid, we ADD all of its outputs (txid, output index) to this map, so they are available to be referenced by later transactions that want to spend those outputs
<LarryRuane> so, even though all the unspent outputs (UTXOs) are saved on disk (in the `chainstate` directory within your data directory, in LevelDB format), the most recent ones are saved in memory -- in this very unordered_map we're talking about today
<LarryRuane> we'd like this to happen as often as possible, because it makes IBD much faster than it would otherwise be, because reading from disk is like 2 orders of magnitude, or more, slower than just reading from memory
<kevkevin> ahh ok so the unordered map is just the latest set of UTXO's, is there a max size to this unordered list and if so is that max size configurable?
<LarryRuane> kevkevin: great question, the `-dbcache` setting in your configuration, default 450 MiB (450*1024*1024) determines the max mem size for this map, plus some other memory caches,
<LarryRuane> and also (I had to discover all this myself recently), the mempool cache is used for this map during IBD, and it has a separate config setting, `-maxmempool` i think, and its default is 300 MiB
<LarryRuane> this 750 is quite small for many machines, so if you're about to do IBD, and you have a fairly high end system, increase either of those settings, and it will be MUCH faster
<LarryRuane> so like i have a Raspi (myNode), and it has only 4 GB total memory, so probably best not to change its settings (their default config actually does change it slightly)
<LarryRuane> and each entry contains (in this case of the coins map) the map key (a `COutpoint` like we described) and a `Coin` which is the amount of this output and its `scriptPubKey` .. did I miss anything, @stickies-v ?
<LarryRuane> so again, we're validating a tx... we loop across its inputs ... each one contains a `COutpoint` ... we look in the map using this `COutpoint` (which remember is a txid and output index) ...
<LarryRuane> kevkevin: yes, we read the disk! if this output was created a long time ago, it won't be in memory but may be on disk, so we have to read the disk (slow)
<LarryRuane> so when we're validating a block, we're creating these UTXO entries in the memory map ... but let's say that the LAST transaction in the block is invalid!
<LarryRuane> it's pretty cool how these layers work but it took me a while to figure it out, and I'm still not very knowledgable on it, see src/coins.cpp
<LarryRuane> I think this relates to what some of you may know much better than me, functional programming ... where data structures are much more often immutable, and you apply changes atomically once everything is validated or no errors, else discard
<LarryRuane> Okay so back to unordered_map ... it's faster than an (ordered) `std::map` ... the tradeoff being that a `std::map` allows you to iterate the entries in key-order, but at the expense of time and (maybe) storage
<LarryRuane> I think there are some `std::map`s in bitcoin core that could be `std::unordered_map` instead, but were coded before `std::unordered_map` existed! It was added only more recently
<LarryRuane> So anyway, an unordered_map has this bucket array, and that has to be accounted for when we try to figure out how much actual memory this map is consuming, and this (finally!) relates to this PR
<LarryRuane> So let's see... sorry this is all kind of disorganized, any more questions about this coins map (maps) or the entries they contain? did I miss anything?
<LarryRuane> but this layer in between (you can think of it as) makes the unordered_map's allocations more efficient in terms of both speed and (pyysical) memory usage, even though the unordered_map (which we don't control) is doing exactly the same memory allocations
<LarryRuane> but I think mainly what it did is allowed MORE coins entries to be cached in memory before we hit that physical memory limit, so there is a higher hit ratio (the percentage of times we look for a UTXO in memory and it's present, don't have to read disk)
<LarryRuane> so actually, those mempool and block maps also use this new memory allocator, but there's probably only a minor benefit, because there's small compared to the main one
<LarryRuane> okay, whew, sorry this is so messy, but finally, what this PR does is to improve the way we calculate physical memory usage for this (well, any) coins utxo map
<LarryRuane> (and be aware, this really isn't an important PR, I'm not sure it will even be merged! but I saw it as a good excuse for discussing this important memory data structure!)
<LarryRuane> gosh we're almost out of time, let me just throw it open to anyone, does anyone have answers to any of the questions on https://bitcoincore.reviews/27748?
<LarryRuane> Seems like the `std::unordered_map` implementation should use the custom memory allocator to allocate the bucket array... so then its physical memory usage would be accounted for in the "chunks" (see the line just above, like 185)
<LarryRuane> in that case, beyond a certain rather small allocation size, the custom allocator just does a normal system allocation (i.e. `new` in c++)
<LarryRuane> in this PR (that we're reviewing) we just keep track of any system allocations that WE (the custom allocator) do, and account for the bucket array that way, without ever having to call `m.bucket_count()`