we looked at zanzibar yesterday, where a user A has access to an object B if there's a path between them in the access graph. let's walk through how they make this graph reachability problem efficient.
Comments
Log in with your Bluesky account to leave a comment
checking path reachability is difficult: users may have access to millions+ of objects, and doing a naive depth-first search in the object graph on every access would be really expensive.
zanzibar addresses this with their "leopard indexing" system. the core idea here is *to make assumptions about the structure of the access control graph*, and not have to solve the general graph reachability problem.
intuitively, each user is a member of a group, which may be nested in another group, which may then own a project. projects may have many documents, but the set of all projects visible to a user should be relatively small.
with this assumption, their indexing system precomputes the set of highlighted nodes reachable from each user. then, for each object, it also precomputes the set of all highlighted nodes that are one step away.
Comments