wallet: parallel fast rescan (approx 8x speed up with 8 threads)#34400
wallet: parallel fast rescan (approx 8x speed up with 8 threads)#34400Eunovo wants to merge 14 commits into
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/34400. ReviewsSee the guideline and AI policy for information on the review process.
If your review is incorrectly listed, please copy-paste ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
|
I would have expected rescanning to be I/O bound rather than CPU, in which case parallelization could make things worse (more random seeking). Have you benchmarked this on a non-SSD? |
Fast rescan checks block filters, which involves considerable hashing. This PR parallelises the checking of block filters, and my benchmarks show considerable improvements in rescan speeds with block filters. Slow rescan, which is I/O bound, remains the same. I expect the speedup to be transferable to non-SSD machines, but I haven't benchmarked this. |
|
#33689 has been merged; the cherry-picked Threadpool commit has been removed. |
furszy
left a comment
There was a problem hiding this comment.
I like the PR conceptually but I think it would be nice to first improve the current scanning code structure, then land the parallelization feature. The current code mixes a lot responsibilities.
Similar to what you did in 6335316, but into a separate PR so we can first land some good building blocks for this to happen.
Some quick pseudo-code structuring how I imagine it, which is similar to yours:
Scan(wallet, start_block_hash, end_block_hash, fn_filter_block, fn_process_block, interrupt) {
it_current_hash = start_block_hash;
while (it_current_hash != end_block_hash || interrupt) {
// Skip block if needed (this function contains the BlockFilterIndex check if enabled)
if (fn_filter_block(it_current_hash)) continue;
// (this is more or less how we currently do it, we fetch the block and the next block hash at the same time)
block = chain.find_block(it_current_hash).next_block(it_current_hash);
// (inside this function the wallet will digest the block update the filter and save progress if needed)
fn_process_block(block);
}
}
|
Concept ACK |
I moved the test change into #34667 and the |
…orrectly updated during scanning eb00707 test/wallet: ensure FastWalletRescanFilter is updated during scanning (Novo) Pull request description: Part of bitcoin/bitcoin#34400 On master, the `wallet_fast_rescan.py` test will pass even if the fast rescan filters are not updated during wallet rescan. This PR improves the `wallet_fast_rescan.py` test so that this no longer happens. Testers can verify by applying this diff ```diff diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 63dab29..f7d6c5f84a 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1898,7 +1898,7 @@ CWallet::ScanResult CWallet::ScanForWalletTransactions(const uint256& start_bloc bool fetch_block{true}; if (fast_rescan_filter) { - fast_rescan_filter->UpdateIfNeeded(); + // fast_rescan_filter->UpdateIfNeeded(); auto matches_block{fast_rescan_filter->MatchesBlock(block_hash)}; if (matches_block.has_value()) { if (*matches_block) { ``` and running the `wallet_fast_rescan.py` test. The test will pass on master but fail on this PR. ACKs for top commit: achow101: ACK eb00707 Bortlesboat: re-ACK eb00707 rkrux: tACK eb00707 ismaelsadeeq: Tested ACK eb00707 Tree-SHA512: bcd66db0be6604b084230fa3d3aa8d99f5a1a679a7a92592a5e8962abbcf35a14fb6883f25c9e8e6c4799893b774b1c6766876587417f35c4190562ef5ad39fb
…orrectly updated during scanning 16d0cb3 test/wallet: ensure FastWalletRescanFilter is updated during scanning (Novo) Pull request description: Part of bitcoin/bitcoin#34400 On master, the `wallet_fast_rescan.py` test will pass even if the fast rescan filters are not updated during wallet rescan. This PR improves the `wallet_fast_rescan.py` test so that this no longer happens. Testers can verify by applying this diff ```diff diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 63dab29..f7d6c5f84a 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1898,7 +1898,7 @@ CWallet::ScanResult CWallet::ScanForWalletTransactions(const uint256& start_bloc bool fetch_block{true}; if (fast_rescan_filter) { - fast_rescan_filter->UpdateIfNeeded(); + // fast_rescan_filter->UpdateIfNeeded(); auto matches_block{fast_rescan_filter->MatchesBlock(block_hash)}; if (matches_block.has_value()) { if (*matches_block) { ``` and running the `wallet_fast_rescan.py` test. The test will pass on master but fail on this PR. ACKs for top commit: achow101: ACK 16d0cb3 Bortlesboat: re-ACK 16d0cb3 rkrux: tACK 16d0cb3 ismaelsadeeq: Tested ACK 16d0cb3 Tree-SHA512: bcd66db0be6604b084230fa3d3aa8d99f5a1a679a7a92592a5e8962abbcf35a14fb6883f25c9e8e6c4799893b774b1c6766876587417f35c4190562ef5ad39fb
Add unit tests locking in currently untested rescan behavior, so that the upcoming ChainScanner refactor can be reviewed against them: - a reorged-out block that the block filter does not match is skipped and the scan ends successfully at the reorg point; a reorged-out block that must be inspected fails the scan - rescan reservation lifecycle: single reservation at a time, RAII release, the with_passphrase flag, and idle accessor values - bounded scans stop exactly at max_height, including a single-block range (progress start == end) - a tip extension while the scan is running is picked up instead of stopping at the height the scan started with - save_progress=false must not touch the wallet's best block record - RescanFromTime moves the returned timestamp past unreadable (pruned) blocks and returns it unchanged when nothing needs scanning - missing block filters must not cause blocks to be skipped - loading a wallet that is behind the chain tip rescans from its recorded best block (inclusive), the path loadwallet takes
Move scan state atomics (abort, scanning, passphrase, start time, progress) into ChainScanner and expose it via Scanner(). All callers use Scanner().Scan() directly. The newly added `m_scanner` is an incomplete type so CWallet's constructor and destructor is moved into wallet.cpp where the type is complete. This change introduces a new circular dependency of the form "wallet/scan -> wallet/wallet -> wallet/scan" which is added to `EXPECTED_CIRCULAR_DEPENDENCIES`.
Callers now reach this via Scanner().ScanFromTime() rather than a CWallet member function, keeping all scan logic in ChainScanner.
Dequeue the current block at the top of the Scan loop and extract the lookup of its chain position and the queueing of its active-chain successor into QueueNextBlock. Since the current block is now dequeued at the top of the loop, update progress_current there as well so the reported progress keeps referring to the block being processed, as before.
This commit refactors the block filtering logic from ShouldFetchBlock into a new ReadNextBlocks method that returns the blocks that are ready to be scanned. This prepares the code for pipelined and parallel block filter checking while keeping the current single-threaded, one block at a time behaviour. State for a single Scan() call lives in a ScanContext that is local to Scan() and passed through the helpers. The QueueNextBlock helper is absorbed into the new ReadNextBlock, its only caller: consuming the pending block, recording whether it is still in the active chain, and queueing its successor are one operation. Read blocks carry the still-active flag, so a reorged-out block that must be inspected fails the scan while a filter-skipped one stays skipped. Progress is still updated and logged for filter-skipped ranges from the scan loop, keeping the previous per-block reporting cadence.
This parameter will be used in a future commit to determine the number of threads to use for parallel fast-rescan. 8 threads is chosen as a reasonable MAX_WALLETPAR, benchmarks show 8x improvement on fast-rescan with 8 threads. The member lives with the other public wallet options so that tests can configure it directly.
This commit implements parallel block filter checking. ParallelFilterChecker owns the pipeline: the scan loop pushes read blocks into its queue, the executor submits batches of checks to its thread pool, and TryPop() pops the front block together with its verdict, in block order. Each task checks a span of up to FILTER_TASK_SPAN blocks; batching amortizes the scheduling cost of a task, which may otherwise rival the cost of the checks themselves. In-flight work is capped at WorkersCount()*2 span tasks so a scan that ends early does not leave workers checking blocks that get discarded, and the queue is bounded by MAX_BLOCKQUEUE_SIZE to limit the block hashes held in memory. When the pipeline is saturated the main thread helps with queued checks and then blocks on the oldest verdict instead of spinning. Synchronization: - Operations requiring cs_wallet (GetLastBlockHeight, SyncTransaction) remain on the main thread since cs_wallet is a RecursiveMutex and Scan is called from AttachChain which locks cs_wallet - Workers only read the wallet's filter set; the set is only updated after a keypool top-up (FastWalletRescanFilter::NeedsUpdate), and FilterExecutor::Reset() first drains every submitted check and discards undelivered verdicts, which were computed against the old scripts (documented on FastWalletRescanFilter)
Pause the submission of filter checks at interval boundaries so that ReadNextBlocks returns and the scan loop can log progress and give ScanBlock() a chance to save progress. The scan loop resets the interval for skipped ranges as well as scanned blocks, so a paused pipeline always resumes.
Run the filter-dependent scan tests with parallel filter checking (-walletpar 1 and 4). The wallet loading rescan test also runs on the parallel path now, with a log hook asserting that the multi-threaded variant actually engaged: this covers a rescan that starts from a mid-chain block with cs_wallet held.
The wallet now uses parallel scan by default, so existing functional tests now exercise the parallel scan logic. `wallet_fast_rescan` is updated to test both serial and parallel fast scan.
|
I've made some improvements which have increased the speedup from 5x at 8 threads to 8x at 8 threads. 8x speedup seems to be the peak for now. The results have been updated in the PR description, #34400 (comment) |
This PR speeds up wallet fast-rescan by executing the filter checks in parallel while ensuring that the filters are updated properly so that no output scripts are missed. Benchmarks, outlined below, show considerable improvement that tapers off at around
8xspeedup at8threads.Prerequisite PRs
CWallet::ScanForWalletTransactionsto prepare for the work in this PR.Benchmarks
NOTE: to reproduce, please tune your system with
pyperf system tuneEDIT
Set up your node to use block filters by setting
blockfilterindex=1in your bitcoin.conf file and ensure your blockfilterindex is synced to the tip before attempting to reproduce.Using the following command on mainnet with a wallet with no scripts and hyperfine version
1.20.0:Table 1 was obtained on a machine with the following specifications
Table 1. Table of results of a mainnent benchmark of scanning 200000 blocks. The improvements seem to peak at
8xspeedup despite the machine having an excess number of Cores (20).Worst Case
This parallel fast rescan checks the filters for a series of blocks in parallel. One of the following cases can occur:
This Python script patch python script creates custom chains designed with payments at specified intervals to observe the performance of parallel fast rescan in two scenarios:
Fig 1 shown below was produced using this patch on a machine with the following specifications
Fig 1. Graphs showing the average time to complete a scan of a chain 5000 blocks high with payments at different intervals on Regtest. In the expected case, parallel fast rescan is faster for payments at all intervals for thread count > 1. In the worst case, below 8 threads, parallel fast rescan is slightly slower than baseline at short intervals (<=100 blocks). At 8 threads, parallel fast rescan performs better even at the 50-block interval. These benchmarks use 33faeab as a baseline in place of master because master doesn't have the
-walletparconfig parameter. All materials for this custom benchmark can be found here.Although not explicitly checked with Valgrind, hyperfine reported that memory usage stayed the same across all runs. I'm not sure to what degree Hyperfine's memory usage report can be trusted, but the PR limits the number of block hashes that can be held in memory for processing to
1000(not configurable by the user).