Dev Handbook
Handbook/System design

Design a social graph

A worked design for shortest-path queries across a sharded friendship graph.

3 min read·Dev Handbook
In this article

Define use cases and constraints

Use cases (in scope)

  • User searches for someone and sees the shortest path to that person.
  • Service has high availability.

Constraints and assumptions

  • Traffic is not evenly distributed; some searches are popular, others run once.
  • The graph does not fit on one machine; edges are unweighted.
  • 100 million users, ~50 friends each → 5 billion friend relationships.
  • 1 billion friend searches/month.

Usage

  • 400 searches/second.

Sketch the high-level design

Fig 1Traverse across the owning graph shards
STUDY MODEL
Inspect one part at a timeEntry
  1. Entry

    The client reaches a web server and Search API.

  2. Traversal

    The user-graph service explores graph neighbors with breadth-first search.

  3. Lookup

    A lookup service routes person IDs to their graph shard.

  4. Person servers

    Person servers A, B, and C hold the illustrated shards.

The graph service performs breadth-first search; lookup finds the shard that owns an ID.

How to read this model

A traversal carriage beside a shard-location catalogue. The object is a teaching analogy. Inspecting a part highlights its role; it does not execute or simulate the software. Cabinet trays are records, workpieces are data, and latches are checks. Unless an explanation states a quantity, compartments and sample workpieces do not denote data counts. Part dimensions are not a quantitative scale.

Define the core components

Without the scale constraint, an unweighted shortest path is a plain BFS. At scale, users are sharded across Person Servers, reached through a Lookup Service.

  1. Client → Web Server → Search API → User Graph Service.
  2. The User Graph Service uses the Lookup Service to find the Person Server holding a given person_id, then runs BFS using friend_ids as adjacent nodes.

Scale the design

Fig 2Reduce cross-shard traversal work
STUDY MODEL
Inspect one part at a timeEntry
  1. Entry

    DNS, a load balancer, and web servers precede the Query API.

  2. Graph service

    The user-graph service performs the traversal.

  3. Lookup and cache

    The lookup service routes IDs; memory cache supplies suitable hot results.

  4. Batched shards

    Person servers A, B, and C serve batched shard requests under the graph’s ownership rule.

Caching and batching reduce machine-to-machine calls during graph traversal.

How to read this model

A traversal console beside cached lookups and shard cabinets. The object is a teaching analogy. Inspecting a part highlights its role; it does not execute or simulate the software. Cabinet trays are records, workpieces are data, and latches are checks. Unless an explanation states a quantity, compartments and sample workpieces do not denote data counts. Part dimensions are not a quantitative scale.

  • 400 reads/s → serve person data from a memory cache; helps repeat searches and well-connected people.
  • Cache complete or partial BFS traversals; batch-compute offline and store in NoSQL.
  • Reduce machine jumps by batching friend lookups on the same Person Server; shard by location.
  • Run two BFS searches at once (source and destination) and merge paths.
  • Start BFS from high-degree people (fewer degrees of separation).
  • Set a hop/time limit before asking the user to continue.

Additional talking points

  • SQL scaling patterns and NoSQL: see database.
  • A graph database (Neo4j) would be natural here if not for the constraint: see graph database.
Keep track of your reading.

Your reading progress stays in this browser.