Introduction Link to heading

Google’s Zanzibar is a groundbreaking global authorization system designed to handle billions of objects and users. As described in Google’s research paper, Zanzibar is capable of processing 10 million client queries per second with a latency of less than 10 milliseconds while maintaining 99.999% availability. This article explores the core principles and data modeling techniques that make Zanzibar a leader in access control solutions. We’ll delve into its unique approach to consistency, flexibility, and scalability, providing insights into how Google manages permissions at an unprecedented scale in this first part of our exploration of Zanzibar.

Why Zanzibar: The Need for Scalable Authorization Systems Link to heading

Creating a permissions system within an application can be complex. When a user creates permissions within an application to manage their content, this becomes even more challenging since these permissions become a core part of each request. As the system scales, so does the complexity of such a system, which creates security holes within the application, compromising the user content in your application. ¹
For example, web-based photo storage services typically allow photo owners to share some photos with friends while keeping other photos private. Such a service must check whether a photo has been shared with a user before allowing that user to view the photo. Robust authorization checks are central to preserving online privacy. ²
Zanzibar creates a fine grained, highly scalable authorization service using the concepts of Relationship Based Access Control (ReBAC).

Principles of Zanzibar Link to heading

The Zanzibar authorization system works on the following principles ²

Correctness Link to heading

• It must ensure consistency of access control decisions to respect user intentions.
• Zanzibar supports global consistency of access control decisions through two interrelated features.
• First, it respects the order in which ACL changes are committed to the underlying data store.
• Second, it can ensure that authorization checks are based on ACL data no older than a client-specified change. Thus, for example, a client can remove a user from a group and be assured that subsequent membership checks reflect that removal.
• Zanzibar provides these ordering properties by storing ACLs in a globally distributed database system with external consistency guarantees².

Flexibility Link to heading

It must support a rich set of access control policies as consumer and enterprise applications require.

Groups can contain other groups, which illustrates one of the challenges facing Zanzibar.

Group memberships are an essential class of ACL, where
the object is a group, and the relation is semantically equivalent to a member. Groups can contain other groups, which illustrates one of the challenges facing Zanzibar: evaluating whether a user belongs to a group can entail following a long chain of nested group memberships².

Low Latency Link to heading

It must respond quickly because authorization checks are often in the critical path of user interactions. Low tail latency is significant for serving search results, often requiring tens to hundreds of checks.

Zanzibar employs various techniques to achieve low latency and high availability in this globally distributed environment. Its consistency protocol allows most requests to be served with locally replicated data without requiring cross-region round trips. Zanzibar stores its data in normalized forms for consistency. It handles hot spots on normalized data by caching final and intermediate results and deduplicating simultaneous requests. It also applies techniques such as hedging requests and optimizing computations on deeply nested sets with limited denormalization².

High Availability Link to heading

It must reliably respond to requests because client services would be forced to deny users access without explicit authorizations.

Large Scale Link to heading

It needs to protect billions of objects shared by billions of users. It must be deployed around the globe to be near its clients and their end users.
Zanzibar responds to over 95% of authorization checks within 10 milliseconds and has maintained more than 99.999% availability for the last 3 years.

Zanzibar Data modeling Link to heading

Zanzibar uses a simple but powerful data-modeling language that allows clients to define arbitrary relations between users and objects, such as owner, editor, commenter, and viewer. It includes set-algebraic operators such as intersection and union for specifying potentially complex access control policies regarding user-object relations. For example, an application can specify that users granted editing rights on a document are also allowed to comment on the document, but not all commenters are given editing rights.

Understanding Zanzibar’s Relational Tuple Model Link to heading

Zanzibar uses relational tuples, the semantic representation of its ACL policies.
It can represented as follows:

$$\{tuple\} := \{object\} ‘\#’ \{relation\} ‘@’ \{user\}$$

$$ \{object\} := \{namespace\} ‘:’ \{object_id\} $$

$$ \{user\} := \{user\_id\} | \{userset\}$$

$$ \{userset\} := \{object\}’\#’ \{relation\} $$

Lets a take a look at some parsed examples:

This is a very simple tuple which defines relation based of userId 10 having owner permission to object doc:readme

In this example we define the relationship on the userId 11 as a member of group:eng.

This is a complex example defining a chained relation. Notice how two usersets are linked to one another with @.

Consistency Model Link to heading

To maintain the consistency of changes to ACLs, Zanzibar must respect the order in which users modify the ACLs and object contents to avoid unexpected sharing of the data. The task here is to prevent the “new enemy” problem that can arise when the order in the permissions are read is not aligned with the order of changes in the permission. [Read more about the new enemy problem in the Authzed Blog]

Preventing the “new enemy” problem requires Zanzibar to understand and respect the causal ordering between ACL or content updates, including updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar. Hence, Zanzibar must provide two fundamental consistency properties: external consistency, and snapshot reads with bounded staleness.

To maintain consistency across multiple transactions, Zanzibar adds a timestamp to causally related changes, i.e., changes that happen one after the other. With causally meaningful timestamps, any two changes x, y which occur one after the other such that their respective timestamps are T_x < T_y , then any reads at or after T_y will include the changes done at T_x

Any reads happening in the Zanzibar system are done from a read snapshot, and to avoid applying old ACLs to new contents, the ACL check evaluation snapshot must not be staler than the causal timestamp assigned to the content update, which means any content update done at timestamp T_c , snapshot read one at any time ≥ T_c will include the changes done in T_c .

To avoid evaluating checks for new contents using stale ACLs, one could try to continually evaluate at the latest snapshot such that the check result reflects all ACL writes up to the check call. However, such evaluation would require global data synchronization with high latency round trips and limited availability ².

The Zanzibar setup in Google uses Spanner to store ACLs to achieve this. Google Cloud Spanner is a globally available database with a TrueTime mechanism. Spanner assigns each version change with a microsecond resolvable timestamp to reflect the causal ordering of the changes. ACL check is done at a single snapshot timestamp across multiple database reads so that all writes with timestamp increment the check snapshot, and only those writes are visible to the ACL check.

Zanzibar follows the following protocol to allow checks to be evaluated on already replicated data:

1. A Zanzibar client requests an opaque consistency token called a zookie for each content version when a content modification is about to be saved. Zanzibar encodes the current global timestamp and does an atomic write on the client machine to store the zookie. It should be observed that a content change check is only done when the content is changed. It needs to only happen once in the update transaction.
2. The client sends the zookie in subsequent ACL check requests to ensure the check snapshot is as latest as the content version’s timestamp.

Namespace Configuration Link to heading

Namespace configurations define relations of the ACL objects in Zanzibar. According to the Zanzibar’s research paper ²

A namespace configuration specifies its relations as well as its storage parameters. Each relation has a name, a client-defined string such as viewer or editor, and a relation config. Storage parameters include sharding settings and an encoding for object IDs that helps Zanzibar optimize the storage of integer, string, and other object ID formats.

This means a namespace defines how ACL object relations are defined and stored in Zanzibar.

For example, if a system has roles “Viewer,” “Editor,” and “Owner,.” If a user is defined as an owner, adding a relation tuple for all three roles is redundant and wasteful. Namespaces can rewrite the ACL policies based on these roles to improve this. Here is an example taken from the paper

name: "doc"
relation { name: "owner" }
relation {
 name: "editor"
 userset_rewrite {
  union {
   child { _this {} }
   child { computed_userset { relation: "owner" } }
}}}
relation {
 name: "viewer"
 userset_rewrite {
  union {
   child { _this {} }
   child { computed_userset { relation: "editor" } }
   child { tuple_to_userset {
     tupleset { relation: "parent" }
     computed_userset {
       object: $TUPLE_USERSET_OBJECT  # parent folder
relation: "viewer" }}}
}}}

• _this returns all the policies of the current role.
• computed_userset computes the policies based on the relation defined within it.
• tuple_to_userset computes a tupleset from the input object, fetches relation tuples matching the tupleset (a set of tuples with a given object_id which can be used to look up ACLs for a given object), and computes a userset from every fetched relation tuple.

API Link to heading

Zanzibar provides APIs for clients to read, write, modify, watch, check, and expand operations.
All these API methods use zookie in their request. A zookie is an opaque cookie that contains a globally meaningful timestamp and/or a client content version, and/or a read snapshot. A zookie is designed to be opaque so that clients cannot misuse a cookie by sending arbitrary timestamps.
Let’s take a closer look at each of these APIs

Read Link to heading

For a read API, the client sends one or more tuplesets and an optional zookie containing a timestamp and a snapshot version.
With the zookie clients can request a read snapshot no earlier than the previous write operation. If the request does not contain the zookie, Zanzibar will choose a reasonably recent snapshot, which generally offers a lower latency response than if a zookie was provided.

It should be noted that read requests only depend on the content of the relation tuples and do not reflect userset rewrite rules. For example, even if the viewer userset always includes the owner userset, reading tuples with the viewer relation will not return tuples with the owner relation. Clients that need to understand the effective userset can use the Expand API.

Write Link to heading

Zanzibar clients can use the write API to modify a relation tuple to add or remove an ACL. Clients can also modify all tuples related to an object using a read-modify-write process that uses a read RPC followed by a write RPC. This process works as follows:

1. Read all relation tuples of an object, including a per-object “lock” tuple.
2. Generate the tuples to write or delete. Send the writes, along with a touch on the lock tuple, to Zanzibar, with the condition that the writes will be committed only if the lock tuple has not been modified since the read. A touch is being used on the lock tuple to make sure the access time on the lock tuple is updated.
3. If the write condition is not met, go back to step 1.

Watch Link to heading

A watch request specifies one or more namespaces and zookie representing the time to start watching. A watch response contains all the tuple modification events in ascending timestamp order from the requested start timestamp to a timestamp encoded in a heartbeat zookie included in the watch response. The client can use the heartbeat zookie to repeatedly call on the watch API to resume watching where the previous watch response was left off.

Check Link to heading

Like reads, a check is evaluated at a consistent snapshot no earlier than the given zookie.
To authorize application content modifications, our clients send a special check request, a content-change check. A content-change check request does not carry a zookie and is evaluated at the latest snapshot. If a content change is authorized, the check response includes a zookie for clients to store along with object contents and use for subsequent checks of the content version. The zookie encodes the evaluation snapshot and captures any possible causality from ACL changes to content changes because the zookie’s timestamp will be greater than that of the ACL updates that protect the new content.

Expand Link to heading

Unlike the Read API, Expand follows indirect references expressed through userset rewrite rules. The result is represented by a userset tree whose leaf nodes are user IDs or usersets pointing to other object relation pairs, and intermediate nodes represent union, intersection, or exclusion operators. Expand is crucial for our clients to reason about the complete set of users and groups with access to their objects, allowing them to build efficient search indices for access-controlled content.

Continue reading about Zanzibar Architecture and Implementation in the next Part Zanzibar - Google’s Consistent, Global Authorization System - Part 2

References Link to heading