Lesson 13.2• 8 min read

Graph traversal and bidirectional BFS

BFS across servers, searching from both ends (b^d versus 2·b^(d/2) in an idealized tree), stopping correctly, and the primer’s other optimizations.

What you will learn

Find a shortest path with breadth-first search when every step is a network call.
Explain why the search grows so fast with each hop.
Search from both ends, stop correctly, and apply the primer's other optimizations.

Breadth-first search across servers

Edges are unweighted, so breadth-first search finds a shortest path: explore everyone one hop away, then two hops, and so on, remembering each person's predecessor.

In the primer's design, the User Graph Service runs the BFS. For each person it visits, it:

asks the Lookup Service which Person Server holds that person;
fetches the person, and their friend_ids, from that server;
queues the friends it has not seen yet.

Every expansion is therefore a network round trip. The primer marks the repeated lookup as a "potential for optimization".

Why it gets expensive

If everyone had $b$ friends and no friends were shared, BFS would reach about $b^d$ people within $d$ hops. With $b = 100$ and $d = 4$ :

b^d = 100^4 = 10^8

Real graphs share many friends, so the true count is lower, but it still grows very fast with each hop.

Searching from both ends

The primer's first suggested optimization: "Do two BFS searches at the same time, one starting from the source, and one from the destination, then merge the two paths." Each side only needs to go about half the distance:

2 \cdot b^{d/2} = 2 \times 100^2 = 2 \times 10^4

In this idealized tree that is 5,000 times fewer people reached. On real, overlapping graphs the saving is smaller but still large. The visual runs both searches on a random graph and counts the friend lists each one fetches.

Stopping correctly. Expand one whole level at a time, usually on the smaller frontier. When a level reaches people the other search has already seen, finish that level, then take the meeting point with the smallest total distance. Stopping at the very first contact can return a path that is longer than necessary.

The primer's other optimizations

Cache people, and complete or partial BFS results, in a memory cache such as Redis or Memcached. This helps "people who do multiple searches in succession" and well-connected people.
Batch compute offline complete or partial traversals and store them in a NoSQL database.
Reduce machine jumps by batching the friend lookups that live on the same Person Server.
Start from people with many friends, as they are more likely to shorten the path.
Limit the search by time or number of hops, then ask the user whether to continue.
Without the no-graph-database rule, use a graph database or graph query language.

BFS from one side or both

Both searches run for real on a random friendship graph. Each friend list fetched would be a lookup on some person server.

Users5,000

Average friends10

Path length (hops)

One-sided BFS: lists fetched

581

Bidirectional: lists fetched

Fewer fetches

21.5×

Path found: u0 → u4 → u2116 → u1362 → u4999

The idealized formula

Branching factor b50

Distance d4

b^d = 6,250,000 versus 2·b^d/2 = 5,000. This assumes a tree with no shared friends; real graphs overlap, so the measured gain above is smaller.

Figure 2: Distributed Bidirectional BFS pathfinding architecture coordinating forward and backward traversal workers across distributed in-memory graph cache clusters.

Key takeaways

Each person visited costs a lookup and a fetch, and with $b$ friends the search reaches about $b^d$ people in $d$ hops.
Searching from both ends reaches about $2 \cdot b^{d/2}$ : in the idealized tree with $b = 100$ , $d = 4$ , 5,000 times fewer.
Expand whole levels, usually the smaller side; when the two meet, finish the level before choosing the shortest meeting point.
Cache people and partial results, batch lookups on the same server, and limit the search by time or hops.

Sources

System Design Primer: Design the data structures for a social network, shortest path and scaling

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.