Add an API to exactly "Set" a relation

[mateenkasim]

Problem Statement

TLDR

I propose creating a "Set" API that receives a resource type, resource ID, and relation name as well as a subject or set of subjects, and it atomically does the following:

• Deletes all tuples that previously had this resource type, resource ID, and relation name
• Creates new tuples using the given subject or set of subjects

Abstractly, this allows for atomically setting a relationship to an exact value (or set of values) without requiring the user to read the old value, construct preconditions for avoiding race conditions, or construct explicit DELETE operations.

Description

It's established that all SpiceDB relations are essentially many-to-many relations. Consider this schema:

definition student {}

definition class {
    relation enrolled: student
}

In this case, the many-to-many relation enrolled is appropriate; a class can have many enrolled students, and a student can be enrolled in many classes. Now, consider this schema:

definition folder {}

definition file {
    relation parent: folder
}

In this case, the many-to-many relation is inappropriate; a folder can have many files, but a file can have exactly one parent folder. If a user wants file.parent to be a many-to-one relation, this must be enforced at the application level, not the DB level.

Users of SpiceDB will always want to model one-to-one, many-to-one, and many-to-many relations, and I believe SpiceDB users are duplicating a lot of work to enforce these invariants at the application level. To make this easier without extending the schema, SpiceDB could expose an atomic "Set" operation that exactly defines a relation.

I consider two scenarios:

• One-to-One or Many-to-One relations, where there must be at most one (or exactly one, depends on context) subject under that relation per resource at any time
  • e.g. The second schema above, each file must have exactly one parent folder
  • Currently, users must do the following to atomically set this relation's subject to some value W
    • ReadRelationships to get the current subject, call it V
    • Make a Precondition that checks V is still the current subject, call it P
    • If V is not null, create a RelationshipUpdate to DELETE the tuple with subject V
    • Create a RelationshipUpdate to CREATE/TOUCH the tuple with new subject W
    • Make a WriteRelationships request using P and the above two RelationshipUpdates
    • If the call failed due to P, you know someone else changed the relation concurrently. Repeat the whole process again.
• Many-to-Many relations, which are the loose default in SpiceDB
  • e.g. In the first schema above, when a new school year begins, an admin may want to "Set" the class roster to a new list, completely wiping the old list in one atomic transaction.
  • Currently, users must do the following to atomically set this relation to a specific set of tuples T
    • ReadRelationships to get all current subjects, call this set of subjects S
    • Make a Precondition that checks that all of S are still current subjects, call it P
      • This is to prevent two concurrent "set" operations succeeding, where the resulting relation contains the union of both sets. This is a situation that could not happen when single-threaded, and so should be avoided when multi-threaded.
    • If S is not empty, create a RelationshipUpdate for each s$\in$S to DELETE the tuple with subject s
    • Create a RelationshipUpdate for each t$\in$T to CREATE/TOUCH the tuple with new subject t
    • Make a WriteRelationships request using P and all the above RelationshipUpdates
    • If the call failed due to P, you know someone else changed the relation concurrently, potentially with another "set" operation. Repeat the whole process again.

This is quite a lot of work to enforce an otherwise common DB paradigm. It would be alleviated if SpiceDB had a semantic to exactly "set" the relationship, internally handling the deletion of all previous values without requiring the user to know what those previous values were.

Solution Brainstorm

I'm not completely sure what the Set API would look like. I offer two options here, one for each scenario mentioned above.

• One-to-One or Many-to-One relations, where there must be at most one (or exactly one, depends on context) subject under that relation per resource at any time
  • e.g. The second schema above, each file must have exactly one parent folder
  • This could be solved with a new RelationshipUpdate.Operation: OPERATION_SET
    • Deletes all previous tuples with the same resource and relation
    • Writes a single new tuple, the result of "setting" the relation

RelationshipUpdate(
    operation=RelationshipUpdate.Operation.OPERATION_SET, # Notice the new operation
    relationship=Relationship(
        resource=ObjectReference(
            object_type="file",
            object_id="F"
        ),
        relation="parent",
        subject=SubjectReference( # This is the single new subject of the many-to-one relationship
            object=ObjectReference(
                object_type="folder",
                object_id="P"
            )
        )
    )
)

• Many-to-Many relations, which are the loose default in SpiceDB
  • e.g. In the first schema above, when a new school year begins, an admin may want to "Set" the class roster to a new list, completely wiping the old list in one atomic transaction.
  • This could be solved with a new SetRelationship API.
    • Deletes all previous tuples with the same resource and relation
    • Writes a given set of new tuples, which are now the only tuples under this resource/relation
    • This would perform the compound "Set" operation atomically, but it wouldn't allow atomic transactions with other operations. This is the same behavior as the current DeleteRelationships API, which allows doing many deletes but can't perform Writes in the same transaction.

// To specify only the resource and the relation
// Distinct from RelationshipFilter because you can't specify the subject
message RelationshipHead {
    ObjectReference resource = 1;
    string relation = 2;
}

// Clears all tuples that match the RelationshipHead
// Writes new tuples using the RelationshipHead as resource/relation and the given subjects as subject
message SetRelationshipRequest {
    RelationshipHead relationship_head = 1;
    repeated SubjectReference subjects = 2;
}

Of course, my goal is the capability this operation provides, and I am not attached to the APIs I proposed. Happy to hear anyone else's thoughts on the matter or other solutions if they come up. Thanks for all the work y'all do on SpiceDB!

[tstirrat15]

One piece of context: for this use case, SpiceDB is the primary store of this data. I think in other contexts these sorts of invariants would be enforced by the API/datastore that was the primary store of the data prior to replication into SpiceDB.

[mateenkasim]

I think this is the same request as was asked here, setting a relationship regardless of the previous value: https://github.com/authzed/spicedb/issues/887

[vroldanbet]

This sounds reasonable, that would be useful API. My primary concern is that transactionally deleting a wide relation (think a relation with hundreds of thousands of relationships) won't work. Most databases will struggle with such large transactions, which is why DeleteRelationships has an API to support batching deletes of a wide relation, because users observed WriteRelationship with DELETE causing disruption in their backing datastores.

This would work if we could restrict the side of those relations so that transactions stay at a reasonable size.