Zanzibar is a set of servers in front of a set of Spanner databases. This page names the parts, then follows one Check request through them, then looks at how the data is laid out on disk. The numbers at the end are the ones the paper reports for production in 2018.
The parts
Which boxes are there, and which way does data flow between them? The paper answers with its Figure 2. The version below keeps its colours (clients blue, servers yellow, Spanner databases green) and drops the detail.
Notice that the clients talk to two kinds of server. aclservers answer the four request types; watchservers only stream changes. In the paper’s words, aclservers “are organized in clusters and respond to Check, Read, Expand, and Write requests”, while watchservers “tail the changelog and serve a stream of namespace changes to clients in near real time” (§3). Leopard is an index for large and deeply nested groups; it has its own page.
The offline pipeline produces “dumps of the relation tuples in each namespace at a known snapshot timestamp” and garbage-collects “tuple versions older than a threshold configured per namespace” (§3).
One Check, step by step
The request to follow: is Beto a viewer of the readme? In the running example the readme’s viewers include the members of group:eng, and Beto is one of them, so the answer is yes. Zanzibar has to find that out by reading two objects, doc:readme and group:eng.
It lands on any server, which fans out
Which server does the work? Any of them can take the request, and the work is then spread by object.
Server A did not need to own either object. The paper describes exactly this shape: “Requests arrive at any server in a cluster and that server fans out the work to other servers in the cluster as necessary. Those servers may in turn contact other servers to compute intermediate results. The initial server gathers the final result and returns it to the client.” (§3)
Consistent hashing picks the peer
How did A know to ask B about the readme? The servers of a cluster form one distributed cache: “Cache entries are distributed across Zanzibar servers with consistent hashing” (§3.2.5). The scheme is from Karger et al. (STOC ’97), which the paper cites as [20]. For most namespaces the forwarding key is computed from the object ID (§3.2.5).
Notice that viewer and owner on the readme meet on the same server. That is the point of keying on the object: “processing a check on ⟨object#relation⟩ often involves indirect ACL checks on other relations of the same object and reading relation tuples of the object. These checks and reads can be processed by the same server since they share the same forwarding key with the parent check request.” (§3.2.5) Karger et al. design consistent hashing so that when a cache is added or removed, only the minimum fraction of objects needed to keep the load balanced has to move, which is why it suits a cache.
For keys that are hot, the paper adds that it uses Slicer “to help distribute hot keys to multiple servers” (§3.2.5).
Both ends of a call cache the answer
What happens when many servers ask C about group:eng at once, say because a search result page checks dozens of documents that are all shared with eng?
The callers’ caches and the callee’s cache stack into a tree: “To handle hot forwarding keys, we cache results at both the caller and the callee of internal RPCs, effectively forming cache trees.” (§3.2.5) Cache keys include the snapshot timestamp, and timestamps are “rounded up to a coarse granularity, such as one or ten seconds”, so that most recent requests share entries (§3.2.5). In production, check caching had “a 10% hit rate on the delegate’s side” and “a 2% hit rate” on the delegator’s side; the paper notes that, low as these rates look, “they prevent 500K internal RPCs per second from creating hot spots” (§4.4).
The lock table collapses identical requests
A cache only helps once it holds the answer. If many identical requests arrive before the first one has finished, they would all miss and all go to Spanner: a cache stampede (the paper’s reference [3]). How does C avoid that?
The paper: “we maintain a lock table on each server to track outstanding reads and checks. Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (§3.2.5) For checks, the lock table saved “an additional 12%” on the delegate’s side and “an additional 3%” on the delegator’s side (§4.4).
Two refinements came later (§3.2.5). For a very popular object, Zanzibar reads and caches all tuples of ⟨object#relation⟩ at once, “trading read bandwidth for cacheability”. And because a cancelled sub-check leaves its cache key empty, it delays “eager cancellation when there are waiters on the corresponding lock table entry”.
Reads to Spanner are pooled
Now take a check that touches several relations of one object: is Chen a viewer of the readme? Under the paper’s Figure 1 config, viewer includes editor, editor includes owner, and viewers of the parent folder are viewers of the document. So server B has four tuple sets of the readme to read.
The leaves run concurrently: “we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (§3.2.3) Their reads are grouped: “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner.” (§3.2.3) The parent tuple then points at folder:A, and folder:A#viewer is forwarded to the server that owns folder:A, where Chen is found. The paper does not say how many RPCs a pool turns into; “fewer” is as far as it goes.
The tuple layout makes this cheap: the primary key order “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (§3.1.1, see Storage below).
Slow Spanner reads are hedged
Some reads will be slow for reasons that have nothing to do with the request. For calls to Spanner and to Leopard, Zanzibar uses request hedging, from Dean and Barroso, “The Tail at Scale” (CACM, 2013), the paper’s reference [16]. When does the second request go out?
Hedging means “we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests” (§3.2.7). The second request waits: “we first send one request and defer sending hedged requests until the initial request is known to be slow”, with the delay set by an estimator of an “Nth percentile latency based on recent measurements” (§3.2.7). In production “1% of Spanner reads, or 200K reads per second, benefit from hedging” (§4.4).
Each client is fenced in
A shared service has to stop one client from slowing down the others. §3.2.6 lists four limits:
- CPU: each RPC is costed in “generic cpu-seconds”; each client has a global CPU limit, and “its RPCs will be throttled if it exceeds the limit and there is no spare capacity in the overall system.”
- Outstanding RPCs: each server limits the total, and the number per client.
- Spanner: “the maximum number of concurrent reads per (object, client) and per client on each Spanner server.”
- Lock tables: “different lock table keys for requests from different clients”, so that Spanner throttling one client does not block another.
The Watch path
Writes also feed a stream. Where does a change go after Anne writes a tuple?
“Every Zanzibar write is committed to both the tuple storage and the changelog shard in a single transaction.” The Spanner server that hosts the changelog shard acts as transaction coordinator “to minimize blocking of changelog reads on pending transactions” (§3.1.2). Leopard is one consumer of this stream: its incremental indexer “calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications” (§3.2.4).
Storage
Which databases are there, and what does a row look like? There are three kinds (§3).
Tuple databases. “We store relation tuples of each namespace in a separate database, where each row is identified by primary key (shard ID, object ID, relation, user, commit timestamp).” (§3.1.1) Because the commit timestamp is part of the key, old versions stay on their own rows, “so that we can evaluate checks and reads at any timestamp within the garbage collection window”. The running example’s tuples would sit in the doc and group databases like this:
| Database | shard ID | object ID | relation | user | commit timestamp |
|---|---|---|---|---|---|
doc |
s(readme) | readme |
owner |
user:anne |
t₁ |
doc |
s(readme) | readme |
parent |
folder:A#... |
t₂ |
doc |
s(readme) | readme |
viewer |
group:eng#member |
t₃ |
group |
s(eng) | eng |
member |
user:beto |
t₄ |
Rows of one object sort together; the paper says this key order “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair”. “Usually the shard ID is determined solely by the object ID”; for groups with very many members it can be “computed from both object ID and user” (§3.1.1). The paper does not give the shard function, so s(…) above is a placeholder, and the exact encoding of the user column is not described either.
Changelog. One database for all namespaces, keyed by (changelog shard ID, timestamp, unique update ID), “where a changelog shard is randomly selected for each write” (§3.1.2).
Namespace configs. One database with two tables: the configs, “keyed by namespace IDs”, and “a changelog of config updates”, “keyed by commit timestamps”. A server loads every config at startup and then follows that changelog (§3.1.3).
Replication. “Replicas exist in dozens of locations around the world, with multiple replicas per region. The 5 voting replicas are in eastern and central United States, in 3 different metropolitan areas to isolate failures but within 25 milliseconds of each other so that Paxos transactions commit quickly.” (§3.1.4) Spanner itself is described in Corbett et al. (OSDI ’12), the paper’s reference [15].
Operational numbers
The paper’s §4 reports these figures. The per-API peaks and the latencies come from 7-day periods in December 2018 (§4, §4.2); the paper does not tie the other figures to a stated period. Each cell is quoted as written.
| What | The paper’s words | § |
|---|---|---|
| Time in production | “more than 5 years” | 4 |
| Namespaces | “more than 1,500 namespaces defined by hundreds of client applications” | 4 |
| Tuples | “more than 2 trillion relation tuples that occupy close to 100 terabytes” | 4 |
| Replication | “fully replicated in more than 30 locations around the world” | 4 |
| Client load | “more than 10 million client queries per second (QPS)” | 4 |
| Peak by API | “Check requests peak at roughly 4.2M QPS, Read at 8.2M, Expand at 760K, and Write at 25K” | 4 |
| Servers | “more than 10,000 servers organized in several dozen clusters around the world” | 4 |
| Servers per cluster | “from fewer than 100 to more than 1,000, with the median near 500” | 4 |
| Check Safe latency | “At the 50th, 95th, 99th, and 99.9th percentiles it peaks at roughly 3, 11, 20, and 93 msec, respectively.” | 4.2 |
| Availability | “above 99.999% over the past 3 years of operation at Google” | 4.3 |
| Internal RPCs | “22 million internal “delegated” RPCs per second, split about evenly between reads and checks” | 4.4 |
| Cache lookups | “approximately 200 million lookups per second at peak, 150 million from checks and 50 million from reads” | 4.4 |
| Reads to Spanner | “only 20 million read RPCs per second to Spanner” | 4.4 |
| Spanner read latency | “0.5 msec at the median, and 2 msec at the 95th percentile” | 4.4 |
| Hedged reads | “1% of Spanner reads, or 200K reads per second, benefit from hedging” | 4.4 |
Notice the ratio in the last rows: 200 million cache lookups per second against 20 million read RPCs to Spanner, about ten in-memory lookups for every read sent to storage.
Sources
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3, §3.1, §3.2.3, §3.2.5–§3.2.7, §4: https://www.usenix.org/conference/atc19/presentation/pang
- Karger et al., “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, STOC ’97 (paper ref. [20]): https://people.csail.mit.edu/karger/Papers/web.pdf
- Dean and Barroso, “The Tail at Scale”, Communications of the ACM 56(2), 2013 (paper ref. [16]): https://research.google/pubs/the-tail-at-scale/
- “Cache stampede”, Wikipedia, as cited by the paper (ref. [3]): https://en.wikipedia.org/wiki/Cache_stampede
- Adya et al., “Slicer: Auto-sharding for datacenter applications”, OSDI ’16 (paper ref. [12]): https://www.usenix.org/conference/osdi16/technical-sessions/presentation/adya
- Corbett et al., “Spanner: Google’s globally-distributed database”, OSDI ’12 (paper ref. [15]): https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf