Zanzibar normally answers a Check by following tuples from the object to the user, one lookup at a time. For most data that is fast. For groups nested many levels deep, it is not, and Zanzibar hands those checks to Leopard, an index that precomputes the nesting.
Why nesting is slow
Extend the running example. group:eng is now inside group:product, which is inside group:all, and the readme is shared with all of group:all. How many lookups does it take to learn that Beto can view the readme?
The tuples behind the figure are:
doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto
Notice that step n cannot begin until step n − 1 has returned. The paper calls this pointer chasing and says it “can be expensive when indirect ACLs or groups are deep or wide” (§3.2.3). Wide hurts too: if group:all held a hundred child groups, step 2 would branch a hundred ways. So: “Recursive pointer chasing during check evaluation has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups. For selected namespaces that exhibit such structure, Zanzibar handles checks using Leopard, a specialized index that supports efficient set computation.” (§3.2.4)
Two kinds of set
Leopard stores “a collection of named sets using (T, s, e) tuples, where T is an enum representing the set type and s and e are 64-bit integers representing the set ID and the element ID” (§3.2.4). Group membership uses two set types:
GROUP2GROUP(s): the groups that are “directly or indirectly” sub-groups of the ancestor group s.MEMBER2GROUP(s): the groups in which user s is a “direct” member.
What do the sets hold for the example?
Notice the asymmetry. All of the nesting is folded into GROUP2GROUP, so a user’s side only has to record where the user was added directly. In the paper’s words, “Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard” (§3.2.4).
Membership is a non-empty intersection
“To evaluate whether user U is a member of group G, we check whether” (§3.2.4)
(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅
That is: is any group the user was added to directly also somewhere under G? What does that give for Beto and Anne against group:all?
The four sequential reads of the first figure became two set lookups and one intersection. To finish the original question, Zanzibar still reads the readme’s tuple that names group:all#member; the depth below that is what Leopard removes. The paper does not spell out how a Check is split between ordinary evaluation and Leopard queries, so this split is a reading of §3.2.4, not a quote.
Intersection on sorted lists
How cheap is the intersection? “Index tuples are stored as ordered lists of integers in a structure such as a skip list, thus allowing for efficient union and intersections among sets. For example, evaluating the intersection between two sets, A and B, requires only O(min(|A|, |B|)) skip-list seeks.” (§3.2.4)
Notice that the work follows the shorter list. When a user is a direct member of only a few groups, MEMBER2GROUP(U) is short and the test stays cheap even when GROUP2GROUP(G) is huge. The paper gives no set sizes; that case is an assumption. The index “is sharded by element IDs”, and shards “are usually served entirely from memory” (§3.2.4).
Three parts
“The Leopard system consists of three discrete parts: a serving system capable of consistent and low-latency operations across sets; an offline, periodic index building system; and an online real-time layer capable of continuously updating the serving system as tuple changes occur.” (§3.2.4) How do they connect?
- Offline index builder. It “generates index shards from a snapshot of Zanzibar relation tuples and configs, and replicates the shards globally. It respects userset rewrite rules and recursively expands edges in an ACL graph to form Leopard index tuples.” Servers “swap old shards with new ones when they become available”.
- Incremental layer. The offline index alone “cannot do so at a fresh and consistent snapshot”, so servers keep “an incremental layer that indexes all updates since the offline snapshot”, each update a
(T, s, e, t, d)tuple “where t is the timestamp of the update and d is a deletion marker”. “Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.” - Feed. “the Leopard incremental indexer calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications and transforms the updates into a temporally ordered stream of Leopard tuple additions, updates, and deletions.”
All quotes in this list are from §3.2.4. Because updates carry timestamps and are merged up to the query timestamp, a Leopard answer can reflect the same snapshot as the rest of the Check; the paper’s stated purpose for the incremental layer is “To support consistent ACL evaluation”.
The cost: one write, many index updates
Flattening is paid for at write time. Go back to before eng was added to product, and suppose group:eng has two sub-groups of its own, group:infra and group:web. Now someone adds eng to product. How many index tuples change?
The count is the number of ancestors on one side times the number of descendants on the other, so it grows with both depth and width. To compute it, “Generating updates for the GROUP2GROUP tuples requires the incremental indexer to maintain group-to-group membership for denormalizing the effects of a relation tuple update to potentially multiple index updates.” At Google’s scale: “In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.” (§3.2.4)
A deletion is subtler than the figure: an index tuple can only be removed if no other path still connects the two groups. The paper does not describe how the indexer decides that.
This is also why Leopard is the exception. Elsewhere “Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4)” (§3.2.5), and Leopard is used only for selected namespaces “that exhibit such structure” (§3.2.4).
In production
From §4.4, over 7 days: “The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile”, and “Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile.” The incremental layer “writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.” Calls to Leopard are hedged like calls to Spanner (§3.2.7).
Sources
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3.2.3, §3.2.4, §3.2.5, §3.2.7, §4.4: https://www.usenix.org/conference/atc19/presentation/pang