[Perf] Facilitate the caching of the block tree #3030

ljedrz · 2025-11-18T16:10:29Z

This PR targets #3026.

I used pprof to analyze the loading of a full mainnet ledger, and the resulting flamegraph:

indicated that nearly 96% of the associated work is the creation of the block tree. I double-checked it, and indeed, around 90% of the loading time was spent on that operation.

These changes facilitate the caching of the block tree alongside the ledger, and automatically loading it on startup. A snarkOS counterpart PR will follow, where one of the methods introduced here will be automatically called on shutdown.

While I don't have the full mainnet ledger locally, I have verified that the one I do have loads more quickly when these changes are introduced.

Signed-off-by: ljedrz <[email protected]>

ljedrz · 2025-11-20T08:52:15Z

I ran the numbers on a full maninnet ledger after these changes, and it's a clear improvement:

before: 239.75s
after:   27.82s (down 88%)

Dumping the serialized block tree took 2.48s, and the resulting file was 965MiB.

For future reference, I'm also attaching the updated flamegraph of a ledger load (w/o rayon for increased clarity):

I'll analyze it to see if there's room for more improvement, but these would be follow-ups unrelated to the changes from this PR.

kaimast · 2025-11-20T18:00:00Z

ledger/store/src/helpers/rocksdb/block.rs

+
+        if let Ok(serialized_tree) = fs::read(&path) {
+            // Deserialize a ready block tree.
+            let ret = bincode::deserialize(&serialized_tree).or_else(|e| {


Should there be additional checks here to ensure the block tree is up-to-date? I think you can just compare the most recent block hashes.

note L259: the file is removed as soon as it's loaded, in order to ensure that it won't be reused, and the new one is only created on shutdown (on snarkOS side); it's a valid concern if we ever want to cache the block tree outside of shutdown conditions, but I don't think we do

My worry was about clients moving ledger snapshots around and restoring an old file. Another, very unlikely, case is that the file gets corrupted but deserializes fine.
Adding another sanity check, if not too expensive, could save us some headaches in the future.

sure, that's a fair concern; I'm not too savvy with the tree myself, do you have a suggestion how to easily sanity-check it? or @vicsn?

The merkle tree's leaves are the block hashes.

Inside of struct MerkleTree, we still store hashes of those leaves in:

/// The internal hashes, from root to hashed leaves, of the full Merkle tree. tree: Vec<PH::Hash>,

Looking at the API which MerkleTree exposes, I see 3 options. We should pick one which balances simplicity and speed:

use pub const fn number_of_leaves to see if it matches the number of blocks (not sure if this requires iterating over the entire db index).

use pub fn prove the final leave see if it returns without error (not very idiomatic)

use pub fn leaf_hashes to match the last block hash (though note you have to manually hash the leave to see if it matches)

ledger/store/src/block/mod.rs

kaimast · 2025-11-20T18:09:15Z

Looks great to me! I left one comment about potentially loading an outdated cache, which I believe needs to addressed.

Additionally, I wonder if we could store the block tree on Ledger::drop and not have snarkOS counterpart. That would be cleaner and ensure it is only invoked during shutdown. snarkOS shutdown is a little messy as of now, though, so that might be not possible yet (hence ProvableHQ/snarkOS#3915).

Signed-off-by: ljedrz <[email protected]>

vicsn · 2025-11-21T09:48:36Z

PR looks great, will approve after Kai's comments are addressed

ljedrz · 2025-11-21T09:54:40Z

I wonder if we could store the block tree on Ledger::drop and not have snarkOS counterpart.

Yeah, it did work just fine, and I guess there's no reason not to have it happen implicitly; I'll remove the snarkOS-side PR if this change is accepted.

In other words, review comments addressed.

ljedrz · 2025-11-21T11:34:57Z

After some additional tests I noticed that the Ledger is not internally Arced, so the Drop impl needs to be adjusted; I should have it ready soon.

Signed-off-by: ljedrz <[email protected]>

ljedrz · 2025-11-21T12:43:54Z

This is the right direction, but I'm not always seeing the Drop being triggered; I need to run some more snarkOS tests.

ljedrz · 2025-11-21T13:15:52Z

@kaimast ok, I have a temporary shutdown solution for snarkOS to ensure that the Drop gets triggered. I'll propose it, and it can later be superseded by your changes.

Edit: filed as ProvableHQ/snarkOS#4021.

vicsn

LGTM, but let's await Kai

ledger/store/src/helpers/rocksdb/block.rs

…hecked Signed-off-by: ljedrz <[email protected]>

ljedrz · 2025-11-25T15:17:57Z

I've introduced a very cheap (basically free) coherence check in Ledger::load_unchecked; as a bonus, we now call BlockStore::max_height - which traverses the entire reverse state root map (meaning it is somewhat expensive, even though it is optimized) - only once.

vicsn · 2025-11-25T17:43:35Z

ledger/src/lib.rs

-        let latest_height =
-            ledger.vm.block_store().max_height().with_context(|| "Failed to load blocks from the ledger")?;
+        // Ensure that the greatest stored height matches that of the block tree.
+        ensure!(


Brilliant find - can you confirm that you manually tested that we get the expected error message? A simple way could be to run a network, remove a node's ledger but nót their block cache, and then to start the node again

I did test locally that it works, though I haven't swapped the cached tree to check the error; that being said, I initially used the value of 1 instead of 0 for the genesis scenario, and the node did fail to load (but I don't remember if the message was there). I can double-check with a swapped ledger as soon as I can.

…h the storage Signed-off-by: ljedrz <[email protected]>

ljedrz · 2025-11-26T09:02:52Z

I've tested both possible cases:

when the block tree is above the storage, BlockStore::open now fails with Block {height} exists in tree but not in storage; perhaps you used a wrong block tree cache file?
when the block tree is below the storage, Ledger::load_unchecked now fails with The stored height is different than the one in the block tree; please ensure that the cached block tree is valid or delete it

raychu86 · 2025-11-26T18:04:29Z

ledger/store/src/block/mod.rs

-        // Construct the block tree.
-        debug!("Found {} blocks on disk", hashes.len());
-        let tree = N::merkle_tree_bhp(&hashes)?;
+        let tree = storage.create_block_tree()?;


Can you add subsequent checks here to ensure that the root of the block tree matches the proper state root in the state_root_map for the expected block height that the tree is supposed to represent?

If this fails, we would need to reconstruct the tree from scratch.

raychu86 · 2025-11-26T18:05:35Z

ledger/store/src/block/mod.rs

+
+    /// Serializes and persists the current block tree.
+    #[cfg(feature = "rocks")]
+    pub fn cache_block_tree(&self) -> Result<()> {


Is there a lock we can add to enforce that this operation is properly performed and completed at shutdown?

This is executed as part of the Drop impl for the Ledger, which is a synchronous operation and always fully concludes on a clean shutdown, and in snarkOS, even in case of a panic (as it uses the default panic = "unwind" mode); using a lock isn't necessary, as the aforementioned impl has full exclusive ownership of the Ledger (via &mut self).

Is this documented somewhere in the code? It'd be nice to indicate the atomic properties of the Drop impl

Isn't the block store also dropped when dropping the ledger? Maybe we could not expose this function at all, and just have it happen on drop?

@raychu86 I extended the docs for the Drop impl.
@kaimast I think there is utility in having it as a method on BlockStore too, in case we want to use it for some test run or if we ever need to extend the Drop impl for the Ledger (which is the right impl to use, as all the stores only ever exist as part of the Ledger, so it's a clear central point for cleanups).

Signed-off-by: ljedrz <[email protected]>

ledger/src/lib.rs

kaimast

LGTM! I think @raychu86 comments are all addressed as well.

ledger/store/src/block/mod.rs

vicsn · 2025-12-18T16:31:09Z

@ljedrz can you merge in origin/staging?

Signed-off-by: ljedrz <[email protected]>

ljedrz · 2025-12-19T09:16:00Z

Merged staging and addressed the final suggestions.

ljedrz added 3 commits November 18, 2025 13:57

feat: facilitate the (de)serialization of the MerkleTree

315a73c

Signed-off-by: ljedrz <[email protected]>

perf: allow the block tree to be cached

d5b8d5a

Signed-off-by: ljedrz <[email protected]>

chore: adjust the lockfile

a10b0b7

Signed-off-by: ljedrz <[email protected]>

ljedrz requested a review from vicsn November 18, 2025 16:10

ljedrz mentioned this pull request Nov 18, 2025

[Perf] Cache the block tree on shutdown ProvableHQ/snarkOS#4017

Closed

ljedrz mentioned this pull request Nov 20, 2025

[Perf] More unchecked deserialization from the DB #3034

Merged

kaimast reviewed Nov 20, 2025

View reviewed changes

ledger/store/src/block/mod.rs Outdated Show resolved Hide resolved

ljedrz added 2 commits November 21, 2025 10:13

perf: use a BufWriter to dump the block tree

f0d9b5e

Signed-off-by: ljedrz <[email protected]>

feat: cache the block tree when dropping the Ledger

6578b41

Signed-off-by: ljedrz <[email protected]>

ljedrz mentioned this pull request Nov 21, 2025

[Feature] Implement a parallel chunked serialization utility #3037

Open

ljedrz marked this pull request as draft November 21, 2025 11:34

ljedrz force-pushed the perf/cache_block_tree branch from a9bbcf9 to 9dfebec Compare November 21, 2025 12:17

ljedrz marked this pull request as ready for review November 21, 2025 12:18

refactor: wrap the Ledger in an Arc

66f8742

Signed-off-by: ljedrz <[email protected]>

ljedrz force-pushed the perf/cache_block_tree branch from 9dfebec to 66f8742 Compare November 21, 2025 12:30

ljedrz marked this pull request as draft November 21, 2025 12:43

ljedrz marked this pull request as ready for review November 21, 2025 13:15

vicsn approved these changes Nov 22, 2025

View reviewed changes

vicsn reviewed Nov 24, 2025

View reviewed changes

ledger/store/src/helpers/rocksdb/block.rs Show resolved Hide resolved

tweak: perform a cheap coherence check for height in Ledger::load_unc…

a9fa52a

…hecked Signed-off-by: ljedrz <[email protected]>

vicsn reviewed Nov 25, 2025

View reviewed changes

logs: provide additional information when the block tree doesn't matc…

6515e41

…h the storage Signed-off-by: ljedrz <[email protected]>

vicsn approved these changes Nov 26, 2025

View reviewed changes

raychu86 assigned raychu86 and unassigned raychu86 Nov 26, 2025

raychu86 requested changes Nov 26, 2025

View reviewed changes

ljedrz added 2 commits November 27, 2025 14:58

feat: add an extra safeguard to Ledger::load_unchecked

88f2a3f

Signed-off-by: ljedrz <[email protected]>

logs: add a DEBUG log indicating the source for the block tree

ebfff4c

Signed-off-by: ljedrz <[email protected]>

ljedrz requested a review from raychu86 November 27, 2025 14:06

docs: add an extra comment to Ledger::drop

27d6dc8

Signed-off-by: ljedrz <[email protected]>

kaimast reviewed Dec 5, 2025

View reviewed changes

ledger/src/lib.rs Outdated Show resolved Hide resolved

kaimast self-requested a review December 5, 2025 21:36

kaimast approved these changes Dec 5, 2025

View reviewed changes

raychu86 reviewed Dec 17, 2025

View reviewed changes

ledger/store/src/block/mod.rs Outdated Show resolved Hide resolved

raychu86 approved these changes Dec 17, 2025

View reviewed changes

ljedrz added 2 commits December 19, 2025 09:38

tweak: apply review comments

89a002e

Signed-off-by: ljedrz <[email protected]>

Merge branch 'staging' into perf/cache_block_tree

e84a844

vicsn approved these changes Dec 19, 2025

View reviewed changes

vicsn merged commit 4e3855d into ProvableHQ:staging Dec 19, 2025
6 of 7 checks passed

[Perf] Facilitate the caching of the block tree #3030

[Perf] Facilitate the caching of the block tree #3030

Uh oh!

Conversation

ljedrz commented Nov 18, 2025

Uh oh!

ljedrz commented Nov 20, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kaimast commented Nov 20, 2025

Uh oh!

vicsn commented Nov 21, 2025

Uh oh!

ljedrz commented Nov 21, 2025

Uh oh!

ljedrz commented Nov 21, 2025

Uh oh!

ljedrz commented Nov 21, 2025

Uh oh!

ljedrz commented Nov 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vicsn left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ljedrz commented Nov 25, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ljedrz Nov 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ljedrz commented Nov 26, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ljedrz Nov 27, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kaimast left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vicsn commented Dec 18, 2025

Uh oh!

ljedrz commented Dec 19, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

ljedrz commented Nov 21, 2025 •

edited

Loading

ljedrz Nov 25, 2025 •

edited

Loading

ljedrz Nov 27, 2025 •

edited

Loading