Performance

This document explains the time complexity of Ory Keto. Main memory complexity will be analyzed and added at a later point. We only examine the evaluation engines (check- and expand-API) as all other parts are mainly determined by dependencies like your database of choice, or the de-/encoding of messages. Examples given omit the namespace for clarity.

Check engine

In essence, the check-engine assumes that the relation tuples and their indirections assemble an acyclic directed graph, known as the graph of relations.

Consider the following example:

file#access@(file#owner)       // probably defined via subjectset rewrites
file#access@user1              // access was granted directly
file#owner@user2               // file owner record; indirectly gets access

This is interpreted as the following graph:

A check request of the form object#relation@user will be evaluated by searching the graph starting at object going through relation trying to reach user. The request is allowed if there is such a path.

The algorithm used in Ory Keto for this graph traversal is breadth-first search. In the worst case it has a time complexity of O(n+e) where n is the number of nodes reachable from the node object#relation through e edges. Space complexity is O(n). Rearranged, both space and time complexity are O(b^d) where b is the maximum breadth and d the maximum depth in the graph, seen from the search root. [1]

This means that the complexity heavily depends on the structure of the graph. If it contains deeply nested indirections, it will require many recursive calls to resolve those indirections. Analogously, if there are widely nested indirections, Ory Keto has to possibly resolve all of them. The goal is to design the ACL tuples in a way such that there are only few indirections to resolve. Learn more in our best practices around ACL design.

Because of this we decided that generic benchmarks won't yield any meaningful result. We will therefore add a comparison with other similar projects later on.

Expand engine

Similar to how the check-engine traverses the graph of relationtuples, the expand-engine builds the tree of all set operations it encounters. It resolves all indirections starting at the requested subjectset up to the specified depth. Because it also uses breadth-first search, time and space complexity linearly depend on the nodes reachable from the requested subjectset. The same performance considerations apply here, while it's important to note that requesting a low depth will further limit the complexity of the operation. The returned tree can also exceed reasonable size limits quickly if the relationtuples are deeply and/or widely nested.

References

[1] Breadth-first search on Wikipedia