guide:architecture@en

Guides

Architecture, from one Check to Spanner

The servers and databases behind Zanzibar, followed through a single Check request and the Watch stream.

Facts checked on Paper sections §3, §3.1, §3.2.5, §3.2.6, §3.2.7, §4

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.

Zanzibar architecture, simplifiedClients send Check, Read, Expand and Write to the aclservers in a Zanzibar serving cluster; the watchserver is drawn outside the cluster, as in the paper. The aclservers load namespace configs from Spanner, read and write relation tuples in one Spanner database per namespace, and append every write to the changelog, also in Spanner. A watchserver tails the changelog and streams changes to clients (the Watch API) and to Leopard (the paper's Figure 2 draws Leopard as a separate indexing system). A periodic offline pipeline reads the tuple databases, dumps snapshots and garbage-collects old versions; Leopard builds its index from those snapshots and answers set computations for the aclservers.Zanzibar serving clusterSpannerclientsaclserverswatchserverclientsnamespace configsrelation tuples(one DB per namespace)changelogofflinepipeline(periodic)LeopardCheck, Read,Expand, Writeloadread, writeappendtailWatchchangesdump,GCsnapshotssetcomputation
Redrawn and simplified from the paper's Figure 2. Arrows show the direction of data flow. Clients appear twice only to keep the lines apart: the same clients call the aclservers and subscribe to Watch.

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.

A Check fans out across a clusterA client sends Check to aclserver A. Server A asks aclserver B, which handles doc:readme, whether Beto is a viewer of the readme. Server B finds that members of group:eng are viewers and asks aclserver C, which handles group:eng, whether Beto is a member. Answers travel back along the same arrows to A, which replies to the client.clientaclserver Areceives Checkaclserver Bkey: doc:readmeaclserver Ckey: group:engCheckviewer of readme?member of eng?
Check(user:beto, viewer, doc:readme). Answers come back along the same arrows; A replies to the client.

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).

Forwarding keys mapped onto a ring of serversFour aclservers, A, B, C and D, sit on a ring. The requests doc:readme#viewer and doc:readme#owner both hash on the object doc:readme and go to server B. group:eng#member goes to server C. folder:A#viewer goes to server D.aclserver Aaclserver Baclserver Caclserver Ddoc:readme#viewerdoc:readme#ownergroup:eng#memberfolder:A#viewerhash(doc:readme)hash(doc:readme)hash(group:eng)hash(folder:A)
Both readme requests go to B because the key is the object, not the relation. The ring is the textbook picture of consistent hashing; the paper does not say which variant Zanzibar uses.

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?

Caches at the caller and the callee form a treeThree aclservers, A, D and E, each with a cache, ask aclserver C whether a user is a member of group:eng. Server C has its own cache and reads group:eng's tuples from Spanner only on a miss.aclserver A+ cacheaclserver D+ cacheaclserver E+ cacheaclserver C+ cachegroup tuples(Spanner)eng member?on a miss
A hit at a caller saves an RPC to C. A hit at C saves a read from Spanner.

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?

A lock table lets one of several identical requests throughRequest 1 asks C for cache key K; C misses and records K in its lock table. Request 2 asks for the same key and is made to wait. C reads the rows from Spanner once, fills the cache and releases the entry. Both requests get the answer.timerequest 1aclserver Crequest 2Spannerask for key Kmiss: lock Kask for key KK locked: waitread oncerowsfill cacheansweranswer
Request 2 blocks instead of going to Spanner. Only one read is issued for key K.

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.

Leaf reads for one check share one poolEvaluating whether Chen is a viewer of doc:readme needs the readme's viewer, editor, owner and parent tuples. The four leaves are evaluated at the same time on aclserver B, which pools their reads before sending them to the doc database in Spanner.doc:readme#viewerdoc:readme#editordoc:readme#ownerdoc:readme#parentaclserver Bpools the readsdoc tuples(Spanner)fewer RPCs
Check(user:chen, viewer, doc:readme). All four leaves start at once; their reads go out together.

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?

A deferred hedged readThe aclserver sends a read to Spanner replica 1, which is slow. After the hedging delay, the aclserver sends the same read to replica 2. Replica 2 answers first; the aclserver uses that answer and cancels the read at replica 1.timeaclserverSpanner replica 1Spanner replica 2hedgecancelsend readslowdelay passedsame readreplyuse first replycancelled
The hedge is sent only after the first read is known to be slow.

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?

From a write to the Watch streamA client sends a Write to an aclserver. In one Spanner transaction the aclserver writes the tuple to the doc namespace database and an entry to a changelog shard. The watchserver tails the changelog and streams the change to Watch clients and to Leopard's incremental indexer.clientWriteaclserverdoc tupleschangelog shardwatchserverWatch clientsLeopardindexertuplesame txnsame txntailchanges
The tuple and its changelog entry are committed in one transaction, so the stream cannot miss a write or show one that did not commit.

“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).

Zanzibar's Spanner databasesOne database per namespace holds relation tuples: here doc, group and folder. A single namespace config database holds the configs and a changelog of config updates. A single changelog database, shared by all namespaces, records tuple updates. The aclservers read and write the tuple databases, load and monitor the config database, and append to the changelog.doc tuplesgroup tuplesfolder tuplesaclserversnamespace configs(configs + their changelog)changelog(all namespaces)read, writeload, monitorappend
One tuple database per namespace (left), one config database and one changelog shared by every namespace (right).

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