Update documentation to reflect that sparse packing now maps all columns of a layer at once and packs layers sequentially, reversing the previous choice to avoid materializing a packed copy. This change introduces an extra write/read cycle for the dense matrix, increasing pack benchmark time from 1.11s to 1.60s. - Modify `pack_sparse_bit_matrix` in `src/obicompactvec/src/bitmatrix/sparse.rs` to always convert via the dense packed format, simplifying logic by removing conditional handling of existing files and ensuring a single mapping. - Update `pack_sparse_compact_int_matrix` in `src/obicompactvec/src/sparse_intmatrix.rs` to exclusively handle conversion from the dense packed format (`matrix.pcmx`) to sparse, removing columnar format handling and simplifying file cleanup. - Adjust `scripts/bench_merge_oracle.sh` to extract `PACK_WALL` metrics via `stage_field` for merge operations, updating grep patterns and output messages to report pack wall time. - Revise `DevDocMD/implementation/merge_mmap_audit.md` and `merge_scaling.md` to document the new sequential packing strategy, noting that `N_part` scaling applies only to incremental merges and that `obisys::MemoryBudget` is no longer used by merge. - Bump package version in `src/obikmer/Cargo.toml` from 1.4.3 to 1.4.4.
42 lines
4.5 KiB
Markdown
42 lines
4.5 KiB
Markdown
# Merge: scaling to thousands of genomes (open, 2026-11-17)
|
|
|
|
Open design question raised during the mmap refactor (`merge_mmap_audit.md`). Target: merges of ~6 000 genomes of a few Gb each. Nothing here is implemented or measured. Figures are estimates, labelled as such.
|
|
|
|
## What scales with what (after the mmap refactor)
|
|
|
|
| Cost | Depends on | Status |
|
|
|---|---|---|
|
|
| Live source layers + dst columns per partition (merge pass 2) | `SRC_GROUP × src_n`, not the source count | fixed by plan A |
|
|
| Pass-2 column RAM | `SRC_GROUP × src_n × N_part × (1/8 \| 1)` B | bounded, see below |
|
|
| Pass-1 de Bruijn graph | ≥ ~19 B per *new* k-mer (`HashMap<u64, AtomicU8>`, verified in `obidebruinj/src/debruijn/graph.rs`) | unchanged |
|
|
| Columnar intermediate files | `n_genomes × n_layers × n_partitions` (6 000 × 2 × 256 ≈ 3 M files, estimate) | **does not scale** |
|
|
| Sparse `pack` | used to map **all** columns of a layer at once (`ColumnarBitMatrix::open`); layers are packed one after another, so `n_genomes` maps per partition (186 × 192 concurrent ≈ 36 k, estimate) | **fixed 2026-11-17**: now goes columnar → dense `matrix.pbmx` (sequential concatenation, unmapped) → sparse, one mapping per partition |
|
|
|
|
`N_part`: k-mers of one dst partition over all layers. Pass-2 column RAM stays below pass-1 graph RAM for one-shot merges. It dominates only for **incremental** merges, where few genomes are added to a large index: the new layer is small, the existing layers are large. Example (estimate): `N_total = 1e12`, counts, 192 concurrent partitions → ~1.5 TB. A memory-budgeted concurrency cap is needed there whatever the column strategy. `obisys::MemoryBudget` exists but is no longer used by merge.
|
|
|
|
## Why a columnar intermediate at all
|
|
|
|
The sparse format (`bitmatrix/sparse.rs`) is row-major and deduplicated: per slot, either one genome (`singleton.pfiv`) or a `dict_id` (`multi.pfiv`) into a dictionary of distinct genome sets (`dict_offsets` + `dict_values.bin`). Its builder only offers `push_row(genomes)`, i.e. the **complete** genome set of a row, rows in **slot order**.
|
|
|
|
Merge discovers values **column by column** (source by source), in **random slot order** (MPHF order). The columnar files are a transposition buffer: they absorb random per-column writes, and `pack` transposes them row by row.
|
|
|
|
## Options to build the final format directly
|
|
|
|
1. **All sources at once.** That is exactly what plan A removed. No.
|
|
2. **Whole matrix in RAM.** `N_part × n_genomes / 8` B per partition: ~3 TB at 6 000 genomes and `N_part = 4e9` (estimate). No.
|
|
3. **External sort of `(slot, genome)` pairs.** Volume ∝ non-zeros ≈ Σ genome k-mers (~6 000 × 3e9). That is huge, while the final format is small precisely because genome sets repeat. No.
|
|
4. **Incremental sparse update per source group** (most promising). Per group:
|
|
- fill the group's columns in RAM (as now);
|
|
- stream the partition's existing sparse matrix **sequentially in slot order**;
|
|
- for each row: new set = old set ∪ group bits. Through the dictionary this is a transition `(old dict_id, group bit pattern) → new dict_id`, which can be memoised in a table;
|
|
- write the new sparse matrix sequentially, then publish.
|
|
|
|
No columnar files, no `pack`, no per-genome mapping, sequential I/O only. It also removes the re-merge bug: it starts from an existing sparse matrix instead of requiring a columnar one.
|
|
|
|
The cost is **one full pass over the partition's sparse matrix per group**. With `SRC_GROUP = 2` and 6 000 genomes that is 3 000 rewrites, far too many. Groups must therefore be large (64–256 sources), and group column RAM grows with them: `group × N_part / 8` B, e.g. 32 GB per partition for 64 sources at `N_part = 4e9` (estimate). One parameter trades passes against RAM, and it should be sized from a memory budget. The count matrix (`sparse_intmatrix.rs`) has its own format and needs the same analysis.
|
|
|
|
## Related findings
|
|
|
|
- The module header of `bitmatrix/sparse.rs` says "not used by any production code path yet". This is stale: `finalize_indexed` packs to sparse by default.
|
|
- The new layer of a merge is not byte-reproducible run to run: unitig segmentation varies, so the MPHF, evidence and matrix row order vary with it (measured 2026-11-17, `layer_1/*` differs in all 256 partitions; `layer_0` and metadata are identical). `obikmer index` shows the same behaviour. Merge oracles therefore compare sorted dumps, not file hashes. Where the non-determinism originates (parallel graph fill or unitig walk) is not established.
|