System requirements

Functional:

Provide suggestions to users

Non-Functional:

Low latency

Reliability

Scalability

Availability

Capacity estimation

1 billion Daily Users and each user hits 10 queries per day on an avg

10 billion queries/day

(10 billion / 24*60*60) QPS

API design

Database design

Use tries

For database, we can use multiple databases for different use cases. For storing user metadata, use MySQL. And for query and suggestions, use NoSQL.

High-level design

Clients start typing in the browser search bar. The request goes to load balancer, which sends it to the web server. Web server checks in the cache and if not there then sends the request to the application server. Then it checks the cache, if not there then fetches data from the database. And returns to the end user.

Request flows

Clients start typing in the browser search bar. The request goes to load balancer, which sends it to the web server. Web server checks in the cache and if not there then sends the request to the application server. Then it checks the cache, if not there then fetches data from the database. And returns to the end user.

Detailed component design

Databases will internally use a trie datastructure to store and retrieve suggestions

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

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

Future improvements

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