index: block filters sync, reduce disk read operations by caching last header

furszy commented at 12:42 pm on November 28, 2023: member

Work decoupled from #26966 per request.

The aim is to remove an unnecessary disk read operation that currently takes place with every new arriving block (or scanned block during background sync). Instead of reading the last filter header from disk merely to access its hash for constructing the next filter, this work caches it, occupying just 32 more bytes in memory.

Also, reduces cs_main lock contention during the index initial sync process. And, simplifies the indexes initialization and shutdown procedure.

Testing Note: To compare the changes, added a pretty basic benchmark in the second commit. Alternatively, could also test the changes by timing the block filter sync from scratch on any network; start the node with -blockfilterindex and monitor the logs until the syncing process finish.

Local Benchmark Results:

*Master (c252a0fc0f4dc7d262b971a5e7ff01508159193b):

ns/op	op/s	err%	total	benchmark
132,042,516.60	7.57	0.3%	7.79	`BlockFilterIndexSync`

*PR (43a212cfdac6c64e82b601c664443d022f191520):

ns/op	op/s	err%	total	benchmark
126,915,841.60	7.88	0.6%	7.51	`BlockFilterIndexSync`

DrahtBot commented at 12:42 pm on November 28, 2023: contributor

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.

Type	Reviewers
ACK	Sjors, TheCharlatan, andrewtoth, achow101
Concept ACK	brunoerg

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:

#29432 (Stratum v2 Template Provider (take 3) by Sjors)
#24539 (Add a “tx output spender” index by sstone)
#24230 (indexes: Stop using node internal types and locking cs_main, improve sync logic by ryanofsky)

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.

DrahtBot added the label UTXO Db and Indexes on Nov 28, 2023

Sjors commented at 2:09 pm on November 28, 2023: member

Ran bench on MacBook Pro 2019 (2,3 GHz 8-Core Intel Core i9, SSD):

0src/bench/bench_bitcoin -filter=BlockFilterIndexSync

Before (486c71bc707f5765fc6698a746cf221bab1ac357):

ns/op	op/s	err%	total	benchmark
336,034,835.00	2.98	0.6%	19.86	`BlockFilterIndexSync`

After:

ns/op	op/s	err%	total	benchmark
339,403,771.80	2.95	0.6%	19.98	`BlockFilterIndexSync`

Not seeing any improvement in the bench. Haven’t tried running the full indexer though.

furszy commented at 2:26 pm on November 28, 2023: member

Ran bench on MacBook Pro 2019 (2,3 GHz 8-Core Intel Core i9, SSD):
0src/bench/bench_bitcoin -filter=BlockFilterIndexSync
Before (486c71b):

ns/op op/s err% total benchmark 336,034,835.00 2.98 0.6% 19.86 BlockFilterIndexSync After:

ns/op op/s err% total benchmark 339,403,771.80 2.95 0.6% 19.98 BlockFilterIndexSync Not seeing any improvement in the bench. Haven’t tried running the full indexer though.

Probably, it is because the benchmarks, same as the unit tests, create temp directories. Which may be faster to access than regular directories. See #26684#pullrequestreview-1566578747. I should verify if the bench framework accepts custom paths so we can test this differently. Most likely, it doesn’t and we should add the feature.

Also, you could increase the CHAIN_SIZE variable inside the benchmark. Go from 600, to 3000 or more. The time should grow up linearly. I didn’t do it merely because the bench would take longer to setup but the difference should be evident with a longer chain.

in src/bench/index_blockfilter.cpp:12 in 486c71bc70 outdated

 8+#include <node/chainstate.h>
 9+#include <node/context.h>
10+#include <test/util/index.h>
11+#include <test/util/mining.h>
12+#include <test/util/setup_common.h>
13+#include <util/strencodings.h>

TheCharlatan commented at 3:13 pm on November 29, 2023:

Nit: Can you make this new file IWYU-correct?

in src/bench/index_blockfilter.cpp:5 in 486c71bc70 outdated

0@@ -0,0 +1,44 @@
1+// Copyright (c) 2023-present The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or https://www.opensource.org/licenses/mit-license.php.
4+
5+#include <bench/bench.h>

TheCharlatan commented at 3:24 pm on November 29, 2023:

Nit: Put this include on its own line (like e.g. in bip324_ecdh.cpp), or fix the include order.

furszy commented at 2:06 am on November 30, 2023:

done

in src/index/base.cpp:173 in fe6a520aa8 outdated

184+                Commit();
185+                break;
186             }
187+            if (pindex_next->pprev != pindex && !Rewind(pindex, pindex_next->pprev)) {
188+                FatalErrorf("%s: Failed to rewind index %s to a previous chain tip",
189+                           __func__, GetName());

TheCharlatan commented at 3:25 pm on November 29, 2023:

Nit: There is a whitespace issue at the start of this line.

furszy commented at 2:08 am on November 30, 2023:

fixed

TheCharlatan approved

TheCharlatan commented at 3:33 pm on November 29, 2023: contributor

ACK 63ef83d72a979e9e557eec9fe87c2795a963dedb

furszy force-pushed on Nov 30, 2023

TheCharlatan approved

TheCharlatan commented at 5:01 pm on November 30, 2023: contributor

Re-ACK b19585e00a52c0b571e70ddb8f7c996d598c3435

luke-jr commented at 2:37 am on December 5, 2023: member

Probably, it is because the benchmarks, same as the unit tests, create temp directories. Which may be faster to access than regular directories.

Is it, though? I would think the OS should have this cached regardless?

furszy commented at 8:24 pm on December 5, 2023: member

Probably, it is because the benchmarks, same as the unit tests, create temp directories. Which may be faster to access than regular directories.

Is it, though? I would think the OS should have this cached regardless?

We will know it soon. I’m working on a way to test it inside #26564#pullrequestreview-1761271269.

But, it seems to be an orthogonal topic. Regardless of the result, which could vary depending on the OS, the changes in this PR should be good to go as is.

Conceptually, the block filter index synchronization process makes a db call on every new block (forever) just to get the tip’s header hash when it could just cache those 32 bytes.

furszy commented at 4:00 am on December 29, 2023: member

Finished testing this on a custom directory. Results are favorable @Sjors and @luke-jr. I have observed that access to the OS temp directory is faster than accessing regular directories locally. Benchmark outputs are provided at the end.

The testing methodology is as following:

Running ./bench_bitcoin -filter="BlockFilterIndexSync" -testdatadir=<custom_test_datadir_path> on any of the following branches:

Branch 1 -> Which includes: this PR changes + #26564 + a commit that introduces the custom datadir feature for the benchmark framework.

Branch 2 -> Which includes: the block filter index benchmark + #26564 + a commit that introduces the custom datadir feature for the benchmark framework.

The results were:

For Branch 1

ns/op	op/s	err%	total	benchmark
117,648,576.33	8.50	0.5%	6.96	`BlockFilterIndexSync`

For Branch 2

ns/op	op/s	err%	total	benchmark
121,370,493.17	8.24	0.5%	7.16	`BlockFilterIndexSync`

DrahtBot added the label CI failed on Jan 16, 2024

andrewtoth commented at 10:31 pm on February 22, 2024: contributor

This patch seems to be doing more than what is in the description. From my understanding, it is also reducing cs_main lock contention in the renamed Sync method, which is also now made public. The former seems like a simple win, but it’s unclear to me why we want the latter? Also, a refactor to indexes in init.cpp that also seems fine but unrelated? Maybe the PR description can be updated to describe the motivation behind these other changes?

furszy commented at 0:18 am on February 23, 2024: member

Updated per feedback. Thanks @andrewtoth!

This patch seems to be doing more than what is in the description. From my understanding, it is also reducing cs_main lock contention in the renamed Sync method, which is also now made public. The former seems like a simple win, but it’s unclear to me why we want the latter?

The benchmark, introduced in the second commit, makes use of it. If BaseIndex::Sync() is not public, the benchmark would need to call BaseIndex::StartBackgroundSync(), who wraps BaseIndex::Sync() on a separate thread, which goes against the objective of the benchmark (we want to bench the process, not the time it takes the OS to create, wait-for and destroy a thread).

Also, it facilitates the future decoupling of the index inner thread in #26966. Replacing it for a thread-pool class provided by the caller.

Also, a refactor to indexes in init.cpp that also seems fine but unrelated? Maybe the PR description can be updated to describe the motivation behind these other changes?

Sure. This PR improves the index sources. And, while the changes simplify the code, to me, pushing a PR just to do such small code refactoring does not seem worth the efforts (from reviewers and from myself). Will update the description. Thanks!

in src/index/blockfilterindex.h:47 in 91161841fe outdated

43@@ -44,6 +44,8 @@ class BlockFilterIndex final : public BaseIndex
44 
45     bool AllowPrune() const override { return true; }
46 
47+    bool Write(const BlockFilter& filter, uint32_t block_height, const uint256& header);

Sjors commented at 1:39 pm on February 23, 2024:

91161841fe2449a956b5eea76d5ebec626ce161e: maybe call it filter_header.

furszy commented at 7:35 pm on February 23, 2024:

Done as suggested

in src/index/blockfilterindex.cpp:218 in 8cf8a434aa outdated

214@@ -215,6 +215,22 @@ size_t BlockFilterIndex::WriteFilterToDisk(FlatFilePos& pos, const BlockFilter&
215     return data_size;
216 }
217 
218+std::optional<uint256> BlockFilterIndex::ReadHeader(int height, const uint256& expected_block_hash)

Sjors commented at 2:37 pm on February 23, 2024:

8cf8a434aa253d40ac19085aa8505f1eeac6f748: ReadFilterHeader?

furszy commented at 7:35 pm on February 23, 2024:

Done as suggested

in src/index/blockfilterindex.h:46 in 90969c2acb outdated

41@@ -42,6 +42,9 @@ class BlockFilterIndex final : public BaseIndex
42     /** cache of block hash to filter header, to avoid disk access when responding to getcfcheckpt. */
43     std::unordered_map<uint256, uint256, FilterHeaderHasher> m_headers_cache GUARDED_BY(m_cs_headers_cache);
44 
45+    // Last computed header to avoid disk reads at every new block.
46+    uint256 last_header{};

Sjors commented at 2:43 pm on February 23, 2024:

90969c2acb6154df5b4629f69dd2ffc3a9480cb7: m_last_header

furszy commented at 7:35 pm on February 23, 2024:

Done as suggested

in src/index/blockfilterindex.cpp:227 in b19585e00a outdated

223@@ -215,10 +224,25 @@ size_t BlockFilterIndex::WriteFilterToDisk(FlatFilePos& pos, const BlockFilter&
224     return data_size;
225 }
226 
227+std::optional<uint256> BlockFilterIndex::ReadHeader(int height, const uint256& expected_block_hash)

andrewtoth commented at 2:57 pm on February 23, 2024:

nit: could be const function.

in src/index/blockfilterindex.cpp:267 in b19585e00a outdated

267     }
268 
269     BlockFilter filter(m_filter_type, *Assert(block.data), block_undo);
270 
271+    const uint256& header = filter.ComputeHeader(last_header);
272+    bool res = Write(filter, block.height, header);

andrewtoth commented at 2:58 pm on February 23, 2024:

nit: const bool.

andrewtoth commented at 3:04 pm on February 23, 2024: contributor

Concept ACK

I’ve ran the benchmark locally on this PR and the branches you mention in #28955#pullrequestreview-1798579472, and it is sometimes better on one branch then the other for both tests. The results you show are very small improvements which I think could just be attributed to noise.

Regardless of the result, which could vary depending on the OS, the changes in this PR should be good to go as is.

I agree, except for the first 2 commits. The benchmark as I mentioned doesn’t seem particularly useful, and the Sync method being made public should then only be done in a patch that will take advantage of it’s new accessibility.

Sjors commented at 3:14 pm on February 23, 2024: member

Concept ACK

I synced the block filter from scratch at c3e2915b14900c1379e4c3f1ac0262f60b362431 (rebased on master) and then on the last commit. AMD Ryzen 7950x with SSD drive running Ubuntu 23.10:

before: 5 hours 35 minutes
after: 5 hours 46 minutes

So not much difference, which seems fine with the goal of #26966 in mind - which does make a dramatic difference.

I haven’t measured the performance impact on syncing the index during IBD; in light of 5d5e22b979d00ca3d3c4b4013fea43ba58f571bc that might be more significant because there’s more going on in cs_main.

Can you add some rationale to the b19585e00a52c0b571e70ddb8f7c996d598c3435 commit message as to what was preventing this simplification before? @andrewtoth wrote:

The benchmark as I mentioned doesn’t seem particularly useful,

Benchmarks are also useful to prevent future regressions.

furszy force-pushed on Feb 23, 2024

furszy commented at 7:49 pm on February 23, 2024: member

Updated per feedback. Thanks both.

Can you add some rationale to the https://github.com/bitcoin/bitcoin/commit/b19585e00a52c0b571e70ddb8f7c996d598c3435 commit message as to what was preventing this simplification before?

Nothing was preventing it.

The benchmark as I mentioned doesn’t seem particularly useful

Have you tried it on a spinning disk? The diff should be noticeable there. We need to avoid disk writes/reads where is possible. See #28037 discussion as a good example of it.

the Sync method being made public should then only be done in a patch that will take advantage of its new accessibility.

Have merged the first two commits.

DrahtBot removed the label CI failed on Feb 23, 2024

Sjors commented at 9:28 am on February 24, 2024: member

tACK 08d8608c51beb66dab4e12ac06559a70517fb054

DrahtBot requested review from andrewtoth on Feb 24, 2024

DrahtBot requested review from TheCharlatan on Feb 24, 2024

TheCharlatan approved

TheCharlatan commented at 1:08 pm on March 6, 2024: contributor

Re-ACK 08d8608c51beb66dab4e12ac06559a70517fb054

DrahtBot removed review request from andrewtoth on Mar 6, 2024

DrahtBot requested review from andrewtoth on Mar 6, 2024

DrahtBot added the label Needs rebase on Mar 12, 2024

bench: basic block filter index initial sync

Introduce benchmark for the block filter index sync.
And makes synchronous 'Sync()' mechanism accessible.

bcbd7eb8d4

index: blockfilter, decouple Write into its own function 331f044e3b

index: blockfilter, decouple header lookup into its own function a6756ecdb2

furszy force-pushed on Mar 12, 2024

furszy commented at 12:45 pm on March 12, 2024: member

Rebased due a one-line conflict with #29236.

DrahtBot removed the label Needs rebase on Mar 12, 2024

Sjors commented at 2:50 pm on March 12, 2024: member

Tidy complains about

0index/blockfilterindex.cpp:135:22: error: Unterminated format string used with LogPrintf [bitcoin-unterminated-logprintf,-warnings-as-errors]
1  135 |             LogError("Cannot read last block filter header; index may be corrupted");
2      |                      ^                                                            
3      |                                                                                   \n

index: cache last block filter header

Avoid disk read operations on every new processed block.

f1469eb454

index: decrease ThreadSync cs_main contention

Only NextSyncBlock requires cs_main lock. The
other function calls like Commit or Rewind will
lock or not cs_main internally when they need it.

Avoiding keeping cs_main locked when Commit() or
Rewind() write data to disk.

0faafb57f8

refactor: init, simplify index shutdown code 99afb9d15a

furszy force-pushed on Mar 12, 2024

DrahtBot added the label CI failed on Mar 12, 2024

Sjors commented at 3:07 pm on March 12, 2024: member

re-ACK 99afb9d15a08d2f46739f4d2b66c63dbabd7a44e

DrahtBot requested review from TheCharlatan on Mar 12, 2024

TheCharlatan approved

TheCharlatan commented at 8:24 pm on March 12, 2024: contributor

Re-ACK 99afb9d15a08d2f46739f4d2b66c63dbabd7a44e

DrahtBot removed the label CI failed on Mar 13, 2024

andrewtoth approved

andrewtoth commented at 2:25 pm on March 16, 2024: contributor

ACK 99afb9d15a08d2f46739f4d2b66c63dbabd7a44e

brunoerg commented at 4:28 pm on March 19, 2024: contributor

Concept ACK

achow101 commented at 4:19 pm on March 20, 2024: member

ACK 99afb9d15a08d2f46739f4d2b66c63dbabd7a44e

DrahtBot requested review from brunoerg on Mar 20, 2024

achow101 assigned achow101 on Mar 20, 2024

achow101 merged this on Mar 20, 2024

achow101 closed this on Mar 20, 2024

furszy deleted the branch on Mar 20, 2024

maflcko commented at 8:24 am on April 15, 2024: member

Follow-up in #29867 (comment)

index: block filters sync, reduce disk read operations by caching last header #28955

Code Coverage

Reviews

Conflicts

For Branch 1

For Branch 2