Step 1: Understand the problem and establish a scope

Questions:

1. From which part of the query does the matching start, the start or the middle part?
   1. It should begin from the start of the query.
2. How many suggestions for autocomplete should be shown?
   1. 5
3. How to know which suggestion to show?
   1. Depending on the search frequency of the query.
4. Is English the only supported language?
   1. Yes.
5. Are we considering Uppercase and special characters in the query?
   1. No, only lowercase English letters.
6. How many users are using the product?
   1. 10 mil DAU

Auto-suggestions should be fast enough, as Facebook suggests in their articles, a response should be shown within 100 ms. The results should be relevant to the search query and sorted by some criteria, such as frequency, popularity, or other ranking systems.

Back-of-the-envelope estimation

• 10 Million DAU.
• On average, a user makes 10 requests per day.
• The average query has a size of 20 bytes; each ASCII character is 1 byte.
• For each character of the query, the client sends a request to the server, making it 20 requests per query.
• 10 000 000 DAU * 10 queries/day * 20 chars / 24 hours / 3600 seconds ≈ 24 000 QPS
• 24 000 QPS * 2 = 48 000 Peak QPS
• Assuming 20% of the queries are new: 10 mil * 10 q/d * 20 bytes * 20 % = 0.4 GB of storage per day is taken

Step 2: High-level design