SpiceDB Zookies: Solving the New-Enemy Problem

Learn how SpiceDB uses Zookies (consistency tokens) to solve the 'New-Enemy Problem' and ensure causal consistency in distributed relationship-based access control.

The Consistency Gap in Distributed Permissions

Imagine a user is removed from a sensitive project group. The application updates the permissions database, and the user receives a confirmation that their access is revoked. However, because the permissions data is distributed across multiple global regions, the local cache in the user's current region hasn't updated yet. The user refreshes their page and still has access to the project. This is the "New-Enemy Problem": a race condition where a permission check is performed against a stale snapshot of the data, allowing an unauthorized action to occur immediately after access was revoked.

SpiceDB solves this using Zookies (consistency tokens). A Zookie is not a session cookie; it is a timestamp-based token that tells SpiceDB: "Do not answer this request unless your data is at least as fresh as this token." This ensures causal consistency, meaning if a user performs an action that changes a permission, any subsequent action they take will see the effect of that change.

How Zookies Enforce Causal Consistency

In a Relationship-Based Access Control (ReBAC) system, permissions are stored as tuples (e.g., user:alice is member of group:engineering). When you write a new tuple to SpiceDB, the server returns a Zookie. This token represents a specific point in time—a snapshot of the global state.

When the application later calls CheckPermission, it passes that Zookie back to SpiceDB. If the SpiceDB node handling the request is lagging behind the timestamp in the Zookie, it will not return a stale "Allow" or "Deny." Instead, it will wait for the data to catch up or route the request to a node that is up-to-date. This prevents the system from making a decision based on an outdated view of the relationship graph.

Practical Implementation: The Write-then-Check Flow

To implement this correctly, your application must treat the Zookie as a piece of state that follows the user's session or the specific resource's lifecycle. You should store the most recent Zookie returned from a write operation and include it in all subsequent read requests.

Example Workflow

Assume you are using the zed CLI or a gRPC client to manage a document's permissions. The following sequence demonstrates the consistency loop:

The Write: An admin removes a user from a document.
```
# Run via zed CLI (requires admin permissions)
zed write document:doc_1#viewer user:bob
```
The response from SpiceDB will include a consistency_token (the Zookie). Crucial: Your application must save this token in your database or session store.

The Check: The user attempts to access the document. The application retrieves the last known Zookie for this resource and passes it to the check request.

# Run via zed CLI
zed check document:doc_1#viewer user:bob --token <LAST_KNOWN_ZOOKIE>

The Result: Because the token is provided, SpiceDB guarantees that the check is performed against a snapshot that includes the removal of user:bob, returning a definitive Denied result even if the local node is experiencing slight replication lag.

Trade-offs and Limitations

While Zookies eliminate the New-Enemy Problem, they introduce specific engineering trade-offs:

Latency Spikes: If a request arrives with a very recent Zookie at a lagging node, that node must wait for the data to synchronize before responding. This can increase P99 latency during periods of high database load.
Storage Overhead: Your application layer now needs to manage and persist these tokens. If you lose the Zookie, you must fall back to a "global" consistency level or risk stale reads.
Deep Graph Traversal: SpiceDB resolves permissions by traversing a graph (e.g., User → Group → Role → Resource). While Zookies ensure the snapshot is fresh, very deep nesting can still impact the speed of the evaluation itself.

Verifying Your Consistency Logic

To verify that your Zookie implementation is working, you can simulate a stale read. In a staging environment with multiple SpiceDB nodes, perform a write to Node A, then immediately attempt a CheckPermission on Node B without providing the Zookie. If the replication lag is sufficient, you may see a stale result. Repeat the check with the Zookie; the request should either block until updated or return the correct, fresh result.

Solving the New-Enemy Problem with SpiceDB Zookies