#145 Share index rows between a timeline and its forks instead of copying them
–
- github
- github/openchronology/timeline-app
- github/openchronology/timeline-app#145
- issue
- state:closed
Follow-up to #140 / #144. Related: #135 (very large timelines), #138 (forks share saved history). ## Problem Since #144, a fork or duplicate copies its source's index in the database (`copyIndex` in `server/store.mjs`) instead of rebuilding it in Node. Saved history is already shared (#138). The cost that's left is writing a full second copy of the index, which grows with the timeline. At 200,000 benchmark moments that's about 650,000 rows and their index entries, 23–33 s per fork: | Table | Rows (approx.) | Copy time | |---|--:|--:| | `oc_moments` | 200,000 | 4.2 s | | `oc_nodes` (moment tree) | 200,000 | 3.0 s | | `oc_entity_search` | 220,000 | 6.4 s | | `oc_duration_nodes` | 20,000 | 1.0–2.5 s | | `oc_edge_nodes` | 20,000 | 0.6–1.5 s | | `oc_relationships` | 20,000 | 0.5–0.8 s | That's (`bench/fork-save.mjs`, 8-core VM, PostgreSQL 17.) Each copy also takes the same storage again, and at a billion moments (#135) copying the index isn't viable at all. ## Goal Forking takes about the same time whatever the timeline's size: seconds, not minutes, at 200,000 moments and beyond. A fork costs storage for what it changes, not a second index. Reads and saves on a fork stay as fast as on its source. ## Options ### A. Copy-on-write (persistent) index structures Copies share index rows until one side changes them. **Trees** (`oc_nodes`, `oc_duration_nodes`, `oc_edge_nodes`): - Make nodes immutable and addressable outside their timeline: a node space, or a global node ID, instead of `(timeline_id, id)`. - A save path-copies, writing new nodes from the changed leaves up to a new root: O(log n) nodes per change, which the AVL code (`PersistentTree` in `server/avl.mjs`) already touches. - A fork starts with its source's root IDs and writes nothing. **Keyed rows** (`oc_moments`, `oc_relationships`, `oc_entity_search`): an overlay like saved history's. A copy reads its own rows first and then its base's, with tombstones for removals. - These tables are mostly read by key or through the tree (`moment_ids` in nodes), so the overlay mainly affects lookups by key and search. **Reclaiming space:** shared nodes are freed only when no timeline's root reaches them, by reference counting or a periodic mark-and-sweep. **Trade-offs:** - Forks become O(1), and saves stay O(log n). - It touches every query that reads the trees, for windows, summaries, search and views: they would key nodes by node space, not timeline. - Garbage collection is new machinery. - It's also the structure that scales furthest (#135). ### B. Fork now, copy in the background The fork request returns at once. The index is copied afterwards, in batches outside the request, and the fork is unavailable or read-only until the copy finishes, with progress shown. **Trade-offs:** - Small and low-risk; it reuses `copyIndex` in batches. - Responsiveness is fixed, but the work and storage are not. - Needs a "preparing" state, resumption after a restart, and a decision about saves to the source meanwhile. The copy is made from a fixed revision, so the source can keep changing; its history rows give that revision's entities. ### C. Read-through until first write A new fork reads its source's index at the base revision until its first save, and only then builds or copies its own. **Trade-offs:** - Cheap for forks that are never edited, which is common for reading and comparison. - It still pays the full copy on the first save. - Reads would have to serve the source's index at a fixed revision while the source keeps saving, which the live index can't do without A's immutability. ## Suggested path 1. **B first:** forks respond immediately, with the copy batched in the background and the fork marked as preparing. That's the user-facing fix, and it's small. 2. **Then A for the trees**, measured against #135's targets: path-copying trees with shared nodes and garbage collection, then overlays for the keyed tables. This removes the copy and the duplicate storage altogether. ## ……
Related
- #134 Keep saved history as rows instead of whole documents
- #135 Scale saves and whole-timeline work toward very large timelines (1 billion moments)
- #138 Share saved history between timelines and their forks
- #140 Copy a fork's index in the database instead of rebuilding it in Node
- #144 Copy a fork's index in the database instead of rebuilding it
- #146 Answer large forks at once and copy their index afterwards
- #147 Version index rows so forks can later share them
- #149 Forks read through to their source's index (#145, phase 2)
- #150 Release index versions forks no longer read, and compact forks (#145, phase 3)
- #152 Forks past four levels copy only what their source changed
- #154 Make saves follow the nodes they touch, and timeline creation linear
- Version index rows so forks can later share them
- Merge pull request #150 from openchronology/feature/index-cleanup
- Merge pull request #149 from openchronology/feature/fork-read-through
- Answer large forks at once and copy their index afterwards
Open #145 Share index rows between a timeline and its forks instead of copying them in the timeline