Designing Himeji: Airbnb’s Scalable Centralized Authorization System

Authorization plays a critical role in preventing unauthorized data access and platform abuse. While authentication verifies who an actor is, authorization determines what that actor is permitted to do.

Consider real-world access control challenges across modern platforms:

• Instagram: Ensuring private account posts are accessible only to approved followers.
• Airbnb: Revealing property Wi-Fi credentials or exact check-in locations only to users with confirmed reservations.
• Google Drive: Determining if a user can edit a file nested within a folder shared transitively with an indirect user group.

In a monolithic architecture, access checks are often simple in-process function calls against a single database. However, as organizations transition to microservices, distributed services need a low-latency, highly available, centralized source of truth for access decisions.

To solve this, Airbnb built Himeji, a centralized authorization engine designed to scale to millions of concurrent requests while supporting expressive, fine-grained access control. This article breaks down Himeji’s tuple-based data model, relational graph evaluations, and high-throughput distributed architecture.

---

1. The Core Data Model: Authorization as Tuples

Storing permissions as arbitrary relational tables across separate microservices leads to fragmented business logic and consistency anomalies. Inspired by Google’s Zanzibar paper, Himeji standardizes all permissions into unified relational tuples.

Every authorization rule in Himeji is represented as a 3-element tuple:

$\langle \text{Entity}, \text{Relation}, \text{Principal} \rangle$

• Entity: The resource or sub-resource being accessed. Formatted as entity_type:entity_id[:part] (e.g., post:123:comment, listing:101).
• Relation: The specific privilege or role on that entity (e.g., owner, read, write, guest).
• Principal: The actor attempting the operation, such as a user identity (user:123) or a reference to another entity relation.

Tuple Representation

In storage and query logic, these tuples are represented compactly using the following notation:

<entity>#<relation>@<principal>

Example

If user:123 has write permissions on the comments of post 456, the tuple is stored as:

post:456:comment#write@user:123

---

2. Preventing Tuple Explosion with Set Theory and Transitivity

A naive implementation of tuple-based access control would explicitly insert an authorization row for every allowable action. For example, if an author creates a post, the system would need to insert separate tuples for read, write, edit_comment, delete, and like. Storing permutations explicitly triggers a combinatorial tuple explosion that degrades write throughput and bloats storage.

Himeji solves this by applying set theory and transitive relation inheritance.

Relational Hierarchies as Unions

Instead of storing redundant permissions, relations are expressed hierarchically using set unions (logical OR):

$\text{write} = \text{write} \cup \text{owner}$ $\text{read} = \text{read} \cup \text{write} = \text{read} \cup \text{write} \cup \text{owner}$

By defining read as a union of explicit read rights and transitive write/owner rights, ownership automatically grants both read and write capabilities.

graph TD
    Owner[Owner] -->|implies| Write[Write]
    Write -->|implies| Read[Read]
    
    subgraph Permissions Evaluation
    Read --> UnionCheck{Evaluates Union}
    UnionCheck --> CheckRead[Check: entity#read@principal]
    UnionCheck --> CheckWrite[Check: entity#write@principal]
    UnionCheck --> CheckOwner[Check: entity#owner@principal]
    end

Evaluation Walkthrough

Suppose user:123 creates listing 1. The database stores only one tuple:

listing:1#owner@user:123

When a downstream service asks: “Can user:123 read listing:1?”, Himeji evaluates listing:1#read@user:123:

1. Expand read to $\text{read} \cup \text{write} \cup \text{owner}$.
2. Query listing:1#read@user:123 $\rightarrow$ False (not in DB).
3. Query listing:1#write@user:123 $\rightarrow$ False (not in DB).
4. Query listing:1#owner@user:123 $\rightarrow$ True (matches stored tuple).
5. Union evaluation: $\text{False} \lor \text{False} \lor \text{True} = \mathbf{True}$.

This configuration-driven approach keeps writes minimal ($O(1)$ tuple creation per resource creation) while allowing flexible role graphs.

---

3. Modeling Indirect and Nested Permissions (Entity References)

Real-world authorization often depends on dynamic business events or intermediate states. For example, Airbnb restricts access to a listing’s exact physical address until a guest books a confirmed reservation.

Himeji models this via entity references, allowing an authorization rule to traverse relationships between different domain entities.

Rule Definition

To access a listing’s location, the rule is defined as:

listing:$ID:location#read = owner UNION (listing:$ID#reservation @ reference(reservation:$RID#guest))

Database State

Consider three tuples stored in Himeji’s database:

1. listing:1#owner@user:123 (Host ownership)
2. listing:1#reservation@reference(reservation:500) (Listing linked to Reservation 500)
3. reservation:500#guest@user:456 (User 456 is the guest on Reservation 500)

Step-by-Step Resolution

A service checks: “Can user:456 read the location of listing:1?” (listing:1:location#read@user:456)

sequenceDiagram
    autonumber
    participant Client as Calling Service
    participant Engine as Himeji Engine
    participant DB as Storage / Cache

    Client->>Engine: Check listing:1:location#read for user:456
    Engine->>DB: Query listing:1#owner@user:456
    DB-->>Engine: False
    
    Engine->>DB: Resolve listing:1#reservation link
    DB-->>Engine: Returns reference(reservation:500)
    
    Engine->>DB: Query reservation:500#guest@user:456
    DB-->>Engine: True
    
    Engine-->>Client: Authorized (True)

1. Check Direct Ownership: Evaluates listing:1#owner@user:456 $\rightarrow$ Returns False.
2. Evaluate Reservation Dependency: Looks up active reservations linked to listing:1. The system discovers reference(reservation:500).
3. Resolve Referenced Entity: Substitutes $RID with 500 and evaluates whether the principal has the guest relation on reservation:500:

   reservation:500#guest@user:456

   This tuple exists in the database $\rightarrow$ Returns True.
4. Final Decision: The union evaluates to True, granting user:456 read access.

By treating relations as string templates with runtime entity replacement, complex multi-hop ACLs are simplified into deterministic key lookups.

---

4. The System Architecture

Himeji decomposes its end-to-end flow into three functional tiers: the Orchestration Layer, the Caching Layer, and the Persistent Data Layer.

graph TB
    Client[Downstream Microservices] 
    
    subgraph Orchestration Layer
        WriteService[Himeji Write Service]
        ReadService[Himeji Read Service / Engine]
    end

    subgraph Caching Layer
        CacheRing[Sharded & Replicated Cache Cluster]
    end

    subgraph Persistent Storage Layer
        DB[(Sharded Relational DB / MySQL)]
        CDC[Change Data Capture / Debezium]
        Kafka[(Apache Kafka)]
        Workers[Invalidation Workers]
    end

    Client -->|Writes / Mutations| WriteService
    WriteService -->|Direct Write| DB
    
    Client -->|Authorization Checks| ReadService
    ReadService -->|Consistent Hashing| CacheRing
    CacheRing -.->|Cache Miss Fallback| DB
    
    DB -->|Binlog Stream| CDC
    CDC -->|Mutation Events| Kafka
    Kafka --> Workers
    Workers -->|Invalidate Keys| CacheRing

Layer 1: Orchestration Layer

The entry point for client microservices, split across dedicated read and write paths:

• Write Flow: Straightforward and synchronous. Writes directly mutate tuples in the persistent storage layer.
• Read Flow: Evaluates access rules. To keep read operations fast and scalable, the read engine routes lookups through consistent hashing directly to the caching layer.

Layer 2: Sharded Caching Layer

Authorization checks occur on almost every RPC across Airbnb’s infrastructure. Himeji’s caching tier is optimized for high read throughput:

• 98% Cache Hit Rate: The vast majority of tuple lookups and evaluation graphs are served in-memory.
• Consistent Hashing: Keys are routed across a distributed cache cluster via consistent hashing, ensuring predictable data ownership and even load distribution.
• Replica Redundancy: Cache nodes are replicated so that if an instance crashes, adjacent nodes can immediately take over the hash space without hammering the database.

Layer 3: Persistent Data Layer

• The authoritative source of truth is a horizontally sharded relational database (e.g., MySQL).
• Each record stores the primary tuple components (entity, relation, principal) alongside metadata, indexed for point lookups.

---

5. Cache Invalidation via CDC and Apache Kafka

With a 98% cache hit rate, cache invalidation is critical. If a user cancels a reservation or their access is revoked, stale cache entries could allow unauthorized access.

To ensure low-latency cache consistency without adding latency to the write path, Himeji uses asynchronous Change Data Capture (CDC):

flowchart LR
    A[Database Mutation] -->|Commit to Binlog| B[CDC Engine]
    B -->|Publish Event| C[Kafka Topic]
    C -->|Consume| D[Invalidation Workers]
    D -->|Evict Stale Key| E[Himeji Cache Node]

1. Transactional Write: An authorization change (e.g., reservation cancellation) is committed to the sharded database.
2. CDC Emission: A CDC pipeline reads the database transaction logs (binlog) and converts row updates into event streams published to Apache Kafka.
3. Targeted Invalidation: Dedicated cache invalidation workers consume from Kafka, extract the mutated tuple, and evict the corresponding key from the cache cluster.
4. Read Repair: The next authorization check for that entity experiences a cache miss, loads the latest state from the database, and repopulates the cache.

This pattern decouples write processing from cache maintenance while keeping the cache invalidation lag small, predictable, and resilient to traffic spikes.

---

6. Architectural Trade-offs and Design Principles

Design Decision	Advantage	Trade-off / Cost
Tuple-Based Modeling	Universal schema across all microservices; eliminates fragmented authorization tables.	Requires recursive or iterative expansion for nested relationships.
Set Transitivity (Union)	Prevents combinatorial explosion of access entries in storage.	Increases evaluation read queries from 1 lookup to $N$ lookups across the hierarchy.
Asynchronous CDC Invalidation	Zero overhead on write path latency; guarantees cache updates are tied to committed transactions.	Introduces a brief window of eventual consistency bounded by Kafka replication and worker consumer lag.
Consistent Hashing Cache Ring	Deterministic key ownership with minimal key redistribution during cluster resizing.	Cache rebalancing cascades require replication to prevent sudden database fallback spikes.

---

Summary

Airbnb’s Himeji demonstrates how to scale fine-grained authorization in complex microservice environments:

1. Standardize on Tuples: Model permissions as $\langle \text{Entity}, \text{Relation}, \text{Principal} \rangle$.
2. Use Set Theory: Define transitive relationships through unions to eliminate redundant data.
3. Support Dynamic References: Allow rules to dynamically traverse domain models (e.g., listings to reservations).
4. Optimize the Read Path: Combine sharded caching with consistent hashing to achieve a 98% hit rate.
5. Automate Invalidation: Use CDC and Kafka to keep caches consistent with the underlying database without burdening the write path.