A high-level "view" of the problem
In our previous blog post we discussed a scenario that is common when building modern multi-user or multi-tenant applications: How to provide each user with their own "view" of the resources found within the system in a performant and safe manner. Such views are often found on landing pages, application entry points, and other kinds of "start" pages, where a user desires to see their most recently accessed or available resources. Providing the correct resources to display for a particular user from the set of all resources is known as ACL Filtering, where correct is defined as ensuring that the current user has permission to view (or edit, etc), with those that fail being excluded from view.
On the surface this problem seems fairly straightforward: simply check every resource to be displayed against the current user’s set of permissions. Yet despite the apparent simplicity, it has been our experience that solving this problem in a performant and secure manner is one of the larger challenges facing application developers today.
Why is performing ACL or permission based filtering so very hard?
A massive undertaking
In a word: scale.
In order to properly and securely filter the resources a user is capable of viewing, the permissions check must be performed for each (relevant) resource found within the application. For some applications, the number of resources to check may be small: if your application is showing the last 10 opened documents for a user, then checking these 10 documents may be very quick. For other queries, however, the numbers of resources to check could be in the millions (or more): imagine trying to show a paginated list of all documents which the current user can edit; even if the page size is merely 25 documents, there is no guarantee how many documents will need to be checked before that limit is met.
In applications making use of database-defined permissions models, this problem is traditionally handled by joining the resource table being displayed with the permissions tables necessary for filtering.
At first glance, this seems a reasonable solution: Simply add as many necessary JOIN statements to the select in order to properly filter the results, and the database will handle the rest!
Unfortunately, in practice, each additional JOIN statement often adds significant overhead to the query, and results in massive increases in query time as each of the joined tables grows in size.
In our own experience, we have had databases where the majority of CPU time and resources were spent on such permissions filtering, forcing hand written brittle optimization and manual pagination (or limited subqueries) as workarounds.
In applications making use of Policy Engines, the situation is even worse: all potential resources first have to be fetched from the database and then filtered by the policy engine.
Because Policy Engines are almost always executed alongside an application, this takes the inefficiencies of the database JOIN and multiplies them with networking overhead.
Both these examples demonstrate the underlying problem: trying to filter all the resources down to those visible or accessible to the user will quickly hit scaling limits once more than perhaps a few hundred or thousands of resources exist (let alone millions or billions).
What if there was another way?
Checking in with Authzed
In another previous blog post, we described how Authzed computes permissions answers (if you have not read that blog post, we recommend doing so now and then returning here).
As shown, permissions in Authzed are computed by walking the graph formed by combining object definitions and the relationships between data, searching for a path from the Object (say, a specific document) to the Subject (for example, a user) via an Action (e.g. reader):
Jill is the owner of somedocument, so she is also a reader
This structure of answering permissions allows for computing complex permissions hierarchies, including inferred or implicit permissions, as well as nesting such as groups. It also allows for use of graph-based optimizations, such as walking subgraphs in parallel, to allow for faster computation where possible.
We thought to ourselves if we could take advantage of the graph nature to compute which Subjects could perform an Action on an Object, could we also use it to do the reverse: find out which Objects could have an Action performed on them by a specific Subject?
Reversing a permissions check
The answer, as it turned out, is yes! Because all Checks in Authzed are answered by walking a graph, we realized we could perform a similar operation (but in "reverse").
As an example, let’s take our sample Check from above:
Is
Jill[Subject] areaderof [Action] documentsomedocument[Object]?
As we saw above, this answer to this Check is computed by walking the graph from somedocument, through reader, through owner and finally reaching Jill, proving that she has access to read the document.
Now let’s imagine we wanted to find all documents in the system in which Jill is the reader. We can compute this information by reversing the question we’re asking:
Jill [Subject] a reader of [Action] a document [Object]?
Jill [Subject] a reader [Action]?
To compute the answer to this question, we can therefore walk the graph "backward", starting at the Subject (Jill) and walking until we find the correct Action, returning any Objects found there:
At first glance, this seemed a simple enough solution: Start at the Subject (Jill) and walk backward from her across any path that can potentially reach the Action on the type of Object for which we are querying.
However, we quickly hit a road bump: in addition to the standard union operation for computing permissions, Authzed also supports intersection and exclusion. Intersection and exclusion, however, cannot be computed without all child paths themselves having been computed, meaning that we’d have to perform the equivalent of a "reduce" operation at any intersection or union. Fortunately, this led to a natural solution: map, then reduce.
The great filter
We therefore landed on our current solution for ACL-aware indexing: the Lookup API.
The Lookup API, when given a specific Subject, and a class of Object and Action, performs a map reduce operation over the Authzed permissions graph, starting at the Object+Action, towards reaching the Subject wherever it can be found.
Taking our previous example of all the documents which Jill is a reader:
Each path is mapped over the objects found, and then reduced as we go along, until only those objects accessible to the Subject via the specified Action remain.
Thus, by taking advantage of the graph nature of Authzed’s permission system, we can now elegantly and performantly compute an ACL-aware filter of objects!
Trying the API
The beta Lookup API is available today for testing and use.
Have any questions, comments or just want to chat? Visit the Discord.
Additional Reading
If you’re interested in learning more about Authorization and Google Zanzibar, we recommend reading the following posts:
