Loading...
User Scenario
when user type one letter, will get N popular words suggestion
return the top n popular suggestion based on prefix of the typed content
store the popular words
good metrics: popular -> the most hit words in the two weeks
availability
low latency
500M DAU
every user search 6 times, type 4 letters
Search 4 * 6 * 500M = 12B
QBS = 12B / ~100k ~ 120k
peak QPS = 120K * 3 - 360K
get word suggestions(tpyed_word)
suggestions
prefix. primary key
keywords word list
Word Count Table
keyword
hit_count
use log data to
user type one letter and send the request to typeahead service
service find the wordlist from Trie in memory and return.
if machine down, the service will deserialized the Trie from disk
Data collections service calculate the word count from log data and build Trie on offline query service
after update , switch the traffic to updated query service
Data collections service calculate the word count table and sorted it order by hit count DESC
For each node in Trie, will store the popular word list, when receive the request, the service will return the word list in constant time
Store the Trie in memory, will highly increase the speed of reading
To Save space, when user do search, generate a random number range from 1 - 10000, only when number is 1, record the log. In this case, the total log size will be dived by 10000 but not effect the popular words
Scalibility
Use Consisstant Hashing to store the Trie in momery make the Trie even distributed in query services
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?