Repository navigation
Materialize slices, not graphs: copy-on-write worldline state (tracking) #782
Description
Tracking container. This issue groups executable work and owns implementation status for one accepted design. It is not itself a pull request. Each unit below is one independently mergeable change and gets its own issue or PR when started.
Design
The accepted design is docs/architecture/sliced-readings-and-copy-on-write-strands.md, introduced on branch docs/copy-on-write-state-design (not yet on main). Summary:
- Echo materializes slices, not graphs. A slot's value at a basis is what its latest producing tick at or before that basis wrote, else its value in the worldline's initial state. Echo resolves a slot through an index of its producers and does not replay unrelated ticks or build undemanded entities.
- A tick pays for what it changes. Commit cost must not grow with the size of unchanged state or with the length of history.
- Rollback does not copy.
- A strand is copy-on-write. It resolves a slot from its own producers first, otherwise from its source lane at the fork basis. Forking copies no state.
- A checkpoint is a retained root; a wormhole is a compressed tick range between two roots that keeps its receipts and witness.
- Memory holds a working set. Echo does not assume a state fits in memory, and no operation may require a whole state, or two copies of one, in memory.
The page also records what the runtime does today, so the design is not read as current behavior.
Evidence that motivates it
Measured 2026-10-12 in the guarded Docker worker (Linux VM, release build, compare-and-set workload, one run per configuration, medians).
Tick cost against graph size, no WAL, one cell changed per tick, measured on the PR #786 source:
| Nodes | Tick p50 |
|---|---|
| 1 | 0.038 ms |
| 1,000 | 0.096 ms |
| 10,000 | 0.63 ms |
| 100,000 | 7.2 ms |
Read from source, not separately measured: a scheduler pass clones the graph state of each touched worldline for rollback, the engine commit guard clones it again, and native-rule commits derive their patch with a whole-state diff_state. fork_strand clones the runtime and provenance, replays the source state at the fork tick, and registers the child with an independent copy. ReplayCheckpoint stores a full materialized state. slice_worldline_indices exists and only tests call it.
Executable units
Edges below are proposals from reading the code, not accepted dependencies.
- Worldline slot index. Maintain, per worldline, an index from slot to producing ticks, updated at commit and truncated on rollback. Witness: for every slot at every tick of a generated history, the index resolves the same value as the materialized state. Additive; no behavior change. Prerequisites: none.
- Sliced reads. Serve a single-slot read at an arbitrary tick from the index instead of replay. Prerequisite: 1, because the read uses the index.
- Footprint-sliced tick preparation for Echo-interpreted operations. Prepare a bounded operation from the slots in its exact footprint. Prerequisite: 1.
- Emitted deltas for native-rule commits. Remove the whole-state diff and the pre-commit state clone. Prerequisites: none known; independent of 1–3.
- Copy-on-write strands. Fork records the basis; the child resolves through its own producers then the source lane at the basis. Prerequisites: 1 and 3, because the child has no materialized state to tick against.
- Materialized state as a cache. The runtime stops requiring a complete materialized state per worldline. Prerequisites: 2, 3, 4, 5.
- Content identity for retained parts. Parts are referenced by content hash and may be absent from memory. Prerequisite: 6.
Open decisions
- State root.
state_roothashes the reachable graph, which visits every reachable element. Making it incremental touches committed hashes and needs its own decision. Units 1–5 must not change any committed hash. - Adjacency queries. "All edges of a node" is a set query, not a single slot, and needs its own index.
- Wormholes between roots. Not scheduled here beyond the definition in the design page.
Not in scope
- Durability modes for the WAL (none / deferred / strict).
- Keep production adoption.
- Any release.
Already done separately (not part of this container)
- PR Roll back ticks and submissions from journals, not copies of history #786 (
perf/rollback-without-history-copies): tick and submission rollback no longer copy committed history. - PR Sync a WAL commit once instead of three times #784 (
perf/wal-commit-sync-once): one sync per WAL commit instead of three.
Neither is merged at the time of writing.
Activity
flyingrobots commentedon Oct 13, 2026
Relation to content-addressed storage (Keep). Slicing needs a place to fetch parts from. The intended path is: slot index → producing tick → patch or value by content hash → bytes through Echo's physical-content port. That makes content storage the backing store for the working set, and it is the reason unit 7 (content identity for retained parts) exists.
What exists today: the Echo-owned physical-content port and its memory and disk adapters (#769), the Echo/Keep identity bridge (#768), and a disabled-by-default experimental Keep
ReferenceStoreadapter (#770) that claims no restart durability. A durable Keep read adapter, durable reconciliation and production adoption (roadmap K04–K06) are not done and remain conditional on Keep's storage admission requirements. Units 1–6 do not depend on Keep; unit 7 depends on the content port, not on a specific backend.flyingrobots commentedon Oct 13, 2026
Adjacency queries: Roaring bitmap indexes. This addresses the "all edges of a node" open decision above.
What exists:
crates/echo-trace/src/lib.rssays "Graph is truth. Delta log is transport. Roaring is index."docs/topics/RuntimeConstellation.mdsays Roaring selectors are indexes.EvidenceSegmentincrates/warp-core/src/evidence.rshas aselector_index_rootfield described as the root digest of a sparse selector index (Roaring bitmap). No Roaring crate is inCargo.lock.git-warpimplements it: sharded forward and reverse edge bitmaps (EdgeShard), aBitmapNeighborProviderbehind a neighbor-provider port, an incremental index updater, and a checkpoint neighborhood bitmap pager.Proposed shape for Echo (a proposal, not an accepted edge):
This would be its own executable unit after unit 1, or folded into unit 1 if the producer index adopts the same representation. It adds a dependency, so it needs the dependency policy check and a decision on which Roaring implementation and serialized form Echo binds to.
flyingrobots commentedon Oct 13, 2026
Prior art: Roaring in
git-mind. Surveyed read-only by a separate agent; I have not re-read the sources myself. Roaring code exists only on the archived C brancharchive/c23-final@e56d30bf.main@18b98b63replaced it with a thin wrapper around git-warp.Implemented there:
<2hex>/<oid>.forward|.reverse, one blob per key, so a query loads exactly one bitmap.Described there but never built: incremental build from the last tip, edge-id resolution back to edges, tombstones, 64-bit bitmaps, Bloom filters, hot/cold splitting.
Lessons for Echo, from the agent's reading and the authors' own notes:
flyingrobots commentedon Oct 13, 2026
Review corrections to the design (PR #785, commit e8f6c9a). Three things changed and affect the units above:
RewriteRulediscovers its match and footprint from a view over a complete instance. That path needs a bounded discovery aperture or a state-independent footprint contract and is a further open decision; it also bounds unit 4.Cached-reading identity now includes rights, budget, projection and reducer versions and obstruction posture.
flyingrobots commentedon Oct 13, 2026
Progress and measurements (2026-10-12). Guarded worker (Linux VM), release build, compare-and-set workload, no WAL, single runs, tick p50.
Merged: #790 slot write index (unit 1).
In review:
What remains on a large graph: three whole-state hashes per Action tick (frontier basis, root before commit, root after commit), about 0.5 ms each at 100,000 nodes. Two steps:
WorldlineStateto be private to its module so every mutation goes through one accessor (about twenty call sites). Planned next, after Commit executable-operation Actions in place; roll back from a journal #793.SnapshotAccumulatoris not incremental today; it rebuilds from the state.Other whole-state copies found and not yet addressed:
TrustedRuntimeHost's direct prepared-operation commit clones the whole runtime and provenance (trusted_runtime_host.rs,let mut next_runtime = self.runtime.clone()), andfork_strandclones both for rollback. Neither is on the tick path.flyingrobots commentedon Oct 14, 2026
Correction (2026-10-13): the per-tick figures I reported here (for example 100,000 nodes: 5.03 ms down to 0.54 ms for one Action) were measured on scenes whose nodes were not reachable from the root, so the state root, which covers only reachable content, skipped them. The relative improvements from the merged work hold; the absolute figures do not describe a realistic scene. With every node reachable, a tick at 100,000 nodes costs about 70 ms, almost all of it the whole-state root; see #845.