Skip to content

Checkpoint: Skip-List Traversal with Fat checkpoints #92

@julio4

Description

@julio4

See #91

Modify the Checkpoint architecture to support non-linear history traversal. Currently, DatabaseRef implementations must traverse the entire linked list to find a state key. We need to introduce a "skip-list" mechanism where checkpoints can reference a "Fat" ancestor containing accumulated state.

Update CheckpointInner to include:

  • accumulated_state: Option<BundleState>: The merged state up to this point.
  • fat_ancestor: Option<Arc<Self>>: A direct reference to the nearest "Fat" checkpoint.

Update Traversal Logic in DatabaseRef implementation for Checkpoint to use fat_ancestor

  • Check local state -> Check accumulated state -> Jump to fat_ancestor or Fallback to linear prev scan/Base state.

Explicit Accumulation

  • Add a public .fat() method to Checkpoint that forces the creation of an accumulated checkpoint at the current tip.
  • Use BundleState::extend to merge state transitions correctly.

CheckpointInner struct should be updated without breaking existing public API.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions