| # Proposal: Counted Reversible Overlay Diffs
|
|
|
| ## Summary
|
|
|
| Use **per-key change counts carried by both overlay state and diffs**, together
|
| with distinct operations for confirming a prefix and reverting a suffix. Keep
|
| `phantom_removals` to distinguish cancellation from deletion of an existing
|
| value.
|
|
|
| This is a design proposal. The complete design has not been implemented in the
|
| repository.
|
|
|
| The required behavior is:
|
|
|
| - Apply diffs oldest-first and revert them newest-first.
|
| - Replay diffs on other overlays with a compatible logical starting state.
|
| - Preserve later pending changes when an earlier prefix reaches the database.
|
| - Clear all pending state when all represented changes have been applied.
|
| - Support empty values, cancellations, repeated values, and tree lifecycle
|
| changes on both Fjall and Sled.
|
| - Avoid rebuilding the entire remaining sequence during cleanup or rollback.
|
|
|
| ## 1. The information missing from the current state
|
|
|
| Consider:
|
|
|
| ```text
|
| D0: insert k, remove k
|
| D1: insert k=v
|
| D2: remove k
|
| ```
|
|
|
| The final raw overlay state contains `removed[k]`. D0's diff contains a phantom
|
| removal for the same key.
|
|
|
| The current state-cleanup loop removes that marker unconditionally:
|
|
|
| ```rust
|
| for k in diff.removed.keys().chain(diff.phantom_removals.iter()) {
|
| self.removed.remove(k);
|
| }
|
| ```
|
|
|
| Two histories require different results:
|
|
|
| | Pending history | Current raw state | Required state after confirming D0 |
|
| | --- | --- | --- |
|
| | D0 alone | `removed = {k}` | Empty |
|
| | D0, D1, D2 | `removed = {k}` | Keep `removed[k]` for D2 |
|
|
|
| The flattened state and D0 alone cannot distinguish these cases. Value equality
|
| does not solve the equivalent problem for repeated writes either:
|
|
|
| ```text
|
| D0: insert k=v
|
| D1: remove k
|
| D2: insert k=v
|
| ```
|
|
|
| Clearing the cached value merely because it matches D0 would erase D2's pending
|
| insertion.
|
|
|
| ## 2. Count recorded changes, not captured diff objects
|
|
|
| For each key:
|
|
|
| - The overlay stores the total number of outstanding recorded edits.
|
| - A diff stores how many of those edits it represents.
|
| - A new recorded edit increments the overlay's count.
|
| - Replaying a diff adds **that diff's count**, rather than incrementing once.
|
|
|
| Conceptually, each key's diff is:
|
|
|
| ```text
|
| (before, after, change_count)
|
| ```
|
|
|
| The existing value representation can remain:
|
|
|
| - `cache`: insertion or replacement, including the previous value.
|
| - `removed`: deletion of an existing value, including that value.
|
| - `phantom_removals`: absent-to-absent cancellation.
|
|
|
| Counts are additional metadata. An absent key remains distinct from an existing
|
| key whose value is empty.
|
|
|
| These counts are relative contributions, **not global IDs or timestamps**. A
|
| diff carries its own contribution, not the source overlay's entire cumulative
|
| count.
|
|
|
| ### Required invariants
|
|
|
| - Calling `diff()` repeatedly does not change counts.
|
| - Uncaptured edits are already counted and therefore protected.
|
| - `inverse()` swaps the value transition and preserves the count.
|
| - Combining diffs adds their contributions.
|
| - No-op value transitions retain their counted metadata until consumed.
|
| - Zero-count pending entries are removed.
|
| - All mutation paths preserve the accounting, including replay, clear,
|
| checkpoints, and clones.
|
|
|
| Counting registered diff objects instead would require a separate registration
|
| lifecycle, special handling for uncaptured edits, and additional handling for
|
| diffs that aggregate several blocks.
|
|
|
| ## 3. Confirmation and reversion are different operations
|
|
|
| ### Confirm an applied prefix
|
|
|
| After successfully writing a diff to the database:
|
|
|
| 1. Subtract its count from each affected key.
|
| 2. If the remaining count is positive, preserve the current overlay entry.
|
| 3. If the count reaches zero, clear the entry and counter.
|
|
|
| Do not compare values to decide whether a later change exists. A phantom-only
|
| diff still requires confirmation even though it produces no database writes.
|
|
|
| Confirmation is valid only for a prefix represented in that overlay. Counts do
|
| not establish that an arbitrary incoming diff belongs to its pending history.
|
|
|
| ### Revert a pending suffix
|
|
|
| When undoing the newest pending diff:
|
|
|
| 1. Subtract its counts.
|
| 2. Where earlier changes remain, restore the diff's **before-value** into the
|
| overlay.
|
| 3. Where no changes remain, remove the overlay entry and inherit from the
|
| backend.
|
|
|
| The diff already carries the previous values needed for ordered rollback. This
|
| does not require last-touch history or replay of the entire remaining sequence.
|
| The operation must undo a suffix; newer edits must be reverted first.
|
|
|
| ### Stage an inverse as new work
|
|
|
| This is distinct from removing a pending suffix:
|
|
|
| ```rust
|
| overlay.add_diff(&diff.inverse())?;
|
| ```
|
|
|
| Staging an inverse **adds** its counts. It does not implicitly unregister the
|
| original diff. This distinction is particularly important because a phantom-only
|
| diff equals its own inverse.
|
|
|
| Reverting an already-applied database change uses the inverse transition. Its
|
| original pending contribution has already been consumed and must not be
|
| subtracted again.
|
|
|
| ## 4. Worked example
|
|
|
| ```text
|
| D0: insert k, remove k -> count 2
|
| D1: insert k=v -> count 1
|
| D2: remove k -> count 1
|
| ```
|
|
|
| The final live state contains:
|
|
|
| ```text
|
| removed[k]
|
| change_count[k] = 4
|
| ```
|
|
|
| Confirmation proceeds as follows:
|
|
|
| | Applied diff | Remaining count | Overlay action |
|
| | --- | ---: | --- |
|
| | D0 | 2 | Preserve `removed[k]` |
|
| | D1 | 1 | Preserve `removed[k]`, hiding the backend's `v` |
|
| | D2 | 0 | Clear the marker and counter |
|
|
|
| For **D0 alone**, the count starts at 2. Applying D0 subtracts 2 and clears
|
| everything.
|
|
|
| For `insert v -> remove -> insert v`, the later insertion remains represented
|
| until its own contribution is consumed. Identical values no longer confuse
|
| cleanup.
|
|
|
| ## 5. Diff subtraction must account for counts
|
|
|
| For one key, subtracting a prefix means:
|
|
|
| ```text
|
| Current: B -> C, representing n edits
|
| Prefix: B -> A, representing m edits
|
|
|
| Result: A -> C, representing n-m edits
|
| ```
|
|
|
| This assumes the prefix belongs to the represented history and shares the
|
| starting state. If edits remain, retain the resulting entry even when its
|
| before-value and after-value are equal.
|
|
|
| For the cancellation example:
|
|
|
| ```text
|
| Combined snapshot: absent -> absent, count 4
|
| Subtract D0: absent -> absent, count 2
|
| Subtract D1: v -> absent, count 1
|
| ```
|
|
|
| D2 becomes a real removal with previous value `v`.
|
|
|
| Subtracting D0 no longer makes the intermediate diff empty: it still represents
|
| two outstanding edits. This also prevents the database layer from prematurely
|
| dropping this tree entry.
|
|
|
| Relevant emptiness and equality checks must respect the remaining change
|
| metadata. Batch generation can omit transitions requiring no database writes,
|
| while retaining their metadata for cleanup.
|
|
|
| ## 6. Replay on another overlay
|
|
|
| When overlay B imports a diff from A:
|
|
|
| 1. Apply its value transitions to B's pending state.
|
| 2. Add its count contributions to B's existing counts.
|
|
|
| No source-overlay IDs or source-global counters are copied.
|
|
|
| ### Starting-state compatibility
|
|
|
| Portability has an essential semantic condition:
|
|
|
| ```text
|
| Source diff: A -> B
|
| Destination currently contains C
|
| ```
|
|
|
| Applying that diff's inverse restores **A**, not **C**. Therefore, replay must
|
| start from the expected logical before-state. Deliberately applying it to a
|
| different state requires producing a rebased diff with the destination's actual
|
| previous values.
|
|
|
| ### Keep the operations explicit
|
|
|
| - Append a diff to an overlay.
|
| - Write a diff to the database.
|
| - Confirm a known pending prefix after it was written.
|
| - Revert a pending suffix.
|
|
|
| Writing an incoming diff must not automatically consume unrelated pending
|
| changes merely because their keys, values, or counts match.
|
|
|
| For overlays sharing a backend, one writer can write a common prefix and the
|
| other overlays can confirm that same prefix locally. Each overlay updates its
|
| own accounting exactly once.
|
|
|
| ## 7. Tree lifecycle needs separate reversible state
|
|
|
| A complete database-level fix cannot stop at key counters.
|
|
|
| Creation, dropping, and restoration must carry explicit reversible lifecycle
|
| information, including:
|
|
|
| - Whether the tree existed before and after the change.
|
| - The logical contents needed to undo a drop.
|
| - Pending overlay state preserved while the tree is hidden.
|
| - The structural change's outstanding contribution.
|
|
|
| In particular:
|
|
|
| - An empty tree is different from a nonexistent tree.
|
| - A drop's undo image must reflect the logical state **before that diff**,
|
| including earlier pending changes.
|
| - That image must remain separate from mutable pending-state bookkeeping.
|
| - Whole-tree cleanup must respect later key and lifecycle changes.
|
| - Restoration must correctly update initial/new/dropped-tree bookkeeping.
|
| - Double inversion must preserve the lifecycle transition and its metadata.
|
|
|
| The existing dropped-tree issue needs its dedicated fix. Key counters alone
|
| cannot repair it.
|
|
|
| ## 8. Cost
|
|
|
| Confirmation and pending rollback are proportional to the keys in the affected
|
| diff, with normal map-lookup costs. They do not clone all remaining values or
|
| replay the entire sequence.
|
|
|
| Counts add per-key numeric metadata in state and diffs, plus any associated map
|
| overhead. They do not require another copy of all value history.
|
|
|
| The existing `diff(&sequence)` calculation still has its sequence-subtraction
|
| cost. This design does not eliminate that cost.
|
|
|
| ## 9. Validation
|
|
|
| The counted key-transition rules were exercised in a bounded single-key model
|
| covering **18,489 configurations and 53,838 transitions**, including:
|
|
|
| - Uncaptured edits.
|
| - Cancellation and identical-value writes.
|
| - Prefix confirmation and suffix rollback.
|
| - Empty values.
|
| - Aggregated diffs.
|
| - Forward and inverse replay on another overlay.
|
|
|
| This validates the key-level rules within that model. It is not validation of a
|
| complete backend or tree-lifecycle implementation.
|
|
|
| Implementation regressions must cover both Fjall and Sled, including:
|
|
|
| - Full cleanup after cancellation-only and mixed diffs.
|
| - Preservation of later writes and removals during prefix confirmation.
|
| - Reverting a suffix after an earlier prefix has already been confirmed.
|
| - Branch replacement and replay on another compatible overlay.
|
| - Repeated read-only diff capture and aggregate application.
|
| - Inverse and double-inverse behavior.
|
| - Tree creation, dropping, restoration, and same-block edits followed by a drop.
|
| - Checkpoint consistency and backend failure handling.
|
|
|
| ## Recommendation
|
|
|
| Implement **counted reversible deltas**, explicit **confirm-versus-revert
|
| semantics**, and separate **reversible tree-lifecycle state**.
|
|
|
| This supplies the information missing from the current flattened state while
|
| preserving portable diffs and avoiding full-sequence rebuilding during cleanup
|
| or rollback.
|