Terms are in alphabetical order. Code names from the paper’s configuration language (_this, computed_userset, tuple_to_userset) are sorted without their underscores. Examples use the running example: Anne, Beto and Chen; doc:readme in folder:A; group:eng.
A–C
- ACL
- Access control list: the set of users allowed to do something to an object. In Zanzibar an ACL is not stored as one list but as many relation tuples. More: Access control models, §1, §2.1.
- aclserver
- The main Zanzibar server type. Answers Check, Read, Expand and Write, and fans work out to other aclservers in its cluster. More: Architecture, §3.
- at-least-as-fresh
- The rule for a zookie: Zanzibar may evaluate at any snapshot no older than the zookie’s timestamp, not only at that exact one. This freedom is what lets it serve most requests from local replicas. More: Consistency, §2.2.
- bounded staleness
- A snapshot read may be older than “now”, but not older than a bound. In Zanzibar the bound is the zookie the client sends. Spanner offers this directly: the client gives an upper bound on staleness and Spanner picks the timestamp (Spanner paper, §4.1). More: Consistency, §2.2.
- cache stampede
- Many concurrent requests for the same uncached result all go to storage at once before the cache fills. Zanzibar prevents it with a lock table. The paper cites the Wikipedia article for the term (reference [3]). More: Architecture, §3.2.5.
- changelog
- A Spanner database holding the history of tuple updates, written in the same transaction as each tuple write. Watch reads from it. More: Architecture, §3.1.2.
- Check
- The API call that asks whether a user is in a userset ⟨object#relation⟩, for example “is Chen a viewer of
doc:readme?”. Evaluated at a snapshot no earlier than the given zookie. More: Relation tuples, §2.4.4, §3.2.3. computed_userset- A rewrite-rule leaf that takes another relation’s userset on the same object, for example “every editor is a viewer”. More: Relation tuples, §2.3.1.
- consistent hashing
- A way to assign keys to servers so that adding or removing a server moves only a small fraction of the keys. Zanzibar uses it to spread cache entries over the servers of a cluster. Introduced by Karger et al. (STOC 1997) for web caches. More: Architecture, §3.2.5.
- content-change check
- A Check sent when a user is about to save new content. It carries no zookie, is evaluated at the latest snapshot, and returns a zookie the client stores with the new content version. More: Consistency, §2.2, §2.4.4.
D–H
- denormalization
- Storing a precomputed copy of derived data, such as flattened group-to-group membership, instead of computing it from the original rows. Zanzibar avoids it in storage and uses it only in Leopard. More: Leopard, §3.2.4, §3.2.5.
- exclusion
- A rewrite-rule operator: the users in one userset but not in another. More: Relation tuples, §2.3.1.
- Expand
- The API call that returns the effective userset of ⟨object#relation⟩ as a tree, following rewrite rules. Leaves are user IDs or usersets; inner nodes are union, intersection or exclusion. More: Relation tuples, §2.4.5.
- external consistency
- If update x happens before update y, x gets a smaller timestamp than y, even when the two are coordinated outside the system. Zanzibar gets this from Spanner. The paper cites Gifford’s 1981 Stanford thesis for the term (reference [18]); Spanner states it as: if T1 commits before T2 starts, T1’s commit timestamp is smaller than T2’s. More: Consistency, §2.2.
- fan-out
- One request turning into many sub-requests, for example an aclserver sending parts of a Check to other servers in its cluster. More: Architecture, §3, §3.2.5.
- heartbeat zookie
- A zookie in each Watch response marking how far the stream has reached, so the client can resume from there. More: §2.4.3.
- hedging
- Sending the same request to a second server once the first is known to be slow, using whichever reply arrives first and cancelling the other. Zanzibar hedges calls to Spanner and Leopard, not calls between its own servers. The technique is described in Dean and Barroso, “The Tail at Scale” (CACM, 2013). More: Architecture, §3.2.7.
- hot spot
- A key, object or group that receives far more traffic than others and can overload the server that stores it, for example a popular group shared by many ACLs. More: Architecture, §3.2.5.
I–N
- intersection
- A rewrite-rule operator: the users in every one of several usersets. More: Relation tuples, §2.3.1.
- Leopard
- An indexing system for deeply nested or very wide groups. It flattens group membership into sets of integers so a membership check becomes a set intersection, and keeps up to date through Watch. More: Leopard, §3.2.4.
- lock table
- A per-server table of in-flight reads and checks. Of the requests that share a cache key, only one runs; the rest wait for its result. More: Architecture, §3.2.5.
- lock tuple
- An ordinary relation tuple that clients touch on every write to an object, so a write can be made conditional on nobody else having written since the read. More: §2.4.2.
- namespace
- A client-defined kind of object, such as
docorfolder. The part before the colon indoc:readme. Each namespace’s tuples live in their own database. More: Relation tuples, §2.1, §2.3, §3.1.1. - namespace config
- The configuration of one namespace: its relations, each with an optional userset rewrite rule, plus storage parameters such as sharding. More: Relation tuples, §2.3, §3.1.3.
- new enemy problem
- Showing content to someone who was removed from its ACL, because the check ignored the order of two ACL changes or applied an ACL older than the content. More: Consistency, §2.2.
O–R
- object
- The thing being protected, written ⟨namespace⟩:⟨object_id⟩, such as
doc:readme. More: Relation tuples, §2.1. - Paxos
- A consensus protocol that lets a group of replicas agree on each write even if some of them fail. The paper places the five voting replicas of Zanzibar’s storage within 25 ms of each other so that Paxos transactions commit quickly. See Lamport, “Paxos Made Simple” (2001). More: Architecture, §3.1.4.
- pointer chasing
- Answering a Check by following usersets one hop at a time: from the readme’s viewers to
group:eng#member, then to that group’s members, and so on. Slow when groups are deep or wide. More: Relation tuples, Leopard, §3.2.3, §3.2.4. - Read
- The API call that returns stored tuples matching one or more tuplesets. It does not apply rewrite rules. More: Relation tuples, §2.4.1.
- Recent request
- See Safe / Recent requests. More: Consistency, §4.1.
- relation
- A named relationship between an object and a user, or between two objects (as
parentlinks a document to its folder), such asowner,viewer,memberorparent. Defined in the namespace config. More: Relation tuples, §2.1, §2.3. - relation tuple
- One stored fact, ⟨object⟩#⟨relation⟩@⟨user⟩, such as
doc:readme#owner@user:anne. The only kind of permission data Zanzibar stores. More: Relation tuples, §2.1. - replica
- A copy of the data in one location. Zanzibar’s data is replicated to dozens of locations so most reads can be served nearby. More: Architecture, §3.1.4.
S
- Safe / Recent requests
- The paper’s split of requests by zookie age. Safe requests carry zookies more than 10 seconds old and can usually be served in-region; Recent requests carry newer zookies and often need a cross-region round trip. More: Consistency, §4.1.
- A slice of a database or index stored and served separately. A tuple’s shard ID usually comes from its object ID, and for very large groups from the object ID and the user. More: Architecture, §3.1.1, §3.2.4.
- snapshot read
- A read that sees the database exactly as of one timestamp: every write at or before it and none after. Zanzibar evaluates each Check at a single snapshot. Spanner defines it as “a read in the past that executes without locking” (Spanner paper, §4.1). More: Consistency, §2.2.
- Spanner
- Google’s globally distributed database. Zanzibar stores tuples, namespace configs and the changelog in it and relies on its timestamps for consistency. Described in Corbett et al., OSDI 2012. More: Consistency, Architecture, §2.2, §3.
T
- tail latency
- The latency of the slowest requests, such as the 99th or 99.9th percentile. It matters because one page of search results may need tens to hundreds of checks. See Dean and Barroso, “The Tail at Scale” (CACM, 2013). More: Architecture, §1, §3.2.7, §4.2, §4.5.
_this- The rewrite-rule leaf that returns the users in stored tuples for this object and relation, including usersets those tuples point at. The default when a relation has no rule. More: Relation tuples, §2.3.1.
- timestamp quantization
- Rounding evaluation timestamps up to a coarse step, such as one or ten seconds, so that many requests share a timestamp and therefore cache entries. It does not weaken consistency: a zookie only sets a lower bound, and a Spanner snapshot read at a future timestamp waits until TrueTime has passed it (§3.2.5). More: Architecture, Consistency, §2.2, §3.2.5.
- TrueTime
- Spanner’s clock mechanism, which gives each write a microsecond-resolution timestamp that reflects causal order. It is what makes Zanzibar’s timestamps meaningful.
TT.now()returns an interval guaranteed to contain the true time; see the Spanner paper (OSDI 2012), §3. More: Consistency, §2.2, §3.2.5. - tupleset
- A selector for stored tuples: a single tuple key, or all tuples for an object ID or userset, optionally limited to one relation. Used by Read and by
tuple_to_userset. More: Relation tuples, §2.4.1. tuple_to_userset- A rewrite-rule leaf that reads some tuples of the object and computes a userset from each, for example “look up the readme’s parent folder and take its viewers”. More: Relation tuples, §2.3.1.
U–W
- union
- A rewrite-rule operator: the users in any of several usersets. All three branches of
viewerin the paper’s Figure 1 are joined by union. More: Relation tuples, §2.3.1. - user
- The third part of a tuple: either a single user ID or a userset. More: Relation tuples, §2.1.
- userset
- An ⟨object⟩#⟨relation⟩ pair standing for every user with that relation to that object, such as
group:eng#member. Lets a tuple grant access to a group, and groups contain groups. More: Relation tuples, §2.1. - userset rewrite rule
- Part of a relation config: a function from an object ID to a userset expression tree, built from
_this,computed_usersetandtuple_to_usersetcombined by union, intersection and exclusion. More: Relation tuples, §2.3.1. - userset tree
- The result of Expand: leaves are user IDs or usersets, inner nodes are set operators. More: Relation tuples, §2.4.5.
- Watch
- The API call that streams tuple changes for one or more namespaces in timestamp order, starting from a zookie. Used to keep secondary indexes, such as Leopard, up to date. More: Architecture, §2.4.3.
- watchserver
- The server type that answers Watch by tailing the changelog. More: Architecture, §3.
- Write
- The API call that adds or removes tuples. Clients that rewrite all tuples of an object use a read, then a write conditional on the lock tuple being unchanged. More: Architecture (what one write touches), §2.4.2.
Z
- zookie
- An opaque token encoding a timestamp. A client gets one from a content-change check (Read and Write responses also carry zookies), stores it with the content, and sends it with later checks so they are evaluated at a snapshot at least that fresh. More: Consistency, §2.2, §2.4.
Sources
- J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
- D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
- J. Dean and L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
- L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
- D. K. Gifford, “Information Storage in a Decentralized Computer System”, PhD thesis, Stanford University, 1981 (paper reference [18]; no online copy checked)
- “Cache stampede”, Wikipedia, en.wikipedia.org (the source the paper cites)
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang