SpiceDB New-Enemy Reads: Diagnosing Stale Permission Checks with ZedTokens

The recognizable condition

You grant a permission, then immediately check it and get denied. The write succeeded, the check is fast, but the result is wrong for a few hundred milliseconds to seconds. In a distributed SpiceDB deployment this is the New-Enemy problem: a read hits a replica that has not yet seen the preceding write.

SpiceDB uses a Zanzibar-style consistency model. Writes return a ZedToken, also called a zookie. A ZedToken is a version marker for the data set. Reads can be made causally consistent by passing at_least_as_fresh_as with a token from a prior write. The engineering decision is to keep SpiceDB stateless about client sessions and push token storage to the client.

Cause and diagnostic table

Symptom	Likely cause	Quick test
Check returns false immediately after a successful WriteRelationships	Read hit a lagging replica, no freshness constraint	Repeat check with at_least_as_fresh_as set to token from the write
Check with at_least_as_fresh_as times out or is slow	Token is newer than replica can reach quickly	Compare token from write vs token returned in check response
Checks are consistently stale even with token	Client stores and reuses an old token, or never updates token after writes	Log token values on write and on subsequent checks
Intermittent denials under load, no token used	Eventual consistency without causal reads	Enable token propagation for the request chain

Ordered checks

1. Confirm the write returns a token and you capture it

Run the write from the client host that performs authorization mutations. Required permission is write access to the namespace in SpiceDB.

# Example write, client side
WriteRelationships(
  updates: [{operation: OPERATION_TOUCH, relationship: ...}]
)

Expected check: the response metadata includes a zed_token. If your SDK hides metadata, inspect the response object for a token field. Risk: if you discard the token, causal reads are impossible.

2. Verify token propagation to the next check

Immediately issue a CheckPermission for the same subject-object-permission tuple, passing at_least_as_fresh_as with the token captured in step 1.

# Example check, same client process
CheckPermission(
  subject: ...,
  object: ...,
  permission: ...,
  at_least_as_fresh_as: <token_from_write>
)

Expected check: the request is accepted and the response contains a zed_token that is >= the requested token. If the check is denied despite the token, the write may not have affected the requested permission.

3. Inspect client token storage

Check how the client stores the latest token per user session or per request chain. The token must be updated after every successful write in that chain.

Expected check: token value monotonically increases for a given logical session. Risk: storing a token globally across unrelated users can cause unnecessary waits.

4. Measure replica lag under load

Perform a write, capture token, then issue two parallel checks: one with at_least_as_fresh_as and one without. Compare latency.

Expected check: the unconstrained check may be faster but occasionally stale; the constrained check is slower when replicas lag but returns causally consistent results. Risk: using at_least_as_fresh_as with a very fresh token can increase latency and risk timeouts.

Fixes tied to findings

If the write returns no token: verify client SDK version and that you are reading response metadata, not just the result payload.

If token is captured but not passed: update the client middleware to carry the latest ZedToken forward in the same request chain. This is the core fix for New-Enemy.

If token is stale: ensure the client updates its stored token after each write and does not reuse a token from an earlier unrelated operation. Avoid caching a token for longer than the session.

If constrained checks are consistently slow: consider relaxing freshness for non-critical reads, or investigate cluster replication lag, network partitions, and write quorum settings. Do not lower consistency for security-critical decisions.

Limitations and verification

at_least_as_fresh_as does not guarantee low latency. The replica may need to wait until it has applied writes up to the requested token. An outdated or incorrect token can cause the system to wait for a version that will never be reached on that replica.

Practical verification without claiming test results: perform a write, capture the returned ZedToken, then perform a check with that token via at_least_as_fresh_as. Then perform a check without the token against the same cluster. Observe that the constrained check reflects the write while the unconstrained check may lag.

Escalation criteria

Escalate to platform/SRE if constrained checks regularly time out, tokens stop advancing, or token values returned by reads are consistently behind writes for more than your replication SLO. Also escalate if you observe token reuse bugs across users, which can cause cross-tenant freshness waits.

Do not escalate for occasional single-digit millisecond lag; that is expected in a distributed system using causal consistency.