System requirements

Functional:

1. for each query, show top 5 most relevant terms
2. performance, system should show autocomplete results in less than 100ms
3. search query in English and lowercase

Non-Functional:

List non-functional requirements for the system...

1. scalable
2. hight available

Capacity estimation

Estimate the scale of the system you are going to design...

assume:

• 10M DAU
• 10 searches per day
• each search term about 20 chars long, e.g. `system design interview`
  • search?query=s
  • search?query=sy
  • search?query=sys
  • search?query=syst
  • search?query=syste
  • search?query=system
  • ...

QPS: (2 ^ 20 * 10 ) * (10 * 20) / (60*60*24) = 24000

PQPS: 2 * QPS = 48000

API design

Define what APIs are expected from the system...

GET /api/search

request:

{

query: 'do' // search query

}

response:

{

data: ['do', 'dog', 'dollar', 'doll', 'dong' ] // 5 top most relevant words

error: '', // error message

status: 0 // API status code

}

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

High-level design

see diagram

2 main services:

data aggregate service

steps:

• it gathers user query log, analytizes log, <term, frequency> e.g. `app: 100`, `apple: 1000`...
• workers execute async jobs at specific interval (weekly). they build the Trie data structure and store it in Trie DB
• Tire DB is a persistent data storage
  • use key-value store, each Trie node maps to k:v pair in
  • key is prefix, value is top 5 most frequent words, e.g. `app: [[apple: 1000], [apple store: 2000], [apple mac: 3000]...]`
• snapshot Trie DB weekly and store in Trie cache, e.g. use Redis, in memory DB for faster read

query service

given search query, get the most relevant terms from Trie cache , and form the result and return results in JSON

Request flows

1. search API request hit LB
2. LB routes the request to API services
3. API server get data from Trie cache and forms HTTP response, return in JSON
4. if data not in trie cache, get data from DB, and fill Trie cache

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trie data structure

each Trie node maps to K:V pair in Trie DB

k: 'do', v: [[dog: 1000], [dont: 2000]...]

Trie operations

create

got data from logs, and created by workers

update

update prefix frequency

2 options.

option 1: update trie weekly

option 2: directly update Trie data structure. if Tire is small, it is okay, but if it is large, will be slow, because all ancestor nodes need to be updated

so we choose option 1.

delete

we dont want to display hateful suggestions, add a filter service between query service and Trie cache. we can flexibly filter words based different filter rules

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

current design doesn't support treading search queries, like breaking news. because workers are offline jobs that update Trie weekly. to support treading search queries, need to do more frequent trie update, like hourly

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

if internet is not available, client side store cache as well

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

1. support multiple language
2. support trending search queries
   1. breaking news.
3. support different regions have different search suggestion
   1. create different tries for different regions