System Design: [Authorization service name]

Reference design for a relationship-based authorization service in the style of Google Zanzibar: access rules are stored as relation tuples (object, relation, subject), a namespace configuration defines how relations combine and inherit, and applications call Check, Expand, List and Watch APIs instead of embedding permission logic. It covers consistency tokens ("zookies") and the new-enemy problem, check evaluation and caching, deeply nested groups, reverse lookups, latency SLOs and sharding of the tuple store. Concepts follow Pang et al., "Zanzibar: Google's Consistent, Global Authorization System" (USENIX ATC 2019) and the public documentation of the open-source OpenFGA and SpiceDB projects. It follows the 12-section structure of the System Design Document template. Replace every [bracketed] value and every row marked Example.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Each product (documents, projects, billing) implements its own permission checks against its own tables. Sharing a folder with a group works in the documents product but not in search, which shows titles the user cannot open. A permissions bug last quarter exposed private projects to former team members because the project service cached roles for 30 minutes after removal. Adding a new sharing feature takes each team weeks.]

1.2 Proposed solution

[Example: A central authorization service stores every access fact as a relation tuple, such as doc:readme#viewer@group:eng#member. A versioned namespace configuration defines how relations combine: an editor is also a viewer, and a viewer of a folder is a viewer of every document in it. Products call Check on every request, ListObjects to filter search results, and Write when users share or unshare. Every write and check returns a consistency token; when content changes, the product stores a fresh token with the new content version, and later checks pass it so a check never uses data older than the last permission change that matters. Tuples live in a sharded, replicated database; check results are cached per snapshot and distributed across servers by consistent hashing.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

• [Example: authentication and user identity (the identity provider issues sub; see Identity Provider and SSO System Design Template (system-design/design-identity-sso-provider))]
• [Example: attribute conditions such as time of day or IP range (phase 2, as caveats evaluated on top of tuples)]
• [Example: policy-as-code for infrastructure (stays in the existing policy engine)]
• [Example: end-user audit log UI (products read the Watch stream)]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Storage

Consequence: 2 TB of logical data does not fit on one node with headroom, so the tuple store is sharded from day one, by object (section 5.4).

3.3 Storage reads

Consequence: the cache hit ratio is the dominant lever. If $h$ drops from 0.8 to 0.6, reads double to 800 000/s and the shard count doubles, so the cache gets its own deep dive (7.2) and its own SLO. Each shard then holds about 6 TB / 32, or roughly 190 GB, which is comfortable.

3.4 Changelog

Consequence: seven days of Watch history is about 600 GB, small enough to keep in the same store as a time-ordered table, so Watch needs no separate log system at this scale.

3.5 Latency

A check that walks six levels of nesting with one storage read per level costs six sequential round trips. At 1 to 2 ms per read that is 6 to 12 ms, already at the p95 budget. Consequence: evaluate branches of a union in parallel, cache intermediate results, and index deeply nested groups (7.3).

3.6 Summary

4. API design

4.1 Operations

Consistency modes accepted by every read operation:

4.2 Request and response examples

A check that protects content changed after a permission write passes the token saved with that content. A write that removes one viewer and adds a group is atomic, guarded by a precondition on the owner tuple.

POST /v1/check
Content-Type: application/json

{"object": "doc:readme", "relation": "view", "subject": "user:alice",
 "consistency": {"at_least_as_fresh": "zk_CAESBgjM8tK9Bg"}}

HTTP/1.1 200 OK
{"allowed": true, "checked_at": "zk_CAESBgjQ8tK9Bg"}

POST /v1/write
Content-Type: application/json

{"writes": [{"object": "doc:readme", "relation": "viewer", "subject": "group:eng#member"}],
 "deletes": [{"object": "doc:readme", "relation": "viewer", "subject": "user:mallory"}],
 "preconditions": [{"must_exist": {"object": "doc:readme", "relation": "owner", "subject": "user:alice"}}]}

HTTP/1.1 200 OK
{"written_at": "zk_CAESBgjR8tK9Bg"}

4.3 Errors and limits

5. Data model

5.1 Entities

Tuples are the bulk of the data; the configuration, changelog and group index are derived from or describe them.

5.2 Tuple format

A tuple is object#relation@subject, where the subject is either a direct subject (user:alice) or a userset (group:eng#member, meaning "every subject with relation member on group eng"). Example tuples:

5.3 Namespace configuration

Rewrite rules compute a relation from other relations. The Example below uses a neutral notation; translate it into the schema language of the engine you choose.

type user

type group
  relation member: user | group#member

type folder
  relation owner: user
  relation viewer: user | group#member
  permission view = viewer + owner

type doc
  relation parent: folder
  relation owner: user
  relation editor: user | group#member
  relation viewer: user | group#member
  permission edit = editor + owner
  permission view = viewer + edit + parent->view

+ is union; parent->view follows the parent tuple and checks view on the folder (a tuple-to-userset rewrite). Intersection and exclusion (viewer & not blocked) are possible but expensive; allow them only where a reviewer has measured the fan-out.

5.4 Access patterns

Consequence of AP-01: a "hot" object such as a company-wide group lives on one shard. Section 7.2 handles it with caching rather than by splitting the object.

6. High-level design

7. Detailed design

7.1 Deep dive: consistency and the new-enemy problem

Problem. A permission change and a content change arrive in order, but a check reads a stale replica and evaluates the new content against the old permissions. Two classic forms:

1. Alice removes Bob from a folder, then adds a confidential document to it. A check that sees the document but not the removal lets Bob read it.
2. Alice removes Bob from a document's viewers, then asks Charlie to add sensitive text. A check that ignores the order of the two changes lets Bob see the new text.

Choice and reason. Option C makes freshness proportional to need. Most checks run at a snapshot a few seconds old, which caches well, yet any check that protects content changed after a permission change is guaranteed to see that change. The tuple store must assign commit timestamps that respect real-time order across shards (external consistency); a store without this property breaks the guarantee for multi-shard writes.

Client contract. On every content change, run a content-change check (fully_consistent, or at least as fresh as any permission write the product just made) and store the returned checked_at token next to the new content version (for example in the document row). Storing only the token of an earlier permission write is not enough when another user changes the content later. Pass the stored token on every check of that content. When no token exists, use minimize_latency for listings and fully_consistent only for security administration pages.

7.2 Deep dive: check evaluation and caching

Choice and reason. Snapshots are quantized (for example rounded down to the nearest second) so that many checks share one snapshot and therefore share cache keys. The owner of a key deduplicates concurrent identical requests: if a thousand requests ask about the same company-wide group at the same snapshot, one storage read serves all of them. Cache entries never need invalidation because they are keyed by snapshot; they expire by age.

Evaluation rules:

• Evaluate union branches in parallel and return on the first true.
• Cap recursion depth (4.3) and detect cycles with a visited set.
• Hedge slow storage reads: after the p95 latency of that shard, send the same read to another replica and take the first answer.
• Never cache a result computed at a snapshot newer than the one requested under a key for the older snapshot.

7.3 Deep dive: deeply nested groups

Organisations nest groups (team in department in division). A check that walks ten levels makes ten sequential reads.

Choice and reason. The index is a set computation over the changelog, maintained incrementally and versioned by commit timestamp. A check that needs a snapshot newer than the index falls back to option A for the missing interval, so correctness never depends on index lag. Measure write amplification: adding a group of 50 000 members to a parent group creates up to 50 000 index entries.

7.4 Deep dive: reverse lookups for lists and search

Choice and reason. Combine C with a final BatchCheck of the returned page so that index lag can hide a result but never leak one.

7.5 Schema changes

Treat the namespace configuration like a database migration: validate types, reject removal of a relation that still has tuples, run the new version in shadow mode (evaluate both versions and compare results on sampled traffic), then activate. Every check response reports the schema version used.

How real systems do it: Google Zanzibar

The Zanzibar paper (Pang et al., USENIX ATC 2019) describes a global system that stores access control lists as relation tuples in Spanner and evaluates them with namespace configurations made of userset rewrite rules. Its consistency token, called a zookie, encodes a commit timestamp; clients receive one when they change content and send it back with later checks, which is how Zanzibar addresses the new-enemy problem while still serving most checks from slightly older snapshots. The paper describes forwarding sub-requests to peers chosen by consistent hashing so caches are shared, a lock table that merges identical concurrent requests, request hedging against slow replicas, and a separate indexing system (Leopard) that flattens deeply nested group membership. The authors report 95th-percentile latency under 10 ms and availability above 99.999% over three years of production use. This box is a paraphrase; read the paper for the actual architecture and measurements.

8. Scalability and performance

Latency budget for an uncached check at p95 (target 10 ms):

9. Reliability, security and operations

9.1 Failure modes

Fail closed. When a check cannot complete within its deadline, the client library denies. Clients may cache positive results for at most [5] seconds to ride out short blips; they never cache across a permission write they made themselves, and never answer a check that carries a token newer than the cached result's snapshot from that cache.

9.2 Security

Cross-check with the Threat Model Template (security/threat-model) and the policy decision point role in the Zero Trust Architecture Plan Template (security/zero-trust-architecture).

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Migration and rollback

[Example: A backfill job converts existing ACL rows into tuples; a change-data-capture stream keeps them in sync during dual-run. The product flag authz.source switches between legacy and service per namespace; rollback flips the flag and takes effect within 60 s.]

11.3 Risks

12. Appendices

12.1 Traceability

12.2 Open questions

12.3 Glossary

12.4 References

Standard and licence note

Based on the public Zanzibar paper and the public documentation of the OpenFGA and SpiceDB projects cited in 12.4, and on common industry practice for authorization services. This is a reference design with illustrative numbers, not a description of any vendor's product; check the current documentation of the engine you adopt, because consistency options and API names differ between engines and versions. Original text written for this collection. Template licence: MIT.