Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
List the key non-functional requirements (performance, scalability, reliability, etc.)...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
GET /suggestions?q=hello&limit-5 - get 5-top suggestions for search string
200 ["suggestion1", "suggestion2", ...]
POST /suggestions - add search string to analytics
{
"query": "hello",
"timestamp": ...
}
200 - Ok
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
Client sends a request to get top-k suggestions. API Gateway limits the request count and redirect the request to appropriate server. Load balancer distributes the load between API servers. API servers find and read top-k from Trie in Cache. If there cache miss, we read from DB and add data to cache. For cache we can use Redis. Eviction policy - least recently used. And for DB we can use key-value database, where key is a prefix, value is top-k suggestions for fast access, e.g. Cassandra.
When client sends search query, we save it to Apache Kafka. Logs are stored to HDFS. Aggregator service reads this data and aggregates and writes query frequency to DB. We can also use key-value DB for fast access by key. Trie create services read aggregate data and create Trie. We also consider the weight of the search string: recent string have more weight. Trie is saved to Trie DB, that was described below. We should do a backup of old tree or version the trie to rollback support. Then we should to replace old data in cache. This is batch update. For continuously update we should use Kafka -> Trie create service > per-prefix counters in Redis.
For multi-region search we can use other tries for each region.
We should also collect metricts to see the correctness of suggestions.
We have to store a lot of Trie data. We can use sharding for cache and DB. We can shard by prefix. For example, a-h - 1-st shard, i-q - 2nd shard, r-z - 3rd shard. Or we can add more shards and divide by 2 letters, e.g. aa-ah, ai-aq etc. But some letters have a lot of words, and some letters have few words. We can use DB for mapping letters/prefixex and shards. For example letters x-z we can save on the same shard.
If cache slow or down we can respond by empty response.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Storing in key-value DB:
prefix -> ["search1": score1, "search2": score2, ...]
Storing query frequency in key-value DB:
query_string -> frequency, last_updated.
Query logs are stored at HDFS
We can shard by prefix. For example, a-h - 1-st shard, i-q - 2nd shard, r-z - 3rd shard. Or we can add more shards and divide by 2 letters, e.g. aa-ah, ai-aq etc. But some letters have a lot of words, and some letters have few words. We can use DB for mapping letters/prefixex and shards. For example letters x-z we can save on the same shard.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.