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.
read
mobile/web client send request to api gateway
apigateway route the traffic the backend application server
the application server requests
the backend server does the cache lookup
if cache miss, look up within db and then fill the result into cache
write
mobile/web client send request to api gateway
apigateway route the traffic the backend application server
the application server requests
the application append the counter to the s3 bucket
cron job
map reduce job which takes the s3 bucket and dump into a k-v store with query and their frequencies
the worker service takes each entry as input and generate a trie in memory. and at the very last, the application traverse through the trie tree and dump each node into the k-v db.
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...
memory consumption vs fast lookup, another way is to not store the sorted list per node. but only at the leaf node, which saves memory.
but during the runtime lookup, it requires the traverse the entire trie tree below the node corresponding to the last executed query
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
support multi-language with unicode encoding and regionalized dataset and store
personalized search via ML models
establish stream connection between clients/mobile app, since a user is likely to send a series of requests within a short period of window