Loading...
only in english
provide suggestion every time users type one new character or remove the old character
provide 5-10 sorted suggestions per request
the latency of generating per list of suggestions should be low, e.g p50 50ms and p90 100ms
Based on DAU 100M
Read QPS each user make 10 queries per day, each query average with 20 characters, with 5 deletions.
25 * 10 * 100 * 1000 * 1000 / (3600 * 24) = 290K qps
Write QPS
Because we need to update the count based on popularity. That means we need to handle per write per completed query. The qps is actually:
10 * 100 * 1000 * 1000 = 11K. Use 10K for simplicity
Read Throughput
Read throughput, average with 20 characters(20byte) per suggestion entry, up to 10 top suggestions per request.
290K qps * 200 bytes = 290 * 1000 * 200 = 59MB/s
Storage(TTL one month)
10K write, we could assume 5% of queries are new.
10K * 5% * 3600 * 24 * 30 = 26G
addNewWord(string)
when user completed the query, this will dump a new entry to object storage(s3, gcp bucket)
updateIndex(string query, int count)
we could run a cron job on daily basis. the job basically aggregate each query term globally with a counter. Then use the aggregated counter to update the search index
retrieveSuggestion(string)
the application will look up the search index and return the sorted suggestions
s3 on the write path, append only with query
class Node {
Map
string str;
}
The trie data structure can be cached in memory and persisted on local disk and be preloaded on the provision.
there should be another k/v store with str -> [suggestions...]
api gateway
backend application that handling `retrieveSuggestion` and `addNewWord`.
There should be a distributed cache to speed up the frequent search entries.
K-V store as the persistent storage
s3 storage which stores the query and their searched frequency
a cron job which dumps the aggregated query with each of the frequency
a worker service which take the aggregated result from mapreduce and call `updateIndex` to generate the tire tree and also dump to the k-v store.
mobile/web client send request to api gateway
apigateway route the traffic the backend application server
the application server requests
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...
since the write path can be executed
the cache volume might be a bottleneck when the dictionary keeps growing. we can partition based on the range of first characters, e.g a-c, f - q, ...
weekly updated trie might not be sufficient enough
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?