An ACL check answers “may this user do this, now”. In a system replicated across the world, “now” is the hard part: different servers have seen different writes. This page explains which order Zanzibar promises to respect, how Spanner makes that promise cheap to keep, and how the zookie lets a client set the minimum freshness a check needs.
The new enemy problem
The paper opens §2.2 with a rule: “ACL checks must respect the order in which users modify ACLs and object contents to avoid unexpected sharing behaviors.” It calls the failure the “new enemy” problem: a user who has just been removed from an ACL still sees content that the removal was meant to hide.
The paper gives two examples. This page keeps the paper’s own names, Alice, Bob and Charlie, for these two so you can read them next to §2.2; everywhere else it uses the running example of Anne, Beto and Chen.
What can go wrong if a check sees the second change but not the first? The left frame is a system without ordering; the right frame is the same story under Zanzibar.
Notice that there is no snapshot that contains A2 but not A1. That is the whole guarantee: §2.2 explains that if a check runs at T < T_A2 “the document ACLs will not include the folder ACL”, and if it runs at T ≥ T_A2 > T_A1 it “will observe update A1, which removed Bob from the folder ACL”.
Example B differs in one detail: the second change is to the document’s contents, which live in the client application’s storage, not in Zanzibar. Zanzibar never sees that write. How can it know that a check about the new contents must be fresh enough?
The dashed arrow is the fix. The zookie travels with the content, so the check about B2 cannot run at a snapshot older than B2, and every such snapshot already contains B1. The rest of the page explains the two properties this relies on and the protocol that moves the zookie around.
Causally meaningful timestamps
§2.2 names two properties: external consistency and snapshot reads with bounded staleness. The paper cites Gifford’s 1981 dissertation for external consistency. The Spanner paper states the same property for transactions: “if a transaction T1 commits before another transaction T2 starts, then T1’s commit timestamp is smaller than T2’s”, and notes that this is “equivalently, linearizability”, citing Herlihy and Wing (1990).
In Zanzibar’s words (§2.2), two causally related updates x ≺ y get timestamps with T_x < T_y. A snapshot read at timestamp T “observes all updates with timestamps ≤ T”. Put together: if a read sees y, it also sees everything that happened before y. This works because the store is multi-version: Spanner defines a snapshot read as “a read in the past that executes without locking” (Spanner §4.1), and in a multiversion store “each write on a data item produces a new copy (or version)” (Bernstein and Goodman, 1983).
What does a reader see under that rule, and what can a reader of an eventually consistent replica see? In this variation the readme starts outside folder:A. Anne first removes Chen as a viewer of folder:A (x, committed at T=10), then moves doc:readme into folder:A (y, at T=20).
Notice that the two snapshot reads differ in how much they see but never in order: each one is a prefix of the history. The eventual replica will converge too, but until then it can show a state that never existed. The paper draws this contrast itself in §5: TAO “offers eventual global consistency with asynchronous replication”, while Zanzibar “provides external consistency and snapshot reads with bounded staleness”.
Where the timestamps come from: TrueTime
Zanzibar does not compute these timestamps itself. It stores ACLs in Spanner, whose “TrueTime mechanism assigns each ACL write a microsecond-resolution timestamp, such that the timestamps of writes reflect the causal ordering between writes” (§2.2). The outline of how that works is in §3, §4.1.2 and §4.2.1 of the Spanner paper (OSDI ’12).
TT.now()returns an interval[earliest, latest]that is guaranteed to contain the absolute time at which it was called. The uncertaintyεis half the interval’s width; in Google’s production environment it was “typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval”.- Start: the leader gives a write a commit timestamp
sno less thanTT.now().latest. - Commit wait: clients cannot see the write until
TT.after(s)is true, that is, untilshas definitely passed everywhere. Spanner notes that “the expected wait is at least 2 ∗ ε̄”, whereε̄is the average error bound (§4.2.1).
How does waiting make the timestamps causal?
Notice the last step: anything caused by the write starts after the client was told, which is after s had definitely passed, so its own TT.now().latest, and its timestamp, is larger than s. That is external consistency, paid for with a few milliseconds of waiting per write. §5 of the Zanzibar paper sums it up: Zanzibar “builds on Spanner’s TrueTime abstraction” to “provide linearizable commit timestamps encoded as zookies”.
The same paper explains why Zanzibar cannot use a logical clock instead: Lamport clocks “require explicit participation of all ‘processes’, where in Zanzibar’s use cases some of the ‘processes’ can be external clients or even human users” (§5). In Example A, the “asks” arrow is Alice talking to Charlie, a channel no clock sees.
The zookie protocol
Snapshot reads at a well-ordered timestamp solve Example A. Example B also needs the check to be fresh enough. One way would be to evaluate every check at the latest snapshot, but §2.2 rejects that: it “would require global data synchronization with high-latency round trips and limited availability”. Instead, the client carries the needed freshness itself, as a zookie: “an opaque byte sequence encoding a globally meaningful timestamp that reflects an ACL write, a client content version, or a read snapshot” (§2.4).
Who holds the zookie at each step? In the figure, Anne saves an edit to doc:readme, and later Beto opens it.
Step by step, following §2.2 and §2.4.4:
- Content-change check. When a user is about to save a change, the client sends a content-change check. It “does not carry a zookie and is evaluated at the latest snapshot” (§2.4.4).
- Zookie minted. If the change is allowed, the response includes a zookie. Zanzibar “encodes a current global timestamp in the zookie and ensures that all prior ACL writes have lower timestamps” (§2.2).
- Stored with the content. “The client stores the zookie with the content change in an atomic write to the client storage” (§2.2). The check itself does not have to be in the same transaction as the content write.
- Carried by later checks. Every later check of that content version sends the stored zookie.
- Evaluated at least as fresh. “A check is always evaluated at a consistent snapshot no earlier than the given zookie” (§2.4.4).
In Example B, the zookie stored with the new contents encodes T_B2, and T_B2 > T_B1, so Bob’s check in step 5 must see his removal.
The zookie is opaque on purpose. The paper uses “an opaque cookie instead of the actual timestamp to discourage our clients from choosing arbitrary timestamps and to allow future extensions” (§2.4). §5 adds that the protocol “does not let clients read or evaluate ACLs at an arbitrary snapshot”, which is what leaves the choice to Zanzibar.
Why “at least as fresh” and not “exactly at”
A zookie is a lower bound. Zanzibar may evaluate a check at the zookie’s timestamp or at any later one. §2.2 calls this the protocol’s “at-least-as-fresh semantics” and says it “allow[s] Zanzibar to choose any timestamp fresher than the one encoded in a zookie”. The freedom is used in three ways.
- Default staleness (§3.2.1). With no zookie, the server picks “a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency”. Each server tracks how often reads at a given staleness had to leave the zone and moves the default to “the lowest ‘safe’ value”. The paper notes this “is purely a performance optimization” because “Zanzibar always respects zookies when provided”.
- Quantization (§3.2.5). Evaluation timestamps are “rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies”. Rounding up never breaks a lower bound.
- Shared caches (§3.2.5). Cache keys contain the snapshot timestamp, so results from different snapshots are never mixed. Because of the rounding, “the vast majority of recent checks and reads” are evaluated at the same timestamps and “share cache results”.
What does rounding up buy when three checks arrive with zookies a few hundred milliseconds apart?
Notice that T_q may even be slightly in the future. §3.2.5 covers that case: Spanner “ensures that a snapshot read at timestamp T will observe all writes up to T—this holds even if T is in the future, in which case the read will wait until TrueTime has moved past T.”
Safe and Recent requests
The price of freshness is distance. “When a zookie timestamp is higher than that of the most recent data replicated to the region, the storage reads require cross-region round trips to the leader replica” (§4.1). The storage replicates with “replication heartbeats with 8-second intervals”, so §4.1 splits requests at 10 seconds:
- Safe requests “have zookies more than 10 seconds old and can be served within the region most of time”.
- Recent requests “have zookies less than 10 seconds old and often require inter-region round trips”.
The 8 seconds match the Spanner paper, where “a leader by default advances MinNextTS() values every 8 seconds”, so replicas “can serve reads at timestamps greater than 8 seconds old in the worst case” (Spanner §4.2.1).
The paper’s Table 2 (§4.2) gives the latency of each kind, in milliseconds, as mean (standard deviation) over a 7-day period in December 2018:
| API | 50%ile | 95%ile | 99%ile | |
|---|---|---|---|---|
| Safe | Check | 3.0 (0.091) | 9.46 (0.3) | 15.0 (1.19) |
| Safe | Read | 2.18 (0.031) | 3.71 (0.094) | 8.03 (3.28) |
| Safe | Expand | 4.27 (0.313) | 8.84 (0.586) | 34.1 (4.35) |
| Recent | Check | 2.86 (0.087) | 60.0 (2.1) | 76.3 (2.59) |
| Recent | Read | 2.21 (0.054) | 40.1 (2.03) | 86.2 (3.84) |
| Recent | Expand | 5.79 (0.224) | 45.6 (3.44) | 121.0 (2.38) |
| Recent | Write | 127.0 (3.65) | 233.0 (23.0) | 401.0 (133.0) |
The medians are close; the tails are not. A Recent Check’s 95th percentile is 60.0 ms against 9.46 ms for a Safe one, the cost of the cross-region trip. Writes are slowest because they “always require distributed coordination among Spanner servers” (§4.2); in Spanner that coordination includes commit wait. Per §4.1 and Figure 3, Safe requests outnumber Recent ones by “about two orders of magnitude”, “which allows Zanzibar to serve the vast majority of ACL checks locally”. Most requests can be Safe because a zookie is only a lower bound: a check of older content may use older, already replicated data.
Sources
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.2, §2.4, §2.4.4, §3.2.1, §3.2.5, §4.1, §4.2 (Table 2), §5.
- James C. Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI ’12, §1, §3, §4.1, §4.1.2, §4.2.1.
- Maurice P. Herlihy and Jeannette M. Wing, Linearizability: A Correctness Condition for Concurrent Objects, ACM TOPLAS 12(3), July 1990, pp. 463–492.
- Philip A. Bernstein and Nathan Goodman, Multiversion Concurrency Control: Theory and Algorithms, ACM TODS 8(4), December 1983.
- David K. Gifford, Information Storage in a Decentralized Computer System, PhD thesis, Stanford, 1981 (Zanzibar reference 18); also Xerox PARC CSL-81-8 (Spanner reference 16). No link verified.