Understand the Problem

When searching on Google or shopping at Amazon, as you type in the search box, one or more matches for the search term are presented to you. This feature is referred to as autocomplete, typeahead, search-as-you-type, or incremental search. Figure 1 presents an example of a Google search showing a list of autocompleted results when “dinner” is typed into the search box. Search autocomplete is an important feature of many products. This leads us to the interview question: design a search autocomplete system, also called “design top k” or “design top k most searched queries”.

Step 1 – Understand the problem and establish design scope#

The first step to tackle any system design interview question is to ask enough questions to clarify requirements. Here is an example of candidate-interviewer interaction:

Requirements

Here is a summary of the requirements:

• Fast response time: As a user types a search query, autocomplete suggestions must show up fast enough. An article about Facebook’s autocomplete system ¹ reveals that the system needs to return results within 100 milliseconds. Otherwise it will cause stuttering.

• Relevant: Autocomplete suggestions should be relevant to the search term.

• Sorted: Results returned by the system must be sorted by popularity or other ranking models.

• Scalable: The system can handle high traffic volume.

• Highly available: The system should remain available and accessible when part of the system is offline, slows down, or experiences unexpected network errors.

Back of the envelope estimation#

• Assume 10 million daily active users (DAU).

• An average person performs 10 searches per day.

• 20 bytes of data per query string:

• Assume we use ASCII character encoding. 1 character = 1 byte

• Assume a query contains 4 words, and each word contains 5 characters on average.

• That is 4 x 5 = 20 bytes per query.

• For every character entered into the search box, a client sends a request to the backend for autocomplete suggestions. On average, 20 requests are sent for each search query. For example, the following 6 requests are sent to the backend by the time you finish typing “dinner”.

  search?q=d

  search?q=di

  search?q=din

  search?q=dinn

  search?q=dinne

  search?q=dinner

• ~24,000 query per second (QPS) = 10,000,000 users * 10 queries / day * 20 characters / 24 hours / 3600 seconds.

• Peak QPS = QPS * 2 = ~48,000

• Assume 20% of the daily queries are new. 10 million * 10 queries / day * 20 byte per query * 20% = 0.4 GB. This means 0.4GB of new data is added to storage daily.