Authorization & Account Systems — Graph Traversal, Isolation, Non-repudiation Behind One CheckRBAC vs ABAC vs ReBAC · Multi-tenancy · Audit Log

Problem Scenario + Requirements

Design the authorization system for a B2B SaaS platform (think Notion / GitHub / Figma): the org structure is Org → Team → Project → Resource, four levels with cascading inheritance — an Org admin can touch everything, a Project member only their own project. It looks like a simple "can this user read this doc?", but it's the hottest path every API request must pass through: one mistake is a privilege-escalation leak, one slow check drags down the whole site.

Treat it as a real system and size it:

• Tenants: 100K Orgs; the largest Org has 50K users and millions of resources.
• QPS: one page render does tens to hundreds of checks (one per list row), so peak authorization-check QPS exceeds 500K — an order of magnitude above business QPS.
• Latency SLO: check p99 < 10ms (the real numbers Zanzibar/Himeji hit), or it dominates total request latency.
• Correctness: default deny; revocation must take effect fast (a stale cache must not let an ejected user keep reading).
• Isolation: tenant data physically/logically isolated — one tenant must never read another's data.
• Auditability: who changed whose permission, when, and what they accessed — traceable and tamper-evident (SOC2 / GDPR).

This issue covers four things: what model expresses permissions, how to compute hierarchical inheritance fast, how to isolate tenants, and how to make the audit log non-repudiable.

High-Level Architecture

graph TD
    APP["Service
API / frontend BFF"]
    PDP["Policy Decision Point
Check(user, perm, obj)?"]
    CACHE["Permission cache
sharded+replicated · in-mem filter"]
    STORE["Relation store
relation tuples · Postgres/Spanner"]
    CDC["CDC / invalidation
binlog → Kafka"]
    AUDIT["Audit log
append-only · hash chain"]
    APP -->|"1. check"| PDP
    PDP -->|"2. hit"| CACHE
    CACHE -->|"3. miss → origin"| STORE
    STORE -->|"4. mutation"| CDC
    CDC -->|"5. invalidate"| CACHE
    APP -->|"6. perm change / sensitive access"| AUDIT

The PDP (Policy Decision Point) is the core: business code never judges permissions itself — it asks the PDP "does this subject have this permission on this object?". The PDP centralizes both the decision logic (policy) and the decision data (who's in which group, who owns what) — authorization logic pushed down to the data layer rather than scattered across every microservice, the shared centralizing philosophy of both Airbnb Himeji and Google Zanzibar. The cache layer is sharded + replicated and filters relations in memory, hitting origin only on miss; the write path turns mutations into cache-invalidation events via CDC. The audit log is a side channel — independent, never on the check hot path.

Key Technical Points

① Authorization model: RBAC vs ABAC vs ReBAC — express permissions via "roles", "attributes", or "relationships"

Trade-off in one line: RBAC is simple but roles explode; ABAC is flexible but hard to audit and hard to answer "who can access X"; ReBAC (Zanzibar-style) naturally expresses hierarchy and sharing but you must build a graph-traversal engine.

[Principle] The three models answer the same question with different data structures:

• RBAC: user → role → permission. "Alice is admin, admin can delete." A decision is a table lookup.
• ABAC: a boolean expression over attributes. "if user.dept == resource.dept && time < 18:00 then allow." A decision is evaluating a policy (e.g. OPA/Rego, AWS IAM policy).
• ReBAC: model permissions as relation tuples between objects (object#relation@subject); a decision is a reachability traversal over the relation graph. "doc:readme#viewer@user:alice", "doc:readme#viewer@group:eng#member" — a viewer can be a user or "all members of group eng", so hierarchy and sharing unfold naturally. This is Google Zanzibar's core abstraction.

[Pseudo-code] A ReBAC check is essentially a recursive graph traversal with "userset rewrite":

# pseudo-code — Zanzibar-style check: does obj's relation contain subject?
def check(obj, relation, subject) -> bool:
    for tuple in tuples(obj, relation):          # read (obj#relation@?)
        u = tuple.subject
        if u == subject:
            return True                          # direct hit
        if u.is_userset():                       # e.g. group:eng#member
            if check(u.obj, u.relation, subject):# recursively expand userset
                return True
    # userset rewrite: viewer inherits from editor, owner, or parent's viewer
    for rule in rewrite_rules(obj.type, relation):   # e.g. viewer = editor + parent.viewer
        if check_rewrite(obj, rule, subject):
            return True
    return False

The magic is in rewrite_rules: viewer = self | editor | parent→viewer lets permissions cascade down the hierarchy — no need to copy permissions onto every resource.

② Hierarchical inheritance & check performance — deep traversal vs materialized reverse index

Trade-off in one line: real-time recursive traversal is cheap to write but expensive to read (long latency tail on deep hierarchies); materialized expansion is fast to read but amplifies writes and adds invalidation-consistency problems.

[Principle] With Org→Team→Project→Doc four levels, "can Alice read this doc?" may have to climb from the doc up to the Org and expand the whole group tree — one check triggers dozens of tuple reads, and depth and fan-out determine the tail latency. Two optimization routes:

• Real-time traversal + cache sub-results: cache and reuse each intermediate decision like check(group:eng, member, alice); merge concurrent origin reads with single-flight. Simple, cheap writes, but p99 jitter on cold cache or deep graphs.
• Materialized reverse index: pre-expand and store "object → all users with access" or "user → all accessible objects", so a check degrades to one lookup. Zanzibar's Leopard index precomputes flattened membership sets for deep/wide nested groups. The cost is write amplification (one group change updates a huge number of materialized rows) and invalidation complexity.

Consistency pitfall: permission revocation must take effect promptly, or "someone just removed from a project can still read for 5 minutes" is a security incident. Zanzibar uses a Zookie (a token carrying a timestamp) to guarantee "a permission read is no older than a given write", binding external consistency to cache freshness — the key thing that sets it apart from an ordinary cache.

# pseudo-code — fast revocation: version + CDC invalidation, not pure TTL
def revoke(group, member):
    db.delete(tuple(group, "member", member))      # 1. persist
    bump_version(group)                            # 2. bump that object's perm version
    cdc.publish(InvalidateEvent(group))           # 3. binlog→Kafka→cache nodes drop key
# read side: cache entries carry version; check validates version not stale, else origin

③ Multi-tenant isolation — shared DB row-level vs schema-per-tenant vs DB-per-tenant

Trade-off in one line: a shared DB saves cost but "miss one WHERE and you leak across tenants"; a DB-per-tenant gives the strongest isolation but ops/migration cost explodes linearly with tenant count.

[Principle] Three isolation tiers map to three cost tiers:

Mainstream SaaS defaults to shared DB + row-level (cost wins) and uses Postgres Row-Level Security (RLS) to turn "forgot WHERE" from a human discipline into a database-enforced guarantee: once the policy is set and the connection sets app.tenant_id, the DB automatically appends the tenant filter to every query — no leak even if the app forgets it. Large customers (with physical-isolation compliance) then get a dedicated DB, a hybrid tiered approach.

-- Postgres RLS: push tenant isolation down to the database
ALTER TABLE documents ENABLE ROW LEVEL SECURITY;
CREATE POLICY tenant_isolation ON documents
  USING (tenant_id = current_setting('app.tenant_id')::uuid);
-- each connection, when entering a tenant context:
SET app.tenant_id = '...';   -- all queries afterward are auto-filtered, no manual WHERE

④ Audit log — append-only and tamper-evidence

Trade-off in one line: audit must be written inside the business transaction so it isn't lost, yet must not slow/pollute the business DB; to be trustworthy it must resist tampering, but "fully immutable" conflicts with "operable".

[Principle] The fundamental difference from ordinary logging: an audit log is evidence and must be complete (no lost events), tamper-evident (unchangeable after the fact), traceable (who/what/when/from where).

• No loss: write critical events like permission changes via the Outbox pattern (see Day 7) — the audit record and the business mutation in the same transaction, then CDC ships it to audit storage, avoiding "business succeeded but audit lost".
• Tamper-evident: append-only + a hash chain — each record stores hash(prev_hash + payload); alter any middle record and every subsequent hash breaks, exposing the tampering. Periodically anchor the chain head to an external store (WORM / notarization) to even defend against deleting whole segments.
• No business impact: audit goes to independent storage (append-optimized columnar/object store), separate from OLTP; queries are low-frequency analytics, off the business hot path.

# pseudo-code — hash-chained audit, tampering detectable
def append_audit(event):
    prev = store.last()                  # take previous record
    record = {
        "actor": event.actor, "action": event.action,
        "target": event.target, "ts": now(),
        "prev_hash": prev.hash,
    }
    record["hash"] = sha256(prev.hash + canonical_json(record))
    store.append(record)                 # append-only, never UPDATE/DELETE

def verify():                            # patrol: recompute each hash, alert on break
    for r in store.scan():
        assert r["hash"] == sha256(r["prev_hash"] + canonical_json(strip_hash(r)))

Scaling & Optimization

• From embedded to centralized PDP: early on, permissions live in each service as if user.role==...; at scale, extract a centralized authorization service (Zanzibar/Himeji/OpenFGA) for unified model, audit, and caching.
• Read/write split + reverse index: for "which projects can I see", use a materialized user→objects reverse index instead of checking each object one by one (N+1 authorization).
• Policy as code: model ABAC with OPA/Rego to version, test, and canary policies, avoiding hand-editing rules in production.
• Cache warming & degradation: authorization is the hottest path; warm cold starts from historical hot keys; when the PDP is unavailable, fail-closed (default deny) not fail-open — availability yields to security.

Common Pitfalls + Interview Follow-ups

• Fail-open vs fail-closed: what if the authz service dies? Fail-closed (deny) is almost always right — better to reject legitimate requests than allow escalation. But weigh it: denying all on a core read path takes the whole site down, so limited degradation may be OK for low-sensitivity operations.
• N+1 authorization: 100 list rows = 100 checks, p99 amplified. Use BatchCheck or a reverse index to get the full set at once. "How do you do list-page permission filtering" is a classic.
• Revocation lag: pure TTL caches delay revocation until expiry. You must invalidate actively via CDC/version — "how fast does ejection take effect" is a classic follow-up.
• RLS connection-pool context leak: reusing a connection without RESET of tenant_id → cross-tenant read. Don't forget BYPASSRLS roles and migrations skipping policies.
• Using the business DB as audit source: if a business table can UPDATE, it isn't trustworthy audit. Audit must be append-only + tamper-evident + independent storage.
• Baking permissions into a JWT, then unable to revoke: with many permission claims inside the JWT, a permission change leaves the old token valid (see Day 24). Authorization decisions should hit the PDP live; the JWT carries identity only.

Deeper Resources

• Zanzibar: Google's Consistent, Global Authorization System — USENIX ATC 2019, the foundational ReBAC paper (relation tuples, userset rewrite, Zookie, Leopard index).
• Himeji: a scalable centralized system for authorization at Airbnb — an industrial Zanzibar implementation (sharded cache, CDC invalidation, Aurora storage).
• OpenFGA · Authorization Concepts — RBAC / ABAC / ReBAC / Zanzibar concept comparison and a hands-on implementation (Auth0/Okta, CNCF).
• The data model behind Notion's flexibility — permission inheritance via block tree + parent pointer.
• PostgreSQL · Row Security Policies — native database implementation of row-level multi-tenant isolation.
• Designing Data-Intensive Applications (Kleppmann) — the consistency & causality chapters, to understand the external consistency behind Zookie.

Deeper Thinking