How Airbnb Migrated Its 7 Billion Node Identity Graph to an Internal Knowledge Graph Platform

Why a Knowledge Graph Matters for Trust & Safety

Every large platform faces a fundamental challenge: understanding how users, devices, and accounts are connected. For Airbnb, these connections are critical for detecting fraud, preventing account takeovers, and enforcing trust policies.

Airbnb’s identity graph is the backbone of this effort. It models users and their relationships as vertices and edges in a graph database, enabling queries like:

• “Is this new account linked to any previously banned accounts?”
• “Does this device ID appear across multiple suspicious bookings?”

As the platform grew, the graph exploded in complexity — 7 billion nodes, 11 billion edges, growing by 5 million edges per day. The original architecture couldn’t keep up. This case study walks through the evolution, the migration to an internal knowledge graph infrastructure, and the key optimizations that made it work.

The Three Iterations of the Identity Graph

Phase 1: Relational + KV Store

Initially, Airbnb stored user data in a relational database and edge lists as JSON blobs in a key-value store. As graph density increased, joining tables became prohibitively expensive, and the JSON approach made traversal queries slow and brittle.

Pain points: High cost, poor scalability, no native graph traversal.

Phase 2: Third-Party SaaS Graph Database

In 2021, Airbnb adopted a managed PaaS graph database. This improved horizontal scalability and introduced a real graph query language (Gremlin). However, it came with new challenges:

• Long-tail latency: High-fanout nodes caused P99 latency to spike unpredictably.
• Operational instability: Periodic manual instance reboots were required to maintain performance.
• Limited control: Fine-grained indexing and query tuning were difficult or impossible.
• Vendor lock-in: Migrating away would be costly if needs changed.

Phase 3: Internal Knowledge Graph Infrastructure

In 2024, Airbnb built a paved-path graph platform based on JanusGraph (an open-source distributed graph database) with DynamoDB as the storage backend and OpenSearch for indexing. The identity graph was the first tenant to migrate.

Why JanusGraph + DynamoDB?

• Storage separation allowed Airbnb to leverage DynamoDB’s proven scalability while controlling the graph logic layer.
• Gremlin query language was preserved, making migration easier.
• Open source codebase meant full visibility and ability to patch.

// Example Gremlin query used in identity graph
// Find all accounts linked to a given user within 3 hops
g.V().has('user_id', 'target_user')
  .repeat(__.bothE('linked_account').otherV().simplePath())
  .times(3)
  .path()
  .limit(100)

Key Optimizations for Performance

To meet Airbnb’s strict latency requirements, the team made several deep changes to the JanusGraph engine:

1. Optimized transactions: Replaced JanusGraph’s default locking with DynamoDB’s conditional writes and transaction APIs, reducing overhead while maintaining data integrity.
2. Parallel query execution: The getMultiSlices interface was improved to fetch data in parallel, cutting latency for high-fanout queries (e.g., a user with thousands of linked accounts).
3. Client-side query rewriting:
   • Removed Path steps where possible, replacing them with conditional acyclic checks to avoid falling back to slow non-batched backend queries.
   • Optimized side-effect steps to minimize computation within aggregation operations.
4. Observability: Integrated Airbnb’s distributed tracing into the internal fork, closing the observability gap that existed in the open source version.

// Simplified example of client-side query optimization
// Before: using path() step (can be slow)
// After: using dedup() and where() to ensure acyclic results
g.V().has('user_id', 'target')
  .repeat(__.bothE('linked').otherV().dedup())
  .times(3)
  .where(without('visited'))
  .dedup()

Migration Strategy: Side-by-Side with Shadow Traffic

Airbnb didn’t flip a switch. The migration used a careful shadow traffic approach:

1. Both the old vendor solution and the new internal solution ran in parallel.
2. Both engines supported Gremlin, so identical queries could be benchmarked side-by-side.
3. After benchmarking confirmed the internal solution met latency and throughput targets, production traffic was gradually shifted.

Results: What Did Airbnb Gain?

Limitations and Caveats

• JanusGraph is not a silver bullet. It requires significant operational expertise to tune, especially for high-fanout workloads.
• Storage separation adds complexity. While beneficial, managing both JanusGraph and DynamoDB means more moving parts than an all-in-one solution.
• Gremlin query optimization is still manual. The client-side rewriting described above required deep understanding of both the data and the query engine.
• Not all use cases benefit equally. Queries with very few hops (1–2) may not see dramatic gains; the biggest wins are in multi-hop traversals.

Conclusion: Build vs. Buy — A Data Point for Your Architecture

Airbnb’s journey is a powerful case study for any team considering a knowledge graph infrastructure. The decision to build an internal platform paid off in:

• Performance: 10x write throughput and significantly lower P99 latency.
• Control: Full ability to tune, patch, and evolve the graph engine.
• Stability: No more manual reboots, faster incident resolution.

However, this approach is not for everyone. If your graph workload is small (< 1B edges) or your team lacks graph database expertise, a managed PaaS may still be the right choice. But if you’re scaling to billions of nodes and need sub-100ms traversal queries, the internal path is worth considering.

Next steps for your learning:

• Controlling Floating-Point Determinism in CUDA: A Deep Dive into CUB's New API — another deep dive into performance-critical infrastructure.
• Building the Perfect Pie Chart in CSS: A Semantic and Accessible Approach — a completely different domain, but shows the same principle of choosing the right tool for the job.

Source: This analysis is based on Airbnb Engineering’s post on Scaling Airbnb’s identity graph with a unified knowledge graph infrastructure.