Design A Typeahead


Facebook Typeahead

Screen Shot 2015-09-30 at 10.30.58 PM

1. Preload 1st Degree Data into Browser Cache

Screen Shot 2015-09-30 at 10.41.43 PM

Once Alice clicks the search box, it sends off a request(basically calling first-degree.php in this case) to retrieve all of the user’s direct friends, pages, groups, applications, and upcoming events. Then save it in the browser cache. So that it can immediately show the results without sending another request. 

2. AJAX request and Load Balancer

Screen Shot 2015-09-30 at 10.46.25 PM

Now Alice types ‘B’, it should first show Bob since it is in the browser cache. Then it fires an ajax request (typeahead.php in this case), the load balancer is responsible for routing the request to different servers. Typically each server only handles one specific category of results(friend-of-friend, object-of-friend, events, etc). 

Those blue rectangles are services which could be applied on multiple machines. The global service is for something which are independent to querying user. Like the most popular game or event, since ther we can save latency by storing recent results in a memcached-based query cache.

3. Aggregator

Aggregator delegates queries to multiple lower-level services in parallel and integrating their results.

4. Fetching Data and Validating Results

The results returned by the aggregator are simply a list of ids. The web tier needs to fetch all the data from memcache/MySQL to render the results and display information like the name, profile picture, link, shared networks, mutual friends, etc. The web tier also needs to do privacy checking here to make sure that the searcher is allowed to see each result.

5. Displaying the Results

The results with all the relevant data are sent back to the browser to be displayed in the typeahead. These results are also added to the browser cache along with the bootstrapped connections so that similar subsequent queries don’t need to hit the backend again.

Typeahead Algorithm




Leave a Reply

Your email address will not be published. Required fields are marked *