guide:glossary@en

Guides

Glossary

Every term a reader meets in the Zanzibar paper, in plain words, with a pointer to the guide page and the paper section that explain it.

Facts checked on

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 doc or folder. The part before the colon in doc: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 parent links a document to its folder), such as owner, viewer, member or parent. 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.
shard
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 viewer in 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_userset and tuple_to_userset combined 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