Zanzibar stores permissions as relation tuples: one fact per row, read as “this user has this relation to this object”. Everything else on this page, rewrite rules, Check and Expand, is computed from those rows.
The running example: Anne, Beto and Chen (user:anne, user:beto, user:chen); the document doc:readme in folder:A; the group group:eng. Anne owns the readme, Beto is in eng, eng members view the readme, and Chen views folder A.
The grammar
The paper (§2.1) gives the text notation as four rules:
⟨tuple⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩ ‘@’ ⟨user⟩
⟨object⟩ ::= ⟨namespace⟩ ‘:’ ⟨object_id⟩
⟨user⟩ ::= ⟨user_id⟩ | ⟨userset⟩
⟨userset⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩
A tuple has three parts. The object is a namespace plus an ID, such as doc:readme. The relation is a name the namespace defines, such as owner or viewer. The user is either a single user ID or a userset. In the paper a user ID is an integer; this site writes user:anne so the example stays readable.
What does a single tuple say?
It says one thing: Anne has the relation owner to doc:readme. The paper lists the primary keys that identify a tuple: namespace, object ID, relation and user.
Usersets: a tuple that points at a group
The fourth grammar rule is the interesting one. A userset is itself an object plus a relation: group:eng#member means “every user who has the relation member to group:eng”. When a tuple’s user is a userset, one row grants something to a whole set of users, and that set is defined by other rows.
How does one tuple give every member of eng access to the readme?
Notice that no row mentions Beto and the readme together. Beto is a viewer because he is in the set the second tuple points at. Add a member to eng and that member can view the readme with no change to the readme’s ACL.
The same trick nests. A group’s member can be another userset, for example group:eng#member@group:sre#member (a hypothetical sub-team, not part of the running example), and membership then runs through as many levels as the tuples describe. The paper puts it in one line: “a ⟨userset⟩ allows ACLs to refer to groups and thus supports representing nested group membership” (§2.1). It also explains the payoff: modelling with tuples rather than per-object ACLs “allows us to unify the concepts of ACLs and groups” (§2.1). A group is just an object whose member relation is an ACL.
Table 1 as one graph
The paper’s Table 1 lists four example tuples. With users 10 and 11 renamed to Anne and Beto, and one tuple added for Chen, they are:
| Tuple | Reads as |
|---|---|
doc:readme#owner@user:anne |
Anne is an owner of the readme |
group:eng#member@user:beto |
Beto is a member of eng |
doc:readme#viewer@group:eng#member |
Members of eng are viewers of the readme |
doc:readme#parent@folder:A#... |
The readme is in folder A |
folder:A#viewer@user:chen |
Chen is a viewer of folder A (not in Table 1) |
The #... on the fourth row is the paper’s notation for “a relation that does not affect the semantics of the tuple” (Table 1 caption): the tuple points at the folder itself, not at a set of its users.
What do all five rows look like together?
Notice that the parent edge says nothing about access. As the paper puts it, some relations “only define abstract relations between objects. These abstract relations may indirectly affect access control given userset rewrite rules specified in namespace configs” (§2.1). Whether Chen can see the readme depends on such a rule, which is the next section.
Namespace configuration
Before a client stores tuples, it configures a namespace such as doc or folder (§2.3). The config lists the namespace’s relations, each with a name and a relation config, plus storage parameters: sharding settings and an encoding for object IDs.
Tuples alone do not define the effective ACL. Many clients want every editor to also be a viewer. Storing an extra viewer tuple for each editor of each object would be, in the paper’s words, “wasteful and make it hard to make modifications across all objects” (§2.3.1). Instead a relation config can carry a userset rewrite rule: a function that takes an object ID and returns a userset expression tree.
This is the paper’s Figure 1, verbatim:
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"
} } }
} } }
Figure 1: Simple namespace configuration with concentric relations on documents. All owners are editors, and all editors are viewers. Further, viewers of the parent folder are also viewers of the document.
The leaves of a rewrite tree come in three kinds (§2.3.1):
| Leaf | What it returns | In Figure 1 |
|---|---|---|
_this |
The users in stored tuples for this object and relation, including usersets those tuples point at. The default when a relation has no rule. | The viewer tuples stored on doc:readme |
computed_userset |
Another relation’s userset on the same object. | editor on the same doc; for editor, owner |
tuple_to_userset |
Reads a tupleset from the object, then computes a userset from each tuple it finds. | Read the doc’s parent tuples, then take viewer on each parent folder |
Leaves combine with union, intersection and exclusion (§2.3.1). Figure 1 uses only union. An intersection would require a user to be in every child, for example “editors who are also in eng”; an exclusion would remove a set, for example “viewers except a blocked list”. Those two examples are illustrations, not from the paper.
What tree does the viewer rule build for one document?
Notice that owner sits two levels down: owners are editors, editors are viewers. That is what the caption of Figure 1 means by “concentric relations”. The right branch is the only one that leaves the document: it follows a stored parent edge to another object.
Check as a graph search
A Check request names a userset ⟨object#relation⟩ and a user, and asks whether the user is in it (§2.4.4). Without rewrite rules, the paper writes the evaluation as a recursive formula (§3.2.3): the user is in ⟨object#relation⟩ if a tuple ⟨object#relation@U⟩ exists, or if a tuple ⟨object#relation@U′⟩ exists where U′ is a userset and the user is in U′. The paper calls this recursion “pointer chasing”. Rewrite rules “are also translated to boolean expressions as part of check evaluation” (§3.2.3), so the expression tree above becomes an OR of three branches.
The question for the next four figures: can Chen view doc:readme? Each frame uses the same graph and highlights the edges the current branch reads. The folder namespace config is not in the paper; these frames assume folder#viewer has no rewrite rule, so it is just _this.
Step 1: _this
Does a stored viewer tuple on the readme include Chen?
The only stored viewer is a userset, so Check recurses into group:eng#member. Its only member is Beto. This branch says no.
Step 2: computed_userset editor, then owner
Is Chen an editor, or an owner?
The rewrite moves from viewer to editor to owner on the same object. No stored tuple is needed for the first two hops: they come from the config. The one owner is Anne, so this branch also says no.
Step 3: tuple_to_userset, find the parent
Which folder is the readme in?
The parent tuple is the “abstract relation” from Table 1. On its own it grants nothing; the rewrite rule turns it into a new question about another object.
Step 4: folder:A#viewer
Is Chen a viewer of folder A?
The path user:chen → folder:A → doc:readme answers the question. Notice that the edges point the same way in every frame but the search ran from the readme outwards: Check starts at ⟨object#relation⟩ and looks for the user.
Pointer chasing like this “works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide” (§3.2.3). For those namespaces Zanzibar uses the Leopard index, described on the Leopard page.
Read and Expand
Two API calls look at the same data from different heights.
Read (§2.4.1) returns stored tuples only. A request names one or more tuplesets: a single tuple key, or all tuples for an object ID or a userset in a namespace, optionally narrowed to one relation. The paper is explicit that “Read results only depend on contents of relation tuples and do not reflect userset rewrite rules” (§2.4.1). Reading doc:readme with relation viewer in the running example returns one row:
doc:readme#viewer@group:eng#member
Anne is missing even though every owner is a viewer, and Chen is missing even though he can view the readme.
Expand (§2.4.5) “follows indirect references expressed through userset rewrite rules”. It returns a userset tree: leaves are user IDs or usersets that point to other ⟨object#relation⟩ pairs, and inner nodes are union, intersection or exclusion.
What does Expand return for doc:readme#viewer?
Notice the two dashed leaves. Per §2.4.5, a leaf can be a userset that points elsewhere, so a client that wants every individual (Beto, Chen) expands those leaves in turn. The paper does not say how deep a single Expand call recurses; this figure stops at the usersets the doc’s own rules reach. The paper names the use case: Expand lets clients “reason about the complete set of users and groups that have access to their objects, which allows them to build efficient search indices for access-controlled content” (§2.4.5).
Sources
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang