Don’t empty dbcache on prune flushes: >30% faster IBD #28280

Since #17487 we no longer need to clear the coins cache when syncing to disk. A warm coins cache significantly speeds up block connection, and only needs to be fully flushed when nearing the dbcache limit.

For frequent pruning flushes there’s no need to empty the cache and kill connect block speed. However, simply using Sync in place of Flush actually slows down a pruned full IBD with a high dbcache value. This is because as the cache grows, sync takes longer since every coin in the cache is scanned to check if it’s dirty. For frequent prune flushes and a large cache this constant scanning starts to really slow IBD down, and just emptying the cache on every prune becomes faster.

To fix this, we can add two pointers to each cache entry and construct a doubly linked list of dirty entries. We can then only iterate through all dirty entries on each Sync, and simply clear the pointers after.

With this approach a full IBD with dbcache=16384 and prune=550 was 32% faster than master. For default dbcache=450 speedup was ~9%. All benchmarks were run with stopatheight=800000.

While the 2 pointers add memory to each cache entry, it did not slow down IBD. For non-pruned IBD results were similar for this branch and master. When I performed the initial IBD, the full UTXO set could be held in memory when using the max dbcache value. For non-pruned IBD with max dbcache to tip ended up using 12% more memory, but it was also 2.7% faster somehow. For smaller dbcache values the dbcache limit is respected so does not consume more memory, and the potentially more frequent flushes were not significant enough to cause any slowdown.

For reviewers, the commits in order do the following: First 4 commits encapsulate all accesses to flags on cache entries, and then the 5th makes flags private. Commits refactor: add CoinsCachePair alias to coins: call ClearFlags in CCoinsCacheEntry destructor create the linked list head nodes and cache entry self references and pass them into AddFlags. Commit coins: track flagged cache entries in linked list actually adds the entries into a linked list when they are flagged DIRTY or FRESH and removes them from the linked list when they are destroyed or the flags are cleared manually. However, the linked list is not yet used anywhere. Commit test: add cache entry linked list tests adds unit tests for the linked list. Commit coins: pass linked list of flagged entries to BatchWrite uses the linked list to iterate through DIRTY entries instead of using the entire coins cache. Commit validation: don't erase coins cache on prune flushes uses Sync instead of Flush for pruning flushes, so the cache is no longer cleared.

Inspired by this comment.

Fixes #11315.

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #30326 (optimization: Reduce cache lookups in CCoinsViewCache::FetchCoin by paplorinc)
• #28216 (fuzz: a new target for the coins database by darosior)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Also, I’m curious how you are performing your benchmarks and generating all those nice graphs. Do you mind sharing what tools you use?

At the time I had a spare and otherwise idle machine set up I could use. I don’t have the bash script at hand but IIRC I had a merge base (MB) and a pull-request (PR) binary I’d run with different prune and dbcache configurations. After each run, the script would rename and move the debug log (with extra -debug=coindb -debug=prune) to a separate folder. After all runs were done, I loaded the debug logs into the following Jupyter notebooks to parse the debug logs and to generate the graphs. For anyone revisiting this, these are the relevant comments #20827 (comment), #20827 (comment), and #20827 (comment) for my setup and results.

I’ve uploaded the jupyter nodebooks here https://gist.github.com/0xB10C/89c2903290cfb1840792d41dcd079646. The first was used for a partial IBD from 500k-600k and the second one with a full IBD. Both times syncing from a local node on the same host. The notebooks expect the debug log files with the name debug_{binary}_{cset}_{run}.log where {binary} is either MB or PR, {cset} is an integer specifying the configuration set (pruning and dbcache parameter), and {run} is an integer numbering the run of this binary-cset combination if I did multiple. Feel free to remix and share in any way you want. Keep in mind that parsing logs is quite fragile as log message format can change. Feel free to reach out if there are questions.

Bench running now, should have some results in the next day or so.

0$ ( bitcoinperf --no-teardown bench-pr --num-blocks 30_000 --run-id no-flush-on-prune \
1    --bitcoind-args='-dbcache=4000 -prune=550' --run-count 3 28280 && \
2    pushover 'Bench for andrewtoth SUCCEEDED!' ) || \
3  pushover 'Bench for andrewtoth failed'

Rebased, ran the following benchmark using hyperfine. Sync to block 800k 3 times on master commit and the last commit of this branch (I updated the commit recently, but no code changes only commit order changes to satisfy CI), dbcache=4000 and prune=550:

0hyperfine \
1--export-markdown ~/bench.md \
2--show-output --parameter-list commit 498994b6f55d04a7940f832e7fbd17e5acdaff15,216bd93138a46cdfa66523878a36d0e634476079 \
3--prepare 'git checkout {commit} && make -j$(nproc) src/bitcoind; sync; sudo /sbin/sysctl vm.drop_caches=3; rm -rf ~/.bitcoin/blocks; rm -rf ~/.bitcoin/chainstate;' \
4-M 3 './src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=<local_node> -stopatheight=800000'

Results from ~/bench.md:

The second commit is this branch, so it runs 24% faster than master. @jamesob I suppose 30k blocks is not enough to appreciate the effect of syncing with a full cache?

I didn’t think this through yet, but this might be an alternative way to achieve the same thing: Instead of the double linked list, split the cacheCoins map up into 4 different maps, one map for each flag setting, e.g. as a std::array<CCoinMap, 4> m_cache_coins_per_flag;. Index is the flag, e.g. m_cache_coins_per_flag[FRESH | DIRTY] to get the map with all entries that are fresh & dirty. Instead of setting a flag & linking the list, use the unordered_map’s auto node = extract(...) and insert(std::move(node)) to move the entry to the corresponding map. This only relinks the unordered_map node and causes no allocation, pointers to the entry stay valid.

This approach would have a few advantages:

• Less memory usage: no m_flag member is needed that actually required 8 bytes due to alignment, no 2 pointers needed for interlinking, and multiple maps means overall bucket sizes will stay smaller.
• processing the maps might be faster: iteration is fast because e.g. skipping non-dirty entries is trivial (they are in a different map). There might be a hashing overhead though from extract() and insert().

For this to work, all 4 maps need to use the same m_cache_coins_memory_resource (insert() into a different map where the allocator doesn’t compare equal is undefined behavior).

@martinus something similar was mentioned in #15265 (comment). However, with your approach every access would require 4 lookups.

Ha, of course; I didn’t think about that at all.

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/22665800478

@0xB10C rebased after #20827 was merged, and ran the following benchmark:

 0hyperfine --export-markdown ~/bench.md --show-output --parameter-list commit 015ac13dcc964a31ef06dfdb565f88f901607f0e,25bdbc7f340884b3ab871c7948a4f2693037b871 --prepare 'git checkout {commit} && make -j$(nproc) src/bitcoind; sync; sudo /sbin/sysctl vm.drop_caches=3; rm -rf ~/.bitcoin/blocks; rm -rf ~/.bitcoin/chainstate;' -M 3 './src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=<local network node ip> -stopatheight=800000'
 1
 2...
 3
 4Benchmark 1: ./src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=<local network node ip> -stopatheight=800000 (commit = 015ac13dcc964a31ef06dfdb565f88f901607f0e)
 5
 6  Time (mean ± σ):     27241.365 s ± 33.693 s    [User: 34791.898 s, System: 7357.098 s]
 7  Range (min … max):   27202.978 s … 27266.037 s    3 runs
 8
 9Benchmark 2: ./src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=<local network node ip> -stopatheight=800000 (commit = 25bdbc7f340884b3ab871c7948a4f2693037b871)
10
11  Time (mean ± σ):     22153.568 s ± 37.663 s    [User: 27818.681 s, System: 4309.878 s]
12  Range (min … max):   22119.682 s … 22194.118 s    3 runs
13 
14Summary
15  ./src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=192.168.2.13 -stopatheight=800000 (commit = 25bdbc7f340884b3ab871c7948a4f2693037b871) ran
16    1.23 ± 0.00 times faster than ./src/bitcoind -dbcache=4000 -prune=550 -printtoconsole=0 -connect=192.168.2.13 -stopatheight=800000 (commit = 015ac13dcc964a31ef06dfdb565f88f901607f0e)

So this is 23% faster than master when using dbcache=4000, prune=550. (I just rebased again but 015ac13dcc964a31ef06dfdb565f88f901607f0e is master and 25bdbc7f340884b3ab871c7948a4f2693037b871 is my branch). @sipa thank you for your review! Addressed your nits and added more comments about flagged entries.

Rebased and ran some faster benchmarks, 2 each but only until 400k. Will do some more going to 800k.

Command was

 0hyperfine \
 1--export-markdown ~/bench.md \
 2--show-output \
 3--parameter-list commit 0d509bab45d292caeaf34600e57b5928757c6005,499f1f029a265fbeb4824e5cb84726f82ca2824b \
 4--parameter-list dbcache 450,16384 \
 5--parameter-list prune 550,0 \
 6--prepare 'git checkout {commit} && \
 7make -j$(nproc) src/bitcoind; \
 8sync; sudo /sbin/sysctl vm.drop_caches=3; \
 9rm -rf /home/user/.bitcoin/blocks; \
10rm -rf /home/user/.bitcoin/chainstate;' \
11-M 2 \
12'echo '{commit}' && \
13./src/bitcoind -datadir=/home/user/.bitcoin \
14-dbcache={dbcache} \
15-prune={prune} \
16-printtoconsole=0 \
17-connect=<local node> \
18-stopatheight=400000'

Ran benchmarks to 800k blocks, 2 times each. As expected, results are very good when running pruned. When running non-pruned with default dbcache, however, master was 1% faster. I think this slowdown is negligible though and the improvements to syncing with pruning enabled make this worth the changes here. Also, potential improvements like #28945 will make up for it.

For frequent pruning flushes there’s no need to empty the cache and kill connect block speed. However, simply using Sync in place of Flush actually slows down a pruned full IBD with a high dbcache value. This is because as the cache grows, sync takes longer since every coin in the cache is scanned to check if it’s dirty. For frequent prune flushes and a large cache this constant scanning starts to really slow IBD down, and just emptying the cache on every prune becomes faster.

To fix this, we can add two pointers to each cache entry and construct a doubly linked list of dirty entries. We can then only iterate through all dirty entries on each Sync, and simply clear the pointers after.

Perhaps I’m missing something, but it seems to me that the obvious solution to this problem is to have BatchWrite always delete dirty entries and clear the flags on all entries, rather than implementing a whole new data structure? BatchWrite already iterates the entire cache anyways, so it would make sense to me that we can consolidate all of the operations that occur for each cache entry.

@achow101 That works, but it misses the point. If you delete the dirty entries on a prune flush, then those entries need to be re-read from disk when they are (likely soon) spent.

Sorry, I meant clear the Dirty and spent ones. Basically just move the stuff that Sync() does into the loop that BatchWrite is doing.

Am I right that after this change (or alternatives which let BatchWrite just iterate dirty/fresh entries), it would be possible to (perhaps dramatically) reduce the periodic flush time, so that after IBD, we basically always have a mostly non-dirty cache? Such a change could be made today of course, but the cost of iterating the entire cache every time would add up quickly.

I believe you are right, but I’m unsure what the benefit is that you see. From my understanding, the periodic flushes are solely to prevent data loss in case of unclean shutdown (otherwise, flushing from filling the dbcache or flushing from shutting down cleanly prevent data loss). With a 24 hour periodic flush schedule and #15218, the most that is at risk is ~144 blocks worth of data?

If you are talking about periodic flushes during IBD though, that might be a benefit that could obviate #15218 and properly fix #11600. If we reduce the periodic flush interval to an hour or so, then only an hour or so of IBD data would be at risk of rolling back. This would of course mean that there is less opportunity for the cache to delete FRESH & DIRTY entries on spend so they never have to hit the disk, so it would be less performant. But it would still keep the cache for connecting blocks quickly.

BatchWrite already iterates the entire cache anyways @achow101 I think this is what you might not be clear about. BatchWrite iterates the entire cache, but this patch does not. After this patch BatchWrite only iterates flagged entries, which is a much smaller subset of the cache.

I tried moving everything in the loop in Sync into BatchWrite, along with cachedCoinsUsage so it can be decremented as we delete spent coins from the child cache, and it looks like it will take many times longer to sync with dbcache=16384 prune=550 than current master. So I don’t think that’s a viable alternative solution to what is proposed here.

@achow101 I think this is what you might not be clear about. BatchWrite iterates the entire cache, but this patch does not. After this patch BatchWrite only iterates flagged entries, which is a much smaller subset of the cache.

Yes, that was what I was missing. It just wasn’t clear to me from the description that this was implemented as another performance improvement in addition to clearing dirty and spent UTXOs.

A non-pruned IBD with full dbcache to tip ended up using 12% more memory, but it was also 2.7% faster somehow.

I’m not sure if I understand this, is this still the case? Why would a node use more memory after this pull? Shouldn’t the 2 added pointers be included in the dbcache accounting, resulting in more frequent flushes due to the cache filling up faster, but not in an increase in memory when the cache is full?

Also, potential improvements like #28945 will make up for it.

It seems #28945 (comment) was abandoned since

A non-pruned IBD with full dbcache to tip ended up using 12% more memory, but it was also 2.7% faster somehow.

I’m not sure if I understand this, is this still the case? Why would a node use more memory after this pull? Shouldn’t the 2 added pointers be included in the dbcache accounting, resulting in more frequent flushes due to the cache filling up faster, but not in an increase in memory when the cache is full?

This is no longer the case. When I did the initial benchmarks the full UTXO set could be stored in memory, and so a full IBD on mainnet would be 14.7 GB for master and 16.5 GB for this pull. Today both master and this pull will hit the max limit and flush at some point, so their memory usage should be near identical. You are correct that if the dbcache limit is set below the maximum UTXO set size then this pull will not use more memory.

For clarity, this pull only uses more memory if the entire IBD can occur without a single flush. What I meant in the description is this pull uses more memory when the entire utxo set is stored in memory and never flushed.

This pull could use more memory again on mainnet if #28358 is merged, and this pull will use more memory on other chains than mainnet if the UTXO size is smaller than the dbcache setting.

Also, potential improvements like #28945 will make up for it.

It seems #28945 (comment) was abandoned since

In my recent benchmarks it was again slightly faster on this branch for default dbcache and no pruning. So I think this PR is essentially the same.

Fantastic change, would be helpful if you could make it a bit more digestible by separating it into smaller commits (especially splitting high-risk changes from low-risk refactoring), explaining the changes in commit messages.

Thank you @paplorinc! I did try initially to separate the changes more. However, I found the third commit has to have all those changes done in one commit otherwise the test-all-commits CI job will fail. Changing only parts of it can break the tests, and break building the fuzz targets. I will explore to see if I can break it down any further and keep CI happy.

Changing only parts of it can break the tests

I usually try to recreate every line, after I have all the changes by interactively rebasing the current state and adding small refactoring under the current commit. E.g. these could be separate commits doing a single thing:

• renaming bool erase to bool will_erase
• changing it->second.flags usages to it->second.GetFlags() (again, without change in behavior, but you could also add another commit after this which extracts the usages and returns it->second.IsFresh() instead, making commits after it easier to read)
• changing it->second.flags |= to use it->second.AddFlags(CCoinsCacheEntry::DIRTY); (without any change in behavior, just doing it in a method)
• changing iterators to the new linked list - without any other change in logic.

etc, I think you got the picture. By extracting these to separate trivial commits (which are followed by high risk changes, done in as few lines as possible without any refactorings in the way), we can concentrate on the difficult ones (which are a lot simpler and in separate commits themselves).

Thanks!

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/26841759796

@mzumsande @paplorinc thank you very much for your reviews! I’ve rebased and updated with all your suggested changes.

I also updated the commits for easier review. First, flags is encapsulated whenever used, then made private. Then linked list head and self references are added to AddFlags, followed by AddFlags and ClearFlags actually maintaining a linked list of entries. Lastly, the linked list is used for BatchWrite instead of passing the entire map of entries.

This kept me up at night, we should be able to get rid of m_prev by doing insertions and deletions slightly differently:

• we’d have an immutable SENTINEL value always serving as the last element (instead of nullptr);
• insertion would always be in front of the previous element, which would serve as the new head (iterating from which will always get us to the SENTINEL);
• deletion would copy the content (node, flag and next) of the next node instead (unless it’s a SENTINEL), and dispose of that instead.

Something like this:

 0diff --git a/src/coins.h b/src/coins.h
 1--- a/src/coins.h	(revision c36363f6b24c7ab2afe198d9855f507ddf096e1f)
 2+++ b/src/coins.h	(date 1719755615706)
 3@@ -123,11 +123,11 @@
 4      * parent cache, the FRESH-but-not-DIRTY coin will be tracked by the linked
 5      * list and deleted when Sync or Flush is called on the CCoinsViewCache.
 6      */
 7-    CoinsCachePair* m_prev{nullptr};
 8     CoinsCachePair* m_next{nullptr};
 9     uint8_t m_flags{0};
10 
11 public:
12+    static CoinsCachePair SENTINEL;
13     Coin coin; // The actual cached data.
14 
15     enum Flags {
16@@ -154,22 +154,19 @@
17     //! Adding a flag also requires a self reference to the pair that contains
18     //! this entry in the CCoinsCache map and a reference to the head of the
19     //! flagged pair linked list.
20-    inline void AddFlags(uint8_t flags, CoinsCachePair& self, CoinsCachePair& head)
21+    inline void AddFlags(uint8_t flags, CoinsCachePair& next)
22     {
23         if (!m_flags && flags) {
24-            m_prev = &head;
25-            m_next = head.second.m_next;
26-            if (m_next) m_next->second.m_prev = &self;
27-            head.second.m_next = &self;
28+            m_next = &next;
29         }
30         m_flags |= flags;
31     }
32     inline void ClearFlags()
33     {
34-        if (m_flags) {
35-            if (m_next) m_next->second.m_prev = m_prev;
36-            m_prev->second.m_next = m_next;
37-            m_prev = m_next = nullptr;
38+        if (m_flags && m_next != &SENTINEL) {
39+            coin = std::move(m_next->second.coin);
40+            m_flags = m_next->second.m_flags;
41+            m_next = m_next->second.m_next;
42         }
43         m_flags = 0;
44     }

What do you think?

we should be able to get rid of m_prev by doing insertions and deletions slightly differently

But we can’t move the coin from the next entry to us. The coinsCache map will still point to the next entry for that outpoint.

The coinsCache map will still point to the next entry for that outpoint

Yeah, but we can update the map in constant time, right? Do you think that would measurably slow down execution? Could the memory savings of one less pointer allow us to increase cache hit rate, or am I completely off here?

Oh wait, we only need random access for deletion! Otherwise we can clear the flags on iteration!

Brilliant! I think this could work then.

@andrewtoth Just high-level brainstorming, and I really don’t want to push this PR into something more complex than necessary.

But would it be possible to have a map from outpoints to entries, with a singly-linked list through the entries, such that *(map[key].m_prev) stores the data for key key, rather than map[key] itself?

But would it be possible to have a map from outpoints to entries, with a singly-linked list through the entries, such that *(map[key].m_prev) stores the data for key key, rather than map[key] itself? @sipa Sorry I’m not sure I follow. What does *(map[key].m_prev) store?

@andrewtoth

So the data structure we want has (a) an index on COutPoint and (b) a single-linked list that stores an iteration order. The issue (I think, I haven’t followed in detail) is that we need the ability to delete entries found through the (a) index, and if we naively do that, the entry that (b) points to the deleted entry will have its prev pointer invalidated.

My suggestion is “shifting” the values of the map by one. map[key] stores the UTXO for the entry that is (b)-after key, so the UTXO for outpoint key is found in *(map[key]->m_prev) instead. This means an extra indirection on lookup (which may make the whole thing already not worth it from a performance perspective), but it does mean entries can be deleted (to delete key, do { auto to_del = map[key]->m_prev; map[key]->m_prev = to_del->m_prev; delete(to_del); }.

@sipa thank you for the suggestion! I think it’s missing the fact that we want entries in the map to possibly not belong to the linked list. So we want to clear the linked list after a non-erasing flush, but leave the map intact otherwise. I don’t think that’s possible with just this data structure. We would need 2 parallel maps, one with unflagged entries and one with dirty entries. I’m not sure if that would be more performant with 2 lookups for every access? I think if we have 2 maps we can also just get rid of the linked list entirely.

You did mention the 2 maps idea a while ago #15265 (comment) and @martinus had a similar idea earlier in this PR discussion.