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:

  1. asks the Lookup Service which Person Server holds that person;
  2. fetches the person, and their friend_ids, from that server;
  3. 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 bbwhat its symbols mean friends and no friends were shared, BFS would reach about bdb^dwhat its symbols mean people within ddwhat its symbols mean hops. With b=100b = 100 and d=4d = 4:

bd=1004=108b^d = 100^4 = 10^8what its symbols mean

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⋅bd/2=2×1002=2×1042 \cdot b^{d/2} = 2 \times 100^2 = 2 \times 10^4what its symbols mean

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 side whose frontier, the people it reached last, is smaller. 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 fetch from a Person Server.

Path length (hops)
4
One-sided BFS: lists fetched
581
Bidirectional: lists fetched
27
Fewer fetches
21.5×
Path found: u0 → u4 → u2116 → u1362 → u4999
The idealized formula
bd = 6,250,000 versus 2·bd/2 = 5,000. This assumes a tree with no shared friends; real graphs overlap, so the measured gain above is smaller.
Users1× instanceWeb server (reverseproxy)2× instancesSearch API2× instancesUser Graph Service2× instancesMemory cache(people)2× instancesLookup Service2× instancesPerson Servers(sharded)4× instancesUsers1× instanceWeb server (reverseproxy)2× instancesSearch API2× instancesUser Graph Service2× instancesMemory cache(people)2× instancesLookup Service2× instancesPerson Servers(sharded)4× instances
Figure 2

Searching from both ends: the User Graph Service runs one search from each person, with people kept in a memory cache.

The User Graph Service runs two breadth-first searches for each request, one from the searcher and one from the person searched for, a level at a time, and stops when they meet. Each person either search visits is read from the memory cache when it is there; a miss asks the Lookup Service for the person’s server and fetches the person from that Person Server. Caching people, and batching the friends that live on one Person Server into one request, cut the round trips that the lesson counts. Counts as in figure 1: the primer’s 400 searches a second at 1,000 a second per server, plus one spare, a cache node and a spare, and four Person Servers.

  • Users: 1 × Users
  • Web server (reverse proxy): 2 × Load balancer
  • Search API: 2 × App server
  • User Graph Service: 2 × App server
  • Memory cache (people): 2 × Cache
  • Lookup Service: 2 × App server
  • Person Servers (sharded): 4 × NoSQL store
  • Users sends requests to Web server (reverse proxy)
  • Web server (reverse proxy) sends requests to Search API
  • Search API sends requests to User Graph Service
  • User Graph Service sends requests to Memory cache (people)
  • User Graph Service sends requests to Lookup Service
  • User Graph Service sends requests to Person Servers (sharded)

Key takeaways

  • Each person visited costs a lookup and a fetch, and with bbwhat its symbols mean friends the search reaches about bdb^dwhat its symbols mean people in ddwhat its symbols mean hops.
  • Searching from both ends reaches about 2⋅bd/22 \cdot b^{d/2}: in the idealized tree with b=100b = 100, d=4d = 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.
Sources2