memdb: concurrent WriteRelationships can be silently lost

[Mr-Pepe]

Disclaimer: This report is mostly AI-generated but it describes a real issue we are encountering in CI and I have manually verified the reproduction instructions.

What platforms are affected?

macos, linux (race is platform-independent; observed on both)

What architectures are affected?

arm64, amd64

What SpiceDB version are you using?

v1.52.0 (spicedb serve-testing); by code inspection the race is still present on main.

Steps to Reproduce

1. Start spicedb serve-testing.
2. In a loop: issue two concurrent WriteRelationships requests (2 TOUCHes each, disjoint resources), then immediately do a fully_consistent ReadRelationships for both resources.
3. Repeat ~10–20k rounds.

Python repro script attached below. On an M-series MacBook it hits ~1 loss per 4,000 rounds:

round 1190: doc b-1190 acked but read back []
round 6263: doc a-6263 acked but read back []
...
done: 20000 rounds, 5 lost-write events

This seems to depend a bit on the machine utilization, so running the repro script multiple times in parallel helps.

Expected Result

Every acked WriteRelationships is visible to a subsequent fully_consistent read.

Actual Result

Occasionally one of the two writes is acked OK but all of its relationships are invisible to an immediately following fully_consistent read. The loss is transaction-granular and self-heals on the next commit to the datastore, so it is only observable in the window between the two commits and whatever write comes next.

Minimum reproducible example

"""Sharp probe for the memdb revision-order inversion race.

Each round: 2 concurrent WriteRelationships (2 TOUCHes each), then an
immediate fully-consistent read of all 4 rels. If commit order inverted
revision order, the later-committed write's rels are invisible at head.
"""

import asyncio
import sys
import uuid

import grpc
from authzed.api.v1 import (
    AsyncClient,
    Consistency,
    ObjectReference,
    ReadRelationshipsRequest,
    Relationship,
    RelationshipFilter,
    RelationshipUpdate,
    SubjectReference,
    WriteRelationshipsRequest,
    WriteSchemaRequest,
)
from grpcutil import insecure_bearer_token_credentials

SCHEMA = """
definition user {}
definition document {
    relation viewer: user
    relation editor: user
}
"""

ENDPOINT = "localhost:30051"


def touch(doc: str, relation: str) -> RelationshipUpdate:
    return RelationshipUpdate(
        operation=RelationshipUpdate.OPERATION_TOUCH,
        relationship=Relationship(
            resource=ObjectReference(object_type="document", object_id=doc),
            relation=relation,
            subject=SubjectReference(
                object=ObjectReference(object_type="user", object_id="tom")
            ),
        ),
    )


async def main() -> None:
    key = f"repro-inv-{uuid.uuid4().hex[:8]}"
    client = AsyncClient(ENDPOINT, insecure_bearer_token_credentials(key))
    await client.WriteSchema(WriteSchemaRequest(schema=SCHEMA))
    rounds = int(sys.argv[1]) if len(sys.argv) > 1 else 20000
    lost_events = 0

    for r in range(rounds):
        doc_a = f"a-{r}"
        doc_b = f"b-{r}"

        async def write(doc: str) -> bool:
            try:
                await client.WriteRelationships(
                    WriteRelationshipsRequest(
                        updates=[touch(doc, "viewer"), touch(doc, "editor")]
                    )
                )
                return True
            except grpc.aio.AioRpcError as e:
                print(f"round {r}: write {doc} error {e.code().name}")
                return False

        ok_a, ok_b = await asyncio.gather(write(doc_a), write(doc_b))

        present: set[tuple[str, str]] = set()
        for doc in (doc_a, doc_b):
            async for resp in client.ReadRelationships(
                ReadRelationshipsRequest(
                    relationship_filter=RelationshipFilter(
                        resource_type="document", optional_resource_id=doc
                    ),
                    consistency=Consistency(fully_consistent=True),
                )
            ):
                present.add((doc, resp.relationship.relation))

        for doc, ok in ((doc_a, ok_a), (doc_b, ok_b)):
            if not ok:
                continue
            got = {rel for d, rel in present if d == doc}
            if got != {"viewer", "editor"}:
                lost_events += 1
                print(f"round {r}: doc {doc} acked but read back {sorted(got)}")

        if r % 5000 == 0 and r > 0:
            print(f"...{r} rounds, {lost_events} losses so far")

    print(f"done: {rounds} rounds, {lost_events} lost-write events")


asyncio.run(main())

Analysis

In `internal/datastore/memdb/memdb.go`, `ReadWriteTx`:

• stamps newRevision := mdb.newRevisionID() at transaction entry, before the user function runs and before the write lock is acquired (the memdb.Txn is created lazily via txSrc on first use);
• on success appends snapshot{newRevision, snap} to mdb.revisions in commit order.

Interleaving:

1. Tx A enters, stamps revision 100, gets preempted before creating its txn.
2. Tx B enters, stamps revision 101, acquires the write txn first, commits → revisions = [..., {101, snapB}].
3. Tx A acquires the write txn, commits → revisions = [..., {101, snapB}, {100, snapA}] — out of order.

Now headRevisionNoLock() returns the last element's revision (100), and SnapshotReader's sort.Search for the first entry >= 100 lands on {101, snapB} — a snapshot taken before A committed. A fully-consistent read therefore misses all of A's acked writes. Any later commit appends a genuinely newer revision and the head read resolves to a complete snapshot again, which is why the loss is transient.

This is distinct from #1545 / #1547: that path (serialization retries exhausted) correctly returns DEADLINE_EXCEEDED to the caller — verified in the same repro under heavier load (230 errored writes, none silently lost). The inversion above is the genuinely silent path, and likely what the original #1545 reporter observed ("responded OK, but actually not written").

Possible fixes: stamp the revision at commit time under the same lock that appends to mdb.revisions, or insert the snapshot in revision order and make headRevisionNoLock return the max.

A Go-level reproduction in the style of TestConcurrentWriteRelsError (two goroutines, read-back after both ReadWriteTx calls return) should hit it as well.

[Naganathan05]

Hi @Mr-Pepe,
I've replicated the issue locally with a simple test TestConcurrentWriteRelsError as you mentioned,
Can I open a PR with fix for this ?