gabriel / musehub public
test_prebuild_reconstruct_linear.py python
186 lines 9.0 KB
Raw
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