New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add support for basic cursors and limits to LookupSubjects #1379
base: main
Are you sure you want to change the base?
Conversation
da48a6b
to
19099a2
Compare
21ae960
to
c386a05
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I didn't have time to finish the review, sorry! This is my first attempt. So far it's looking good, although I have a bunch of questions.
Something I noticed is that when one resumes with a cursor, we are evaluating the whole graph again and sending queries to the database, even though they will return empty. It works, but is a lot of work that is wasted after resuming, and will be directly proportional to the complexity of the schema. Ideally the evaluation of the schema can also resume from where the cursor left off, e.g. if permission view = a + b + c
you'd restart evaluation at c
if that's where you left when the limit was hit. It would spare a bunch of dispatching (network calls across SpiceDBs!) and DB roundtrips.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
(unrelated to this file) I found that ErrLimitReached
in limits.go
is unused.
spicedb/internal/graph/limits.go
Line 9 in 28f9ccd
var ErrLimitReached = fmt.Errorf("limit has been reached") |
internal/services/v1/permissions.go
Outdated
excludedSubjectIDs := make([]string, 0, len(foundSubject.ExcludedSubjects)) | ||
for _, excludedSubject := range foundSubject.ExcludedSubjects { | ||
excludedSubjectIDs = append(excludedSubjectIDs, excludedSubject.SubjectId) | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
can we merge this into the loop below?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I did so, but I'm thinking maybe we just remove it entirely now? The field has been marked deprecated for a number of versions
internal/services/v1/permissions.go
Outdated
for _, excludedSubject := range foundSubject.ExcludedSubjects { | ||
resolvedExcludedSubject, err := foundSubjectToResolvedSubject(ctx, excludedSubject, caveatContext, ds) | ||
if err != nil { | ||
return err |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
lets add some context to those errors, given we are calling foundSubjectToResolvedSubject
in two different spots
internal/services/v1/permissions.go
Outdated
if subject == nil { | ||
continue | ||
} | ||
encodedCursor, err := cursor.EncodeFromDispatchCursor( |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
do we need to allocate a new encoded cursor each time here? Could we reuse the same proto instance and just modify the corresponding field? I did something as an optimization in the ReadRelationships streaming bits and helped a bunch with allocations and GC overhead. It would also spare us calling revision.String()
repeatedly.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It would be far less maintainable, but I'll see what I can do
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Done, but its a bit ugly
if subject.SubjectObjectId != tuple.PublicWildcard { | ||
countSubjectsFound++ | ||
if req.OptionalConcreteLimit > 0 && remainingConcreteLimit <= 0 { | ||
return nil |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Will subjects found continue to be streamed and discarded here even after the concrete limit is hit? Why not discard them earlier in this handler, given that once you reach the limit, you don't really care if a subject is resolved or not?
shouldn't we be signalling no more streaming is needed, e.g. cancelling?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Added cancelation; hopefully it doesn't break the stream
if req.SubjectRelation.Relation != tuple.Ellipsis { | ||
return nil | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
do we need to return earlier with this check given we are calling IsAllowedPublicNamespace
below?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes, to avoid a database roundtrip
internal/graph/lookupsubjects.go
Outdated
return fmt.Errorf("failed to UnionWith under lookupSubjectsExclusion: %w", err) | ||
afterSubjectID, _ := ci.headSectionValue() | ||
|
||
// Filter down the subjects found by the cursor (if applicable) and the apply a limit. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
typo
// Filter down the subjects found by the cursor (if applicable) and the apply a limit. | |
// Filter down the subjects found by the cursor (if applicable) and then apply a limit. |
for _, foundSubjects := range subjects { | ||
for _, foundSubject := range foundSubjects.FoundSubjects { | ||
// NOTE: wildcard is always returned, because it is needed by all branches, at all times. | ||
if foundSubject.SubjectId == tuple.PublicWildcard || (afterSubjectID == "" || foundSubject.SubjectId > afterSubjectID) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
in not sure to understand how we guarantee that we do not skip found subjects that are alphabetically after the current cursor but that hasn't been seen by the stream before.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Because the stream always returns in sorted order from the root. That way, we are always guaranteed to have a defined ordering (alphabetical) coming out of each subproblem
if subjectID == tuple.PublicWildcard { | ||
subjectIDsToPublish = append(subjectIDsToPublish, subjectID) | ||
continue | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
even though we increased the limit by one to accommodate the wildcard, we do not call prepareForPublicshing
here.
This is what I meant earlier with "special casing wildcards". Why increasing the limit by one to account for it instead of just ignoring the limit when we find one?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The wildcard is never applied against the limit because its "special". The limit above is the limit for the datastore call, not the stream.
internal/graph/lookupsubjects.go
Outdated
} | ||
|
||
subjectIDsToPublish = append(subjectIDsToPublish, subjectID) | ||
subjectIDsToPublishWithoutWildcard = append(subjectIDsToPublishWithoutWildcard, subjectID) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
As far as I can tell this slice is only used to identify the latest subjectID so it can be used in the cursor. Why keeping track of all subjectIDs when we just could keep track of the last one?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I was being lazy? Changed
pkg/genutil/slicez/chunking_test.go
Outdated
for _, chunksize := range []uint16{1, 2, 3, 5, 10, 50} { | ||
chunksize := chunksize | ||
t.Run(fmt.Sprintf("test-%d-%d", datasize, chunksize), func(t *testing.T) { | ||
data := []int{} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
data := []int{} | |
var data []int |
pkg/genutil/slicez/chunking_test.go
Outdated
data = append(data, i) | ||
} | ||
|
||
found := []int{} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
found := []int{} | |
var found []int |
testutil.GenResourceTuples("document", "somedoc", "viewer", "user", "...", 580), | ||
testutil.GenResourceTuplesWithOffset("document", "somedoc", "viewer", "user", "...", 1200, 100), | ||
testutil.GenResourceTuplesWithOffset("group", "somegroup", "direct_member", "user", "...", 500, 500), | ||
testutil.GenResourceTuplesWithOffset("group", "parentgroup", "direct_member", "user", "...", 700, 500), |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
nit: this would actually be a childgroup
of somegroup
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Fixed
|
||
dispatchCount, err := responsemeta.GetIntResponseTrailerMetadata(trailer, responsemeta.DispatchedOperationsCount) | ||
req.NoError(err) | ||
req.GreaterOrEqual(dispatchCount, 0) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
there had been some regressions recently around dispatches and I wonder if we could use a new test-case that checks the number of dispatches over a cursored LR call
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
You mean over the LS call? We do now have the test for LR calls
@@ -56,6 +56,23 @@ func (s *SubjectByTypeSet) ForEachType(handler func(rr *core.RelationReference, | |||
} | |||
} | |||
|
|||
func (s *SubjectByTypeSet) ForEachTypeUntil(handler func(rr *core.RelationReference, subjects SubjectSet) (bool, error)) error { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
add a unit test
// Loop until all subjects have been found or we've hit max iterations. | ||
var currentCursor *v1.Cursor | ||
resolvedSubjects := map[string]*v1.LookupSubjectsResponse{} | ||
for i := 0; i < 100; i++ { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
should this be a for loop without the condition? as it stands it's confusing as we have to iterate indefinitely until all elements are streamed
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't want it to hang indefinitely on failure so I put a "large" limit on it
internal/datasets/basesubjectset.go
Outdated
@@ -264,6 +264,25 @@ func (bss BaseSubjectSet[T]) AsSlice() []T { | |||
return values | |||
} | |||
|
|||
// SubjectCount returns the number of subjects in the set. | |||
func (bss BaseSubjectSet[T]) SubjectCount() int { | |||
if _, ok := bss.wildcard.get(); ok { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
reuse HasWildcard
?
@@ -94,5 +94,7 @@ func lookupSubjectsRequestToKey(req *v1.DispatchLookupSubjectsRequest, option di | |||
hashableRelationReference{req.ResourceRelation}, | |||
hashableRelationReference{req.SubjectRelation}, | |||
hashableIds(req.ResourceIds), | |||
hashableCursor{req.OptionalCursor}, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
shouldn't we also consider the wildcard option as part of the dispatch cache key, or else 2 requests with different arguments would collide?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
(edited) No, because the wildcard option is not passed to the dispatcher. It is only used to filter at the API level
) | ||
} | ||
|
||
// yieldMatchingResources yields the current resource IDs iff the resource matches the target |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
// yieldMatchingResources yields the current resource IDs iff the resource matches the target | |
// yieldMatchingResources yields the current resource IDs if the resource matches the target |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
iff
is correct: means "if and only if"
internal/graph/lookupsubjects.go
Outdated
for _, subjectID := range subjectIds { | ||
// subjectsForConcreteIds returns a FoundSubjects map for the given *concrete* subject IDs, filtered by the cursor (if applicable). | ||
func subjectsForConcreteIds(subjectIDs []string, ci cursorInformation) (map[string]*v1.FoundSubjects, error) { | ||
foundSubjects := make(map[string]*v1.FoundSubjects, len(subjectIDs)) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
move this after afterSubjectID == tuple.PublicWildcard
. I also wonder if allocating upfront is to aggressive given subjectID
may be discarded if below the current head section of the cursor.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It could be over allocating, but only if the cursor happens to hit the results set, which is unlikely in aggregate
subjects map[string]*v1.FoundSubjects, | ||
metadata *v1.ResponseMeta, | ||
) (*v1.DispatchLookupSubjectsResponse, func(), error) { | ||
if subjects == nil { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
if nil is an invalid state, then I assume zero value (or an empty map) is also an invalid state, so you may want to check with len
instead
if subjects == nil { | |
if len(subjects) == 0 { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Empty is valid (if unusual), but nil is not
reader datastore.Reader, | ||
) error { | ||
// Check if the direct subject can be found on this relation and, if so, query for then. | ||
directAllowed, err := validatedTS.IsAllowedDirectRelation(req.ResourceRelation.Relation, req.SubjectRelation.Namespace, req.SubjectRelation.Relation) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
this is not expensive but it starts to add up for large datasets. Seems wasteful to run this again when it was just run in lookupDirectSubjects
- we could pass it as argument if we really want to check directAllowed == namespace.DirectRelationNotValid
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I have a long-standing TODO to cache type system operations like these; I'd rather fix it at that layer
afterSubjectID, _ := ci.headSectionValue() | ||
|
||
// If the cursor specifies the wildcard, then skip all further non-wildcard results. | ||
if afterSubjectID == tuple.PublicWildcard { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've seen this in a few places and it worries me a bit the potential risk we would skip subjects because we prematurely published the wildcard. Any way we could detect this?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The only "good" way is via exhaustive unit and consistency testing, unfortunately
internal/graph/lookupsubjects.go
Outdated
} | ||
|
||
// filterSubjectsMap filters the subjects found in the subjects map to only those allowed, returning an updated map. | ||
func filterSubjectsMap(subjects map[string]*v1.FoundSubjects, allowedSubjectIds ...string) map[string]*v1.FoundSubjects { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I see no use of the variadic allowedSubjectIds
so please pass as a slice. NewSet
should also support a slice - a lot of calls in the codebase that end up doing ...
just to pass it to it.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Changed here but not NewSet. We have some places where the variadic is helpful. If you like, I can add another NewSetFromSlice
and change the call sites?
return nil, done, nil | ||
} | ||
|
||
// Determine the subject ID for the cursor. If there are any concrete subject IDs, then the last |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I'm very confused by this, and this ties with an earlier question around various bits in the code base ignoring any further subjectIDs if the wildcard is found, and my concern around guarantees we are not skipping subjects if a wildcard is published earlier than it should.
The code here indicates that the wildcard is used to denote all concrete subjects have been consumed. But at the same time we also find sometimes the wildcard as a subject to publish because it's found. How do we disambiguate those two situations?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We always sort the returned results so the wildcard is last when retrieving from the datastore. This occurs on line 1193 after we union together the wildcard with the concrete results found. Thus, since we sort at every level (and wildcard always sorts last), we're guaranteed that it should always appear at the end. If you like I can add additional point unit tests for the individual reducers to validate this, but we can't really test everything directly
internal/graph/lookupsubjects.go
Outdated
|
||
updatedCI, err := ci.withOutgoingSection(cursorSubjectID) | ||
if err != nil { | ||
return nil, func() {}, err |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
return nil, func() {}, err | |
return nil, done, err |
} | ||
} | ||
|
||
func TestCreateFilteredAndLimitedResponse(t *testing.T) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think we should also assert expectations around the returned cursor, by checking where the cursor is at, given it's critical to denote a branch has been exhausted and there are no more concretes to return.
This example is me attempting to break it. It works as intended because the cursor will be at a
. The next time we iterate we will get b
, and the returned cursor head should be at *
{
"blah",
"",
map[string]*v1.FoundSubjects{
"foo": fsubs("a"),
"bar": fsubs("*", "b"),
},
1,
map[string]*v1.FoundSubjects{
"foo": fsubs("a"),
"bar": fsubs("*"),
},
},
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can you clarify what, exactly, you want me to test? Is this a new unit test or an additional to this one?
}, | ||
}, | ||
{ | ||
"indirect with combined caveat direct", |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
isn't this test exactly the same as the previous one?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
No. One is on viewer
, one is on view
|
||
// CursorForFoundSubjectID returns an updated version of the afterResponseCursor (which must have been created | ||
// by this dispatcher), but with the specified subjectID as the starting point. | ||
func CursorForFoundSubjectID(subjectID string, afterResponseCursor *v1.Cursor) (*v1.Cursor, error) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I couldn't find a test that exercised this
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The API tests do so
c386a05
to
137e08e
Compare
Updated |
137e08e
to
1dec055
Compare
Rebased |
3202a4b
to
b00913b
Compare
b00913b
to
83a96b2
Compare
This change supports a limit (called the "concrete limit") on LookupSubjects and will filter concrete subjects based on the returned cursor. This change does *not* filter intermediate lookups, which will be done in a followup PR.
83a96b2
to
39f033f
Compare
Rebased |
This change supports a limit (called the "concrete limit") on LookupSubjects and will filter concrete subjects based on the returned cursor.
This change does not filter intermediate lookups, which will be done in a followup PR.