# 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*.

<!--
Guidance: How to use this template
- Write the namespace configuration (section 5.3) for two or three real
  resource types before sizing anything. The rewrite rules decide the
  fan-out of a check, and the fan-out decides cache size, shard count and
  latency.
- Decide the consistency contract early (section 7.1). Every client team
  must know when to pass a consistency token and where to store it.
- Keep the deep dives in section 7 to the hard problems: consistency,
  caching, nested groups, reverse lookups. Do not spend reviewer time on
  generic load balancer detail.
- For an interview, follow the 45-minute path in section 1.4 and skip the
  delivery plan.
- Related documents: System Design Document Template
  (`system-design/system-design-document`), Identity Provider and SSO
  System Design Template (`system-design/design-identity-sso-provider`),
  Threat Model Template (`security/threat-model`), Zero Trust Architecture
  Plan Template (`security/zero-trust-architecture`), Multi-Tenancy Design
  Template (`architecture/multi-tenancy-design`).
-->

## Document control

<!-- Guidance: An authorization service is a shared dependency of every product team. Record who owns the namespace schema and who approves changes to it. -->

| Field | Value |
|---|---|
| Document ID | [SDD-AUTHZ-001] |
| System / feature | [Central authorization service] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner | [@owner] |
| Author(s) | [@author] |
| Reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal] |
| Schema owner | [@team] |
| Related | [Identity provider design], [Threat model], [ADR: consistency contract] |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Tech lead | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Staff / principal engineer | [@name] | [Decision] | YYYY-MM-DD |
| Security architect | [@name] | [Decision] | YYYY-MM-DD |
| SRE / operations | [@name] | [Decision] | YYYY-MM-DD |
| Representative client team | [@name] | [Decision] | YYYY-MM-DD |

## Revision history

<!-- Guidance: Note what changed in the design, not the wording. -->

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft for design review |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Added group membership index after nested-group latency tests |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* Consistency contract changed from bounded staleness to tokens |
| 1.0 | YYYY-MM-DD | [@name] | *Example:* Approved |

## Contents

<!-- Guidance: Keep aligned with the headings. -->

1. [Overview](#1-overview)
2. [Requirements](#2-requirements)
3. [Capacity estimation](#3-capacity-estimation)
4. [API design](#4-api-design)
5. [Data model](#5-data-model)
6. [High-level design](#6-high-level-design)
7. [Detailed design](#7-detailed-design)
8. [Scalability and performance](#8-scalability-and-performance)
9. [Reliability, security and operations](#9-reliability-security-and-operations)
10. [Trade-offs and alternatives](#10-trade-offs-and-alternatives)
11. [Delivery plan and risks](#11-delivery-plan-and-risks)
12. [Appendices](#12-appendices)

## 1. Overview

<!-- Guidance: One page a busy reviewer can read alone: the problem, the proposed solution in a paragraph, and the decisions that need their attention. Pitfall: describing role-based access control and calling it relationship-based. -->

### 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

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Consistency contract for clients? | Tokens with "at least as fresh" semantics; full consistency only on request | 7.1 |
| Q-02 | *Example:* Tuple store technology? | Distributed SQL with external-consistency timestamps | 5.4, 10 |
| Q-03 | *Example:* How to handle groups nested 10 levels deep? | Precomputed group membership index for selected namespaces | 7.3 |
| Q-04 | *Example:* How do search and list pages filter results? | ListObjects for small result sets; pre-filter index for search | 7.4 |
| Q-05 | *Example:* Fail open or closed when the service is unreachable? | Fail closed, with a short client-side cache of positive results | 9.1 |
| [Q-nn] | [Question] | [Option] | [Section] |

### 1.4 45-minute interview path

<!-- Guidance: One document serves both an interview and a real review. In an interview, cover the minutes below and pick one deep dive; name the others to show you know they exist. -->

| Minutes | Cover | Output on the whiteboard |
|---|---|---|
| 0 to 5 | Clarify: who calls, what objects, roles or relationships, scale, consistency expectation | Core and below-the-line lists (2.1, 2.3) |
| 5 to 10 | Estimate checks per second, tuples, fan-out per check | Three numbers and their consequences (3.6) |
| 10 to 15 | API: Check, Write, Read, Expand, ListObjects, Watch | Signatures with the consistency token (4.1) |
| 15 to 20 | Data model: tuple, namespace configuration, access patterns | Tuple table and one rewrite rule (5.2, 5.3) |
| 20 to 28 | High-level design: check servers, tuple store, cache, changelog | One diagram (6) |
| 28 to 40 | One deep dive: the new-enemy problem and tokens (7.1) is the strongest choice; caching (7.2) if the interviewer pushes on latency | Options, choice, reason |
| 40 to 45 | Failure modes, fail-closed decision, what changes at 10x | Two rows of the failure table (9.1) |

## 2. Requirements

<!-- Guidance: Separate the core requirements the design must meet from the ones explicitly below the line. Pitfall: promising arbitrary attribute-based policies and relationship graphs in one engine at launch. -->

### 2.1 Core functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* Answer "does subject S have relation R on object O?" (Check) | Must |
| FR-02 | *Example:* Store and delete relation tuples, with optional preconditions (Write) | Must |
| FR-03 | *Example:* Support usersets: a subject can be "members of group G" | Must |
| FR-04 | *Example:* Support relation inheritance within an object (owner implies editor implies viewer) | Must |
| FR-05 | *Example:* Support inheritance across objects (viewer of a folder views its documents) | Must |
| FR-06 | *Example:* Return a consistency token on every write; accept one on every read | Must |
| FR-07 | *Example:* List objects of a type a subject can access (ListObjects) | Must |
| FR-08 | *Example:* Show why access is granted (Expand, as an effective userset tree) | Should |
| FR-09 | *Example:* Stream tuple changes to subscribers in commit order (Watch) | Should |
| FR-10 | *Example:* Version the namespace configuration and reject unsafe changes | Must |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Check latency | *Example:* p95 at or below 10 ms, p99 at or below 30 ms, in region | Server-side timing per API |
| NFR-02 | Availability | *Example:* 99.99% monthly for Check | Successful responses / valid requests |
| NFR-03 | Correctness | *Example:* No check evaluated at a snapshot older than the token supplied | Consistency test suite with injected lag |
| NFR-04 | Throughput | *Example:* 500 000 checks/s at peak, 5 000 tuple writes/s | Load test |
| NFR-05 | Write latency | *Example:* p99 at or below 100 ms | Server-side timing |
| NFR-06 | Isolation | *Example:* One tenant's hot object cannot raise p99 for others | Hot-spot test |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 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

<!-- Guidance: Every number must end in a consequence for the design. A number with no consequence is decoration; delete it. See Back-of-Envelope Estimation and Capacity Model Template (`system-design/back-of-envelope-estimation`). -->

### 3.1 Assumptions

| Input | Symbol | Value | Source |
|---|---|---|---|
| Peak checks per second, all regions | $C$ | *Example:* 500 000 | Gateway metrics of all products x growth |
| Peak tuple writes per second | $W$ | *Example:* 5 000 | Sharing and membership events |
| Stored tuples | $T$ | *Example:* 20 billion | Objects x average ACL entries |
| Bytes per tuple including index overhead | $b$ | *Example:* 100 B | Schema in 5.2 |
| Replication factor | $f$ | *Example:* 3 | Store configuration |
| Average storage reads per uncached check | $k$ | *Example:* 4 | Fan-out measured on the schema in 5.3 |
| Cache hit ratio for sub-problems | $h$ | *Example:* 0.8 | Prototype measurement |
| Reads per second one shard serves at target latency | $r$ | *Example:* 20 000 | Benchmark |

### 3.2 Storage

$$
S = T \times b \times f = 2 \times 10^{10} \times 100 \ \text{B} \times 3 = 6 \ \text{TB}
$$

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

$$
R = C \times k \times (1 - h) = 5 \times 10^{5} \times 4 \times 0.2 = 4 \times 10^{5} \ \text{reads/s}
$$

$$
N_{shards} = \frac{R}{r} \times 1.5 = \frac{4 \times 10^{5}}{2 \times 10^{4}} \times 1.5 = 30 \Rightarrow 32 \ \text{shards}
$$

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

$$
L = W \times 200 \ \text{B} \times 86\,400 \ \text{s} = 5\,000 \times 200 \times 86\,400 \approx 86 \ \text{GB/day}
$$

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

| Quantity | Estimate | Design consequence |
|---|---|---|
| Checks | 500 000/s | Stateless check servers, scaled horizontally |
| Logical tuple data | 2 TB (6 TB replicated) | Shard by object from day one |
| Storage reads | 400 000/s at 80% hit | 32 shards; cache hit ratio monitored as an SLO |
| Changelog | ~86 GB/day | Watch served from a changelog table, 7-day retention |
| Nested check | 6 to 12 ms if sequential | Parallel evaluation, caching, group index |

## 4. API design

<!-- Guidance: The contract matters more than the internals: every product team codes against it. Make the consistency token explicit in every signature. Pitfall: an API that hides consistency so clients cannot reason about stale results. -->

### 4.1 Operations

| Operation | Input | Output | Notes |
|---|---|---|---|
| `Check` | object, relation, subject, consistency | allowed (bool), checked_at token | Hot path; must be cheap |
| `BatchCheck` | up to [100] checks, consistency | list of results | For list pages |
| `Write` | tuples to add, tuples to delete, preconditions | token | Atomic per request |
| `Read` | tuple filter, consistency, page token | tuples, next page token | Admin and debugging |
| `Expand` | object, relation, consistency | userset tree | Explains effective access |
| `ListObjects` | object type, relation, subject, consistency | object IDs (bounded) | Reverse lookup (7.4) |
| `ListSubjects` | object, relation, subject type, consistency | subject IDs (bounded) | Who can see this |
| `Watch` | namespaces, start token | stream of tuple changes with tokens | Commit order per shard |
| `WriteSchema` | namespace configuration | schema version | Validated before activation (7.5) |

Consistency modes accepted by every read operation:

| Mode | Meaning | Typical use |
|---|---|---|
| `minimize_latency` | Any recent snapshot the server chooses | Low-risk reads such as UI hints |
| `at_least_as_fresh(token)` | Snapshot no older than the token | Default for content checks |
| `at_exact_snapshot(token)` | Exactly the token's snapshot | Paging through Read or List results |
| `fully_consistent` | Latest committed data | Right after a security-sensitive change |

### 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.

```http
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"}
```

```http
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

| Condition | Status | Body type |
|---|---|---|
| Unknown namespace or relation | 400 | `problems/schema-mismatch` |
| Precondition failed on Write | 409 | `problems/precondition-failed` |
| Token older than retained history | 410 | `problems/snapshot-expired` (retry with `at_least_as_fresh`) |
| Check exceeded depth limit [25] | 422 | `problems/max-depth` |
| Tenant quota exceeded | 429 | RFC 9457 problem details with `Retry-After` |
| Deadline exceeded | 504 | Client treats as deny (9.1) |

## 5. Data model

<!-- Guidance: Two things are data here: tuples (many, small, sharded) and the namespace configuration (few, versioned, global). Show the access patterns before choosing keys. -->

### 5.1 Entities

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

```mermaid
erDiagram
  NAMESPACE_CONFIG {
    string namespace PK
    int schema_version PK
    text definition
    datetime activated_at
  }
  RELATION_TUPLE {
    string namespace PK
    string object_id PK
    string relation PK
    string subject_type PK
    string subject_id PK
    string subject_relation PK
    bigint commit_ts
  }
  CHANGELOG {
    int shard PK
    bigint commit_ts PK
    string op
    string tuple_key
  }
  GROUP_INDEX {
    string group_id PK
    string member_id PK
    bigint valid_from_ts
  }
  NAMESPACE_CONFIG ||--o{ RELATION_TUPLE : "types"
  RELATION_TUPLE ||--o{ CHANGELOG : "recorded in"
  RELATION_TUPLE ||--o{ GROUP_INDEX : "denormalized into"
```

### 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:

| Tuple | Meaning |
|---|---|
| `doc:readme#owner@user:alice` | Alice owns the document |
| `doc:readme#viewer@group:eng#member` | Members of group eng can view |
| `doc:readme#parent@folder:handbook` | The document sits in folder handbook |
| `group:eng#member@group:backend#member` | Group backend is nested in eng |

### 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.

```text
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

| ID | Query | Served by | Partition key rationale |
|---|---|---|---|
| AP-01 *(Example)* | Direct tuples for (object, relation) during Check | Primary key prefix (namespace, object_id, relation) | Shard by (namespace, object_id) keeps an object's ACL on one shard |
| AP-02 *(Example)* | Is subject a direct member of userset? | Same key plus subject columns | Point read on the object's shard |
| AP-03 *(Example)* | Follow `parent` from a document | AP-01 on relation `parent` | Same shard as the document |
| AP-04 *(Example)* | Groups containing a member, transitively | GROUP_INDEX by member_id (7.3) | Separate index sharded by member |
| AP-05 *(Example)* | Objects a subject can view (ListObjects) | Reverse index by (subject, namespace) plus check filter (7.4) | Secondary index sharded by subject |
| AP-06 *(Example)* | Changes since token for Watch | CHANGELOG by (shard, commit_ts) | Time order per shard; merged by the Watch service |
| AP-07 *(Example)* | Current schema | NAMESPACE_CONFIG, cached in every server | Tiny, global, versioned |

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

<!-- Guidance: One diagram that shows every component on the request paths and where state lives. Name components by responsibility. -->

```mermaid
flowchart LR
  app([Product service]) --> lb[Regional load balancer]
  lb --> cs[Check servers, stateless]
  cs <--> peers[Peer check servers, consistent hashing]
  cs --> cache[(Per-server result cache)]
  cs --> store[(Tuple store, sharded and replicated)]
  cs --> gidx[(Group membership index)]
  app -->|Write| ws[Write path]
  ws --> store
  store --> cl[(Changelog)]
  cl --> watch[Watch service]
  watch --> app
  cl --> idxb[Index builder]
  idxb --> gidx
  admin[Schema admin] --> schema[(Namespace config)]
  schema --> cs
```

| Component | Responsibility | Scales by |
|---|---|---|
| Check servers | Parse request, pick snapshot, evaluate rewrite rules, fan out | Stateless replicas per region |
| Result cache | Cache sub-problem results keyed by (object, relation, subject, snapshot) | Memory per server; peers own key ranges |
| Tuple store | Durable tuples with commit timestamps, multi-region replication | Shards by object |
| Changelog | Ordered record of every tuple change | Shards, retained 7 days |
| Watch service | Merge changelog shards and stream to subscribers | Subscribers |
| Group index | Flattened transitive group membership | Members |
| Schema admin | Validate, version and roll out namespace configuration | Single service |

## 7. Detailed design

<!-- Guidance: Two to four deep dives on the hard problems. For each: options, choice, reason. Pitfall: deep dives on parts that any web service has. -->

### 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.

| Option | How | Cost | Verdict |
|---|---|---|---|
| A. Always fully consistent | Every check reads the latest committed data | Cross-region reads on every check; caches useless | Rejected: misses NFR-01 |
| B. Bounded staleness | Checks read a snapshot at most N seconds old | Window of N seconds where the new-enemy problem occurs | Rejected for content; acceptable for UI hints |
| C. Consistency tokens | Write returns a token encoding its commit timestamp; the product stores it with the content version; checks pass it as "at least as fresh" | Clients must store and forward tokens | **Chosen** |

**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.

```mermaid
sequenceDiagram
  participant P as Product service
  participant A as Authz Write
  participant S as Tuple store
  participant C as Check server
  P->>A: delete doc:plan#viewer@user:bob
  A->>S: commit at t=100
  A-->>P: token(t=100)
  P->>P: save new content with token(t=100)
  P->>C: Check(doc:plan, view, user:bob, at_least_as_fresh t=100)
  C->>C: choose snapshot t=102 (cached, >= 100)
  C->>S: read tuples at t=102
  C-->>P: allowed=false, checked_at t=102
```

**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

| Option | How | Cost | Verdict |
|---|---|---|---|
| A. No cache | Every check reads storage | 2 million reads/s at peak (3.3 with $h = 0$) | Rejected |
| B. Per-server cache | Each server caches its own results | Low hit ratio as fleet grows; hot keys duplicated everywhere | Partial |
| C. Distributed cache by consistent hashing | Each sub-problem key has an owner server; servers forward sub-checks to owners | One extra in-cluster hop for some sub-checks | **Chosen** |

**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.

| Option | How | Cost | Verdict |
|---|---|---|---|
| A. Recursive walk | Follow `group#member` usersets at check time | Latency grows with depth | Default for shallow namespaces |
| B. Flattened membership index | An index builder consumes the changelog and maintains (group, transitive member) pairs; checks do one lookup | Write amplification when a large group changes; index lag | **Chosen for `group` namespace** |
| C. Restrict nesting | Forbid nested groups | Product limitation | Rejected |

**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

| Option | How | Cost | Verdict |
|---|---|---|---|
| A. Check each candidate | Product fetches candidates, then `BatchCheck` | Wasted work when most candidates are denied | For pages of at most [100] items |
| B. ListObjects | Service walks the graph backwards from the subject | Expensive for subjects in many groups; must be bounded | **Chosen for small result sets** |
| C. Pre-filter in search index | Search documents carry the set of principals allowed to view; queries filter by the user's groups; final page is re-checked | Index lag; ACL changes reindex documents | **Chosen for full-text 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

<!-- Guidance: Show how the design meets the numbers in section 3 and where it breaks first. -->

| Concern | Approach | Limit before redesign |
|---|---|---|
| Check rate | Stateless servers, distributed cache | *Example:* Cache memory per region |
| Hot objects | Owner deduplication, quantized snapshots | One owner server's CPU per key |
| Storage reads | 32 shards, hedged reads | *Example:* 640 000 reads/s at 20 000 per shard |
| Write rate | Sharded commits, batched changelog | Cross-shard writes needing coordination |
| Nested groups | Flattened index | Index rebuild time after a large group change |
| ListObjects | Bounded results, pre-filter for search | Subjects in more than [10 000] groups |

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

| Step | Budget |
|---|---|
| Parse, authenticate caller, pick snapshot | 0.5 ms |
| Forward to cache owner (in-cluster hop) | 1.0 ms |
| Up to two parallel storage read rounds | 5.0 ms |
| Group index lookup | 1.5 ms |
| Headroom | 2.0 ms |

## 9. Reliability, security and operations

<!-- Guidance: Name the failure modes, the threats and the signals operators watch. Each mitigation must be testable. -->

### 9.1 Failure modes

| Component | Failure | Detection | Blast radius | Mitigation | RTO |
|---|---|---|---|---|---|
| Check servers | *Example:* Region fleet unavailable | Health checks, error rate | All products in region | Route to nearest region; clients fail closed | 5 min |
| Tuple store shard | *Example:* Leader loss | Store metrics, read errors on shard | Objects on that shard | Automatic leader election; reads from replicas at older snapshots where tokens allow | 1 min |
| Result cache | *Example:* Fleet restart empties caches | Hit ratio below 0.6 | Storage load doubles | Gradual rollout; warm from peers; admission control | 15 min |
| Group index | *Example:* Builder stalls | Index lag above 30 s | Nested-group checks slower | Fall back to recursive walk (7.3) | 30 min |
| Schema rollout | *Example:* Bad rewrite rule activated | Shadow diff, deny-rate spike | Every check in the namespace | Shadow mode; one-step rollback to previous version | 5 min |
| Client | *Example:* Product drops tokens | Share of checks without token | New-enemy exposure in that product | Client library defaults; conformance test | n/a |
| [Component] | [Failure] | [Signal] | [Scope] | [Mitigation] | [RTO] |

**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

| Threat | Control |
|---|---|
| Product service writes tuples outside its namespaces | Per-caller authorization on Write by namespace, enforced by the service |
| Privilege escalation through schema change | Schema changes require review by the schema owner and security; audited |
| Enumeration via ListSubjects | Restricted to callers with an admin scope |
| Tuple data reveals org structure | Encrypt at rest; tuples are confidential data |
| Denial of service by deep or wide graphs | Depth limit, fan-out limit, per-tenant quotas |
| [Threat] | [Control] |

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

| Signal | Metric | Alert threshold |
|---|---|---|
| Check latency | p95 and p99 per API and region | *Example:* p95 above 10 ms for 10 min |
| Cache hit ratio | Per region | *Example:* below 0.7 for 15 min |
| Snapshot age served | Distribution of (now minus snapshot) | *Example:* p99 above 10 s |
| Token usage | Share of checks with a token, per product | Drop of 20% vs. 7-day baseline |
| Depth and fan-out | p99 sub-requests per check | Above 50 |
| Watch lag | Oldest unconsumed change per subscriber | Above 60 s |

### 9.4 Cost estimate

| Item | Unit cost | Quantity | Monthly cost |
|---|---|---|---|
| Check servers | [USD per instance-month] | *Example:* 60 per region x 3 | [USD] |
| Tuple store | [USD per node-month and per TB] | *Example:* 32 shards x 3 replicas, 6 TB | [USD] |
| Group index store | [USD] | [Size] | [USD] |
| Cross-region replication traffic | [USD per GB] | [GB] | [USD] |
| **Total** | | | **[USD]** |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why you chose one. Include what changes at 10x and 0.1x scale. -->

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Model | Roles in each app; attribute policies; relationship tuples | Relationship tuples | Sharing, groups and hierarchy expressed as data | Learning curve; attributes need caveats later |
| Consistency | Full; bounded staleness; tokens | Tokens | Correct where it matters, cached elsewhere | Clients must store tokens |
| Store | Key-value store; sharded SQL; distributed SQL with external consistency | Distributed SQL | Snapshot reads at a timestamp across shards | Cost and operational expertise |
| Build or adopt | Build; adopt OpenFGA or SpiceDB; managed service | [Decision] | [Reason] | [Cost] |
| Lists | Check each; ListObjects; search pre-filter | Hybrid by result size | Bounded cost per call | Two code paths |
| **At 10x** (5 million checks/s) | | | Cache hit ratio and hot-key deduplication become the whole design; consider per-region read replicas of the group index and stricter fan-out limits | |
| **At 0.1x** (50 000 checks/s) | | | A single-region managed database plus an open-source engine is enough; drop the group index and distributed cache | |

## 11. Delivery plan and risks

<!-- Guidance: How the design reaches production safely and what could stop it. Migration of existing ACLs is usually the longest task. -->

### 11.1 Milestones

| Milestone | Scope | Exit criterion | Target date |
|---|---|---|---|
| M1 | Schema for documents and groups; Check and Write in one region | Conformance tests pass, including new-enemy tests | YYYY-MM-DD |
| M2 | Dual-run: products check both old logic and service, log differences | Difference rate below 0.01% for 14 days | YYYY-MM-DD |
| M3 | Service authoritative for documents | No P1 permission incidents for 30 days | YYYY-MM-DD |
| M4 | ListObjects and search pre-filter | Search leakage test passes | YYYY-MM-DD |
| M5 | Multi-region | Regional failover drill within RTO | YYYY-MM-DD |

### 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

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Products ignore tokens, reopening the new-enemy problem | High | High | Client library stores and forwards tokens by default | [@name] |
| R-02 | *Example:* Fan-out of one schema rule breaks latency | Medium | High | Fan-out budget per rule in schema review | [@name] |
| R-03 | *Example:* Backfill misses legacy edge cases | Medium | High | Dual-run comparison before cut-over | [@name] |
| R-04 | *Example:* Service becomes a single point of failure for all products | Medium | High | Multi-region, fail-closed client behaviour tested in game days | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

<!-- Guidance: Supporting detail, traceability, glossary and references. -->

### 12.1 Traceability

| Requirement | Design element | Verification |
|---|---|---|
| FR-01, NFR-01 | 7.2 caching, 8 latency budget | Load test |
| FR-06, NFR-03 | 7.1 tokens | Consistency test with injected replica lag |
| FR-05 | 5.3 `parent->view` | Schema conformance test |
| FR-07 | 7.4 | Leakage test against search |
| FR-10 | 7.5 | Shadow diff report |

### 12.2 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Do we need attribute conditions (caveats) in phase 1? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* How long do we retain snapshots for `at_exact_snapshot` paging? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.3 Glossary

| Term | Meaning |
|---|---|
| Relation tuple | A stored fact `object#relation@subject` |
| Userset | A set of subjects defined as "everyone with relation R on object O" |
| Rewrite rule | A rule computing one relation from others (union, intersection, exclusion, tuple-to-userset) |
| Consistency token (zookie) | Opaque value encoding a snapshot timestamp, returned by writes and accepted by reads |
| New-enemy problem | A check evaluated against permissions older than the content it protects |
| ReBAC | Relationship-based access control |
| Fan-out | Number of sub-checks or reads one check causes |

### 12.4 References

| Reference | Use |
|---|---|
| Pang et al., "Zanzibar: Google's Consistent, Global Authorization System", USENIX ATC 2019, pp. 33 to 46 | Model, tokens, caching, indexing; 7.5 box |
| OpenFGA documentation (openfga.dev), consistency modes and query APIs | Check, Expand, ListObjects, ListUsers; consistency options |
| SpiceDB documentation (authzed.com/docs), consistency and ZedTokens | Consistency modes in 4.1 |
| RFC 9457 Problem Details for HTTP APIs | Error bodies |
| System Design Document Template (`system-design/system-design-document`) | Parent structure |
| Distributed Key-Value Store System Design Template (`system-design/design-distributed-kv-store`) | Storage trade-offs |
| Threat Model Template (`security/threat-model`) | Threat analysis of this service |

## 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.