test_prebuild_reconstruct_linear.py
python
sha256:21f2642e962cac240d3460536a5716b95410af867668811caa72ccc09138d580
perf(fetch): heavy-path parent-first order bounds the manif…
Opus 5.5
patch
4 days ago
| 1 | """musehub#315 / #331 — reconstructing delta-only snapshots must stay linear in history length. |
| 2 | |
| 3 | A multi-commit push stores a full ``manifest_blob`` only for the root and the head; every other |
| 4 | snapshot is delta-only and is rebuilt by walking its parent chain. 0.2.3-rc.1 held every snapshot |
| 5 | row in the session for the whole fetch, so each walk was served from the identity map. The rc.2 |
| 6 | memory fix loads rows in bounded chunks and lets them go — correct, but each delta-only snapshot then |
| 7 | re-read its whole ancestor chain from the database: O(n^2) round trips (staging, gabriel/muse, 1,401 |
| 8 | delta-only snapshots: ~1 s each, the prebuild ran ~25 min instead of 64 s). Contract: |
| 9 | |
| 10 | * PRL_01 a fetch of an n-commit delta-only chain reads each snapshot row O(1) times (linear); |
| 11 | * PRL_02 every reconstructed manifest still round-trips, including across a fork; |
| 12 | * PRL_03 the reconstruction memo holds only the frontier, not the history. |
| 13 | """ |
| 14 | |
| 15 | from __future__ import annotations |
| 16 | |
| 17 | import pytest |
| 18 | from sqlalchemy import event |
| 19 | from sqlalchemy.ext.asyncio import AsyncSession |
| 20 | from unittest.mock import patch |
| 21 | |
| 22 | from muse.core.ids import hash_snapshot |
| 23 | from muse.core.mpack import build_wire_mpack |
| 24 | from muse.core.types import blob_id |
| 25 | from musehub.services import musehub_wire_fetch |
| 26 | from musehub.services.musehub_repository import create_repo |
| 27 | from musehub.services.musehub_wire_push import wire_push_unpack_mpack |
| 28 | from tests.test_multi_tip_manifest_union import ( |
| 29 | _IDENTITY_ID, |
| 30 | _OWNER, |
| 31 | _REAL, |
| 32 | _InMemBackend, |
| 33 | _cid, |
| 34 | _fetch, |
| 35 | _raw_commit, |
| 36 | ) |
| 37 | |
| 38 | |
| 39 | async def _push_chain(session: AsyncSession, backend: _InMemBackend, repo_id: str, name: str, |
| 40 | n: int, branch: str = "main", base: tuple[str, str, dict[str, str]] | None = None, |
| 41 | ) -> tuple[list[str], list[dict[str, str]]]: |
| 42 | """Push ``n`` commits in ONE mpack, each snapshot a one-file delta on its parent's snapshot.""" |
| 43 | commits, snaps, blobs, cids, manifests = [], [], [], [], [] |
| 44 | parent_cid, parent_snap, manifest = (base[0], base[1], dict(base[2])) if base else (None, None, {}) |
| 45 | for i in range(n): |
| 46 | content = f"{name}-file-{i}".encode() |
| 47 | oid = blob_id(content) |
| 48 | path = f"src/{name}/f{i}.py" |
| 49 | manifest = {**manifest, path: oid} |
| 50 | snap_id = hash_snapshot(manifest) |
| 51 | cid = _cid(f"{name}-{i}") |
| 52 | commit = _raw_commit(cid, _REAL.get(parent_cid, parent_cid) if parent_cid else None, snap_id, branch=branch) |
| 53 | _REAL[cid] = commit["commit_id"] |
| 54 | commits.append(commit) |
| 55 | snaps.append({"snapshot_id": snap_id, "parent_snapshot_id": parent_snap, |
| 56 | "delta_upsert": {path: oid} if parent_snap else dict(manifest), |
| 57 | "delta_remove": [], "directories": []}) |
| 58 | blobs.append({"object_id": oid, "content": content}) |
| 59 | cids.append(cid); manifests.append(dict(manifest)) |
| 60 | parent_cid, parent_snap = cid, snap_id |
| 61 | mpack_bytes = build_wire_mpack({"commits": commits, "snapshots": snaps, "blobs": blobs, "tags": []}) |
| 62 | key = blob_id(mpack_bytes) |
| 63 | backend._mpacks[key] = mpack_bytes |
| 64 | with patch("musehub.services.musehub_wire.get_backend", return_value=backend), \ |
| 65 | patch("musehub.services.musehub_wire_push.get_backend", return_value=backend), \ |
| 66 | patch("musehub.storage.backends.get_backend", return_value=backend): |
| 67 | await wire_push_unpack_mpack(session, repo_id, key, pusher_id=_OWNER, branch=branch, |
| 68 | head_commit_id=_REAL[cids[-1]], commits_count=n, |
| 69 | blobs_count=len(blobs), force=True) |
| 70 | await session.flush() |
| 71 | return cids, manifests |
| 72 | |
| 73 | |
| 74 | async def _repo(session: AsyncSession, name: str) -> str: |
| 75 | repo = await create_repo(session, name=name, owner=_OWNER, owner_user_id=_IDENTITY_ID, |
| 76 | visibility="public", initialize=False) |
| 77 | await session.commit() |
| 78 | return repo.repo_id |
| 79 | |
| 80 | |
| 81 | def _count_point_reads(session: AsyncSession) -> tuple[list[str], object, object]: |
| 82 | reads: list[str] = [] |
| 83 | eng = session.bind.sync_engine if hasattr(session.bind, "sync_engine") else session.get_bind() |
| 84 | |
| 85 | def on_exec(conn, cursor, statement, parameters, context, executemany): # type: ignore[no-untyped-def] |
| 86 | if "FROM musehub_snapshots" in statement and "musehub_snapshots.snapshot_id = " in statement: |
| 87 | reads.append(statement) |
| 88 | |
| 89 | event.listen(eng, "before_cursor_execute", on_exec) |
| 90 | return reads, eng, on_exec |
| 91 | |
| 92 | |
| 93 | @pytest.mark.asyncio |
| 94 | async def test_prl_01_delta_only_chain_reconstruction_is_linear(db_session: AsyncSession, monkeypatch: pytest.MonkeyPatch) -> None: |
| 95 | n = 40 |
| 96 | monkeypatch.setattr(musehub_wire_fetch, "_SNAPSHOT_LOAD_CHUNK", 5) # production: 1,682 rows / 200 = 9 chunks |
| 97 | repo_id = await _repo(db_session, "prl-01") |
| 98 | backend = _InMemBackend() |
| 99 | cids, manifests = await _push_chain(db_session, backend, repo_id, "prl01", n) |
| 100 | db_session.expunge_all() # a fresh worker session: nothing is in the identity map |
| 101 | reads, eng, fn = _count_point_reads(db_session) |
| 102 | try: |
| 103 | parsed = await _fetch(db_session, backend, repo_id, want=[cids[-1]]) |
| 104 | finally: |
| 105 | event.remove(eng, "before_cursor_execute", fn) |
| 106 | assert sorted(tuple(sorted(s["manifest"].items())) for s in parsed["snapshots"]) == \ |
| 107 | sorted(tuple(sorted(m.items())) for m in manifests) |
| 108 | # quadratic walk = ~n^2/2 = 780 point reads; linear = at most a couple per snapshot |
| 109 | assert len(reads) <= 2 * n, f"{len(reads)} per-row snapshot reads for {n} snapshots (quadratic chain walk)" |
| 110 | |
| 111 | |
| 112 | @pytest.mark.asyncio |
| 113 | async def test_prl_02_fork_round_trips(db_session: AsyncSession, monkeypatch: pytest.MonkeyPatch) -> None: |
| 114 | monkeypatch.setattr(musehub_wire_fetch, "_SNAPSHOT_LOAD_CHUNK", 3) |
| 115 | repo_id = await _repo(db_session, "prl-02") |
| 116 | backend = _InMemBackend() |
| 117 | cids, manifests = await _push_chain(db_session, backend, repo_id, "trunk", 12) |
| 118 | fork_at = 5 |
| 119 | from muse.core.ids import hash_snapshot as hs |
| 120 | fcids, fmanifests = await _push_chain(db_session, backend, repo_id, "side", 8, branch="side", |
| 121 | base=(cids[fork_at], hs(manifests[fork_at]), manifests[fork_at])) |
| 122 | db_session.expunge_all() |
| 123 | parsed = await _fetch(db_session, backend, repo_id, want=[cids[-1], fcids[-1]]) |
| 124 | got = {s["snapshot_id"]: s["manifest"] for s in parsed["snapshots"]} |
| 125 | for m in manifests + fmanifests: |
| 126 | assert got[hash_snapshot(m)] == m |
| 127 | |
| 128 | |
| 129 | @pytest.mark.asyncio |
| 130 | async def test_prl_03_memo_holds_only_the_frontier(db_session: AsyncSession, monkeypatch: pytest.MonkeyPatch) -> None: |
| 131 | n = 30 |
| 132 | repo_id = await _repo(db_session, "prl-03") |
| 133 | backend = _InMemBackend() |
| 134 | monkeypatch.setattr(musehub_wire_fetch, "_SNAPSHOT_LOAD_CHUNK", 4) |
| 135 | cids, _ = await _push_chain(db_session, backend, repo_id, "prl03", n) |
| 136 | db_session.expunge_all() |
| 137 | sizes: list[int] = [] |
| 138 | real = musehub_wire_fetch._ManifestFrontier.put |
| 139 | |
| 140 | def spy(self, sid, manifest): # type: ignore[no-untyped-def] |
| 141 | real(self, sid, manifest) |
| 142 | sizes.append(len(self)) |
| 143 | |
| 144 | monkeypatch.setattr(musehub_wire_fetch._ManifestFrontier, "put", spy) |
| 145 | await _fetch(db_session, backend, repo_id, want=[cids[-1]]) |
| 146 | assert sizes, "the frontier memo must be used" |
| 147 | assert max(sizes) <= 2, f"frontier grew to {max(sizes)} manifests for a linear chain" |
| 148 | |
| 149 | |
| 150 | def test_prl_04_parent_first_frontier_is_logarithmic_on_branchy_histories() -> None: |
| 151 | """A comb (main line with one side branch per commit) must not retain every fork point.""" |
| 152 | n = 1000 |
| 153 | parent_of: dict[str, str | None] = {"m0": None} |
| 154 | for i in range(1, n): |
| 155 | parent_of[f"m{i}"] = f"m{i - 1}" |
| 156 | parent_of[f"s{i}"] = f"m{i - 1}" |
| 157 | for ids in (list(parent_of), list(reversed(list(parent_of)))): |
| 158 | order, pending = musehub_wire_fetch._parent_first(ids, parent_of) |
| 159 | assert sorted(order) == sorted(ids) |
| 160 | pos = {sid: k for k, sid in enumerate(order)} |
| 161 | assert all(parent_of[s] is None or pos[parent_of[s]] < pos[s] for s in ids) |
| 162 | live: set[str] = set(); left = dict(pending); peak = 0 |
| 163 | for sid in order: # the frontier as wire_fetch_mpack keeps it |
| 164 | if left.get(sid): |
| 165 | live.add(sid) |
| 166 | par = parent_of[sid] |
| 167 | if par in left: |
| 168 | left[par] -= 1 |
| 169 | if left[par] == 0: |
| 170 | live.discard(par) |
| 171 | peak = max(peak, len(live)) |
| 172 | assert peak <= 11, f"frontier peaked at {peak} for a {n}-fork comb" |
| 173 | |
| 174 | |
| 175 | @pytest.mark.asyncio |
| 176 | async def test_prl_05_parent_outside_the_fetch_set_round_trips(db_session: AsyncSession, monkeypatch: pytest.MonkeyPatch) -> None: |
| 177 | monkeypatch.setattr(musehub_wire_fetch, "_SNAPSHOT_LOAD_CHUNK", 3) |
| 178 | repo_id = await _repo(db_session, "prl-05") |
| 179 | backend = _InMemBackend() |
| 180 | cids, manifests = await _push_chain(db_session, backend, repo_id, "prl05", 12) |
| 181 | db_session.expunge_all() |
| 182 | parsed = await _fetch(db_session, backend, repo_id, want=[cids[-1]], have=[cids[4]]) |
| 183 | got = {s["snapshot_id"]: s["manifest"] for s in parsed["snapshots"]} |
| 184 | assert got, "an incremental fetch must carry the new snapshots" |
| 185 | for m in manifests[5:]: |
| 186 | assert got[hash_snapshot(m)] == m |
File History
2 commits
sha256:21f2642e962cac240d3460536a5716b95410af867668811caa72ccc09138d580
perf(fetch): heavy-path parent-first order bounds the manif…
Opus 5.5
patch
4 days ago
sha256:4b96079123117ef5cb85534b46736f29ce37198ade580b968ebf68209c8282f0
perf(fetch): rebuild delta-only snapshots parent-first from…
Opus 5.5
patch
4 days ago