Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 1 billion DAU, and each user trigger autocompete 10 times per day, and peak QPS is twice the average QPS. We will have peak search QPS of
1 billion * 10 / 24 / 3600 * 2 = 231K
For writes, assume we do daily refresh of all text items in the storage, and assume that we have 1 billion text items, the peak write QPS is 23K.
For 1 billion text items, assuming storing each (including metadata) takes 1KB, we need 1TB of storage.
We also need to estimate the search logs being generated. We need the search logs to build our ML system for recommendations and autocomplete. With 10 billion autocomplete events each day, assuming each event takes around 1KB of storage, we will need 10TB of additional storage per day. This takes a lot of space, so we will move all logs over 3 months old to cold storage.
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...
Here is the API for users to get suggestions based on their input:
GET v1/fetch_suggestions {
text_input: String,
user_id: UUID
}
Here's the API that allows users to get back the actual search results:
GET v1/search_results {
text_input: String,
user_id: UUID
}
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.
First of all, all requests to the service go through API gateway and load balancer. The API gateway handles authentication and rate limiting, ensuring every user is authenticated, and no user can send huge request volumes that overwhelm the server.
In our design, there are several paths we need to consider. The core part is ElasticSearch, with supports search and autocomplete at high throughput.
For ingesting text items into ElasticSearch, we have a data ingestion service that receives real-time text item addition, deletion or update events, and triggers an event on Kafka queue. The events gets consumed by an ElasticSearch writer, which then writes the data to ElasticSearch. We use Kafka, a distributed message queue, as a buffer between data ingestion and data writing to ElasticSearch. This way, we can easily configure the write throughput to ElasticSearch cluster, and avoid overwhelming the cluster with huge traffic. The tradeoff here is latest event updates aren't written to the search index in real time. However, this temporary data staleness is acceptable given search is never guaranteed to return most updated results.
When users start typing in, we use prefix fetch from the ElasticSearch cluster to find a huge candidate pool of relevant text documents. We then use the trained machine learning model to get a relevant score for the text documents, rank them, and return the most relevant/popular suggested text documents.
When users confirm and do a search, we also trigger kafka events, we trigger:
Once the analytics service receives the event, it writes both data to the underlying cassandra database. The analytics service pulls data from cassandra to train a machien learning model, that is used to rank items during live retrieval based on popularity and relevance.
This system is highly scalable. ElasticSearch index can be scaled through sharding and replication. High write throughput is buffered by Kafka queue. Cassandra can easily be scaled to support high throughput. Data ingestion traffic is also buffered by kafka queue.
We also keep a local in memory prefix cache in search service's servers. This cache loads the 10000 top queries at startup, and cache search queries afterwards. This will help to mitigate some of the traffic to ElasticSearch, and provide a temporary fallback in case of ES cluster failure. For ES cluster, since we have read replicas for each shard, the system should be robust enough to handle partial shard failures.
New dataset rollout (blue/green deployment)
The offline ML pipeline reads search_query_frequency from Cassandra, trains the frequency model, and generates a snapshot file in S3 with the format:s3://suggestions-snapshots/v2/ ├── prefix_map.avro ├── metadata.json ├── s3://suggestions-snapshots/current -> s3://suggestions-snapshots/v1/ (symlink alias) Each service instance checkscurrentsymlink on startup and periodically polls for updates. To promotev2, we atomically update the symlink (or in Kubernetes, update a ConfigMap). If quality metrics drop post-deployment, we revert the symlink tov1. This gives us instant rollback (seconds, not hours).
Trending queries (streaming path)
For breaking trends, batch is too slow. We add a streaming pipeline:
User keystrokes → Kafka → Stream processor (e.g., Flink) → 1. Detects short-window frequency spikes (last 5 min vs last 24h) 2. Updates a Redis hashmap: `trending_prefixes:{prefix}` with top-10 trending completions 3. Service checks Redis first for trending prefixes before consulting the snapshot or ES This catches "barbie" within 1-2 minutes of the premiere, while the batch ML model still handles long-tail ranking. The Redis TTL auto-expires old trends — no manual cleanup needed.
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...
There are 2 storage we need, one used to store the text items used for search and autocomplete, another used for storing the search query logs.
For storing the search items used for search and autocomplete, we will use an ElasticSearch cluster. It has both tries and inverted trees that are optimized for searches and autocompletes. It can be easily scaled by sharding and replication. It is the ideal storage choice for our use case.
For sharding, we will shard by the hash of document_id. So data will be evenly distributed across different shards.
For each shard, we will create several read replicas to handle the high read throughput.
After sharding, each Finite State Transducers (trie-like data structure) within ElasticSearch will work independently, and merge the results during a search.
We also want to store the search and autocomplete access logs, which can help us to train the ML model for generating autocomplete results. Sample data we store:
table search_logs {
user_id: UUID,
search_text: String,
search_type: String,
search_time: Timestamp,
}
For storing the search logs, we will use cassandra. Cassandra naturally supports high write throughput, and is easily scalable. It is eventually consistent, which is acceptable for log storage.
We also need a separate table in cassandra that aggregates the query frequency per search query, which can help us to find popular/relevant queries.
table search_query_frequency {
search_text: String,
search_frequency: Integer,
search_type: String,
search_time: Timestamp,
}
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
First of all, all requests to the service go through API gateway and load balancer. The API gateway handles authentication and rate limiting, ensuring every user is authenticated, and no user can send huge request volumes that overwhelm the server.
In our design, there are several paths we need to consider. The core part is ElasticSearch, with supports search and autocomplete at high throughput.
For ingesting text items into ElasticSearch, we have a data ingestion service that receives real-time text item addition, deletion or update events, and triggers an event on Kafka queue. The events gets consumed by an ElasticSearch writer, which then writes the data to ElasticSearch. We use Kafka, a distributed message queue, as a buffer between data ingestion and data writing to ElasticSearch. This way, we can easily configure the write throughput to ElasticSearch cluster, and avoid overwhelming the cluster with huge traffic. The tradeoff here is latest event updates aren't written to the search index in real time. However, this temporary data staleness is acceptable given search is never guaranteed to return most updated results.
When users start typing in, we use prefix fetch from the ElasticSearch cluster to find a huge candidate pool of relevant text documents. We then use the trained machine learning model to get a relevant score for the text documents, rank them, and return the most relevant/popular suggested text documents.
When users confirm and do a search, we also trigger kafka events, we trigger:
Once the analytics service receives the event, it writes both data to the underlying cassandra database. The analytics service pulls data from cassandra to train a machien learning model, that is used to rank items during live retrieval based on popularity and relevance.
This system is highly scalable. ElasticSearch index can be scaled through sharding and replication. High write throughput is buffered by Kafka queue. Cassandra can easily be scaled to support high throughput. Data ingestion traffic is also buffered by kafka queue.
We also keep a local in memory prefix cache in search service's servers. This cache loads the 10000 top queries at startup, and cache search queries afterwards. This will help to mitigate some of the traffic to ElasticSearch, and provide a temporary fallback in case of ES cluster failure. For ES cluster, since we have read replicas for each shard, the system should be robust enough to handle partial shard failures.
New dataset rollout (blue/green deployment)
The offline ML pipeline reads search_query_frequency from Cassandra, trains the frequency model, and generates a snapshot file in S3 with the format:s3://suggestions-snapshots/v2/ ├── prefix_map.avro ├── metadata.json ├── s3://suggestions-snapshots/current -> s3://suggestions-snapshots/v1/ (symlink alias) Each service instance checkscurrentsymlink on startup and periodically polls for updates. To promotev2, we atomically update the symlink (or in Kubernetes, update a ConfigMap). If quality metrics drop post-deployment, we revert the symlink tov1. This gives us instant rollback (seconds, not hours).
Trending queries (streaming path)
For breaking trends, batch is too slow. We add a streaming pipeline:
User keystrokes → Kafka → Stream processor (e.g., Flink) → 1. Detects short-window frequency spikes (last 5 min vs last 24h) 2. Updates a Redis hashmap: `trending_prefixes:{prefix}` with top-10 trending completions 3. Service checks Redis first for trending prefixes before consulting the snapshot or ES This catches "barbie" within 1-2 minutes of the premiere, while the batch ML model still handles long-tail ranking. The Redis TTL auto-expires old trends — no manual cleanup needed.
First of all, all requests to the service go through API gateway and load balancer. The API gateway handles authentication and rate limiting, ensuring every user is authenticated, and no user can send huge request volumes that overwhelm the server.
In our design, there are several paths we need to consider. The core part is ElasticSearch, with supports search and autocomplete at high throughput.
For ingesting text items into ElasticSearch, we have a data ingestion service that receives real-time text item addition, deletion or update events, and triggers an event on Kafka queue. The events gets consumed by an ElasticSearch writer, which then writes the data to ElasticSearch. We use Kafka, a distributed message queue, as a buffer between data ingestion and data writing to ElasticSearch. This way, we can easily configure the write throughput to ElasticSearch cluster, and avoid overwhelming the cluster with huge traffic. The tradeoff here is latest event updates aren't written to the search index in real time. However, this temporary data staleness is acceptable given search is never guaranteed to return most updated results.
When users start typing in, we use prefix fetch from the ElasticSearch cluster to find a huge candidate pool of relevant text documents. We then use the trained machine learning model to get a relevant score for the text documents, rank them, and return the most relevant/popular suggested text documents.
When users confirm and do a search, we also trigger kafka events, we trigger:
Once the analytics service receives the event, it writes both data to the underlying cassandra database. The analytics service pulls data from cassandra to train a machien learning model, that is used to rank items during live retrieval based on popularity and relevance.
This system is highly scalable. ElasticSearch index can be scaled through sharding and replication. High write throughput is buffered by Kafka queue. Cassandra can easily be scaled to support high throughput. Data ingestion traffic is also buffered by kafka queue.
We also keep a local in memory prefix cache in search service's servers. This cache loads the 10000 top queries at startup, and cache search queries afterwards. This will help to mitigate some of the traffic to ElasticSearch, and provide a temporary fallback in case of ES cluster failure. For ES cluster, since we have read replicas for each shard, the system should be robust enough to handle partial shard failures.