Loading...
The system could suggest top 10 possible completions for current word.
The system should suggest the word in real time (low latency)
List non-functional requirements for the system...
500M DAU
6 search
10 characters per search
Average QPS = 340k
Peak QPS 1M
get_recommendation(prefix) -> returns 10 top queries
search(query)
Trie or HashMAP
Hashmap has disadvantage of storage. For each query, you will need to store any possible prefix in the query.
Trie: Each node is a character. Each node contains a character and a count of the subtrees
We should have 2 services, Query service and collection services.
Two db: recommendation service db and collection service db.
When user inputs in the client, it will search for top 10 queries in Query Recommendation Service. For each query, it will search for the top 10 quieres through a Trie.
Once the user entered the query, the Collection service will update its Dynamic DDB with the count.
On each day, it will update the database in recommendation service. Note the database update only needs to get top 10 queries each time. No need to update the entire databse.
During Colleciton Service, we do not need to collect each query. We can have a random counter to collect with a rate of 1/1000
We could leverage map reduce to update the query.
We could add a timeout on the frontend.
We can add a backend cache. Everytime we update prefix to top 10, we update backend cache.
Frontend could also add some cache to preload some popular prefix (with user preference). Browser could store user's latest search. Front-end cache could leverage these used search results to accelerate. Also, it could set a TTL.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?