Google Zanzibar: global authorization

01 · CONTEXT

A question on almost every request

In many online interactions, a service needs to confirm that the user has permission to perform an operation on a digital object. Zanzibar is Google's system for storing permissions and performing these checks, offering a data model and a configuration language common to hundreds of services.

According to the paper, authorization brings its own challenges of data consistency and scale. Among the stated goals are correctness, because decisions must respect users' intent, and low latency, because the check is usually on the critical path of the interaction. High availability is also required: without explicit authorization, client services would be forced to deny users access.

ACL data does not lend itself to geographic partitioning, since the check on any object can come from anywhere in the world; for that reason Zanzibar replicates all ACL data across dozens of data centers and distributes the load across thousands of servers.

02 · DATA MODEL

Relation tuples instead of per-object lists

In Zanzibar, ACLs are relations represented as relation tuples, and groups are simply ACLs with membership semantics. According to the paper, building the model around tuples, instead of per-object ACLs, unifies the concepts of ACL and group and allows efficient reads and incremental updates.

One example from the paper is the tuple doc:readme#viewer@group:eng#member, which says that the members of group:eng are viewers of doc:readme. The user side can be a set of users (a userset), which makes it possible to represent nested groups.

Storing one tuple per object for every derived relation would be wasteful and would make bulk changes harder. That is why the client defines, in the relation configurations, userset rewrite rules that describe object-independent relations. In the paper's example configuration, every owner is an editor and every editor is a viewer, and the viewers of the parent folder are also viewers of the document; a flexible language primitive allows policies such as looking up the document's parent folder and inheriting its viewers.

03 · CONSISTENCY

The new enemy problem and the zookie

The check respects the order in which ACL changes were committed to storage. According to the paper, avoiding the new enemy problem requires understanding and respecting the causal order between ACL updates and content updates, and that is why the system needs two properties: external consistency and snapshot reads with bounded staleness.

In the paper's first example, Alice removes Bob from a folder's ACL and then asks Charlie to move new documents into that folder. Bob should not see the new documents, but he could see them if the check ignored the order between the two ACL changes.

1. When a content change is about to be saved, the client makes a content-change check to obtain a zookie for that version.

2. This check carries no zookie and is evaluated on the most recent snapshot; if the change is authorized, the response includes the zookie.

3. The client stores the zookie together with the content change, in a single atomic write to the client's storage.

4. On later checks for that version, the client sends the stored zookie.

5. Zanzibar evaluates the check on a snapshot at least as recent as the zookie, so that ACL changes that precede the content, in causal order, are observed.

Always evaluating on the most recent snapshot would require global synchronization, with high-latency round trips and limited availability. The zookie protocol avoids this: with the clients' cooperation, most checks can be evaluated on data that is already replicated.

The ACLs live in Spanner, which assigns each write a microsecond-resolution timestamp whose order reflects the causal order of the writes, and each check is evaluated at a single snapshot timestamp across several reads. Without a zookie, the server uses a default staleness, chosen so that evaluation is as recent as possible without hurting latency; this is only a performance optimization and does not violate consistency, because the zookies provided are always honored.

The 5 voting replicas sit in the eastern and central US, in 3 different metropolitan areas to isolate failures, but within 25 milliseconds of each other so that Paxos transactions commit quickly.

04 · ARCHITECTURE

Serving checks with low latency

The aclservers are the main type of server and are organized into clusters. The request arrives at any server in the cluster, which distributes the work to the others as needed.

1. The request arrives at any aclserver in the cluster, which distributes the work to the other servers as needed.

2. The tuples and their metadata live in Spanner databases, which the aclservers read and write when responding.

3. The watchservers follow the changelog and serve clients a near-real-time stream of namespace changes.

4. Leopard optimizes large, deeply nested sets and receives the full stream of tuple changes through the Watch API.

5. A periodic pipeline runs offline functions over all the data in Spanner, and Leopard reads periodic snapshots of the ACL data.

A check is converted into a boolean expression, and the leaf nodes are evaluated concurrently. Following pointers from group to group works well for most ACLs, but it can be expensive when groups are deep or wide.

For those cases, Leopard treats group membership as a reachability problem in a graph, where nodes are groups and users and edges are direct memberships. Since the offline index alone does not offer a fresh, consistent snapshot, Leopard merges into the offline index, at query time, the updates with a timestamp less than or equal to the query's.

To favor consistency, Zanzibar avoids denormalizing storage and uses normalized data. The price is that hot spots on common ACLs, such as popular groups, can overload the databases. The authors consider handling hot spots the most critical frontier in the pursuit of low latency and high availability.

1. The server that received the request forwards it to another server using a forwarding key that, in most namespaces, comes from the object ID.

2. Results are cached on both the caller and the callee of internal RPCs, which forms cache trees.

3. Among requests with the same cache key, only one starts processing; the others wait for the cache to be filled.

4. The evaluation timestamp is rounded up, at coarse granularity and respecting zookies, so that many checks share the same cached results.

5. For calls to Spanner, one request is sent first and the redundant request is deferred until the initial one proves slow.

O distributed cache uses consistent hashing across servers. Hedging applies to calls to Spanner and Leopard, but not between Zanzibar servers, because it would duplicate precisely the most expensive checks and worsen latency.

05 · IN PRACTICE

Production numbers and lessons

According to the paper, Zanzibar manages more than 1,500 namespaces defined by hundreds of applications, with more than 2 trillion tuples occupying close to 100 terabytes. It serves more than 10 million queries per second, spread across more than 10,000 servers organized into a few dozen clusters.

In the seven-day sample, the Safe check had latencies of about 3, 11, 20 and 93 ms at the 50th, 95th, 99th and 99.9th percentiles. Availability stayed above 99.999% over three years of operation and, per quarter, the paper reports less than 2 minutes of global unavailability.

Reads are two orders of magnitude more frequent than writes. Writes are the slowest because they always require distributed coordination among Spanner servers.

The paper compares Zanzibar to TAO: TAO offers global eventual consistency with asynchronous replication, while Zanzibar provides external consistency and snapshot reads with bounded staleness, so it respects the causal order between ACL updates and content updates.