Papers
Zanzibar: Google's Consistent, Global Authorization System
Ruoming Pang, Ramon Caceres, Mike Burrows, Zhifeng Chen, Pratik Dave, Nathan Germer, Alexander Golynski, Kevin Graney, Nina Kang, Lea Kissner, Jeffrey L. Korn, Abhishek Parmar, Christina D. Richards, Mengzhi Wang · USENIX Annual Technical Conference (ATC) 2019, 2019
The problem: a single, global, consistent authorization for hundreds of services
Inside Google, products such as Calendar, Drive, Maps, Photos, and YouTube need to continuously answer the same question: can this user access this object? If each service implemented its own ACLs (access control lists), permission semantics would be inconsistent across products, hurting the user experience, and it would be hard to make applications interoperate, for example when an object from one app is embedded in another. The paper describes Zanzibar as the global system Google built to store and evaluate ACLs centrally, offering a uniform data model and a configuration language able to express very different policies, used by hundreds of services. Besides being flexible, the system needs to be correct: authorization decisions must respect the causal order of user actions, so they stay consistent while ACLs and object contents change. And it needs to be fast and available, since the permission check is on the critical path of almost every request. According to the abstract, the system handles trillions of ACLs and millions of authorization requests per second, and over more than three years in production it kept 95th-percentile latency under 10 ms and availability above 99.999%.
Data model: relation tuples, usersets, and rewrite rules
Zanzibar stores ACLs as relation tuples, in the format object#relation@user, for example stating that a given user has the reader relation on a document. Groups are not a special entity: they are just objects whose relations represent membership. The most important point is the concept of a userset: instead of pointing to an individual user, the tuple can point to the set of people who hold a certain relation to another object. This is how nested groups are represented, such as granting access to all members of a group. Each namespace (object type) has a configuration that defines its relations and userset rewrite rules. These rules make it possible to derive a relation from others, without storing redundant tuples. A relation can be defined directly by the stored tuples, inherited from another relation on the same object (for example, whoever is an editor also counts as a reader), or obtained by following a parent object (for example, inheriting the readers of the folder that contains the document). Thus, complex policies live in configuration, and storage holds only simple facts. The main API includes calls such as Read, Write, Check, Expand, and Watch.
Consistency: zookies and the new enemy problem
The paper highlights a subtle problem, called the new enemy problem. Two examples: a user is removed from a folder's ACL, but, because of a stale ACL read, still sees a sensitive document added to the folder right afterward; or an old ACL is applied to new content of a document. To avoid this, Zanzibar must respect the causal order between ACL changes and content changes, which it does with external consistency: ACLs are stored in Spanner, whose commit timestamps (via TrueTime) reflect the causal order of writes. The mechanism that exposes this to clients is the zookie, an opaque token that encodes a globally meaningful timestamp. When the client authorizes a content change, it receives a zookie and stores it along with that version of the content. On later checks, it sends the zookie, and Zanzibar evaluates the check on a snapshot at least as fresh as it. Without a zookie, the system picks a recent snapshot that favors low latency. The trade-off is clear: the client only pays the freshness cost where it needs a causal guarantee, and the rest uses slightly stale data, which is easier to cache.
Architecture and performance: aclservers, Leopard, cache and hedging
The ACLs live in Spanner, and every write also goes to a changelog that feeds the Watch API. The aclservers receive Check, Read, Expand, and Write calls and distribute the work across the cluster; watchservers follow the changelog to stream tuple changes; and offline pipelines generate snapshots and remove old tuple versions. For very large, deeply nested groups, where walking the hierarchy would be slow, there is a separate indexing system, Leopard, which represents group membership as sets to make reachability queries fast: indexes are built offline and an incremental layer applies later updates. Against hot spots, the servers form a distributed cache with consistent hashing, a per-server lock table prevents several requests from computing the same result at the same time (cache stampede), and evaluation timestamps are rounded to coarse intervals so that more requests share cache entries. To reduce tail latency, calls to Spanner and Leopard use hedging: if the response takes longer than a threshold, a backup request is sent and the first response wins. Hedging is not done between Zanzibar's own servers, because the cost of a check varies widely and duplicating the expensive ones would worsen latency.
Legacy: relationship-based authorization outside Google
The paper became the reference for what is called relationship-based access control (ReBAC), in which the decision depends on the relationships between entities and not just on fixed roles as in RBAC. One design lesson is the separation into layers: a minimal data model (tuples), a declarative configuration that derives permissions from them, and a central service that must treat causal consistency, caching, and tail latency as requirements from the start. This design inspired open-source and commercial authorization systems that adopt the model of tuples and namespaces, usually described as inspired by Zanzibar. For those who design systems, the paper teaches two points. First, permission is not just a table of roles: in products with sharing, inheritance through folders, and nested groups, it is a graph of relationships. Second, the ordering between permission changes and content changes matters, and Zanzibar's solution, handing the client a consistency token (the zookie) instead of forcing always-fresh reads, is an example of how to offer a strong guarantee without paying the maximum cost on every request.
See the ideas at work
Practice the designs that use this paper in the System Design school.