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

aristo: fork support via layers/txframes #2960

Open
wants to merge 46 commits into
base: master
Choose a base branch
from
Open

Conversation

arnetheduck
Copy link
Member

@arnetheduck arnetheduck commented Dec 19, 2024

This change reorganises how the database is accessed: instead holding a "current frame" in the database object, a dag of frames is created based on the "base frame" held in AristoDbRef and all database access happens through this frame, which can be thought of as a consistent point-in-time snapshot of the database based on a particular fork of the chain.

In the code, "frame", "transaction" and "layer" is used to denote more or less the same thing: a dag of stacked changes backed by the on-disk database.

Although this is not a requirement, in practice each frame holds the change set of a single block - as such, the frame and its ancestors leading up to the on-disk state represents the state of the database after that block has been applied.

"committing" means merging the changes to its parent frame so that the difference between them is lost and only the cumulative changes remain - this facility enables frames to be combined arbitrarily wherever they are in the dag.

In particular, it becomes possible to consolidate a set of changes near the base of the dag and commit those to disk without having to re-do the in-memory frames built on top of them - this is useful for "flattening" a set of changes during a base update and sending those to storage without having to perform a block replay on top.

Looking at abstractions, a side effect of this change is that the KVT and Aristo are brought closer together by considering them to be part of the "same" atomic transaction set - the way the code gets organised, applying a block and saving it to the kvt happens in the same "logical" frame - therefore, discarding the frame discards both the aristo and kvt changes at the same time - likewise, they are persisted to disk together

  • this makes reasoning about the database somewhat easier but has the downside of increased memory usage, something that perhaps will need addressing in the future.

Because the code reasons more strictly about frames and the state of the persisted database, it also makes it more visible where ForkedChain should be used and where it is still missing - in particular, frames represent a single branch of history while forkedchain manages multiple parallel forks - user-facing services such as the RPC should use the latter, ie until it has been finalized, a getBlock request should consider all forks and not just the blocks in the canonical head branch.

Another advantage of this approach is that AristoDbRef conceptually becomes more simple - removing its tracking of the "current" transaction stack simplifies reasoning about what can go wrong since this state now has to be passed around in the form of AristoTxRef - as such, many of the tests and facilities in the code that were dealing with "stack inconsistency" are now structurally prevented from happening. The test suite will need significant refactoring after this change.

Once this change has been merged, there are several follow-ups to do:

  • there's no mechanism for keeping frames up to date as they get committed or rolled back - TODO
  • naming is confused - many names for the same thing for legacy reason
  • forkedchain support is still missing in lots of code
  • clean up redundant logic based on previous designs - in particular the debug and introspection code no longer makes sense
  • the way change sets are stored will probably need revisiting - because it's a stack of changes where each frame must be interrogated to find an on-disk value, with a base distance of 128 we'll at minimum have to perform 128 frame lookups for every database interaction - regardless, the "dag-like" nature will stay
  • dispose and commit are poorly defined and perhaps redundant - in theory, one could simply let the GC collect abandoned frames etc, though it's likely an explicit mechanism will remain useful, so they stay for now

More about the changes:

  • AristoDbRef gains a txRef field (todo: rename) that "more or less" corresponds to the old balancer field
  • AristoDbRef.stack is gone - instead, there's a chain of AristoTxRef objects that hold their respective "layer" which has the actual changes
  • No more reasoning about "top" and "stack" - instead, each AristoTxRef can be a "head" that "more or less" corresponds to the old single-history top notion and its stack
  • level still represents "distance to base" - it's computed from the parent chain instead of being stored
  • one has to be careful not to use frames where forkedchain was intended
  • layers are only for a single branch of history!

TODO items for this PR:

fix #2949
fix #2950

This change reorganises how the database is accessed: instead holding a
"current frame" in the database object, a dag of frames is created based
on the "base frame" held in `AristoDbRef` and all database access
happens through this frame, which can be thought of as a consistent
point-in-time snapshot of the database based on a particular fork of the
chain.

In the code, "frame", "transaction" and "layer" is used to denote more
or less the same thing: a dag of stacked changes backed by the on-disk
database.

Although this is not a requirement, in practice each frame holds the
change set of a single block - as such, the frame and its ancestors
leading up to the on-disk state represents the state of the database
after that block has been applied.

"committing" means merging the changes to its parent frame so that the
difference between them is lost and only the cumulative changes remain -
this facility enables frames to be combined arbitrarily wherever they
are in the dag.

In particular, it becomes possible to consolidate a set of changes near
the base of the dag and commit those to disk without having to re-do the
in-memory frames built on top of them - this is useful for "flattening"
a set of changes during a base update and sending those to storage
without having to perform a block replay on top.

Looking at abstractions, a side effect of this change is that the KVT
and Aristo are brought closer together by considering them to be part of
the "same" atomic transaction set - the way the code gets organised,
applying a block and saving it to the kvt happens in the same "logical"
frame - therefore, discarding the frame discards both the aristo and kvt
changes at the same time - likewise, they are persisted to disk together
- this makes reasoning about the database somewhat easier but has the
downside of increased memory usage, something that perhaps will need
addressing in the future.

Because the code reasons more strictly about frames and the state of the
persisted database, it also makes it more visible where ForkedChain
should be used and where it is still missing - in particular, frames
represent a single branch of history while forkedchain manages multiple
parallel forks - user-facing services such as the RPC should use the
latter, ie until it has been finalized, a getBlock request should
consider all forks and not just the blocks in the canonical head branch.

Another advantage of this approach is that `AristoDbRef` conceptually
becomes more simple - removing its tracking of the "current" transaction
stack simplifies reasoning about what can go wrong since this state now
has to be passed around in the form of `AristoTxRef` - as such, many of
the tests and facilities in the code that were dealing with "stack
inconsistency" are now structurally prevented from happening. The test
suite will need significant refactoring after this change.

Once this change has been merged, there are several follow-ups to do:

* there's no mechanism for keeping frames up to date as they get
committed or rolled back - TODO
* naming is confused - many names for the same thing for legacy reason
* forkedchain support is still missing in lots of code
* clean up redundant logic based on previous designs - in particular the
debug and introspection code no longer makes sense
* the way change sets are stored will probably need revisiting - because
it's a stack of changes where each frame must be interrogated to find an
on-disk value, with a base distance of 128 we'll at minimum have to
perform 128 frame lookups for *every* database interaction - regardless,
the "dag-like" nature will stay
* dispose and commit are poorly defined and perhaps redundant - in
theory, one could simply let the GC collect abandoned frames etc, though
it's likely an explicit mechanism will remain useful, so they stay for
now

More about the changes:

* `AristoDbRef` gains a `txRef` field (todo: rename) that "more or less"
corresponds to the old `balancer` field
* `AristoDbRef.stack` is gone - instead, there's a chain of
`AristoTxRef` objects that hold their respective "layer" which has the
actual changes
* No more reasoning about "top" and "stack" - instead, each
`AristoTxRef` can be a "head" that "more or less" corresponds to the old
single-history `top` notion and its stack
* `level` still represents "distance to base" - it's computed from the
parent chain instead of being stored
* one has to be careful not to use frames where forkedchain was intended
- layers are only for a single branch of history!
@jangko jangko marked this pull request as ready for review January 29, 2025 09:36
@jangko jangko requested review from tersec and advaita-saha January 29, 2025 09:37
@jangko
Copy link
Contributor

jangko commented Jan 29, 2025

The regression in hive already fixed, now the FAIL/OK = 42/129.
I know there is still 4 regression compared to master branch. It is related to getScore in newPayload and fCU.
But that can be fixed in separate PR.
Because hive's mapper.jq for nimbus-el also need to be fixed, there is no direct effect if I fixed it here.

@advaita-saha
Copy link
Contributor

The regression in hive already fixed, now the FAIL/OK = 42/129. I know there is still 4 regression compared to master branch. It is related to getScore in newPayload and fCU. But that can be fixed in separate PR. Because hive's mapper.jq for nimbus-el also need to be fixed, there is no direct effect if I fixed it here.

Yeah for sure majority issues are fixed now, but we need to also then fix mapper.jq, please create a issue regarding the changes required or you can also give a PR to hive

index* : int

BranchRef* = ref object
blocks*: seq[BlockDesc]
Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

what's the content of blocks? is it all blocks all the way to the base?

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Only one branch directly contains a base block. All other branches only contains blocks up to the fork block. And they can access the ancestor branch through parent branch.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ok - my gut feeling is that the code would be simplified by removing the additional "branchref" layer and simply have a "BlockDescRef". this would be something to consider for future pr:s..

In particular, when a fork/pruning happens somewhere in the "middle" of the list of blocks here, the logic to split and recombine the branchref into a parent and two mini-branches is susceptible to subtle bugs.

it's certainly not impossible to get this logic right, but even if it "saves" on ref instances by grouping ranges of branch blocks under a single entity, the "range of blocks" doesn't really appear in any first-principle descriptions of how the chain works and therefore, one always has to "reason" about this additional abstraction when relating it to the spec.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Next step after fixing misconception in ForkedChain Need to fix some misconception in ForkedChain
5 participants