Zanzibar prevents the new enemy problem with zookies, and zookies work because Spanner gives every write a timestamp that respects causality. Consistency, snapshots and zookies explains both, including how TrueTime and commit wait produce those timestamps. Almost nobody outside Google runs on TrueTime. This page asks what the zookie protocol actually needs from a database, and how products built on other databases get it, or do without.
What a zookie needs from the datastore
The zookie protocol rests on two properties that §2.2 asks of the storage layer, “external consistency and snapshot reads with bounded staleness”:
- Commit order follows causality. If write
xhappened before writey(for example, Anne sawxsucceed and then madey), thenT_x < T_y. In the paper’s words, two causally related updatesx ≺ y“will be assigned timestamps that reflect the causal order:T_x < T_y” (§2.2), and the zookie protocol “ensures that all prior ACL writes have lower timestamps”. - Snapshot reads at or after a given point. A read at
T“observes all updates with timestamps ≤ T” (§2.2), and a check “is always evaluated at a consistent snapshot no earlier than the given zookie” (§2.4.4).
Nothing in this list says “timestamp” in the sense of wall-clock time. The value inside a zookie can be any position in a history, as long as the two properties hold for it. That is why the paper made the zookie opaque: “to discourage our clients from choosing arbitrary timestamps and to allow future extensions” (§2.4).
How do the two properties combine to stop Chen from seeing the readme after he was removed from folder A?
Notice that property ① is about writes that the database may never see as related. §2.2 requires ordering for “updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar”. In the paper’s Example A, the link between the two writes is Alice asking Charlie, outside any system. The database has to order the two commits correctly anyway.
Three ways to get an order
Spanner gets property ① from synchronized clocks with a known error bound, paid for by waiting out the uncertainty on each write (Spanner, OSDI ’12; drawn on the consistency page). Other databases get it, or most of it, in different ways. Where does the order come from in each?
Notice that the single-primary databases get property ① for free, because one server sees every commit in order; what they give up is the paper’s global replication. CockroachDB replicates globally but only partly provides property ①. The next section is about that gap.
CockroachDB: the overlapping-keys rule
CockroachDB has no TrueTime. Its nodes keep loosely synchronized clocks, and the cluster has a maximum clock offset, --max-offset, with a default of 500ms; “If observed clock offsets exceed this limit, servers will crash to minimize the likelihood of reading inconsistent data” (cockroach start). Cockroach Labs’ own comparison with Spanner says “CockroachDB only goes as far as to claim serializability”, and names the anomaly it allows “causal reverse”: causally related transactions can commit with timestamps in the wrong order (Living without atomic clocks, 2022-01-27).
AuthZed reproduced the new enemy problem on CockroachDB with SpiceDB in 2021 (The One Crucial Difference Between Spanner and CockroachDB, 2021-10-14). The post’s summary of the gap: “Cockroach does not provide external consistency for transactions involving non-overlapping keys.” Its test used two writes and a check, run “in sequence (not parallel)”: write an excluded tuple, write a direct tuple, then check allowed = direct - excluded at the second write’s revision; “the check in 3 will succeed”.
What does that look like with the running example, if one node’s clock runs ahead?
Notice the arrow labelled “same key K” in the right frame. Neither clock got better; what changed is that the two transactions now conflict, and CockroachDB orders conflicting transactions correctly. The timestamps in both frames are illustrative; the skew is well inside the 500ms default, so no server would crash.
AuthZed found that a shared read was not enough: “we needed both transactions to write to the same key”. SpiceDB’s CockroachDB driver therefore adds an overlap key to writes, with a strategy chosen by --datastore-tx-overlap-strategy (datastores):
| Strategy | SpiceDB docs |
|---|---|
static (default) |
“All writes overlap to guarantee safety at the cost of write throughput” |
prefix |
“Only writes that contain objects with same prefix overlap” |
request |
“Only writes with the same io.spicedb.requestoverlapkey header overlap” |
insecure |
“No writes overlap, providing the best write throughput, but possibly leaving you vulnerable to the New Enemy Problem” |
The cost, in AuthZed’s words: “This does add a small amount of latency to the write path, but it leaves the read paths performant.” Every static write contends on one row, which is the price the paper paid instead with commit wait.
The datastore docs add one more CockroachDB caveat, on the read side: SpiceDB picks a revision with cluster_logical_timestamp(), “which can differ across nodes by up to the cluster’s” maximum offset, and “A read may not see a recently committed write if the reading node’s timestamp is behind the writing node’s.” As a result, “fully_consistent does not guarantee read-after-write consistency on CockroachDB.” A ZedToken from the write avoids this, because it names the write’s own revision (datastores).
PostgreSQL and MySQL: one primary decides
A single-primary database already sees every commit in order, so property ① needs no clocks. The open question is property ②: reads that may go to a replica that is behind.
SpiceDB’s PostgreSQL driver does not use time at all for ordering. A revision is the transaction id and snapshot from pg_current_xact_id() and pg_current_snapshot(); a comment in the driver says “timestamps cannot be used for ordering transactions in PG”, and that two snapshots can be “mutually uncomparable” (postgres/revisions.go, v1.57.1). A snapshot taken after x committed lists x as committed, which is property ① stated in PostgreSQL’s own terms. The MySQL driver writes a row to a transaction table whose id is AUTO_INCREMENT and uses that id as the revision (migrations, revisions.go). A write that starts after another has committed inserts its row later, so it gets a larger id; that reasoning is this page’s, not stated in the SpiceDB docs.
Read replicas reintroduce lag. How does SpiceDB keep a check at least as fresh as its token when the replica is behind?
The docs describe exactly this: replication lag “would be problematic to SpiceDB’s ability to solve the new enemy problem”, so SpiceDB checks “if the revision has been replicated into the target replica. If missing, it will fall back to the primary.” For MySQL this “requires two roundtrips instead of one”, and the docs warn against a load balancer in front of MySQL replicas “because SpiceDB will not be able to maintain consistency guarantees” (datastores).
Permify, which runs on PostgreSQL, builds its Snap Token the same way: the token holds a PostgreSQL XID8 and a snapshot string (snapshot/token.go, v1.7.6). Its docs describe the token only as “a token that consists of an encoded timestamp” (snap tokens).
Spanner without the paper
SpiceDB also runs on Cloud Spanner, which has TrueTime. There the driver “assumes the database is linearizable and skips the transaction overlap strategy” (datastores), and reads its revision with SELECT CURRENT_TIMESTAMP() (spanner/revisions.go). This is the configuration closest to the paper.
Without a token at all
OpenFGA has no zookie; its docs say the paper “has a feature called Zookies” and that OpenFGA “is considering a similar feature in future releases” (consistency). Instead a query picks MINIMIZE_LATENCY (the default) or HIGHER_CONSISTENCY, which “will skip the cache and query the database directly”. On PostgreSQL with a secondary datastore configured (datastore.secondaryUri, “for postgres only”, configuration), HIGHER_CONSISTENCY also selects the primary: the code comment reads “If we are using higher consistency, we need to use the write database” (postgres.go, v1.22.1).
That gives “as fresh as the primary”, not “at least as fresh as my write”. The difference matters for cost: a zookie lets most checks use a cache or replica and only recent ones go to the primary, while HIGHER_CONSISTENCY sends every such query there. The OpenFGA page draws the cache case; the docs suggest choosing the mode per request by comparing a resource’s last-modified time with the cache TTL, which makes the application keep part of a zookie’s information itself.
Other products:
- Ory Keto has
snaptokenandlatestfields in its Check API, each marked “This field is not implemented yet and has no effect” (check_service.proto). - Warrant reads a
Warrant-Tokenheader and acts only on the valuelatest, which sends the read to the primary; any other value is ignored, and the open-source server returns no token (wookie.go, Warrant). - Topaz documents no token; see the comparison page.
Tom MacWright’s reading notes on the paper make the same observation from the outside: OpenFGA has nothing like zookies, and “neither does Ory Keto” (Reading Zanzibar, 2025-05-02).
Without a token, an application that needs the paper’s guarantee has two options: read from a store that is always current (one primary, no cache), or accept a window in which a removed user can still be allowed.
Mechanism per product
| Product and datastore | Where the order comes from | Token | Reads at or after the token |
|---|---|---|---|
| Paper (Spanner) | TrueTime + commit wait | zookie | any replica; waits if needed (§3.2.5) |
| SpiceDB on Spanner | TrueTime; overlap strategy skipped | ZedToken | Spanner snapshot read |
| SpiceDB on CockroachDB | HLC timestamps; overlap key on writes (static by default) |
ZedToken | AS OF SYSTEM TIME; fully_consistent may miss a write on another node |
| SpiceDB on PostgreSQL | primary’s transaction id and snapshot | ZedToken | replica if it has the revision, else primary |
| SpiceDB on MySQL | AUTO_INCREMENT transaction id |
ZedToken | replica if it has the revision, else primary (two round trips) |
| Permify on PostgreSQL | primary’s XID8 and snapshot |
Snap Token | snapshot from the token |
| OpenFGA | none exposed | none | HIGHER_CONSISTENCY: skip cache, use primary |
| Ory Keto | none exposed | snaptoken field, not implemented |
not available |
| Warrant | none (no token is returned) | Warrant-Token header |
latest only; other values ignored |
Sources for each row are in the sections above. Permify’s read path for a token was not traced in its source; the row reflects the token’s contents only.
Sources
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.2, §2.4, §2.4.4, §3.2.5, §5.
- James C. Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI ’12.
- AuthZed, The One Crucial Difference Between Spanner and CockroachDB, 2021-10-14 (vendor blog).
- AuthZed, Enforcing Causal Ordering in Distributed Systems: The Importance of Permissions Checking, 2021-02-17 (vendor blog).
- AuthZed, Datastores, SpiceDB docs.
- SpiceDB v1.57.1 source:
postgres/revisions.go,mysql/revisions.go,mysqlinitial schema,spanner/revisions.go. - Cockroach Labs,
cockroach start(--max-offset). - Spencer Kimball and Irfan Sharif, Living without atomic clocks: Where CockroachDB and Spanner diverge, Cockroach Labs, 2022-01-27 (vendor blog).
- OpenFGA, Query Consistency Modes and Configuring OpenFGA; v1.22.1 source
pkg/storage/postgres/postgres.go. - Permify, Snap Tokens; v1.7.6 source
snapshot/token.go. - Ory Keto,
check_service.proto. - Warrant,
pkg/wookie/wookie.go. - Tom MacWright, Reading Zanzibar, 2025-05-02.