Concurrent delete_document in the same bank deadlocks: unordered FK cascade into memory_links, plus the stale-observation sweep locking other documents' units (0.9.2)

[kubot-app]

Environment

• hindsight-api 0.9.2 (ebad47824), PostgreSQL backend, pgvector
• Single dataplane process, HINDSIGHT_API_RUN_MIGRATIONS_ON_STARTUP=false, migrations applied by hindsight-admin run-db-migration

Symptom

Two concurrent DELETE /v1/{ns}/banks/{bank_id}/documents/{document_id} requests for different documents in the same bank, issued ~20 ms apart, both aborted:

ERROR - hindsight_api.api.http - Error in /v1/default/banks/<bank>/documents/0c5b1f9c-…: deadlock detected
ERROR - hindsight_api.api.http - Error in /v1/default/banks/<bank>/documents/7531f069-…: deadlock detected

asyncpg.exceptions.DeadlockDetectedError propagates out of api_delete_document and surfaces as HTTP 500. It is intermittent — a retry succeeds.

The workload is an ordinary "delete these N documents" batch: the client fans out ~20 single-document deletes into one bank with asyncio.gather. Since there is no bulk document-delete endpoint, any multi-document deletion is necessarily N concurrent single-document deletes, so this is the expected shape for that operation rather than an unusual access pattern.

Why this is not covered by the existing fixes

This looks adjacent to #2560 / #2570 / #3393 / #3396, but those all fixed paths that delete_document does not use:

• Fix chunk delete deadlock ordering #2570 and fix(retain): match chunk-delete link endpoints through indexable joins (#3387) #3393 gave delete_chunks_by_ids a sorted memory_links pre-delete. delete_document never calls it.
• memory_links lock ordering is still not global: insert sorts on half the unique key, and disagrees with the delete's order #3396 addressed insert-vs-delete ordering in _bulk_insert_links and the chunk-delete order.

delete_document issues a bare parent-row delete and lets Postgres cascade:

deleted = await conn.fetchval(
    f"DELETE FROM {fq_table('documents')} WHERE id = $1 AND bank_id = $2 RETURNING id",
    document_id, bank_id,
)

engine/memory_engine.py:7929-7936 (v0.9.2)

The cascade order is chosen by Postgres per-tuple and is not reachable from SQL, so no amount of ordering elsewhere constrains it. The whole body runs in one transaction under acquire_with_retry + conn.transaction() (:7884-7885), and acquire_with_retry retries only the connection acquire — its own docstring states exceptions raised inside the async with block are not retried (engine/db_utils.py:118-125). So there is no deadlock retry on this path.

Two independent cycles

Either alone is sufficient.

A. FK cascade through memory_links

memory_units.(document_id, bank_id) → documents is ON DELETE CASCADE, and memory_links cascades from memory_units on both from_unit_id and to_unit_id (alembic/versions/5a366d414dce_initial_schema.py:285-290, :457-468). Temporal links are written as explicit bidirectional pairs (engine/retain/link_utils.py:499-501).

For units a ∈ docX, b ∈ docY with links L = (a→b) and M = (b→a):

• DELETE docX cascades from a: from_unit_id removes L, to_unit_id removes M → L then M
• DELETE docY cascades from b: from_unit_id removes M, to_unit_id removes L → M then L

The DEFERRABLE INITIALLY DEFERRED FKs from 9f8e7d6c5b4a move when the cascade runs, not the order within it.

B. The stale-observation sweep touches other documents' rows

delete_stale_observations runs after the cascade, deliberately (engine/memory_engine.py:7929-7932). In engine/memories/pg/writes.py:

obs_ids = [uuid.UUID(obs.unit_id) for obs in affected_obs]
...
for obs in affected_obs:
    for src_str in obs.source_memory_ids:
        if src_str not in deleted_set and src_str not in seen_remaining:
            remaining_source_ids.append(uuid.UUID(src_str))
...
await conn.execute(f"DELETE FROM {fq_table('memory_units')} WHERE id = ANY($1::uuid[])", obs_ids)
...
await conn.execute(f"UPDATE {fq_table('memory_units')} SET consolidated_at = NULL WHERE id = ANY($1::uuid[]) ...",
                   remaining_source_ids)

remaining_source_ids is by construction the observation sources that are not in this document — i.e. memory units belonging to other documents in the bank. Both arrays are built by unordered iteration over an unordered SELECT and passed straight to ANY(...): no ORDER BY, no sort, no FOR UPDATE.

t1  A: DELETE FROM documents (docX)   -> exclusive locks on docX units
t2  B: DELETE FROM documents (docY)   -> exclusive locks on docY units
t3  A: UPDATE memory_units ... ANY(remaining_A)   -- contains docY units -> waits on B
t4  B: UPDATE memory_units ... ANY(remaining_B)   -- contains docX units -> waits on A
                                                  -> 40P01

An observation co-sourced from both documents adds a second edge, since both transactions delete that same row in step obs_ids.

Worth noting the contrast: enqueue_relink_victims and enqueue_entity_prune_candidates, called a few lines earlier in the same transaction, are carefully sorted for exactly this reason (#3034). The sweep below them is not.

Still present on main

Checked origin/main at 6f441b0ae (~1250 commits past v0.9.2): delete_document has the same acquire_with_retry + conn.transaction() shape with no advisory lock and no deadlock retry, and delete_stale_observations is unchanged — obs_ids and remaining_source_ids are still unordered.

Reproduction sketch

1. Create bank B.
2. Retain documents X and Y into B with event times inside the temporal-link window, so memory_links holds cross-document bidirectional pairs. Run consolidation so at least one observation draws source_memory_ids from both.
3. Concurrently: DELETE …/documents/X and DELETE …/documents/Y.
4. Repeat ~20×, or issue 20 document deletes into one bank at once.

Expect one request to fail with DeadlockDetectedError (40P01) → HTTP 500.

Suggested fix

1. Retry on 40P01. retry_with_backoff already classifies DeadlockDetectedError (engine/db_utils.py:40) and is already used for index DDL, the entity-prune batch and bank creation. Wrapping the delete_document transaction body would make this transparent. The body re-reads unit ids and uses DELETE … RETURNING, so it is safe to re-run.
2. Serialise same-bank deletes. SELECT pg_advisory_xact_lock(hashtext($bank_id)) at the top of the transaction eliminates both cycles and is per-bank, so it does not contend across banks. Sorting obs_ids / remaining_source_ids and adding ORDER BY id closes B only — A is a cascade and cannot be ordered from SQL — so ordering alone is not sufficient here.

A regression test shaped like tests/test_memory_links_to_unit_id_concurrent_delete.py, but with two concurrent delete_document calls on two linked documents in one bank, would pin it. The existing test covers insert-vs-delete, not delete-vs-delete.

Caveat

Our captured log line carries only deadlock detected; the server-side DETAIL: naming the relations and tuples was not retained, so which of A or B fired is read off the code rather than observed. Both are present in 0.9.2 and either is sufficient. Happy to re-run with log_lock_waits = on and deadlock_timeout = 1s and attach the deadlock report if that would help pin it.

[r266-tech]

I tried this against current main (bde55237), using the real HTTP document-delete endpoint, the published Python client and an isolated embedded PostgreSQL database. A stub model supplied deterministic facts/observations; no production database was used.

So far I have not reproduced the error: three batches of 20 documents with shared entities, five pairs with event-time links and no shared entities, and five batches of 20 documents with no explicit entities and generated observations all completed. These runs do not prove the race is absent: they do not force the transaction interleaving, and the latter case does not yet assert an observation co-sourced from the two particular concurrently deleting documents.

Could you share the PostgreSQL deadlock DETAIL (the two statements/lock wait edges, with identifiers and document content redacted), and whether the failure also occurs on a recent release? That would distinguish the cascade cycle from the observation cleanup cycle and give a concrete interleaving to make deterministic.

One implementation boundary I found: current delete_document also reaches store-owned deletion and attachment blob cleanup inside its transaction body. A blanket retry of the whole body therefore needs more care than replaying SQL alone. I have not added a speculative retry or claimed a fix from the passing runs.

[r266-tech]

Follow-up: I was able to make the observation-source cycle deterministic by controlling two real engine transactions. After the first document cascade pauses, the second request waits while resetting the first document’s source; resuming the first produces DeadlockDetectedError on current main. The same pattern also reproduces between observation clearing and document deletion.

PR #4339 contains the fix and regression cases. All three cleanup entrypoints take the bank row before their data locks; it avoids replaying attachment/external-store effects. The tests cover rollback, repeated deletion and independent progress in another bank. The new HTTP story also asserts that the two documents really share an observation before deleting them.

Local validation: 126 database/adapter tests, the HTTP story, and full repository lint pass. Hosted CI is still running. This establishes the observation-cleanup cycle; I am not claiming to have separately reproduced every cascade cycle described above.