guide:leopard@en

Guides

Leopard, the group index

How Zanzibar answers membership in deeply nested groups with one set intersection, and what that costs on every write.

Facts checked on Paper sections §3.2.4, §4.4

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?

A nested group chainuser:beto is a member of group:eng, group:eng's members are members of group:product, group:product's members are members of group:all, and group:all's members are viewers of doc:readme. Checking Beto's access starts at doc:readme and reads one object per step: doc:readme, group:all, group:product and group:eng, four reads in sequence.doc:readmegroup:allgroup:productgroup:enguser:beto1. read doc:readme: viewers are group:all2. read group:all: includes group:product3. read group:product: includes group:eng4. read group:eng: Beto is a memberviewermembermembermember
Each step names the object for the next one, so the four reads cannot start together. Each object can also live on a different server (see the architecture page).

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?

GROUP2GROUP and MEMBER2GROUP for the exampleGROUP2GROUP(group:all) is group:all, group:product and group:eng. GROUP2GROUP(group:product) is group:product and group:eng. GROUP2GROUP(group:eng) is group:eng. MEMBER2GROUP(user:beto) is group:eng. MEMBER2GROUP(user:anne) is empty.GROUP2GROUP(group:all)GROUP2GROUP(group:product)GROUP2GROUP(group:eng)MEMBER2GROUP(user:beto)MEMBER2GROUP(user:anne){ group:all, group:product, group:eng }{ group:product, group:eng }{ group:eng }{ group:eng }{ }
GROUP2GROUP is flattened: group:all lists group:eng even though eng sits two levels down. MEMBER2GROUP is not: it lists only direct memberships. Each group is drawn in its own GROUP2GROUP set; the paper does not say so, see the note below.

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?

Membership as an intersectionMEMBER2GROUP(user:beto), which is group:eng, intersected with GROUP2GROUP(group:all), which is group:all, group:product and group:eng, gives group:eng: not empty, so Beto is a member of group:all. MEMBER2GROUP(user:anne), which is empty, intersected with the same set gives the empty set, so Anne is not a member.MEMBER2GROUP(user:beto){ group:eng }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { group:eng }not empty: memberMEMBER2GROUP(user:anne){ }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { }empty: not a member
Two lookups and one intersection, whatever the depth of the nesting. Beto is in; Anne is not.

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)

Intersecting a short sorted list with a long oneList A holds 17, 42 and 90. List B holds 3, 8, 17, 21, 30, 42, 55, 61, 77, 84, 93 and 99. For each element of A, one seek in B finds the first element that is not smaller: 17 finds 17, 42 finds 42, 90 lands on 93, which is not a match. The intersection is 17 and 42, found in three seeks.AB1742903817213042556177849399seek 1: hitseek 2: hitseek 3: miss
Three elements in A, three seeks in B. The twelve elements of B are never scanned one by one. The skip list's upper levels, which make each seek fast, are not drawn.

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?

Leopard's three partsAn offline index builder reads a snapshot of Zanzibar's tuples and configs and produces index shards, which are replicated and swapped into the Leopard serving system. In parallel, an incremental indexer reads Zanzibar's Watch stream and writes timestamped updates into the serving system's incremental layer. aclservers query the serving system, which merges the incremental layer over the offline index at the query timestamp.tuple + configsnapshotoffline index builder(periodic)Leopard servingoffline index+ incremental layerWatch APIincrementalindexeraclserversnew shardstuple changes(T, s, e, t, d)query
The offline path is complete but stale; the incremental path is fresh but only covers changes since the last snapshot. Serving merges the two.
  • 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?

One tuple write fans out into many index updatesAdding the tuple group:product#member@group:eng#member makes group:eng, group:infra and group:web new descendants of both group:product and group:all. The incremental indexer turns the single tuple into six GROUP2GROUP additions: product gains eng, infra and web, and all gains eng, infra and web.group:product#member@group:eng#memberincrementalindexer+ G2G(product, eng)+ G2G(product, infra)+ G2G(product, web)+ G2G(all, eng)+ G2G(all, infra)+ G2G(all, web)1 write
1 Zanzibar tuple, 6 Leopard tuples (the group: prefix is left out): every ancestor of product (product, all) times every descendant of eng (eng, infra, web). MEMBER2GROUP does not 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