Store only the first tree state in each series of identical tree states

[upbqdn]

Storing only the first tree state in each identical series of tree states saves memory, and makes Chain cloning cheaper.

Possible Implementation

We can access the deduped trees using:

Non-finalized state:

Chain.{sapling,orchard}_note_commitment_tree_by_height.range(..=target_height).next_back()

Finalized state (reading is implemented, writing new blocks and updating cached blocks is not):

db.zs_prev_key_value_back_from({sapling,orchard}_note_commitment_tree, target_height)

Performance

This needs a full sync performance test:

The performance of reversed iteration is usually much worse than forward iteration
https://github.com/facebook/rocksdb/wiki/RocksDB-FAQ

[teor2345]

This is important to do eventually because large blocks take up more space on disk. But we don't need to do it any time soon.

[teor2345]

Performance and disk space usage are not a priority for Zebra right now.

[teor2345]

This is required for the note commitment tree scanning in #6642 to have reasonable performance.

[teor2345]

Note from the engineering sync: This seems risky to do between the last release candidate and the first stable release. There is no specific deadline for this change.

[teor2345]

Finalized state:

db.iterator_cf({sapling,orchard}_note_commitment_tree, IteratorMode::From(target_height, Direction::Reverse)).next()

The database read part of this ticket is implemented in PR #6813.

Everything else still needs to be implemented:

• non-finalized state data structure deduplication and lookups
• finalized state deduplication for newly verified blocks
• finalized state deduplication for existing blocks on disk

PR #6813 introduces state minor versions and the idea of a state format update task. But I didn't create the actual task in that PR. I'm happy to help out with that change, currently it's just a vague idea of a design, and a bunch of TODOs.

[teor2345]

@upbqdn lets catch up some time and work out how to make these database changes without breaking compatibility?

[mpguerra]

Please add your planning poker estimate with Zenhub @arya2

[teor2345]

Here's a draft checklist for state format changes, let me know if it works for you!

• update the database format in the Zebra docs
• increment the state minor version
• write the new format in the block write task
• update older formats in the format upgrade task
• test that the new format works when creating a new state, and updating an older state

See the upgrade design docs for more details.

The links won't work until PR #7261 merges.

[teor2345]

Some database compatibility issues have come up in the disk format change part of this ticket, so I'd like to merge them after the 1.1.0 release. This impacts some parts of PR #7266. (But not the compatibility fixes!)

@mpguerra I wasn't sure how to set up those dependencies in ZenHub, did you want to split this ticket into permanent database format changes and in-memory changes? (The memory changes are merged and fine to go in the release.)

[teor2345]

Or we could just remember not to merge PR #7266 before the release.

[mpguerra]

Some database compatibility issues have come up in the disk format change part of this ticket, so I'd like to merge them after the 1.1.0 release. This impacts some parts of PR #7266. (But not the compatibility fixes!)

@mpguerra I wasn't sure how to set up those dependencies in ZenHub, did you want to split this ticket into permanent database format changes and in-memory changes? (The memory changes are merged and fine to go in the release.)

I blocked #7266 on the v1.1.0 release, however that won't physically stop it from merging so I would just add the do-not-merge label to it for now and we need to remember to remove it after the release

[mpguerra]

Did this close by mistake? Or are all the PRs for this issue done already?

[upbqdn]

This shouldn't have been closed. The only reason I can think of might be this line in the PR description:

Address part of #4784.

Which seems odd.

[mpguerra]

I think it's because I linked a PR with this issue in the Github interface and when that PR close this automatically closed also

[upbqdn]

I haven't used that feature yet.