System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• with every letter the user types, we want to show the top 10 searches matching the same prefix
• we update the search queries in our data once a day

Non-Functional:

List non-functional requirements for the system...

• low latency
• scalable: can handle high traffic
• Highly available: The system should remain available and accessible when part of the system is offline, slows down, or experiences unexpected network errors.

Capacity estimation

Estimate the scale of the system you are going to design...

API design

Define what APIs are expected from the system...

GET v1/search?query={xxxx}

Response (top search suggestions):

[

"xxxx",

"xx",

"xxxxxx",

....

]

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

MongoDB as a key-value store

Query: "app"

Completions: {"app":100, "apple": 80, "appache": 50}

Redis will have a similar structure

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

We need to prioritize reads -> store data in Redis as in-memory, super fast, avoid disk operation.

But we probably don't need to store all reads on Redis because it gets pricey as our service grows and some queries are rare so it doesn't provide as much value. So we only store the top searches in Redis. The rest can stay in Mongo DB.

For eviction policy we can use LRU.

Querying Service:

1. user type a query
2. server checks shard manager to find which Redis shard we need to look in
3. server check query in Redis (O(1))
4. if query does not exist, fetch from MongoDB, add cache to Redis.
5. Return completion response from Redis to user

Aggregation Service:

1. if we only need to update queries at the end of day
   • user types a query
   • query goes into a message queue
   • store the query in a event database like Cassandra. It uses a storage structure that resembles LSM. It writes inserts and updates in a log-like structure known as a memtable (in memory) and periodically flushes these memtables to disk in files called SSTables. These SSTable, while optimized for reads of specific rows, are not optimized for range queries or aggregations which is why we need to do the batch processing to pre-aggregate.
   • In order to do the batch processing, we can use a tool like Apache Spark. Spark is a distributed computing engine that is optimized for these types of workflows and can handle the large volume of data that we will be processing.
   • Using map-reduce, Spark will read the raw events in parallel chunks, aggregate them by query key and counts, and then write the aggregated data to our database.
   • We then point to this new instance (switch instances to show updated data)
2. If we want to do real-time processing
   • when a click comes in
   • The aggregation service writes the event to a stream like Kafka or Kinesis.
   • A stream processor like Flink or Spark Streaming reads the events from the stream and aggregates them in real-time.
   • The aggregated data is stored in our mongoDB for querying.

Detailed component design

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...

Simple hash table (word, counter) -> for each user query, we need to find all words matching the prefix (binary search) then use a heap to keep track of the top k searches. Time O(n) too slow

Trie -> native trie doesn't give us much improvement, but storing top k completion at each prefix level give us O(1) for each new letter the user types

Prefix hash tree(Every prefix in the trie is mapped to a key in a hash table. Data on each trie node is mapped to a value in a hash table.): con: lost the relationship between levels.

pro: it's easy to store in a key value store like MongoDB and Redis.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

We can try to update MongoDB directly when a user clicks on a suggestion, but in a distributed system this will increase our write throughput significantly, and we might run into concurrency issue. Because of this, we employed the aggregation service mentioned in the above section, first we dump the data to a queue then depends on the cadence we want to update the data, we either use a streaming tool or we dump it to a event database then run a batch job to aggregate them at a certain time interval.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Query service requires lightning-fast speed. We propose the following optimizations:

AJAX request. For web applications, browsers usually send AJAX requests to fetch autocomplete results. The main benefit of AJAX is that sending/receiving a request/response does not refresh the whole web page.

Browser caching. For many applications, autocomplete search suggestions may not change much within a short time. Thus, autocomplete suggestions can be saved in browser cache to allow subsequent requests to get results from the cache directly. Google search engine uses the same cache mechanism. Figure 12 shows the response header when you type “system design interview” on the Google search engine. As you can see, Google caches the results in the browser for 1 hour. Please note: “private” in cache-control means results are intended for a single user and must not be cached by a shared cache. “max-age=3600” means the cache is valid for 3600 seconds, aka, an hour.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

Sharding: we can shard on the the first letter->26 servers. Can further shard them on second and even third level