Google has an authorization system called Zanzibar that decides who can access what across products like Drive and YouTube. One of the most important services there...
One of the key pieces of Zanzibar is an index called Leopard Index, and that is what makes access checks faster. The idea behind it is the core; let's dig deeper...
In any Google product, authorization comes in two fragments. It has notions of users and groups. Users can be part of groups, and groups can even contain other groups.
Say Alice is in payments-team, which is within backend, which is inside engg. To check whether Alice is in engg, you have to walk up that chain one hop at a time. With deep nesting, that means many lookups across many machines on every access check.
Leopard's indexing system avoids the walk by doing the work in advance. It keeps two lookup tables.
1. member -> group - maps a user to the groups they belong to directly. Alice maps to payments-team.
2. group -> group - maps a group to every group nested under it, at any depth. engg maps to backend and payments-team, plus itself.
To check whether Alice is in engg, look up both sets and see if they share anything. Here, they share payments-team, so the answer is yes. That is two lookups and one overlap check, no matter how deep the nesting goes.
You would have guessed the trade-off that they are making here :) It is the classic.
Now, to stay fresh, the index combines a periodic full rebuild with a stream of recent changes, so new memberships show up quickly.
The cost is on the write side. Placing one group inside another means updating many precomputed entries. That is a good trade for authorization, since checks happen far more often than membership changes.
If you have a slow graph walk on a hot read path, precomputing the answers may be worth considering. A mental model worth remembering.
Hope this helps.