Merge bitcoin/bitcoin#28280: Don't empty dbcache on prune flushes: >30% faster IBD

589db872e116779ab9cae693171ac8a8c02d9923 validation: don't erase coins cache on prune flushes (Andrew Toth)
0e8918755f725b6269ed2be5a0b46f1611233515 Add linked-list test to CCoinsViewCache::SanityCheck (Pieter Wuille)
05cf4e18758618bb493d26014d3a9c89bf28d898 coins: move Sync logic to CoinsViewCacheCursor (Andrew Toth)
7825b8b9aeceb4ff607650cdc9c49e5de9c7719f coins: pass linked list of flagged entries to BatchWrite (Andrew Toth)
a14edada8a051e280af6fedd5130be40247e2d7a test: add cache entry linked list tests (Andrew Toth)
24ce37cb867b95e86d9fd4e50858d64ee8a59abf coins: track flagged cache entries in linked list (Andrew Toth)
58b7ed156d5993b69375bb455b03bd8b17f64fa4 coins: call ClearFlags in CCoinsCacheEntry destructor (Andrew Toth)
8bd3959feaa0e71585bc5e0976f584fb06ee6d14 refactor: require self and sentinel parameters for AddFlags (Andrew Toth)
75f36d241d2a344c5c4ce2c80250bdde91b3295e refactor: add CoinsCachePair alias (Andrew Toth)
f08faeade2f99ae1de6f3c481697541cc16186c7 refactor: move flags to private uint8_t and rename to m_flags (Andrew Toth)
4e4fb4cbabcc10e723534f5f80f3e3cf09f6ca50 refactor: disallow setting flags in CCoinsCacheEntry constructors (Andrew Toth)
8737c0cefa6ec49a4d17d9bef9e5e1a7990af1ac refactor: encapsulate flags setting with AddFlags and ClearFlags (Andrew Toth)
9715d3bf1e4013476539f1523a6b54d2055c32c6 refactor: encapsulate flags get access for all other checks (Andrew Toth)
df34a94e57659c31873c26c86a8de5a032400061 refactor: encapsulate flags access for dirty and fresh checks (Andrew Toth)

Pull request description:

  Since https://github.com/bitcoin/bitcoin/pull/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`.

  |  | prune | dbcache | time | max RSS | speedup |
  |-----------:|----------:|------------:|--------:|-------------:|--------------:|
  | master | 550 | 16384 | 8:52:57 | 2,417,464k | - |
  | branch | 550 | 16384 | 6:01:00 | 16,216,736k | 32% |
  | branch | 550 | 450 | 8:05:08 | 2,818,072k | 8.8% |
  | master | 10000 | 5000 | 8:19:59 | 2,962,752k | - |
  | branch | 10000 | 5000| 5:56:39 | 6,179,764k | 28.8% |
  | master | 0 | 16384 | 4:51:53 | 14,726,408k | - |
  | branch | 0 | 16384 | 4:43:11 | 16,526,348k | 2.7% |
  | master | 0 | 450 | 7:08:07 | 3,005,892k | - |
  | branch | 0 | 450 | 6:57:24 | 3,013,556k |2.6%|

  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](https://github.com/bitcoin/bitcoin/pull/15265#issuecomment-457720636).

  Fixes https://github.com/bitcoin/bitcoin/issues/11315.

ACKs for top commit:
  paplorinc:
    ACK 589db872e116779ab9cae693171ac8a8c02d9923
  sipa:
    reACK 589db872e116779ab9cae693171ac8a8c02d9923
  achow101:
    ACK 589db872e116779ab9cae693171ac8a8c02d9923
  mzumsande:
    re-ACK 589db872e116779ab9cae693171ac8a8c02d9923

Tree-SHA512: 23b2bc01c83edacb5b39aa60bb0b766de9a74ce17f0c59bf13b97b4328a7b758ad9aff6581c3ca88e2973f7658380651530d497444f48d6e22ea0bfc51cc921d

2 files changed, 13 insertions, 7 deletions

diff --git a/src/test/fuzz/coins_view.cpp b/src/test/fuzz/coins_view.cpp
index 41c971c237..368c69819a 100644
--- a/src/test/fuzz/coins_view.cpp
+++ b/src/test/fuzz/coins_view.cpp
@@ -120,12 +120,15 @@ FUZZ_TARGET(coins_view, .init = initialize_coins_view)
                 random_mutable_transaction = *opt_mutable_transaction;
             },
             [&] {
+                CoinsCachePair sentinel{};
+                sentinel.second.SelfRef(sentinel);
+                size_t usage{0};
                 CCoinsMapMemoryResource resource;
                 CCoinsMap coins_map{0, SaltedOutpointHasher{/*deterministic=*/true}, CCoinsMap::key_equal{}, &resource};
                 LIMITED_WHILE(good_data && fuzzed_data_provider.ConsumeBool(), 10'000)
                 {
                     CCoinsCacheEntry coins_cache_entry;
-                    coins_cache_entry.flags = fuzzed_data_provider.ConsumeIntegral<unsigned char>();
+                    const auto flags{fuzzed_data_provider.ConsumeIntegral<uint8_t>()};
                     if (fuzzed_data_provider.ConsumeBool()) {
                         coins_cache_entry.coin = random_coin;
                     } else {
@@ -136,11 +139,14 @@ FUZZ_TARGET(coins_view, .init = initialize_coins_view)
                         }
                         coins_cache_entry.coin = *opt_coin;
                     }
-                    coins_map.emplace(random_out_point, std::move(coins_cache_entry));
+                    auto it{coins_map.emplace(random_out_point, std::move(coins_cache_entry)).first};
+                    it->second.AddFlags(flags, *it, sentinel);
+                    usage += it->second.coin.DynamicMemoryUsage();
                 }
                 bool expected_code_path = false;
                 try {
-                    coins_view_cache.BatchWrite(coins_map, fuzzed_data_provider.ConsumeBool() ? ConsumeUInt256(fuzzed_data_provider) : coins_view_cache.GetBestBlock());
+                    auto cursor{CoinsViewCacheCursor(usage, sentinel, coins_map, /*will_erase=*/true)};
+                    coins_view_cache.BatchWrite(cursor, fuzzed_data_provider.ConsumeBool() ? ConsumeUInt256(fuzzed_data_provider) : coins_view_cache.GetBestBlock());
                     expected_code_path = true;
                 } catch (const std::logic_error& e) {
                     if (e.what() == std::string{"FRESH flag misapplied to coin that exists in parent cache"}) {
diff --git a/src/test/fuzz/coinscache_sim.cpp b/src/test/fuzz/coinscache_sim.cpp
index 648e96b4a0..8e717e96b4 100644
--- a/src/test/fuzz/coinscache_sim.cpp
+++ b/src/test/fuzz/coinscache_sim.cpp
@@ -172,13 +172,13 @@ public:
     std::unique_ptr<CCoinsViewCursor> Cursor() const final { return {}; }
     size_t EstimateSize() const final { return m_data.size(); }
 
-    bool BatchWrite(CCoinsMap& data, const uint256&, bool erase) final
+    bool BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) final
     {
-        for (auto it = data.begin(); it != data.end(); it = erase ? data.erase(it) : std::next(it)) {
-            if (it->second.flags & CCoinsCacheEntry::DIRTY) {
+        for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
+            if (it->second.IsDirty()) {
                 if (it->second.coin.IsSpent() && (it->first.n % 5) != 4) {
                     m_data.erase(it->first);
-                } else if (erase) {
+                } else if (cursor.WillErase(*it)) {
                     m_data[it->first] = std::move(it->second.coin);
                 } else {
                     m_data[it->first] = it->second.coin;