Design a Graph Search Function for a Social Network

Functional

Graph search lets users query the interconnected data of a social network using structured, relationship-aware queries. Unlike traditional text search (which matches keywords against documents), graph search answers questions like "friends of mine who live in New York and like hiking" - queries where who is asking changes the results entirely.

Think of it as SQL for your social graph, but with a natural-language-like interface that non-technical users can construct through autocomplete.

Graph Size

• Users: 2 billion user nodes
• Entity nodes: 500 million (pages, groups, places, events, interests)
• Edges: Each user averages 150 friend connections (bidirectional = 2 directed edges), plus roughly 200 "like" edges, 50 group memberships, and 30 place check-ins. That gives us approximately 2B x 430 = 860 billion directed edges in the graph. Stored as adjacency lists, this is the core data structure.
• Graph storage: Each edge is roughly 32 bytes (source_id 8B + edge_type 4B + target_id 8B + timestamp 8B + metadata 4B). 860B edges x 32B = roughly 27TB of raw edge data. With replication factor 3, that is about 80TB across the cluster.

Why express edges as directed? Because graph traversal is directional. "Friends of User A" reads A's outgoing friend edges. "Who friended User A" reads incoming edges. Storing both directions doubles storage but makes every adjacency list lookup O(1) instead of requiring a full scan for reverse lookups.

The API splits into four concerns: main search, autocomplete, structured query building, and direct graph browsing.

Main Search

1GET /v1/search?q=friends+who+like+hiking+in+Seattle
2&type=user
3&limit=20
4&cursor=eyJvZmZzZXQiOjIwfQ

The storage layer splits into four specialized stores, each optimized for its access pattern.

Graph Store (TAO-like)

The core graph uses an adjacency list model stored in a sharded key-value store, modeled after Facebook's TAO (The Associations and Objects) system.

The architecture separates the read path (search queries) from the write path (graph mutations), connected by an asynchronous indexing pipeline.

Read Path (Search Query)

Search Flow

Let us trace "friends who like hiking in Seattle" from keystroke to results.

Query Planner: The GATE Component

The query planner is the intellectual core of graph search. It takes a parsed query and produces an execution DAG - a directed acyclic graph of operations that, when executed, yields the result set. The planner's decisions determine whether a query takes 50ms or 5 seconds.

Graph Database (Neo4j) vs Custom Graph Store (TAO)

A dedicated graph database like Neo4j provides a rich query language (Cypher), built-in traversal algorithms, and ACID transactions. At Facebook's scale, Neo4j falls short: it does not natively shard across thousands of machines, its general-purpose query optimizer cannot match a custom planner tuned for the specific query patterns of social search, and the operational cost of running a complex graph database at 300 billion edges is prohibitive.

TAO is purpose-built: a thin graph abstraction over sharded MySQL with a massive cache layer. It sacrifices graph query flexibility for horizontal scalability and operational simplicity. The trade-off is that every new query pattern requires explicit engineering in the query planner rather than writing a Cypher query.

Celebrity Node Fan-out

A user with 1 billion followers creates a graph traversal explosion. Querying "friends of [celebrity]" attempts to traverse 1 billion edges - a single query that could consume an entire shard's resources.

Mitigation: Detect high-degree nodes (more than 100K connections) and apply special handling. For outgoing traversals from celebrities, use sampling: instead of traversing all 1B followers, sample 10K representative followers and extrapolate. For incoming traversals ("celebrities who like hiking"), index celebrities separately with higher priority. Set per-query resource budgets (maximum 50K edges traversed per query) to prevent any single query from monopolizing shard capacity.

Semantic Natural Language Search

The current grammar-based parser handles structured queries but fails on natural language like "people I met at the conference last week." This requires temporal reasoning ("last week"), event inference ("the conference" means a specific event the user attended), and co-attendance detection (other users who checked into the same event). An ML-based query understanding layer would parse these queries into structured graph operations, dramatically expanding what users can search for.