Design a Social Graph Search

TL;DR. Breadth-first search finds the shortest path, but on a graph spread across many servers each hop becomes a network call and the search area explodes. Batch lookups by shard, search from both ends at once, limit the depth, and cache what you can.

Learning Objectives

• Store a large graph as adjacency lists across shards
• Explain why a naive distributed BFS is too slow
• Use bidirectional search to cut the work dramatically
• Choose suitable limits and caching for path queries

Intuition

You want to reach someone through friends of friends. Asking everyone you know, then everyone they know, soon means thousands of phone calls. It is much quicker if the target also starts asking outward, and you stop when the two groups find someone in common. Each side only has to go about halfway.

Requirements

Functional

• A user searches for someone and sees the shortest chain of friends connecting them.

Non-functional

• High availability.
• Traffic is uneven, with some searches repeated often.
• The graph does not fit on one machine.

Assumptions: 100 million users, 50 friends each on average, 1 billion searches a month. Edges are unweighted. As an exercise in fundamentals, use general-purpose storage rather than a dedicated graph database.

Capacity Estimation

The raw adjacency data is smaller than you might expect, so it may not be size that forces sharding. Sharding lets you handle the traffic, and keep the lists in memory.

The search area is the real challenge. With 50 friends each, one-directional BFS can reach:

Real networks overlap, so actual counts are lower, but the growth is what matters.

API and Data Model

GET /api/v1/connections/path?from=123&to=456&max_hops=4

{ "path": [123, 87, 912, 456], "hops": 3 }

Each person’s record is an adjacency list:

person:123 -> { name, friend_ids: [87, 412, 950, ...] }

High-Level Architecture

flowchart LR
    C["Client"] --> A["Search API"]
    A --> G["Graph service"]
    G --> M["Path cache"]
    G --> L["Lookup service"]
    G --> P1["Person shard 1"]
    G --> P2["Person shard 2"]
    G --> P3["Person shard 3"]

Deep Dives

Sharding people

Hash the user ID to choose a shard, either by calculating it or through a small lookup service:

def shard_for(person_id):
    return person_id % NUM_SHARDS  # use consistent hashing in production

Consistent hashing avoids moving most people when shards are added. Each friendship is stored on both people’s lists, so a read only touches one person’s shard. Adding a friendship then writes to two shards, which needs a retry or an outbox so the lists do not drift apart.

The problem with a basic search

A textbook BFS fetches one person at a time:

from collections import deque

def shortest_path(source, target):
    queue = deque([source])
    parent = {source: None}
    while queue:
        person = queue.popleft()
        if person == target:
            return build_path(parent, target)
        for friend in get_friends(person):  # a network call per person
            if friend not in parent:
                parent[friend] = person
                queue.append(friend)

At three hops that can mean 125,000 network calls for one search. Two changes fix most of this.

Batching by shard

Search one level at a time. Group that level’s people by shard and make one request to each shard, rather than one per person:

def expand(level):
    by_shard = group_by(level, shard_for)
    responses = parallel(fetch_friends(shard, ids) for shard, ids in by_shard.items())
    return merge(responses)

The number of calls per level now depends on the number of shards, not the number of people.

Searching from both ends

Run the search from both people, always expanding the smaller side, and stop when the two sides meet.

flowchart LR
    A["Source"] --> B["Source's friends"]
    B --> C["Friends of friends"]
    C --> D["Meeting point"]
    D --> E["Target's friends of friends"]
    E --> F["Target's friends"]
    F --> G["Target"]

For a path of 4 hops, each side goes 2 hops, reaching about 2,500 people on each side, rather than up to 6.25 million one way. For precise shortest paths, stop only after finishing the level where the sides first meet, and check for any shorter joined path.

Limits and caching

• Limit the depth. A max_hops of 3 or 4 fits how a feature such as “how you’re connected” is used, and past that the answer is rarely interesting.
• Set a time budget. If it runs out, return “no close connection found” instead of waiting.
• Watch out for very popular accounts. Someone with millions of connections makes one expansion huge. Cap how many friends you expand, or skip them, and accept a result that may not be the very shortest.
• Cache results. Keep popular paths with a TTL. A slightly old path is usually fine, as long as you check a friendship has not ended before showing it.
• Precompute nearby people. Storing each user’s 2-hop neighbourhood makes common queries fast, but costs a lot of storage and refresh work. Consider it for active users only.

Privacy

A person may hide their friend list, or block someone. Check these rules when showing a path, and remember that even proving a connection exists can reveal private information.

Trade-offs

Scaling and Failure Modes

Common Pitfalls

Fetching one person at a time over the network. It is correct and works on small tests, then collapses at scale. Batch by level and shard.

No limits. A single search across a connected graph could touch a huge share of your data. Always set a depth and time limit.

Forgetting the cycle check. Without a visited set, a search keeps revisiting the same people in a graph full of cycles.

Ignoring privacy. A path can reveal friendships someone chose to hide.

Exercise

Add a “people you may know” feature that ranks friends of friends by the number of mutual friends. Should it run during the request or ahead of time?

Key Takeaways

• Each hop multiplies the search area, so a plain BFS on a sharded graph is too slow.
• Batching by shard cuts network calls, while bidirectional search cuts the people visited.
• Depth limits and time budgets keep latency predictable.
• Popular accounts need special handling.
• A graph database is an option, but its traversals are subject to the same physics once data spans machines.

Further Reading

• Graph databases
• Consistent hashing
• Database partitioning and sharding

Flashcards

References

• Donne Martin, “Design the data structures for a social network,” The System Design Primer. https://github.com/donnemartin/system-design-primer/tree/master/solutions/system_design/social_graph