RFC: Enterprise index storage — three orthogonal axes (version / snapshot / tenancy), git-content-addressed graph

[fishmingyu]

Summary

Reframes enterprise index storage around three orthogonal problems that were previously conflated, and proposes mirroring git's content-addressed model rather than inventing our own versioning:

1. Multi-version — as-of-commit graph queries as a repo evolves across commits/branches.
2. Snapshot isolation — one query sees a consistent view of a version, not a half-mutated graph racing a concurrent indexer.
3. Multi-tenancy — isolation between users/tenants. Decided (this RFC): single-org self-hosted, weak isolation (one deployment ≈ one tenant; row-level filtering; tenant_id reserved nullable for a future SaaS RFC).

Central finding (the pivot): cross-file reference edges are today materialized at index time into a single mutable igraph, and eagerly cross-coupled — an incremental patch to file F re-runs LSP references() to rebuild inbound edges living in other, unchanged files. This single fact is what breaks both axis 1 (clean per-file dedup) and axis 2 (free MVCC). The highest-leverage move is therefore not building version storage first, but de-materializing cross-file edges: keep SCIP monikers unresolved per-blob and resolve them lazily at query time + a hot-edge cache. SCIP/LSP already emit the monikers; today's code eagerly resolves and discards them.

Motivation

The three axes have different solutions and different cost centers; bundling them produced a muddy design (see the prior revision of this issue). Separating them:

Axis 1 — multi-version. A code graph's defining property is that most files are unchanged between commits, and git is already a content-addressed version system. Mirror it:

• Content-address per-file symbol subgraphs by file blob hash. SCIP/LSP produce symbols per-document, so store file_content_hash → that file's symbol subgraph. Two commits that don't touch file F share F's subgraph automatically. Storage is O(unique file versions), not O(commits × repo size).
• A "version" degenerates to a manifest: (repo, commit) → {file_blob_hash...} — literally a mirror of git's tree. Snapshotting a new version = writing one manifest, O(1), copies no graph data. The graph as-of a commit = the union of those blob subgraphs.
• Incremental indexing: a new commit only re-runs SCIP/LSP on changed files; everything else reuses its blob hash. This reuse is the precondition for the whole scheme.

So a "snapshot" is not a thing to materialize — it's a logical view of (commit manifest + version predicate).

Axis 2 — snapshot isolation, basically free if the base is immutable. Store edges in an append-only/immutable table keyed by blob hash; a reader pins (commit, overlay) and filters blob_hash ∈ manifest. A concurrent indexer writes new blobs/manifest rows and never touches the rows an old reader sees — that's MVCC, no hand-rolled locks. (This is a concrete instance of the temporal-ordering / fixed-logical-timepoint idea from MemConsist.)

The catch — cross-file edges. Per-file dedup is clean for intra-file edges. But call-graph / cross-file references belong to no single blob. This is the one genuinely expensive part — and today it is implemented in the worst possible form for versioning:

• Cross-file reference edges are fully materialized as real igraph edges with both endpoints resolved to vertex IDs at build time (codeminer/graph/code_graph.py:195-229; C++ backend emits resolved (src_id,tgt_id,type,anchor_file,anchor_line) in scip_decode_core.py:99-123). No unresolved-moniker / query-time path exists.
• An incremental patch to file F rebuilds inbound cross-file edges from other files via LSP references() (patcher_base.py:488 → subgraph_mgr.py:717-770 reconnect_incoming(); outbound via reconnect_outgoing(); deletes record severed in/out edges in delete_file_subgraph()).

Consequences: (1) "G unchanged ⇒ reuse G's subgraph" is violated, because changing F mutates edges attached to unchanged G; (2) MVCC is not free, because the concurrent indexer mutates the very graph a reader is traversing.

Axis 3 — multi-tenancy. Decided: single-org self-hosted, weak isolation. One deployment ≈ one tenant. Users within the org share one committed graph + each their own branch/commit + their own small mutable overlay. Row-level filtering suffices; no per-tenant database. Schema reserves a nullable tenant_id so a future multi-org SaaS RFC is an additive migration, not a rewrite. (Repo/docs/roadmap contain no SaaS/tenant requirement today — only a self-hosted CI runner.)

Detailed Design

The pivot: de-materialize cross-file edges

Stop resolving monikers at build time. Per blob, store:

• intra-file edges (CONTAIN + intra-file references) — immutable, travel with the blob.
• unresolved cross-file references — (src_local_symbol, target_moniker, anchor_line), immutable, travel with the blob. The moniker is SCIP's global stable symbol id.
• definitions index — moniker → (blob_hash, local_symbol) for blobs that define a moniker.

Query-time resolution (bounded k-hop neighborhood, not whole-graph): given the active manifest's blob set, resolve each target_moniker to the defining blob within that manifest, with a hot-edge materialized cache for frequently traversed cross-file edges. This matches the workload (limited-hop retrieval, not global analysis) and removes the eager reconnect_incoming LSP pass from the incremental path entirely.

Net effect: axis 1 dedup becomes clean for all edges; axis 2 MVCC returns to free; incremental indexing gets cheaper.

Storage substrate — boring and unkillable

Versioning/snapshot logic lives in our layer (blob-hash addressing + manifest + version-range predicates), over a dull, durable substrate — DuckDB/Postgres edge tables, conceptually reusing git's object store. Explicitly do not outsource version/time-travel semantics to a niche versioned DB (Datomic, TerminusDB, Dolt). The Kuzu lesson: a niche store can go unmaintained; TerminusDB is in the same ecosystem-size risk band. Keeping versioning in our layer makes swapping the substrate a local change, not another architecture-level migration.

Sketch (single-org, weak isolation; tenant_id nullable, reserved):

blobs(blob_hash PK, ...)                                  -- immutable, content-addressed
intra_edges(blob_hash, src_local, dst_local, edge_type)  -- immutable, follows blob
xref_unresolved(blob_hash, src_local, target_moniker, anchor_line)  -- immutable
defs(moniker, blob_hash, local_symbol)                   -- resolution index
versions(version_id PK, repo_id, commit_sha, schema_ver, model, status, tenant_id NULL)
manifest(version_id, blob_hash)                          -- (repo,commit) -> blob set; mirrors git tree
refs(repo_id, name, version_id, tenant_id NULL)          -- main / release-x / branch -> version
overlays(overlay_id, user_id, base_version_id)           -- per-user dirty workspace
overlay_blobs(overlay_id, blob_hash)                     -- only the user's changed-file subgraphs

A reader pins (version_id, overlay_id?); every read filters blob_hash ∈ manifest(version) ∪ overlay_blobs(overlay).

Pluggable interface (the "hybrid" decision, unchanged)

A minimal backend-agnostic IndexStore contract: catalog/refs/version lifecycle + content-addressed blob put/get/has. Embedded default = SQLite/DuckDB catalog + content-addressed blob dir + FAISS files kept as blobs. A future server backend (Postgres + object store + a real vector DB) implements the same surface with no call-site changes. Validate the surface against the embedded impl only — don't pre-build for the server.

Per-user overlay (axis 3, weak isolation)

A user's uncommitted edits = a small mutable overlay layered on a committed snapshot. Query view = base-as-of-commit ∪ user overlay. The overlay holds only that user's changed-file subgraphs (reuses the existing incremental delta machinery, emitting blobs instead of mutating the shared graph). Dropped on session end.

Trade-offs & Risks

• Query-time resolution cost. k-hop traversal now does moniker→blob resolution. Mitigated by hot-edge cache and the limited-hop workload. This is the deliberate trade for clean versioning + free MVCC.
• De-materialization is invasive. Touches the graph build path, the SCIP/LSP decode (stop eager-resolving monikers, keep them), the incremental patcher (drop reconnect_incoming LSP pass), and the retrieval ops (add resolution + cache). Biggest single chunk of work — but it's the unlock for everything else.
• Storage growth across versions. Bounded by blob dedup (huge cross-commit overlap) + GC of unreffed versions/blobs past a grace window.
• Migration. Import the existing .codeminer_cache/ + repo_manifest.json as one initial version (ref=main); compat shim so old manifest paths still load.
• Substrate discipline. Resist re-coupling cross-file edges into a mutable shared graph "for query speed" — that reintroduces the axis-2 break.

Implementation Plan

• Phase A — de-materialize cross-file edges (the pivot, do first). Keep SCIP monikers unresolved per-blob; add defs index; resolve lazily at query time + hot-edge cache; remove eager reconnect_incoming from the incremental path. Validate graph-query parity against today's materialized graph.
• Phase B — content-addressed blob store + manifests (axis 1). Per-file blob subgraphs keyed by file content hash; versions/manifest/refs tables; incremental index reuses unchanged blobs. Multi-commit coexistence + rollback.
• Phase C — snapshot isolation (axis 2). Reader pins (version, overlay); append-only base; MVCC reads; GC of unreffed versions/blobs.
• Phase D — per-user overlay (axis 3, weak isolation). Mutable overlay layer over a committed snapshot; row-level filtering; tenant_id reserved nullable.
• (Deferred RFCs) server substrate (Postgres + object store), vector-DB swap (Milvus partition-key / Qdrant / LanceDB), multi-org SaaS strong isolation.

Effort

effort/large

[fishmingyu]

Triage — This RFC spans four subsystems:

• scope/graph: cross-file edge de-materialization, igraph MVCC, SCIP decode changes (code_graph.py:195-229, scip_decode_core.py:99-123, patcher_base.py, subgraph_mgr.py)
• scope/indexing: content-addressed blob store, manifest tables, FAISS-as-blob, incremental pipeline changes
• scope/compiler: IndexStore contract, repo_manifest.json migration, version lifecycle
• scope/retrieval: query-time moniker resolution + hot-edge cache (directly modifies the retrieval op path per the RFC body)

Setting priority/P2 — the current single-version mutable graph is a working (if architecturally constrained) workaround; nothing is blocked today.

CC @siriuxyu (graph / indexing / retrieval lead) and @fishmingyu (compiler / overall architecture).