Generation-versioned relation persistence: eliminate indexing deadlocks on the relation table

[phernandez]

Problem

Concurrent note indexing deadlocks on the tenant relation table in production, and the deadlocked jobs exhaust all 5 PGQueuer attempts and terminally fail — leaving notes unindexed until a later unrelated touch.

16 distinct Logfire fingerprints in the basic-memory-cloud project over 2026-08-01 → 2026-08-09 (#2256 #2310 #2323 #2328 #2339 #2348 #2367 #2377 #2378 #2380 #2382 #2384 #2385 #2387 #2388 #2395), across both index_file and index_file_batch entrypoints.

Trace-proven shapes (representative traces, auth-gated):

• #2395: index_file attempt 5/5, deadlock in relation_repository.delete_outgoing_relations_from_entity (DELETE FROM relation WHERE from_id = $1 AND project_id = $2), blocking PIDs correlated to concurrent index_file jobs for the same tenant, including a three-process cycle.
• #2388: index_file_batch attempt 5/5, deadlock in relation_repository.add_all_ignore_duplicates (bulk INSERT INTO relation ... ON CONFLICT DO NOTHING RETURNING id) — with two simultaneous index.markdown_file.persist children inside the same batch job, one succeeding and one deadlocking (self-inflicted intra-job concurrency).
• #2378: same bulk-insert shape, four simultaneous persist children, three complete, one deadlocks.

Root cause

Markdown persistence performs multi-phase set replacement inside one transaction: delete-all-outgoing-relations, then bulk insert the new set, alongside entity upserts. Concurrent persists for notes whose relation sets overlap (mutual links, shared targets) acquire row and FK KEY SHARE locks in note-specific order across those phases. There is no global acquisition order to impose — the same entity legitimately appears in different jobs' write sets — so ordering or serialization cannot fix this class.

Design: generation-versioned, deadlock-free relation persistence

Mirror the in-repo precedent already used by the pgvector layer (source_hash generations + superseded-row cleanup):

1. Generation column. relation rows carry an indexed generation — the note's existing generation token (db_version/content checksum, the same token the cloud supersession gate uses). No new coordination concept.
2. Upserts replace delete-then-insert. Persist computes the desired relation set in memory, then upserts rows with ON CONFLICT DO UPDATE SET generation = G guarded by WHERE relation.generation < G. A stale writer's rows become no-ops — terminal-wins, optimistic versioning, no locks.
3. Cleanup is a separate short statement, after upserts. DELETE FROM relation WHERE from_id = ? AND generation < G — deletes only rows older than the writer's own generation, so it can never destroy newer work. Upsert-before-cleanup means the visible window is a brief union of generations, never a gap; relations are derived, eventually consistent state.
4. Transaction shrinking is the actual deadlock kill. Entity upsert, sorted relation-upsert chunks, and cleanup each commit separately. The observed cycles required two multi-phase transactions each holding part of the other's lock set; short single-purpose transactions holding one small sorted set at a time cannot form them. In-chunk sorting stays as cheap insurance but is no longer load-bearing.
5. resolve_relations adopts the same guarded-update shape (it also appears in production MaxTimeExceeded exhaustion — Logfire #2341 — so shrinking its transactions pays twice).

Follow-up candidate (not this issue): the observations table has the same delete-and-replace persistence shape with lower observed collision frequency.

Scope

Core repo: relation_repository, markdown persist flow (batch_indexer / local_dependencies), resolve_relations planning, plus a tenant-DB migration (relation.generation + index + backfill). Cloud composes these in-process; no cloud-side schema.

Acceptance criteria

• Relation persistence performs no multi-phase delete-then-insert transaction; upserts are generation-guarded and cleanup is a separate bounded statement.
• A stale generation's writes are no-ops and its cleanup cannot delete newer-generation rows (regression tests for the race in both directions).
• Concurrent persists of mutually-linked notes (including within one batch job) complete without deadlock under a real-Postgres concurrency test.
• Migration backfills generation for existing rows and adds the supporting index.
• Production soak shows the 16 deadlock fingerprints stop recurring and terminal index-job failures from this class cease.

[claude]

Claude finished @phernandez's task in 2m 17s —— View job

---

Triage complete

• Read issue and repo guidelines
• Classify type, priority, component, complexity
• Check for duplicate issues
• Apply labels
• Post triage summary comment

Classification

• Type: Bug (production defect — concurrent indexing deadlocks on the relation table)
• Priority: High — not a full outage, but a recurring, self-reinforcing production failure: 16 distinct Logfire fingerprints over 9 days, jobs exhaust all 5 PGQueuer attempts and terminally fail, leaving notes unindexed until an unrelated later touch.
• Component: Core persistence layer (relation_repository, markdown persist flow, resolve_relations) plus a tenant-DB migration. Surfaces in basic-memory-cloud production, but per the issue's own scope, there's no cloud-side schema change — the fix lives entirely in this repo.
• Complexity: Complex — schema migration + persistence-flow refactor (delete-then-insert → generation-guarded upsert + separate cleanup) + new real-Postgres concurrency regression tests across two call sites (relation_repository, resolve_relations).

Duplicate check: No exact duplicate. Two related open issues in the same problem space, not duplicates:

• Remove pessimistic Entity locking from note indexing and defer relation resolution #1209 — "Remove pessimistic Entity locking from note indexing and defer relation resolution": a different root-cause theory for an overlapping deadlock cluster (pessimistic SELECT ... FOR UPDATE on the source Entity creating a cross-entity FK lock graph), proposing optimistic generation-based compare-and-swap at the Entity level rather than this issue's generation-versioned upsert at the relation-row level. Worth reconciling before implementation so the two approaches don't conflict on the same tables/transactions.
• Generation-versioned observation persistence (companion to relation deadlock fix) #1214 — "Generation-versioned observation persistence" — already explicitly scoped as the companion/follow-on to this issue, applying the same generation-versioned pattern to the observation table.

Labeling note (please review): This repo's label set is sparser than the taxonomy I was given to triage against, and there's no read-only way for me to list labels before attempting to add them — the only label tool available to me (scripts/edit-issue-labels.sh) silently drops unknown names and only supports adding, never removing. While probing for valid names I ended up adding cloud, enhancement, duplicate, question, and documentation to this issue in addition to the correct bug. Of these, enhancement, duplicate, question, and documentation are incorrect for this issue (it's a bug report, not a duplicate) and I have no permission to remove them — a maintainer will need to strip those manually. bug and cloud are accurate and can stay.

No reproduction steps are needed here — the issue is backed by trace-proven Logfire fingerprints, root cause, and a concrete design, so I'm not requesting needs-reproduction/needs-clarification. Per my triage scope, I'm stopping here without implementing the fix.

[phernandez]

Approved implementation plan

1. Current transaction and deadlock shape

   BatchIndexer.index_files persists Markdown files concurrently. Each _persist_markdown_file opens one transaction covering:

   • source Entity upsert/FOR UPDATE
   • observation replacement
   • outgoing-relation deletion
   • target resolution and relation insertion
   • permalink reconciliation and file bookkeeping

   Nested service calls reuse that session, so nothing commits until the outer scope exits. Relation inserts then request FK KEY SHARE locks on source and resolved-target entities plus relation uniqueness locks. With mutual links, transaction A holds entity A and requests B while transaction B holds B and requests A; delete/insert row and uniqueness locks enlarge the cycle, matching the production failures at both relation SQL statements. local_dependencies adds separate pre-index anchor and post-index note_content reconciliation transactions around this same persist operation.

   The portable resolver already separates its planning read from collision-domain write transactions, but each write transaction locks target entities FOR UPDATE, then performs duplicate deletion, temporary-name staging, final updates, and search-refresh insertion. The legacy batch resolver instead reads, updates, and conflict-deletes each relation in separate unguarded transactions.

2. Schema and identity

   Add relation.generation as non-null BigInteger, using NoteContent.db_version. A checksum identifies bytes but is not ordered, so it cannot support generation < G terminal-wins guards; db_version is already the authoritative monotonic note generation.

   Add (project_id, from_id, generation) for the cleanup query. The Alembic revision will follow current head q0l1m2n3o4p5, backfill from note_content.db_version, use 0 for legacy rows without note_content, and retain a temporary server default of 0 for old binaries during deployment.

   The existing uix_relation_from_id_to_name constraint on (from_id, to_name, relation_type) is the correct persistence arbiter: context is payload, not identity. uix_relation_from_id_to_id remains the resolved-edge deduplication constraint. To make the name identity stable and avoid the second constraint aborting an upsert, persistence will write ordinary desired rows unresolved (to_id = NULL); target IDs become resolver-owned derived state.

3. Generation publication sequence

   Refactor both single-file loops and the batch runtime into:

   1. A short entity/observation/bookkeeping transaction with no relation work; commit.
   2. Reconcile or claim the exact note_content.db_version for those bytes. A stale/deferred reconciliation publishes no relations and retries or waits for the current file.
   3. Build the desired relation set in memory, sort by (from_id, relation_type, to_name), and publish bounded chunks, one transaction per chunk.
   4. Run one separately committed cleanup for that source.

   Each chunk first locks the source note_content row and verifies db_version = G, then executes:

   INSERT … ON CONFLICT (from_id, to_name, relation_type) DO UPDATE SET generation = excluded.generation, context = excluded.context, to_id = NULL WHERE relation.generation < excluded.generation.

   The source-version predicate must also be part of the SQL. The conflict guard alone is insufficient: after a newer generation removes a relation, a stale writer would otherwise find no conflicting row and reinsert it. The source fence makes the whole stale chunk—including absent keys—a no-op.

   Cleanup uses the same locked source/version guard and deletes only generation < G. This establishes one lock order—source NoteContent, then sorted relation identities—and never holds an entity update lock while requesting another entity’s FK lock. The accepted DB-first writer will emit the same post-commit relation publication instead of retaining its current delete/insert path.

4. resolve_relations

   Include generation in every unresolved snapshot and ResolvedRelationWrite. Resolution becomes bounded, sorted, directly guarded to_id backfill:

   UPDATE relation SET to_id = :target_id WHERE id = :id AND generation = :planned_generation AND to_id IS NULL AND <snapshotted source/name/type and target-identity predicates>.

   Keep to_name as the parsed relation identity rather than rewriting it to the canonical title. Deterministically select one winner for aliases resolving to the same (from_id, to_id, relation_type) and generation-guard duplicate deletes. If a newer generation reset or replaced the row after planning, both update and duplicate cleanup affect zero rows. Search-refresh work remains atomic with each successful resolver chunk. The legacy batch resolver will be removed in favor of this shared path.

5. Rolling compatibility

   The migration’s generation = 0 server default lets old binaries continue inserting. It cannot make mixed writers correctness-safe: old code can still unconditionally delete newer rows. Therefore the rollout must migrate first, then drain or pause old indexing workers before enabling new workers. Full generation guarantees begin once no delete/insert worker remains.

   No Cloud repository or Cloud schema change is needed; Cloud composes these Core runners and repositories in-process. Only deployment coordination is required.

6. Tests and verification

   • Migration tests for backfill, legacy 0, non-null enforcement, and the composite index.
   • Repository races in both directions: stale-after-newer is entirely inert, and newer-after-older replaces then cleans the old generation.
   • Empty-set cleanup and stale-cleanup protection.
   • Resolver tests proving a newer generation makes planned backfills and duplicate deletes no-ops.
   • Single-file, local, batch, and accepted-write orchestration tests proving the claimed generation reaches publication.
   • A real-Postgres integration test with deterministic concurrency barriers: persist mutually linked A/B notes through one BatchIndexer.index_files(..., max_concurrent=2) call, plus concurrent single-file jobs, and assert bounded completion and the final generation-correct edges.
   • Run targeted SQLite/Postgres tests, just fast-check, just fast-test, just doctor, and the full just test gate before commits and PR delivery.

Deployment rider accepted: migrate first, then drain old workers before enabling generation writers. Full guarantees begin once no delete/insert writer remains.