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 networkround trip. The primer marks the repeated lookup as a "potential for optimization".
Why it gets expensive
If everyone had bwhat its symbols mean friends and no friends were shared, BFS would reach about bdwhat its symbols mean people within dwhat its symbols mean hops. With b=100 and d=4:
bd=1004=108what 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×104what 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 NoSQLdatabase.
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.
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 bwhat its symbols mean friends the search reaches about bdwhat its symbols mean people in dwhat its symbols mean hops.
Searching from both ends reaches about 2⋅bd/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.