Files
obikmer/DevDocMD/architecture/hot_resume_memoization.md
Eric Coissac 3bd7fd4f41 Implement memory mapping for file construction
Refactors the building process to utilize memory mapping (`memmap2`) for file creation and introduces the necessary infrastructure for publishing built files atomically. This includes expanding the public API surface and cleaning up deprecated architectural components.
2026-10-15 12:02:33 +02:00

8.6 KiB

Hot resume and memoization of long computations (discussion, 2026-10-14)

Goal (user)

  1. Hot resume: a run killed midway (crash, Ctrl-C, scheduler walltime) restarts from the last finished unit of work, not from zero.
  2. No recomputation: a long function called again with the same parameters (same command rerun, or another command needing the same intermediate) reuses its stored result.

Not a goal: bit-identical resumed samples. Sampling uses an OS-seeded RNG on purpose, repeated runs must stay independent draws to measure variance; a resumed run being a different valid draw is not a defect.

Why it matters: one real run

phylo --entropy 1 --pseudo-alignment --n-sites 5000000 --free-loss --no-ambiguity --quartet --pair-balance --family-overlap --sibling-stats on the 180-genome Primulaceae index, from the stderr of the OAR job (2026-10-13), 256 partitions:

Stage Wall
sibling_stats (full scan, Selection::All) 8 235 s
family_overlap (sweep 1: overlap annex) 5 582 s
sampled_scan: sweep 1 again (entropy + quartet annexes) ≈ 5 347 s
sampled_scan: sweep 2 (pair-weight annex) ≈ 5 296 s
sampled_scan: the draw itself ≈ 9 573 s
distance (Jaccard, not asked for; older binary) 53 s
Total 34 085 s (9 h 28)

The three annex sweeps cost about the same although their per-family work differs, so the cost is the layer traversal. Part of it was addressed by restricting the matrix pass to selected families (family_scan.rs, same session); the sweeps were not fused. Nothing in this run could be resumed or reused: every stage restarts from its beginning.

What exists today (verified in the code, 2026-10-14)

Persisted per-layer annexes. Entropy (entropy*.pent), quartet (quartet*.pbiv), pair weight, sibling annex: one file per layer, built by ensure_layer_* and skipped when path.exists() (family_annexes.rs). A rerun with the same conventions skips every sweep. This is already memoization, keyed by file name only (convention in the name, no fingerprint of the inputs; a rebuilt sibling annex deletes everything derived from it, see pair_coverage_sampling.md).

Not persisted. The family-overlap accumulator (FamilyOverlapAccumulator) is written once at the end of sweep 1 (sibling_builder.rs). The draw (sample_index) and the sibling_stats scan keep their state in memory only.

Defect found, then fixed (2026-10-14): a killed annex build left a file that looked finished. create_mmap_file (obicompactvec/src/mmap_file.rs) created the file at its final path with magic, header and the full length (set_len) before any data was written. A kill during a layer left a valid-looking file with unwritten data; the next run saw path.exists() and treated the annex as built, silently.

Reproduced on the 1x testbed (20 genomes, 512 layers): derived annexes deleted, phylo --family-overlap --quartet --pair-balance --entropy 1 … killed by timeout 6, then rerun. Old binary: 141 finals after the kill, 2 differing from a reference build; the rerun exited 0 and kept both. Fixed binary: kill at 6 s left 499 finals, all identical to the reference, plus 2 .building files; the rerun completed 1 537 files identical to the reference, no .building left. (Kill at 3 s: nothing published, nothing broken.)

Fix. obicompactvec::building_path / publish_built: a file is built under <name>.building and moved to its final name (same-directory rename, atomic) by the builder's close(), after the flush. Applied to the builders that go through create_mmap_file or write their own mmap on the annex path: PersistentBitVecBuilder (all constructors; quartet annex), PersistentFixedIntVecBuilder, PersistentRankSelectBitVecBuilder, FamilyScalarAnnexBuilder (entropy, pair weight), SiblingAnnexBuilder (siblings.psib) and FamilyOverlapAccumulator::write (overlap matrix). A leftover .building is truncated by the next build of that file. A build that is dropped without close() no longer produces the final file (no caller did; workspace tests pass). Also reordered in --sibling-annex: derived annexes are now removed before the new sibling annex is built and published, so a kill between the two leaves the old annex with no derived files, never a new annex next to files computed against the old numbering.

Not covered. The builders outside that path still write at their final name: PersistentCompactIntVecBuilder, the int/sparse matrix builders, EliasFanoBuilder, TempBitVecBuilder/TempCompactIntVecBuilder (temporary by nature) and the index-construction files that use them. The same reasoning applies to them as soon as a stage built on them has to be resumed; not audited. The in-memory overlap accumulator is still lost on a kill (a sweep restarts), now without leaving a corrupt file.

obiksession crate (src/obiksession/): Session (named directory, opaque parameter blob checked on open, whole-lifetime DirLock, artifacts checksummed with xxh3 and mmap-restored) and Memoize (get_or_compute[_with_key], invalidate, cached_keys, MemoKey from Debug + xxh3, the session_memoize! macro). Compiles, 15 tests pass, no caller: obikmer lists the dependency without using it. phylo --session exits with an error (cmd/phylo/mod.rs:271) since session_cache.rs (the consumer tied to PairwiseTally/PartitionDispersion/SnpAlignment) was removed. sample_index(skip_layers) remains as a seam, never called with a non-zero value.

Previous design and why it missed the goal (theory/evolutionary_distances.md, section "Explicit --session"): one session per exact parameter tuple (changing --n-sites made another session), artifacts specific to the sampling result, resume only inside the draw (checkpoint every 8 layers or 30 s). Reuse across commands existed only for the sample. An exhaustive-sample cache from which smaller samples would be drawn was proposed and never done. User judgement: this version did not answer the objective.

Proposed direction (not implemented; to be validated)

Start from the goal, not from the existing crate.

  1. Unit of work = one (partition, layer) step that already produces files. The annex builds, the draw per layer and the scans all iterate that way (for part … for layer …). Resume means "skip the units whose output is complete", exactly what exists() approximates today.
  2. Complete-or-absent outputs. Done for the annex path (see the fix above); the remaining builders are to be covered as their stages become resumable. Prerequisite for everything below. The mechanism lives in obicompactvec (shared lower-level API), not in each consumer.
  3. Key = function identity + parameters + fingerprint of the inputs. A result is reusable iff the function, every parameter that influences it and the identity of its inputs (index content, upstream artifacts) match. Today the key is a file name plus an invalidation convention. The fingerprint requirement is the cost: what identifies an index version cheaply is to be decided (meta file, rebuild counter, hash of annex headers).
  4. The cache holds results of long functions, not domain objects. The crate must not know PairwiseTally. Callers serialize their own values (rkyv was already chosen for that). Whether Memoize's API fits is unproven: it has no caller, no documentation and was written against the earlier design.
  5. Granularity matters more than the API. A cached 9 h result helps only the exact rerun; a per-layer cache also helps a changed parameter that leaves earlier layers untouched. The overlap accumulator (end-of-sweep write) would need a per-layer partial (a sum of per-layer matrices, mergeable) to be resumable.
  6. Fuse before caching. Three sweeps over the same layers where two suffice (overlap first, then entropy + quartet + pair weight together, since the pair weight needs only the finished overlap matrix) is a cost no cache removes on a first run; to do independently.

Open questions

  • Fingerprint of an index version: which cheap, stable identity?
  • Overlap accumulator resume: per-layer partial matrices on disk (size n² × layers) or a checkpoint every N layers?
  • Memoize/Session: keep (adapt to the points above), rewrite, or delete the crate until a caller exists (the "existing code is a hypothesis" rule applies; today it has no user).
  • Scope of the next step: atomic writes are done for the annex path; extend to the other builders, or go to the cache.
  • Draw resume: a layer's draw is independent of the others except through the quotas, which depend on every layer's mass; quotas can be recomputed from annexes on resume (cheap), so only the per-layer survivors need storing.