Cache block filter headers at heights of multiples of 1000 in memory.
Block filter headers at height 1000x are checkpointed, and will be the most frequently requested. Cache them in memory to avoid costly disk reads.
indexes: Add compact block filter headers cache #18960
pull jnewbery wants to merge 1 commits into bitcoin:master from jnewbery:2020-05-cfcheckpts-cache changing 3 files +40 −6-
jnewbery commented at 3:04 PM on May 12, 2020: member
- fanquake added the label UTXO Db and Indexes on May 12, 2020
-
-
in src/index/blockfilterindex.cpp:39 in 6fe202209e outdated
30 | @@ -31,6 +31,8 @@ constexpr char DB_FILTER_POS = 'P'; 31 | constexpr unsigned int MAX_FLTR_FILE_SIZE = 0x1000000; // 16 MiB 32 | /** The pre-allocation chunk size for fltr?????.dat files */ 33 | constexpr unsigned int FLTR_FILE_CHUNK_SIZE = 0x100000; // 1 MiB 34 | +/** Maximum size of the cfheaders cache */ 35 | +constexpr size_t CF_HEADERS_CACHE_MAX_SZ{2000};
theStack commented at 3:18 PM on May 12, 2020:Is there any particular reason for limiting the size of the cache? With this numbers it would be full at block 2000000, i.e. in (2000000-630000)/(6 * 24 * 365) ~ 26 years.
jnewbery commented at 8:08 PM on May 12, 2020:I wanted to have some limit so that a bug doesn't turn into a memory exhaustion possibility (since we only ever add to this map, and never remove). I don't think the exact number matters. Presumably in 26 years, anyone who wants to serve compact block filters from a v0.21 Bitcoin Core server will be able to patch their own code.
theStack commented at 11:26 AM on May 13, 2020:I agree that when in doubt, it's better to be overcautious than risking introducing a memory exhaustion bug -- I just wanted to get sure there are no other reasons for the limit that I'm not aware of.
theStack commented at 3:21 PM on May 12, 2020: memberConcept ACK -- I didn't look very deeply into the proposed solution from the original PR (#16442, commit https://github.com/bitcoin/bitcoin/pull/16442/commits/be5f7c5f8e98416f95d3bd91ab5639b67b28eef2), but this solution here seems to be way simpler.
DrahtBot commented at 7:52 AM on May 13, 2020: member<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
Conflicts
Reviewers, this pull request conflicts with the following ones:
- #18354 (Protect wallet by using shared pointers by bvbfan)
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.
theStack commented at 12:10 PM on May 13, 2020: memberI'm almost ready for ACKing this PR, just have some minor suggestion/discussion points:
- Would it make sense to also only check the cache if we have checkpoints, i.e. a method structure like
bool is_checkpoint = (block_index->nHeight % CFCHECKPT_INTERVAL == 0); if (is_checkpoint) // Check the headers cache // Regular lookup if (is_checkpoint) // Add to the headers cache? Of course, the drawback of this approach is that the condition for checking needs to be removed if the cache is ever used for other filter headers than those from the checkpoints. Also not sure if its really worth it from a performance point of view. But in 999 out of 1000 times the lookup in the map could be skipped.
- In the regular case the cache should never get full, considering that this would by plan only happen in the far future (block 2000000, >25 years from now, with the current maximum size constant of 2000). If it gets full however, should we take some action like putting a debug output or even an assert, to get noticed that we either have some memory exhaustion bug or that the maximum size needs to be increased?
- Any idea how to effectively test performance improvements like this? I don't know anything better than just putting some
LogPrintfs in the cache hit / cache add cases, run the (maybe slightly modified) functional test and analyze the log output to check if it behaves as expected.
in src/index/blockfilterindex.h:36 in 6fe202209e outdated
32 | @@ -30,6 +33,9 @@ class BlockFilterIndex final : public BaseIndex 33 | bool ReadFilterFromDisk(const FlatFilePos& pos, BlockFilter& filter) const; 34 | size_t WriteFilterToDisk(FlatFilePos& pos, const BlockFilter& filter); 35 | 36 | + RecursiveMutex m_cs_headers_cache;
MarcoFalke commented at 12:43 PM on May 13, 2020:Mutex m_cs_headers_cache;nit (feel free to ignore). I haven't tested this, but from reading the code, a non-recursive mutex should be sufficient.
jnewbery commented at 7:30 PM on May 13, 2020:Agree. I'll change to
Mutex.
jnewbery commented at 10:44 PM on May 13, 2020:Done
MarcoFalke commented at 12:46 PM on May 13, 2020: memberin src/index/blockfilterindex.cpp:414 in 6fe202209e outdated
409 | 410 | + if (block_index->nHeight % CFCHECKPT_INTERVAL == 0) { 411 | + // Add to the headers cache 412 | + LOCK(m_cs_headers_cache); 413 | + if (m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) { 414 | + m_headers_cache.emplace(block_index->GetBlockHash(), entry.header);
fjahr commented at 2:59 PM on May 13, 2020:This is a very minor issue but if we use the hash instead of the height as the key we could end up with headers of orphaned blocks in the cache since they will not be overridden or removed. This could also be the case if
CFCHECKPT_INTERVALwould ever change. I know the chances for that happening are slim and if it happens we can deal with it then, just wanted to put it there.
clarkmoody commented at 6:14 PM on May 13, 2020:The test suite explicitly checks that filters for stale blocks may still be fetched.
jnewbery commented at 7:29 PM on May 13, 2020:we could end up with headers of orphaned blocks in the cache
Correct. If there's a re-org across checkpoint block, then the disconnect block's filter header stays in the cache. That's an explicit design decision, since:
- the cost is very small (32 bytes for header + map overhead so < 100 bytes)
- it's an infrequent event
- it saves on the complexity of having to recalculate the cache on re-orgs (eg compare with https://github.com/bitcoin-core-review-club/bitcoin/commit/af3bddfbdfb7de06d6e63a0a425da483c435521a#diff-eff7adeaec73a769788bb78858815c91R1258)
if CFCHECKPT_INTERVAL would ever change
In that case, we'd need to change the software, which would involve a stop/start. This is an in-memory cache so gets dropped on shutdown.
fjahr commented at 3:31 PM on May 13, 2020: memberAgree with previous comments: I prefer this to the previous approach. I think it would be good to have some benchmarks. Otherwise, code looks very good to me.
in src/index/blockfilterindex.cpp:413 in 6fe202209e outdated
408 | } 409 | 410 | + if (block_index->nHeight % CFCHECKPT_INTERVAL == 0) { 411 | + // Add to the headers cache 412 | + LOCK(m_cs_headers_cache); 413 | + if (m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) {
jonasschnelli commented at 6:24 PM on May 13, 2020:doesn't this statically cap (and freeze forever) the cache after inserting 2000 entries? Wouldn't it make sense to have some sort of invalidation logic? (I can't come up with a good one though)
MarcoFalke commented at 6:32 PM on May 13, 2020:If someone can mine enough blocks to fill up this cache, we have other problems. I think an adversary needs to mine blocks in the order of the 2000th triangle number to fill this up.
And when this cache is full due to natural reasons (in 20 years), disks will be fast enough that we won't need a cache.
MarcoFalke commented at 6:33 PM on May 13, 2020:Maybe disks are fast enough or smart enough with caching today already, so it might not be needed after all. A benchmark would be nice...
jonasschnelli commented at 6:38 PM on May 13, 2020:Oh. You'r right. I missed the
% CFCHECKPT_INTERVAL == 0.
jnewbery commented at 7:31 PM on May 13, 2020:Remind me to change this to 4000 in 2026 :)
I agree that a benchmark would be nice.
MarcoFalke commented at 7:33 PM on May 13, 2020:// TODO change to 4000 in 2026;)
jnewbery commented at 7:38 PM on May 13, 2020:oops sorry, I meant 2046
jonasschnelli commented at 6:25 PM on May 13, 2020: contributorConcept ACK
jnewbery force-pushed on May 13, 2020jnewbery force-pushed on May 13, 2020jnewbery commented at 10:48 PM on May 13, 2020: memberWould it make sense to also only check the cache if we have checkpoints, i.e. a method structure like
Done @MarcoFalke
a non-recursive mutex should be sufficient.
Changed
RecursiveMutex->MutexI'm still working on adding a microbench, although it's not clear to me that it'll show any improvement since the disk reads may be cached by the OS for the microbench.
in src/index/blockfilterindex.h:37 in 7ad83ed252 outdated
32 | @@ -30,6 +33,9 @@ class BlockFilterIndex final : public BaseIndex 33 | bool ReadFilterFromDisk(const FlatFilePos& pos, BlockFilter& filter) const; 34 | size_t WriteFilterToDisk(FlatFilePos& pos, const BlockFilter& filter); 35 | 36 | + Mutex m_cs_headers_cache; 37 | + std::map<uint256, uint256> m_headers_cache GUARDED_BY(m_cs_headers_cache);
jkczyz commented at 6:00 AM on May 14, 2020:Any reason
std::unordered_mapcan't be used? I see that the tree-basedstd::mapandstd::setare used primarily throughout the codebase, but figured it may just be historical. Is there another reason these are preferred?
jnewbery commented at 2:07 AM on May 15, 2020:I expect mostly laziness. With an
unordered_map, you need to provide a hash function. In this case, it's easy. The data is all hash digests from block chain data, so I can just take the first 8 bytes from the uint256 filter header.I'll make that change tomorrow.
MarcoFalke commented at 10:23 AM on May 15, 2020:Just as a reminder: There is no free lunch and unordered_map comes with a size penalty
jnewbery commented at 4:17 PM on May 15, 2020:I've reimplemented this as an unordered_map
jkczyz commented at 6:05 AM on May 14, 2020: contributorConcept ACK.
Kudos on the simplicity of this approach!
theStack referenced this in commit e7bb43ec6d on May 14, 2020theStack referenced this in commit 1d504570d1 on May 14, 2020theStack commented at 4:56 PM on May 14, 2020: memberUsing jnewbery's nice node-shell module (a modification of test-shell that allows to connect with the functional test framework to a running full-node) I crafted up a quick and dirty test-script (see branch https://github.com/theStack/bitcoin/tree/pr18960_test) that sends
getcfcheckptrequests with the stop-hash of the halving block 630000 and measures the processing time.Freshly started bitcoind from master branch (w/o checkpoint headers cache implementation), after mempool imports are done:
getcfcheckpt request processing times ===================================== -> first: 53.75ms -> following: 50.70ms (average) =====================================Freshly started bitcoind from PR branch (with checkpoint headers cache implementation), after mempool imports are done:
getcfcheckpt request processing times ===================================== -> first: 50.92ms -> following: 50.80ms (average) =====================================There doesn't seem to be a noticable difference. I don't know if my methodology is flawed though. Maybe all the processing around is taking so much more time that the actual part of fetching the header (from the cache or from disk) is neglectible. If anyone has an idea how to improve the benchmark script, happy to hear suggestions!
// EDIT: As jnewbery found out in the course of today's PR review club meeting, there is a good explanation on why the values are always close to 50ms:
19:36 < jnewbery> There are 100ms sleeps in the messagehandler thread between looping through all peers: https://github.com/jnewbery/bitcoin/blob/7ad83ed252914d6d5b8ed81f103aecf052c68fb7/src/net.cpp#L2061 19:37 < jnewbery> on a non-busy node, 50ms is the average time you have to wait for the message handler thread to wake upmichaelfolkson commented at 6:36 PM on May 14, 2020: contributorApproach ACK
laanwj added this to the "Blockers" column in a project
MarcoFalke commented at 10:26 PM on May 14, 2020: member@theStack I believe in between the requests you can drop the cache to simulate eviction (which may occasionally happen during normal operation). See https://unix.stackexchange.com/questions/17936/setting-proc-sys-vm-drop-caches-to-clear-cache
jnewbery commented at 1:36 AM on May 15, 2020: member@narula suggested in today's PR Review Club meeting that it'd be less cognitive overhead to simply take the
m_cs_headers_cachefor the entirety of theLookupFilterHeader()function, rather than taking, releasing and taking it again. That seem like a reasonable request to me. We can't ever block important work with this lock, so holding it a bit longer than strictly necessary is not an issue.jnewbery commented at 1:56 AM on May 15, 2020: member@theStack - thank you for doing some benching of this. Your approach inspired me to do something similar myself, using debug logs to find the exact time to construct a cfcheckpt response. I've added a
debug_log_deltacontext wrapper to the node_shell, which allows me to provide two debug log messages, then do actions on the node and extract the time delta between those two logs. I applied that patch to:- without a cache
- with this cache
- with @narula's suggestion of taking the lock only once (I was interested to see if there were any performance differences).
And then ran the following node-shell script:
REPO_PATH="<path_to_repo>" DATADIR_PATH="<path_to_datadir>" import sys sys.path.insert(0, f"{REPO_PATH}/test/functional") from test_framework.node_shell import NodeShell test = NodeShell() test.setup(datadir=DATADIR_PATH) # <test_framework.node_shell.NodeShell.__TestShell object at 0x7f7704820490> node = test.nodes[0] bb = node.getbestblockhash() from test_framework.messages import FILTER_TYPE_BASIC, msg_getcfcheckpt request = msg_getcfcheckpt(filter_type=FILTER_TYPE_BASIC, stop_hash=int(bb, 16)) for i in range(15): with node.debug_log_delta("getcfcheckpt request received", "cfcheckpt response constructed"): node.p2ps[0].send_and_ping(request) test.shutdown()no cache
getcfcheckpt request received to cfcheckpt response constructed: 7.824ms getcfcheckpt request received to cfcheckpt response constructed: 7.054ms getcfcheckpt request received to cfcheckpt response constructed: 7.021ms getcfcheckpt request received to cfcheckpt response constructed: 7.303ms getcfcheckpt request received to cfcheckpt response constructed: 7.355ms getcfcheckpt request received to cfcheckpt response constructed: 7.26ms getcfcheckpt request received to cfcheckpt response constructed: 7.169ms getcfcheckpt request received to cfcheckpt response constructed: 7.166ms getcfcheckpt request received to cfcheckpt response constructed: 7.194ms getcfcheckpt request received to cfcheckpt response constructed: 8.574ms getcfcheckpt request received to cfcheckpt response constructed: 7.119ms getcfcheckpt request received to cfcheckpt response constructed: 7.156ms getcfcheckpt request received to cfcheckpt response constructed: 4.153ms getcfcheckpt request received to cfcheckpt response constructed: 8.162ms getcfcheckpt request received to cfcheckpt response constructed: 6.485msThere does seem to be a very slight performance improvement after the first request. Maybe around 5-10% from the mean, but variance is quite high, so it might be noise.
cache (taking locks twice)
getcfcheckpt request received to cfcheckpt response constructed: 12.2ms getcfcheckpt request received to cfcheckpt response constructed: 2.855ms getcfcheckpt request received to cfcheckpt response constructed: 2.992ms getcfcheckpt request received to cfcheckpt response constructed: 2.869ms getcfcheckpt request received to cfcheckpt response constructed: 3.141ms getcfcheckpt request received to cfcheckpt response constructed: 3.692ms getcfcheckpt request received to cfcheckpt response constructed: 3.452ms getcfcheckpt request received to cfcheckpt response constructed: 2.916ms getcfcheckpt request received to cfcheckpt response constructed: 3.413ms getcfcheckpt request received to cfcheckpt response constructed: 3.648ms getcfcheckpt request received to cfcheckpt response constructed: 3.816ms getcfcheckpt request received to cfcheckpt response constructed: 3.84ms getcfcheckpt request received to cfcheckpt response constructed: 3.812ms getcfcheckpt request received to cfcheckpt response constructed: 3.869ms getcfcheckpt request received to cfcheckpt response constructed: 3.445msThe initial request is slower (presumably because the cache needs to be warmed), but subsequent requests are on average >50% faster than with no cache.
cache (taking lock once)
getcfcheckpt request received to cfcheckpt response constructed: 11.785ms getcfcheckpt request received to cfcheckpt response constructed: 3.35ms getcfcheckpt request received to cfcheckpt response constructed: 3.19ms getcfcheckpt request received to cfcheckpt response constructed: 3.475ms getcfcheckpt request received to cfcheckpt response constructed: 3.175ms getcfcheckpt request received to cfcheckpt response constructed: 3.345ms getcfcheckpt request received to cfcheckpt response constructed: 3.274ms getcfcheckpt request received to cfcheckpt response constructed: 3.161ms getcfcheckpt request received to cfcheckpt response constructed: 3.259ms getcfcheckpt request received to cfcheckpt response constructed: 3.217ms getcfcheckpt request received to cfcheckpt response constructed: 3.238ms getcfcheckpt request received to cfcheckpt response constructed: 3.253ms getcfcheckpt request received to cfcheckpt response constructed: 3.33ms getcfcheckpt request received to cfcheckpt response constructed: 3.32ms getcfcheckpt request received to cfcheckpt response constructed: 3.36msThe first request is slightly faster than when taking locks twice (although that might be noise). Subsequent requests are the same speed as the 'taking locks twice' branch, which is what we'd expect because locks are only taken once in that branch if the header is found in the cache. @MarcoFalke - I think these full node manual benches are more meaningful than microbenches, so I'm not planning to add any automated benches to
/src/bench.jnewbery commented at 2:08 AM on May 15, 2020: member@narula suggested in today's PR Review Club meeting that it'd be less cognitive overhead to simply take the m_cs_headers_cache for the entirety of the LookupFilterHeader() function, rather than taking, releasing and taking it again.
I'll make this change tomorrow.
theStack commented at 10:37 AM on May 15, 2020: memberIn yesterday's review club meeting on this PR, it was suggested to put LogPrintf() directly into the network processing code parts to measure the execution time of getcfcheckpt requests. (My previous approach of measuring the request response time from the test framework was not precise enough, as the time also included python overhead and the time for the message handler to wake up.) I did some testing with this refined approach and can roughly confirm the results from jnewbery (see commit https://github.com/theStack/bitcoin/commit/48cff1bb4d27ef0040b18a860a3c897752e3c296):
without cache:
2020-05-14T20:15:11Z getcfcheckpt processing took 10247us 2020-05-14T20:15:11Z getcfcheckpt processing took 6105us 2020-05-14T20:15:11Z getcfcheckpt processing took 6437us 2020-05-14T20:15:11Z getcfcheckpt processing took 5330us 2020-05-14T20:15:11Z getcfcheckpt processing took 6964us 2020-05-14T20:15:11Z getcfcheckpt processing took 5523us 2020-05-14T20:15:12Z getcfcheckpt processing took 5413us 2020-05-14T20:15:12Z getcfcheckpt processing took 5843us 2020-05-14T20:15:12Z getcfcheckpt processing took 7060us 2020-05-14T20:15:12Z getcfcheckpt processing took 6165us ...with cache:
2020-05-14T20:21:26Z getcfcheckpt processing took 9801us 2020-05-14T20:21:26Z getcfcheckpt processing took 2619us 2020-05-14T20:21:26Z getcfcheckpt processing took 3338us 2020-05-14T20:21:26Z getcfcheckpt processing took 2446us 2020-05-14T20:21:26Z getcfcheckpt processing took 2560us 2020-05-14T20:21:27Z getcfcheckpt processing took 2331us 2020-05-14T20:21:27Z getcfcheckpt processing took 2703us 2020-05-14T20:21:27Z getcfcheckpt processing took 2614us 2020-05-14T20:21:27Z getcfcheckpt processing took 2598us 2020-05-14T20:21:27Z getcfcheckpt processing took 2444us ...One can see that there's a speedup of at least 2x with the cache.
Note that my approach to get these numbers was slightly different, as I directly measured the time in bitcoind via
GetTimeMicros()(commit https://github.com/theStack/bitcoin/commit/49f5f3d5444ed6c872dd41be910e2149308b35e7):diff --git a/src/net_processing.cpp b/src/net_processing.cpp index 1df1fab..6e620d9 100644 --- a/src/net_processing.cpp +++ b/src/net_processing.cpp @@ -3380,7 +3380,10 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec } if (msg_type == NetMsgType::GETCFCHECKPT) { + int64_t start_time = GetTimeMicros(); ProcessGetCFCheckPt(pfrom, vRecv, chainparams, connman); + int64_t processing_duration = GetTimeMicros() - start_time; + LogPrintf("getcfcheckpt processing took %lldus\n", processing_duration); return true; }but the idea is the same.
Now I'm very curious if the change from
std::maptostd::unordered_mapshows a noticable difference in performance. @MarcoFalke: Nice idea to drop the cache between the requests. Unfortunately, on my current development box I don't have the permissions (root rights) to do this :/ if anyone having the possibility, the results would be very interesting.jnewbery force-pushed on May 15, 2020in src/index/blockfilterindex.cpp:34 in 4018953ee9 outdated
30 | @@ -31,6 +31,8 @@ constexpr char DB_FILTER_POS = 'P'; 31 | constexpr unsigned int MAX_FLTR_FILE_SIZE = 0x1000000; // 16 MiB 32 | /** The pre-allocation chunk size for fltr?????.dat files */ 33 | constexpr unsigned int FLTR_FILE_CHUNK_SIZE = 0x100000; // 1 MiB 34 | +/** Maximum size of the cfheaders cache */
narula commented at 4:24 PM on May 15, 2020:Nit: give justification in comments for magic numbers so future readers have some idea how this was chosen and if/when it will need to be adjusted.
jnewbery commented at 4:48 PM on May 15, 2020:done
in src/index/blockfilterindex.cpp:421 in 4018953ee9 outdated
406 | 407 | + // Add to the headers cache 408 | + if (m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) { 409 | + m_headers_cache.emplace(block_index->GetBlockHash(), entry.header); 410 | + } 411 | +
jkczyz commented at 4:34 PM on May 15, 2020:You'll still want to condition this on
block_index->nHeight % CFCHECKPT_INTERVAL == 0, otherwise the most recent 2000 requested headers will be cached rather than the desired ones.
jnewbery commented at 4:35 PM on May 15, 2020:yikes. Thanks
jnewbery commented at 4:48 PM on May 15, 2020:done
narula commented at 4:40 PM on May 15, 2020: contributorutACK
jnewbery commented at 4:41 PM on May 15, 2020: memberI've force-pushed a branch that changes this to use an unordered_map and only lock once.
Comparing the unordered map implementation to map:
unordered_map
<details><summary>Log</summary>
getcfcheckpt request received to cfcheckpt response constructed: 12.808ms getcfcheckpt request received to cfcheckpt response constructed: 2.783ms getcfcheckpt request received to cfcheckpt response constructed: 2.712ms getcfcheckpt request received to cfcheckpt response constructed: 2.656ms getcfcheckpt request received to cfcheckpt response constructed: 2.672ms getcfcheckpt request received to cfcheckpt response constructed: 2.82ms getcfcheckpt request received to cfcheckpt response constructed: 2.994ms getcfcheckpt request received to cfcheckpt response constructed: 3.068ms getcfcheckpt request received to cfcheckpt response constructed: 3.335ms getcfcheckpt request received to cfcheckpt response constructed: 3.444ms getcfcheckpt request received to cfcheckpt response constructed: 3.159ms getcfcheckpt request received to cfcheckpt response constructed: 3.194ms getcfcheckpt request received to cfcheckpt response constructed: 2.601ms getcfcheckpt request received to cfcheckpt response constructed: 2.692ms getcfcheckpt request received to cfcheckpt response constructed: 2.982ms getcfcheckpt request received to cfcheckpt response constructed: 3.209ms getcfcheckpt request received to cfcheckpt response constructed: 3.116ms getcfcheckpt request received to cfcheckpt response constructed: 3.136ms getcfcheckpt request received to cfcheckpt response constructed: 2.666ms getcfcheckpt request received to cfcheckpt response constructed: 3.091ms getcfcheckpt request received to cfcheckpt response constructed: 3.444ms getcfcheckpt request received to cfcheckpt response constructed: 3.385ms getcfcheckpt request received to cfcheckpt response constructed: 3.147ms getcfcheckpt request received to cfcheckpt response constructed: 3.145ms getcfcheckpt request received to cfcheckpt response constructed: 3.053ms</p></details> First lookup: 12.8ms, average subsequent lookup: 3.02ms
map
<details><summary>Log</summary>
getcfcheckpt request received to cfcheckpt response constructed: 12.959ms getcfcheckpt request received to cfcheckpt response constructed: 3.001ms getcfcheckpt request received to cfcheckpt response constructed: 3.656ms getcfcheckpt request received to cfcheckpt response constructed: 2.07ms getcfcheckpt request received to cfcheckpt response constructed: 2.537ms getcfcheckpt request received to cfcheckpt response constructed: 2.838ms getcfcheckpt request received to cfcheckpt response constructed: 2.994ms getcfcheckpt request received to cfcheckpt response constructed: 3.143ms getcfcheckpt request received to cfcheckpt response constructed: 3.383ms getcfcheckpt request received to cfcheckpt response constructed: 3.666ms getcfcheckpt request received to cfcheckpt response constructed: 3.889ms getcfcheckpt request received to cfcheckpt response constructed: 3.553ms getcfcheckpt request received to cfcheckpt response constructed: 3.394ms getcfcheckpt request received to cfcheckpt response constructed: 3.3ms getcfcheckpt request received to cfcheckpt response constructed: 3.5ms getcfcheckpt request received to cfcheckpt response constructed: 3.372ms getcfcheckpt request received to cfcheckpt response constructed: 3.329ms getcfcheckpt request received to cfcheckpt response constructed: 3.308ms getcfcheckpt request received to cfcheckpt response constructed: 3.564ms getcfcheckpt request received to cfcheckpt response constructed: 3.746ms getcfcheckpt request received to cfcheckpt response constructed: 3.714ms getcfcheckpt request received to cfcheckpt response constructed: 3.423ms getcfcheckpt request received to cfcheckpt response constructed: 3.517ms getcfcheckpt request received to cfcheckpt response constructed: 3.636ms getcfcheckpt request received to cfcheckpt response constructed: 3.595ms</details> First lookup: 13.0ms, average subsequent lookup: 3.60s
So from this single test, it appears that an unordered_map is indeed faster. That's what we'd expect, since lookup is O(1) and number of lookups required for a single getcfcheckpt request is O(n), so total is O(n). For a map, a single lookup is O(logn), so total is O(nlogn).
The original implementation is faster still, since it's storing the checkpts in a single vector, but the aim of this PR is to avoid disk reads for getcfcheckpt messages, which the simple unordered_map implementation does. Further performance improvements could be done as a follow-up if required.
jnewbery force-pushed on May 15, 2020jkczyz commented at 5:55 PM on May 15, 2020: contributorACK b6eba9e492e1dfb38baec894bfda1cfb4d709e5d
Ran all tests.
fjahr commented at 7:30 PM on May 15, 2020: memberutACK b6eba9e492e1dfb38baec894bfda1cfb4d709e5d
in src/index/blockfilterindex.cpp:399 in b6eba9e492 outdated
392 | @@ -387,13 +393,26 @@ bool BlockFilterIndex::LookupFilter(const CBlockIndex* block_index, BlockFilter& 393 | return ReadFilterFromDisk(entry.pos, filter_out); 394 | } 395 | 396 | -bool BlockFilterIndex::LookupFilterHeader(const CBlockIndex* block_index, uint256& header_out) const 397 | +bool BlockFilterIndex::LookupFilterHeader(const CBlockIndex* block_index, uint256& header_out) 398 | { 399 | + LOCK(m_cs_headers_cache); 400 | + auto header = m_headers_cache.find(block_index->GetBlockHash());
theStack commented at 10:49 AM on May 17, 2020:Before the last change, the cache lookup only happened for checkpoint blocks (i.e. block number modulo 1000 is zero). Is this removal of the condition intended?
jnewbery commented at 4:54 PM on May 18, 2020:No. Not intentional. I just messed up splitting out the
LOCK(m_cs_headers_cache). Thanks for catching this.jnewbery force-pushed on May 18, 20200187d4c118[indexes] Add compact block filter headers cache
Cache block filter headers at heights of multiples of 1000 in memory. Block filter headers at height 1000x are checkpointed, and will be the most frequently requested. Cache them in memory to avoid costly disk reads.
jnewbery force-pushed on May 18, 2020jkczyz commented at 5:22 PM on May 18, 2020: contributorACK 0187d4c118ab4c0f5c2d4fb180c2a8dea8ac53cf
jnewbery renamed this:[indexes] Add compact block filter headers cache
indexes: Add compact block filter headers cache
on May 18, 2020theStack commented at 9:33 AM on May 19, 2020: memberACK 0187d4c118ab4c0f5c2d4fb180c2a8dea8ac53cf :tada:
By the way, I'm neutral to the question on whether to use
std::maporstd::unordered_mapfor the cache --std::unordered_mapdoes indeed seem to lead to some performance improvement (my tests show a rough 10% improvement, see numbers below; jnewberys tests show an even higher improvement of close to 20%), but on the other hand takes both more space (as pointed out by MarcoFalke) and also more code due to the need to provide a hash function. Maybe someone has a more clear opinion on the choice, personally I'm okay with ACKing either version.Test with
std::map:2020-05-19T09:09:01Z getcfcheckpt processing took 13817us 2020-05-19T09:09:01Z getcfcheckpt processing took 2855us 2020-05-19T09:09:01Z getcfcheckpt processing took 3573us 2020-05-19T09:09:01Z getcfcheckpt processing took 3444us 2020-05-19T09:09:01Z getcfcheckpt processing took 3236us 2020-05-19T09:09:01Z getcfcheckpt processing took 3385us 2020-05-19T09:09:01Z getcfcheckpt processing took 3543us 2020-05-19T09:09:01Z getcfcheckpt processing took 3378us 2020-05-19T09:09:01Z getcfcheckpt processing took 3450us 2020-05-19T09:09:01Z getcfcheckpt processing took 3041us 2020-05-19T09:09:01Z getcfcheckpt processing took 3561us ...:arrow_right: Average subsequent lookup: 3,346ms
Test with
std::unordered_map:2020-05-19T08:59:53Z getcfcheckpt processing took 12205us 2020-05-19T08:59:53Z getcfcheckpt processing took 3650us 2020-05-19T08:59:53Z getcfcheckpt processing took 4660us 2020-05-19T08:59:53Z getcfcheckpt processing took 3393us 2020-05-19T08:59:53Z getcfcheckpt processing took 3669us 2020-05-19T08:59:53Z getcfcheckpt processing took 2919us 2020-05-19T08:59:53Z getcfcheckpt processing took 2565us 2020-05-19T08:59:53Z getcfcheckpt processing took 2804us 2020-05-19T08:59:53Z getcfcheckpt processing took 2348us 2020-05-19T08:59:53Z getcfcheckpt processing took 2511us 2020-05-19T08:59:53Z getcfcheckpt processing took 2264us ...:arrow_right: Average subsequent lookup: 3,078ms
fjahr commented at 2:08 PM on May 19, 2020: memberre-utACK 0187d4c118ab4c0f5c2d4fb180c2a8dea8ac53cf
Compared to my last review
is_checkpointvariable is introduced for better readability and if statement that was removed in error is added back: https://github.com/bitcoin/bitcoin/compare/b6eba9e492e1dfb38baec894bfda1cfb4d709e5d..0187d4c118ab4c0f5c2d4fb180c2a8dea8ac53cfin src/index/blockfilterindex.h:42 in 0187d4c118
37 | @@ -30,6 +38,9 @@ class BlockFilterIndex final : public BaseIndex 38 | bool ReadFilterFromDisk(const FlatFilePos& pos, BlockFilter& filter) const; 39 | size_t WriteFilterToDisk(FlatFilePos& pos, const BlockFilter& filter); 40 | 41 | + Mutex m_cs_headers_cache; 42 | + std::unordered_map<uint256, uint256, FilterHeaderHasher> m_headers_cache GUARDED_BY(m_cs_headers_cache);
ariard commented at 1:25 AM on May 21, 2020:If you have to change PR again, you may comment that key value is block hash and mapped value filter-header, type being the same it may be confusing at first look.
jnewbery commented at 3:06 PM on May 21, 2020:Good point. I'll add a comment if I need to retouch the branch.
ariard commented at 1:29 AM on May 21, 2020: memberCode Review ACK 0187d4c.
I prefer this approach of caching inside index instead of net_processing compare to #16442, it reduces cognitive load. I also assent with ignoring reorg as argued, probability of the event is rare enough and overhead cheap enough to justify having some junk in cache.
laanwj commented at 5:34 PM on May 21, 2020: membercode review ACK 0187d4c118ab4c0f5c2d4fb180c2a8dea8ac53cf
laanwj merged this on May 21, 2020laanwj closed this on May 21, 2020laanwj removed this from the "Blockers" column in a project
jnewbery deleted the branch on May 21, 2020sidhujag referenced this in commit ba41194e48 on May 21, 2020jasonbcox referenced this in commit a4c5ff8ec7 on Nov 19, 2020kittywhiskers referenced this in commit 3dfe7bd4d5 on Aug 22, 2021kittywhiskers referenced this in commit bd73a6b004 on Aug 22, 2021kittywhiskers referenced this in commit 26f05134c8 on Sep 16, 2021kittywhiskers referenced this in commit b5c3500676 on Sep 18, 2021kittywhiskers referenced this in commit 5996dbe686 on Sep 19, 2021UdjinM6 referenced this in commit 4ffd42de63 on Sep 21, 2021thelazier referenced this in commit 853c6f587b on Sep 25, 2021kittywhiskers referenced this in commit 6cedb20e18 on Oct 12, 2021DrahtBot locked this on Feb 15, 2022
github-metadata-mirror
This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-05-02 18:14 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me
