Details

Reviewers

None

Group Reviewers

Restricted Project

Summary

We don't want to copy all the block hashes starting at the genesis when most of them will just be ignored because their hashes are already cached.
This diff is a performance optimization.

There are 4 cases to consider:

the cache is empty, so we pass all blockhashes starting at the genesis block (height 0)
the cache has already some of the value it needs, so we pass a shorter range of blockhashes (omitting the lower heights)
the cache has more values than it needs, so we don't pass any hashes (empty vector)
the cache has enough values, but we are requesting the merkle data for an odd number of blockhashes, so we need to pass the last hash so it can be duplicated.

In any case, we pass the blockhash that is the first hash in branch as a parameter to the merkle_root_and_branch method, because now the merkle tree cache may no longer have access to it.

Test Plan

ninja all check-all

Diff Detail

Repository

rABC Bitcoin ABC

Branch

chronik_merkle_optimizewq

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 30415
Build 60350: Build Diff	chronik-client-integration-tests · ecash-lib-integration-tests · ecash-agora-integration-tests · build-chronik-plugins · build-chronik
Build 60349: arc lint + arc unit

Event Timeline

PiRK created this revision.Sep 24 2024, 12:43

Herald added a reviewer: Restricted Project. · View Herald TranscriptSep 24 2024, 12:43

Harbormaster completed remote builds in B30399: Diff 49794.Sep 24 2024, 12:50

Build Bitcoin ABC Diffs / Diff Testing (build-chronik) failed.

Tail of the build log:

   Doc-tests chronik-bridge

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-db

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-http

running 1 test
test chronik/chronik-http/src/protobuf.rs - protobuf::Protobuf (line 29) ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.35s

   Doc-tests chronik-indexer

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-common

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-impl

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-proto

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-util

running 2 tests
test chronik/chronik-util/src/log.rs - log::log (line 65) ... ignored
test chronik/chronik-util/src/log.rs - log::log_chronik (line 87) ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik failed with exit code 1

Build Bitcoin ABC Diffs / Diff Testing (build-chronik-plugins) failed.

Tail of the build log:

   Doc-tests chronik-bridge

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-db

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-http

running 1 test
test chronik/chronik-http/src/protobuf.rs - protobuf::Protobuf (line 29) ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.32s

   Doc-tests chronik-indexer

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-common

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-impl

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-proto

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-util

running 2 tests
test chronik/chronik-util/src/log.rs - log::log (line 65) ... ignored
test chronik/chronik-util/src/log.rs - log::log_chronik (line 87) ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik-plugins failed with exit code 1

fix stuff (it wasn't working when computing an earlier checkpoint)

Benchmark:

$ python
Python 3.12.3 (main, Sep 11 2024, 14:17:37) [GCC 13.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from chronik import client
>>> cl = client.ChronikClient("127.0.0.1", 8331)
>>> pb = cl.block_header(863480, 863480)
>>> pb = cl.block_header(863482, 863482)
>>> pb = cl.block_header(863484, 863484)
>>> pb = cl.block_header(863486, 863486)
>>> pb = cl.block_header(863488, 863488)

Before:

Time elapsed fetching headers is: 96.03466ms
Time elapsed computing merkle tree is: 144.438252ms

Time elapsed fetching headers is: 87.074127ms
Time elapsed computing merkle tree is: 54.741982ms

Time elapsed fetching headers is: 87.528585ms
Time elapsed computing merkle tree is: 49.760862ms

Time elapsed fetching headers is: 87.293025ms
Time elapsed computing merkle tree is: 55.79699ms

Time elapsed fetching headers is: 86.483147ms
Time elapsed computing merkle tree is: 48.828292ms

After

Time elapsed fetching headers is: 111.042448ms
Time elapsed computing merkle tree is: 156.884874ms

Time elapsed fetching headers is: 2.394µs
Time elapsed computing merkle tree is: 28.181696ms

Time elapsed fetching headers is: 1.523µs
Time elapsed computing merkle tree is: 18.933433ms

Time elapsed fetching headers is: 2.404µs
Time elapsed computing merkle tree is: 18.623238ms

Time elapsed fetching headers is: 3.226µs
Time elapsed computing merkle tree is: 18.615498ms

I found this issue while working on an optimization to not load all the blockhashes when we only need the last few ones.

Harbormaster completed remote builds in B30401: Diff 49800.Sep 24 2024, 16:24

wrap some of the newly added complexity in a BlockMerkleTree method (getting the required range of block hashes depending on the cache state)

Harbormaster completed remote builds in B30413: Diff 49821.Sep 25 2024, 10:15

Build Bitcoin ABC Diffs / Diff Testing (build-chronik) failed.

Tail of the build log:

    Checking chronik-plugin-common v0.1.0 (/work/chronik/chronik-plugin-common)
    Checking pin-project v1.1.5
    Checking tungstenite v0.21.0
   Compiling prost-build v0.11.9
    Checking chronik-plugin v0.1.0 (/work/chronik/chronik-plugin)
    Checking toml_datetime v0.6.6
    Checking serde_spanned v0.6.6
    Checking hyper v1.2.0
   Compiling pyo3 v0.22.2
    Checking topo_sort v0.4.0
    Checking seahash v4.1.0
    Checking sync_wrapper v0.1.2
    Checking winnow v0.6.13
    Checking mime v0.3.17
    Checking tokio-tungstenite v0.21.0
    Checking axum-core v0.4.3
    Checking tower v0.4.13
    Checking memoffset v0.9.1
    Checking serde_json v1.0.115
    Checking serde_urlencoded v0.7.1
    Checking hyper-util v0.1.3
    Checking futures-executor v0.3.30
    Checking serde_path_to_error v0.1.16
    Checking base64 v0.21.7
    Checking sync_wrapper v1.0.1
    Checking unicode-segmentation v1.11.0
    Checking matchit v0.7.3
    Checking unindent v0.2.3
   Compiling chronik-proto v0.1.0 (/work/chronik/chronik-proto)
    Checking tower-http v0.5.2
    Checking futures v0.3.30
    Checking convert_case v0.6.0
   Compiling chronik-bridge v0.1.0 (/work/chronik/chronik-bridge)
    Checking toml_edit v0.22.14
   Compiling librocksdb-sys v0.11.0+8.1.1
    Checking axum v0.7.5
   Compiling pyo3-macros v0.22.2
    Checking toml v0.8.14
    Checking chronik-plugin-impl v0.1.0 (/work/chronik/chronik-plugin-impl)
    Checking rocksdb v0.21.0
    Checking chronik-db v0.1.0 (/work/chronik/chronik-db)
    Checking chronik-indexer v0.1.0 (/work/chronik/chronik-indexer)
error: unneeded `return` statement
   --> chronik/chronik-indexer/src/merkle.rs:109:17
    |
109 |                 return None;
    |                 ^^^^^^^^^^^
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_return
    = note: `-D clippy::needless-return` implied by `-D warnings`
    = help: to override `-D warnings` add `#[allow(clippy::needless_return)]`
help: remove `return`
    |
109 -                 return None;
109 +                 None
    |

error: could not compile `chronik-indexer` (lib) due to 1 previous error
ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik failed with exit code 1

Build Bitcoin ABC Diffs / Diff Testing (build-chronik-plugins) failed.

Tail of the build log:

    Checking serde_urlencoded v0.7.1
    Checking hyper-util v0.1.3
    Checking futures-executor v0.3.30
    Checking serde_path_to_error v0.1.16
    Checking sync_wrapper v1.0.1
    Checking matchit v0.7.3
    Checking base64 v0.21.7
   Compiling chronik-proto v0.1.0 (/work/chronik/chronik-proto)
    Checking unindent v0.2.3
    Checking unicode-segmentation v1.11.0
    Checking futures v0.3.30
    Checking tower-http v0.5.2
    Checking convert_case v0.6.0
   Compiling chronik-bridge v0.1.0 (/work/chronik/chronik-bridge)
    Checking toml_edit v0.22.14
   Compiling librocksdb-sys v0.11.0+8.1.1
    Checking axum v0.7.5
   Compiling pyo3-macros v0.22.2
    Checking toml v0.8.14
    Checking chronik-plugin-impl v0.1.0 (/work/chronik/chronik-plugin-impl)
    Checking rocksdb v0.21.0
    Checking chronik-db v0.1.0 (/work/chronik/chronik-db)
    Checking chronik-indexer v0.1.0 (/work/chronik/chronik-indexer)
error: unneeded `return` statement
   --> chronik/chronik-indexer/src/merkle.rs:109:17
    |
109 |                 return None;
    |                 ^^^^^^^^^^^
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_return
    = note: `-D clippy::needless-return` implied by `-D warnings`
    = help: to override `-D warnings` add `#[allow(clippy::needless_return)]`
help: remove `return`
    |
109 -                 return None;
109 +                 None
    |

error: could not compile `chronik-indexer` (lib) due to 1 previous error
[7/7] cd /work && /usr/bin/cmake -E env CARGO_TARGET_DIR="/work/abc-ci-builds/build-chronik-plugins/cargo/build" CARGO_BUILD_RUSTC="/root/.rustup/toolchains/1.76.0-x86_64-unknown-linux-gnu/bin/rustc" CARGO_BUILD_RUSTDOC="/root/.cargo/bin/rustdoc" /root/.rustup/toolchains/1.76.0-x86_64-unknown-linux-gnu/bin/cargo --locked clippy --package 'abc-rust-*' -- -D warnings
warning: virtual workspace defaulting to `resolver = "1"` despite one or more workspace members being on edition 2021 which implies `resolver = "2"`
note: to keep the current resolver, specify `workspace.resolver = "1"` in the workspace root's manifest
note: to use the edition 2021 resolver, specify `workspace.resolver = "2"` in the workspace root's manifest
note: for more details see https://doc.rust-lang.org/cargo/reference/resolver.html#resolver-versions
    Blocking waiting for file lock on package cache
    Blocking waiting for file lock on package cache
    Blocking waiting for file lock on package cache
    Blocking waiting for file lock on package cache
    Blocking waiting for file lock on build directory
    Checking memchr v2.7.2
    Checking libc v0.2.153
    Checking bytes v1.6.0
    Checking http v1.1.0
    Checking object v0.32.2
    Checking backtrace v0.3.71
    Checking stable-eyre v0.2.2
    Checking abc-rust-error v0.1.0 (/work/chronik/abc-rust-error)
    Finished dev [unoptimized + debuginfo] target(s) in 6m 24s
ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik-plugins failed with exit code 1

abstract away more complexity (bock height of the first blockhash passed in the vector). Now we only need to pass the checkpoint height to the merkle_root_and_branch method, and it computes the value on its own. So now we assume that we pass the exact number of required hashes.

PiRK published this revision for review.Sep 25 2024, 11:37

Harbormaster completed remote builds in B30415: Diff 49823.Sep 25 2024, 11:42

Build Bitcoin ABC Diffs / Diff Testing (build-chronik) failed.

Tail of the build log:

   Doc-tests chronik-bridge

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-db

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-http

running 1 test
test chronik/chronik-http/src/protobuf.rs - protobuf::Protobuf (line 29) ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.32s

   Doc-tests chronik-indexer

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-common

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-plugin-impl

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-proto

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests chronik-util

running 2 tests
test chronik/chronik-util/src/log.rs - log::log (line 65) ... ignored
test chronik/chronik-util/src/log.rs - log::log_chronik (line 87) ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik failed with exit code 1

Build Bitcoin ABC Diffs / Diff Testing (build-chronik-plugins) failed.

Tail of the build log:

    Checking axum-core v0.4.3
    Checking hyper v1.2.0
    Checking tokio-tungstenite v0.21.0
    Checking tower v0.4.13
    Checking memoffset v0.9.1
    Checking serde_json v1.0.115
    Checking serde_urlencoded v0.7.1
    Checking futures-executor v0.3.30
    Checking serde_path_to_error v0.1.16
    Checking hyper-util v0.1.3
    Checking unicode-segmentation v1.11.0
    Checking base64 v0.21.7
    Checking matchit v0.7.3
    Checking sync_wrapper v1.0.1
    Checking unindent v0.2.3
    Checking tower-http v0.5.2
    Checking futures v0.3.30
    Checking convert_case v0.6.0
    Checking toml_edit v0.22.14
   Compiling chronik-proto v0.1.0 (/work/chronik/chronik-proto)
   Compiling chronik-bridge v0.1.0 (/work/chronik/chronik-bridge)
   Compiling librocksdb-sys v0.11.0+8.1.1
    Checking axum v0.7.5
   Compiling pyo3-macros v0.22.2
    Checking toml v0.8.14
    Checking chronik-plugin-impl v0.1.0 (/work/chronik/chronik-plugin-impl)
    Checking rocksdb v0.21.0
    Checking chronik-db v0.1.0 (/work/chronik/chronik-db)
    Checking chronik-indexer v0.1.0 (/work/chronik/chronik-indexer)
error: unneeded `return` statement
  --> chronik/chronik-indexer/src/merkle.rs:98:17
   |
98 |                 return checkpoint_height + 1;
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_return
   = note: `-D clippy::needless-return` implied by `-D warnings`
   = help: to override `-D warnings` add `#[allow(clippy::needless_return)]`
help: remove `return`
   |
98 -                 return checkpoint_height + 1;
98 +                 checkpoint_height + 1
   |

error: unneeded `return` statement
   --> chronik/chronik-indexer/src/merkle.rs:127:17
    |
127 |                 return None;
    |                 ^^^^^^^^^^^
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_return
help: remove `return`
    |
127 -                 return None;
127 +                 None
    |

error: could not compile `chronik-indexer` (lib) due to 2 previous errors
ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik-plugins failed with exit code 1

PiRK edited the summary of this revision. (Show Details)Sep 25 2024, 11:47

please the compiler warnings
It is not clear to me why on these two the return statement can be omitted but not on the previous lines (93 and 96, 121 and 115)

error[E0308]: mismatched types
  --> chronik/chronik-indexer/src/merkle.rs:93:21
   |
92 | /                 if height < checkpoint_height {
93 | |                     height + 1
   | |                     ^^^^^^^^^^ expected `()`, found `usize`
94 | |                 }
   | |_________________- expected this to be `()`
   |
help: consider using a semicolon here
   |
94 |                 };
   |                  +
help: you might have meant to return this value
   |
93 |                     return height + 1;
   |                     ++++++           +

Harbormaster completed remote builds in B30417: Diff 49825.Sep 25 2024, 12:16

tobias_ruck added a subscriber: tobias_ruck.Sep 25 2024, 16:50

tobias_ruck added inline comments.

chronik/chronik-indexer/src/merkle.rs
92–98 ↗	(On Diff #49825)	if you don't want return you have to make it into an expression maybe this helps? https://stackoverflow.com/a/68795755

Put this on hold for now, it makes things more complicated. If perf does turn out to be an issue in production we can reconsider doing this.

[chronik] pass only required block hashes to merkle tree cache
AbandonedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 49823

chronik/chronik-indexer/src/merkle.rs

chronik/chronik-indexer/src/query/blocks.rs

[chronik] pass only required block hashes to merkle tree cacheAbandonedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 49823

chronik/chronik-indexer/src/merkle.rs

chronik/chronik-indexer/src/query/blocks.rs

[chronik] pass only required block hashes to merkle tree cache
AbandonedPublic
Actions

Revision Contents
Changeset List