When people explain Google's Zanzibar, they almost always lead with the same idea: permissions as a graph of relationships instead of a role list, so "can Anne edit this doc" becomes "is there a path from Anne to this doc through some chain of group memberships and shares." That's a good idea, and it's also the easy 20% of the 2019 paper, the part you can sketch on a whiteboard in thirty seconds. The other 80%, the part that took years of actual production hardening, is about keeping that graph check both fast and correct while the graph itself is being written to, constantly, by other people's requests. That part almost never makes it into the summary, and it's the more interesting half.
Here's the specific failure that forces the engineering. Someone gets removed from a group that has access to a sensitive folder. A second later, someone else drops a new file into that folder. If the permission check for the removed person happens to hit a cache that's a few seconds stale, they pass a check for content that didn't even exist when their access was revoked. The paper calls this the "new enemy problem," and the name fits. A stale check can do worse than let someone keep access they already had: it can hand them access to brand-new content that didn't even exist yet when they lost permission, purely because the system answered from information that was already wrong.
Most systems just accept that risk under the label "eventual consistency" and move on. Zanzibar doesn't get to, because at Google's scale a permission check that's merely "usually correct" amounts to a security hole with a clock attached to it. The fix is a token, called a Zookie, attached to every write against the permission graph. A write returns one; a later check can pass that token in and demand an answer no staler than the data as of that exact write, and the system is built to actually honor that, not just attempt it. The token encodes a timestamp from Spanner's globally synchronized clock, which is what turns "no staler than this" from a best effort into something provable.
What that buys is almost boring to state plainly: a check carrying a Zookie from a specific removal event is guaranteed to see that removal, every single time, not most of the time. The interesting engineering is less the token itself and more the fact that the whole checking architecture is built around making that guarantee without ever falling back to recomputing everything from scratch on every request, the other honest way to get correctness, and the one that doesn't survive contact with Google-scale traffic.
There's a second, related problem that sits underneath the first one: checking membership in a group with hundreds of millions of members without walking the entire thing on every request. Zanzibar's answer is a precomputed index called Leopard, kept current by consuming a stream of every change to the permission graph and updating incrementally instead of rebuilding from a cold start. Same philosophy as the Zookie, really: refuse the tradeoff between correctness and speed, and build the infrastructure that earns both instead.
I went back through the paper recently in more depth than the usual "it's a graph, neat" treatment gives it, mostly chasing down exactly how the Zookie threads through the check algorithm and what Leopard is actually indexing. I wrote up the longer version, including the check algorithm itself, here: What is Zanzibar?. If you're deciding between OpenFGA and SpiceDB, the two open-source systems that implement this model, this comparison is worth reading before picking one, because the thing that actually differs between them has nothing to do with the relationship-graph data model, both get that part right, and everything to do with how closely each one tracks that same consistency guarantee versus falling back to a plain cache toggle.
The part of this that generalizes past Zanzibar specifically: when a system gets summarized by its data model, it's worth asking what the data model was actually in service of. The graph wasn't the hard part here. Answering fast, at enormous scale, without ever being allowed to shrug and say "probably correct," was.
Top comments (0)