Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize iteration over the keys in the database #1997

Closed
xgreenx opened this issue Jun 28, 2024 · 4 comments
Closed

Optimize iteration over the keys in the database #1997

xgreenx opened this issue Jun 28, 2024 · 4 comments
Assignees
Labels
good first issue Good for newcomers

Comments

@xgreenx
Copy link
Collaborator

xgreenx commented Jun 28, 2024

We have many cases when we need to iterate only over keys of the specific table/column. The current iteration logic loads both key and values into memory and later discards values. To avoid vesting of resources, we can add more functionality and provide iteration only over the keys.

As an example:
When we want to get the last block height, we load the whole CompressedBlock into the memory, when we don't need it.

xgreenx added a commit that referenced this issue Jul 4, 2024
Closes #451

## Overview

Added support for the state rewind feature. The feature allows the
execution of the blocks in the past and the same execution results to be
received. Together with forkless upgrades, execution of any block from
the past is possible if historical data exist for the target block
height. The default size of historical/rewind window is 7 days.

Also added support for rollback command when state rewind feature is
enabled. The command allows the rollback of the state of the blockchain
several blocks behind until the end of the historical window.

## Implementation details

The change adds a new `HistoricalRocksDB` type that is the wrapper
around regular `RocksDB`. This type has inside another RocksDB instance
that is used to duplicate all tables plus has one more column to store
the reverse modifications at each block height. The reverse modification
is the opposite to the operation that was done during transition from
block height X to X + 1. The screenshot below should describe the idea:

<img width="723" alt="image"
src="https://github.com/FuelLabs/fuel-core/assets/18346821/c4becce0-1669-4938-8dd7-87d274efa224">

The key of duplicated tables is extended with block height, and the
value is the reverse operation to reach the state of entry at the
previous height. Having the history of reverse operations, we can
iterate back from the latest version of the entry to the previous one.

Using the main property of the RocksDB(sorting keys by default), lookup
operations are fast and we don't need to iterate all modifications. It
is just enough to find the nearest reverse operation to the target
height.

## Checklist
- [x] New behavior is reflected in tests

### Before requesting review
- [x] I have reviewed the code myself
- [x] I have created follow-up issues caused by this PR and linked them
here
  - #1997
  - #1995
  - #1993
@xgreenx xgreenx added the good first issue Good for newcomers label Aug 12, 2024
@vishnuc77
Copy link

Hi @xgreenx, I'm a first time contributor trying to get involved with the project.
I would like to know whether this task is something like making use of iter_all_keys() in place of (and other similar places) :

pub fn latest_height(&self) -> StorageResult<BlockHeight> {
        self.iter_all::<FuelBlocks>(Some(IterDirection::Reverse))
            .next()
            .ok_or(not_found!("BlockHeight"))?
            .map(|(height, _)| height)
 }

so that CompressedBlock itself would not be loaded into memory, or is there something more to it?

@rymnc rymnc self-assigned this Aug 14, 2024
@rymnc
Copy link
Member

rymnc commented Aug 14, 2024

taking this up 😁

rymnc added a commit that referenced this issue Aug 14, 2024
…2076)

## Linked Issues

Related #1997

## Description

Replaces usages of `iter_all` with `iter_all_keys` in instances where we
only need to iterate over the keys. A follow up PR will be made to
actually iterate over the keys without making allocations for the
values, as described in
https://github.com/FuelLabs/fuel-core/blob/a9e5e89f5fb38e3b3d6e6bdfe1ad339a01f2f3b9/crates/storage/src/iter.rs#L130

## Checklist
- [x] Breaking changes are clearly marked as such in the PR description
and changelog (no breaking changes)
- [x] New behavior is reflected in tests (existing test cases which test
behaviour of iterators pass)
- [x] [The specification](https://github.com/FuelLabs/fuel-specs/)
matches the implemented behavior (no changes to the spec)

### Before requesting review
- [x] I have reviewed the code myself
- [ ] I have created follow-up issues caused by this PR and linked them
here

### After merging, notify other teams

[Add or remove entries as needed]

- [ ] [Rust SDK](https://github.com/FuelLabs/fuels-rs/)
- [ ] [Sway compiler](https://github.com/FuelLabs/sway/)
- [ ] [Platform
documentation](https://github.com/FuelLabs/devrel-requests/issues/new?assignees=&labels=new+request&projects=&template=NEW-REQUEST.yml&title=%5BRequest%5D%3A+)
(for out-of-organization contributors, the person merging the PR will do
this)
- [ ] Someone else?
rymnc added a commit that referenced this issue Aug 19, 2024
## Linked Issues/PRs
<!-- List of related issues/PRs -->

- #1997
- #2076

## Description
<!-- List of detailed changes -->
Implements `iter_store_keys` and `iter_keys` appropriately for in memory
stores and rocksdb. The previous PR made them call it, and this one
changes the underlying implementation to avoid value allocations.

## Checklist
- [x] Breaking changes are clearly marked as such in the PR description
and changelog (no breaking changes)
- [x] New behavior is reflected in tests (tests which test this
behaviour under the hood still pass)
- [x] [The specification](https://github.com/FuelLabs/fuel-specs/)
matches the implemented behavior (no changes to spec)

### Before requesting review
- [x] I have reviewed the code myself
- [x] I have created follow-up issues caused by this PR and linked them
here

### After merging, notify other teams

[Add or remove entries as needed]

- [ ] [Rust SDK](https://github.com/FuelLabs/fuels-rs/)
- [ ] [Sway compiler](https://github.com/FuelLabs/sway/)
- [ ] [Platform
documentation](https://github.com/FuelLabs/devrel-requests/issues/new?assignees=&labels=new+request&projects=&template=NEW-REQUEST.yml&title=%5BRequest%5D%3A+)
(for out-of-organization contributors, the person merging the PR will do
this)
- [ ] Someone else?

---------

Co-authored-by: Hannes Karppila <2204863+Dentosal@users.noreply.github.com>
Co-authored-by: green <xgreenx9999@gmail.com>
@rymnc
Copy link
Member

rymnc commented Aug 19, 2024

should we mark this as closed with #2092?
cc: @xgreenx

@xgreenx
Copy link
Collaborator Author

xgreenx commented Aug 19, 2024

Closed via #2092

@xgreenx xgreenx closed this as completed Aug 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
good first issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

3 participants