Relations are not unique

[aeneasr]

Describe the bug

I can create duplicate relations that express the same thing.

Reproducing the bug

Steps to reproduce the behavior:

$ curl --location --request PUT 'http://localhost:4466/relations' \
--header 'Content-Type: application/json' \
--data-raw '{
    "object": {
        "id": "amorevino",
        "namespace": "tenants"
    },
    "relation": "write",
    "subject": {
        "id": "aeneas"
    }
}'
$ curl --location --request PUT 'http://localhost:4466/relations' \
--header 'Content-Type: application/json' \
--data-raw '{
    "object": {
        "id": "amorevino",
        "namespace": "tenants"
    },
    "relation": "write",
    "subject": {
        "id": "aeneas"
    }
}'

[robinbraemer]

Inserts of duplicate tuples do not error if the tuple already exists (See API).

This is now intended by design as per https://github.com/ory/keto/pull/315#discussion_r526861229.

Current actions:

INSERT - not errors tx if already exists
DELETE - not errors tx if not found

Later we can add actions like:

INSERT_NEW - errors tx if already exists
DELETE_FOUND - errors tx if not found

This is for the gRPC API, do you expect an "already exists" error for PUT in the REST API?

[anonrig]

How do you make sure subjects are not empty, the relation tuples are unique? Due to the database structure of relation_tuples, it's not possible to create uniqueness on the DB layer. the primary key of a relation_tuples table includes commit time, which creates duplicate values and nowhere to make a tuple unique.

[zepatrik]

The question is if there is any downside to this behavior. In the end the system does what it is supposed to do, and also all same relation tuples get deleted because we delete by: https://github.com/ory/keto/blob/6e9c2d16a35ca8d2d1ee95d1e135b8616f7f16f7/internal/persistence/sql/relationtuples.go#L113-L118 We have to think about what implications this has for #517. As the tuple does not change the behavior of the system, we might only want to keep the old one to ensure that the new one does not need propagation time for subsequent requests.

However, we should add tests to ensure this behavior will stay consistent in the future.

[counter2015]

On the one hand, I'm afraid that this kind of duplicates slow the performance.

On the other hand, it make me confused when I use expand API

$ keto expand view videos /cats/1.mp4

∪ videos:/cats/1.mp4#view
├─ ☘ *️
├─ ☘ *️
├─ ∪ videos:/cats/1.mp4#owner
│  ├─ ∪ videos:/cats#owner
│  │  ├─ ☘ cat lady️
│  │  ├─ ☘ cat lady️
│  ├─ ∪ videos:/cats#owner
│  │  ├─ ☘ cat lady️
│  │  ├─ ☘ cat lady️
├─ ∪ videos:/cats/1.mp4#owner
│  ├─ ∪ videos:/cats#owner
│  │  ├─ ☘ cat lady️
│  │  ├─ ☘ cat lady️
│  ├─ ∪ videos:/cats#owner
│  │  ├─ ☘ cat lady️
│  │  ├─ ☘ cat lady️

When query from sql

Due to the database structure of relation_tuples, it's not possible to create uniqueness on the DB layer. the primary key of a relation_tuples table includes commit time, which creates duplicate values and nowhere to make a tuple unique.

I'm not sure whether this is the best solution in terms of performance

A trival way in postgres to create unique constraint like following

alter table keto_0000000000_relation_tuples
add unique (shard_id, object, relation, subject);

Then we can test it

$ keto relation-tuple create cat-videos-example/relation-tuples/ -c cat-videos-example/keto.yml
NAMESPACE   OBJECT      RELATION NAME   SUBJECT             
videos      /cats/1.mp4 owner       videos:/cats#owner      
videos      /cats/1.mp4 view        videos:/cats/1.mp4#owner    
videos      /cats/1.mp4 view        *               
videos      /cats/2.mp4 owner       videos:/cats#owner      
videos      /cats/2.mp4 view        videos:/cats/2.mp4#owner    
videos      /cats       owner       cat lady            
videos      /cats       view        videos:/cats#owner      

$  keto relation-tuple create cat-videos-example/relation-tuples/ -c cat-videos-example/keto.yml
Error doing the request: rpc error: code = AlreadyExists desc = Unable to insert or update resource because a resource with that value exists already

[ryukinix]

Any plan to fix that?

[vgarvardt]

Tried to dig into this issue, quite a lot of layers of abstraction for pretty simple DB structure, but everything end up at https://github.com/ory/keto/blob/master/internal/persistence/sql/persister.go#L88 that is calling pop.Connection.Create(...) method. ORM is doing a lot of magic under the hood but I assume everything ends up with the simple INSERT INTO ... query.

With raw sql it could be pretty easy to check record existence using existing index values, using something like INSERT INTO ... WHERE NOT EXISTS ..., but with ORM something similar can be achieved using pop.Connection.ValidateAndCreate(...) - will try to find out how it works and if it really can solve duplicates problem.

[ryukinix]

That's a nice catch up! It would be awesome for us this being solved. Currently we, at neoway feature store access control, need to check the non-existence ahead of time with a additional http request to avoid duplicates and degradation of permission control system when a new permission need to be added.

Att., Manoel Vilela.

Em qui., 13 de abr. de 2023 18:07, Vladimir Garvardt < @.***> escreveu:

Tried to dig into this issue, quite a lot of layers of abstraction for pretty simple DB structure, but everything end up at https://github.com/ory/keto/blob/master/internal/persistence/sql/persister.go#L88 that is calling pop.Connection.Create(...) method. ORM is doing a lot of magic under the hood but I assume everything ends up with the simple INSERT INTO ... query.

With raw sql it could be pretty easy to check record existence using existing index values, using something like INSERT INTO ... WHERE NOT EXISTS ..., but with ORM something similar can be achieved using pop.Connection.ValidateAndCreate(...) - will try to find out how it works and if it really can solve duplicates problem.

— Reply to this email directly, view it on GitHub https://github.com/ory/keto/issues/292#issuecomment-1507611326, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB2J57WBJL6OSS4PAWOCPFTXBBTKXANCNFSM4TQTORPQ . You are receiving this because you commented.Message ID: @.***>

[76creates]

-- Short Solving this one trough the DB might require adding NOT NULL constraint to subject_id, subject_set_namespace, subject_set_object, and subject_set_relation in keto_relation_tuples.

-- Long In PSQL15+ we can make use of UNIQUE NULLS NOT DISTINCT constraint and it will work, I've tested it with following migration:

-- Delete duplicate relations
DELETE FROM keto_relation_tuples
WHERE (shard_id, nid) IN (SELECT shard_id, nid
                          FROM (SELECT shard_id, nid,
                                       ROW_NUMBER() OVER (
                                           PARTITION BY namespace, object, relation, subject_id, subject_set_namespace, subject_set_object, subject_set_relation
                                           ORDER BY shard_id, nid) AS rnum
                                FROM keto_relation_tuples) t
                          WHERE t.rnum > 1);

-- Add unique constraint
ALTER TABLE keto_relation_tuples ADD CONSTRAINT keto_relation_unique_relations UNIQUE NULLS NOT DISTINCT (
                          namespace, object, relation, subject_id, subject_set_namespace, subject_set_object, subject_set_relation);

Tho the issue is with SQLite, MySQL, and Cockroach which don't support this at the moment(those are the ones I see explicitly stated in the migration files). I am not sure if we need one shoe fits all DB solution, if we do then we need to add NOT NULL constraint and use a default ignored value, empty string, and all 0 UUID.

I've tested PSQL solution, and I get 409 on conflict, seams legit.

I could implement this if approach is approved.