 ICACT20260076 Slide.01
[Big Slide]
[YouTube] |
Chrome  Click!! |
 |
Hi All we are here to present our research on Efficient Indexing for Google Zanzibar Based Authorization Systems Using Graph Dynamic-Transitive Closures. |
| ICACT20260076 Slide.02
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Authorization is the process of deciding what actions a principal (user/service) is allowed to perform on a resource.
It evaluates permissions based on relationships, roles, or policies defined in the system.
In systems like Zanzibar, it answers graph-style questions like: “Can this user perform this action on this object?” |
| ICACT20260076 Slide.03
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
This slide shows how access control has evolved as systems became more complex.
We started with RBAC — Role-Based Access Control.
Here, access is based on who you are in the organization. If you’re assigned the role ‘Editor’, you can view and edit documents. It’s simple and works well in structured environments, but it becomes rigid. Everyone with the same role gets the same permissions, even when context differs.
Next came ABAC — Attribute-Based Access Control.
Instead of just roles, decisions use attributes — things like location, department, or device. For example, a user can edit a document only if their location is the USA. This adds flexibility, but policies become harder to reason about because you’re evaluating many conditions at runtime.
Modern large-scale systems moved to ReBAC — Relationship-Based Access Control.
Here, permissions come from relationships in a graph. Instead of saying ‘you are an editor’, we say ‘you are an editor of Folder A’. Because Folder A contains documents, you automatically get access to all documents inside. This matches how real systems work — users, teams, resources, and hierarchies are all connected.
So the shift is from roles → attributes → relationships, with ReBAC being the model that powers systems like Google Zanzibar because it scales naturally with complex, interconnected data. |
| ICACT20260076 Slide.04
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
As Google’s products grew — Drive, YouTube, Maps, Cloud, Photos, Calendar — each system originally handled permissions in its own way. That led to duplication, inconsistency, and difficulty enforcing security at scale.
Zanzibar was created as a single source of truth for authorization. Instead of every product answering permission questions differently, they all ask one central system questions like ‘Can Alice view video X?’ or ‘Can Bob create a VM in this cloud project?’
Technically, Zanzibar is built on Spanner, Google’s globally distributed database. That gives it strong consistency, global replication, and the ability to serve permission checks reliably across data centers.
The key idea is that authorization becomes an infrastructure service, just like storage or networking. Products don’t implement their own access control logic — they delegate it to Zanzibar.
And the last point is the fun one: you’ve probably used Zanzibar recently without realizing it — anytime you shared a Google Doc, watched a private YouTube video, or accessed a cloud resource, a Zanzibar permission check likely happened behind the scenes |
| ICACT20260076 Slide.05
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
This slide shows how authorization data is actually represented in Zanzibar-style systems.
Instead of storing permissions in tables or role lists, everything is stored as tuples of the form — (object, relation, user). These tuples form a directed graph, often a DAG.
For example, we might store relationships like:
Teacher is editor of marks card
Teacher is reader of homework
Student is editor of homework
Student is reader of marks card
Each of these is just an edge in the graph. Nodes are users and resources, and edges are relationships like reader or editor.
When a permission check happens — like ‘Can the teacher edit the marks card?’ — the system doesn’t look up a role. It performs a reachability check in the graph following these relationships.
This graph-based representation is what allows Zanzibar to model complex hierarchies, inheritance, and nested permissions in a scalable way.” |
| ICACT20260076 Slide.06
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
example of an auth check |
| ICACT20260076 Slide.07
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
SpiceDB is the leading open-source implementation of Google Zanzibar. It stores authorization relationships as a graph and answers permission checks using graph traversal. It brings Zanzibar’s model to real-world systems outside Googl |
| ICACT20260076 Slide.08
[Big Slide]
|
Chrome Click!! |
 |
SpiceDB answers checks using Breadth-First Search on the graph. This works, but for deeply nested relationships, BFS becomes slow because cost grows with graph depth — O(depth).
we found this is the code of spiceDB as well |
| ICACT20260076 Slide.09
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Use Transitive Closure for Indexing
Instead of traversing at runtime, we precompute reachability using transitive closures. Then permission checks become simple set lookups — O(1) instead of graph traversal.
|
| ICACT20260076 Slide.10
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Support Vertices
We compute transitive closures only for a small subset of nodes called support vertices. These act as representatives that help infer reachability for many other nodes |
| ICACT20260076 Slide.11
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Computing transitive closure for all nodes is too costly in large graphs. The storage and update overhead would explode. So we need a smarter approximation. We select few SVs at random and perdiodicallt re-pick , even if we had bad SVs in the beginning they eventually converge |
| ICACT20260076 Slide.12
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
few vertices only , as shown in the image |
| ICACT20260076 Slide.13
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
For each support vertex we maintain:
R⁺ → nodes it can reach
R⁻ → nodes that can reach it
and a set of 3 set axioms we got from Katherine et al
Using these sets, many reachability queries can be answered instantly without traversal.
|
| ICACT20260076 Slide.14
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
We give Dynaclo , our indexing layer used in the hot path for CheckPermission and WriteRelationship. It precomputes reachability information and only falls back to BFS when needed. Most checks are answered in constant time |
| ICACT20260076 Slide.15
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The graph is dynamic — relationships are constantly added or removed. The index must stay correct while handling real-time updates safely and efficiently.
|
| ICACT20260076 Slide.16
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Writes go into a blue–green write queue. One queue collects new writes while the other is used to recompute the index, ensuring updates are applied safely without blocking queries.
|
| ICACT20260076 Slide.17
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Concurrency Control
Locks are carefully used to prevent race conditions between writes and index recomputation. This ensures data integrity and thread safety under high concurrency |
| ICACT20260076 Slide.18
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
How golang helped us here |
| ICACT20260076 Slide.19
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Dataset & Workloads
Experiments used a synthetic ReBAC graph with 20M nodes and 155M edges. Workloads simulated real systems: 100% reads and a realistic 99% read / 1% write mix |
| ICACT20260076 Slide.20
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Dynaclo achieved major improvements:
Up to 13.8× lower latency, 15× higher throughput, and much lower CPU usage. Even in mixed workloads, it significantly reduced tail latency |
