Loading...
10 miliion DAU
peak traffic: 1 million qps
average query 15 characters
each character 2 bytes
Storage:
each user queries 10 times a day
10 * 10^6 * 10 * 15 * 2 = 3GB per day -> 1TB a year
replication factor 3 -> 9GB per day -> 3TB a year
bandwidth
ingress with replication factor of 3 -> 3GB * 3 / (24*60*60) * 8 = 0.8Mbps
egress with top 10 suggestion (N=10) -> 10 * 3GB / (24*60*60) * 8 = 2.7Mpbs
Servers assuming each server can handle 50k requests per second
peak load 1 million qps
10*10^6/(50000) = 200
GET /api/v1/suggestions?query={prefix}
{
list_of_top_10_suggestions: string[]
}
POST /api/v1/queries
{
query: string
}
trie table redis DB
{
key: ac:{prefix},
value: zset {sentence1:score1, sentence2:score2}
}
The prefixes will be stored in a redis DB in a sorted set data structure and the score of each search would be the count of times it was searched.
ac:a | apple, application, apartment | 120, 80, 65 |
ac:ap | apple, application, apartment | 120, 80, 65 |
ac:app | apple, application | 120, 80 |
ac:appl | apple, application | 120, 80 |
ac:apple | apple | 120 |
ac:appli | application | 80 |
ac:applic → … → ac:application | application | 80 |
Kafka event store
{
prefix,
user
}
suggestion counter table NOSQL (Cassandra or Dynamodb)
{
pk: query: string,
frequency: int
time_interval: timestamp
}
Trie snapshot table MongoDB
{
id: int,
parent: int
character: string
top_10_suggestions: string[]
}
parent field will have an index for fast lookup of children of a node.
Suggestion service
This service is responsible for looking for a prefix and fetching the top 10 suggestions starting with a prefix. This service also stores a prefix event in the kafka event store so that it could be consumed asynchrounasly without impacting the latency of the critical path.
Aggregator
This service runs in the background by consuming events from Kafka and calculating the count of each suggestions. The counters will be stored in the Cassandra DB.
Trie Builder
The trie builder will build the new trie periodically in the background. Once a week, the trie builder service will build a new trie tree in Redis and when it's ready, user's requests will be directed to it.
MongoDB will store a snapshot of the trie. in case redis goes down we can rebuild the redis cache from the mongodb partition.
Redis cache will store the prefix suggestions in an efficient way so we can efficiently query top 10 suggestions for a prefix.
Zookeeper will contain mappings between prefix range to redis partition and replica.
The Cassandra DB will contains the queries with the frequency count at each slice of time. The trie builder will use this to build the trie and compute the top 10 suggestions for each prefix.
Calling suggestions API:
Calling query API:
Suggestion service is stateless so we can scale it using cpu load metric. The suggestions are fetched from redis sorted set, so a lookup of some prefix will take O(logn + 10) time.
The query service stores the query event in kafka so it's decoupled from the aggregator processing. The kafka store also provides fault tolerance in case there are partial failures or network partitions so the suggestion service can service requests and be decoupled from the aggregator and trie builder services.
Redis DB
The redis DB will be sharded according to ranges so it can handle increasing load of more prefixes. Since some of the prefix are less common, the db will be sharded in a way that the data is equally distributed and can be adjusted according to changes in the stored suggestions.
Kafka
The kafka streaming platform will store queries events. This will be sharded by using topics for prefix range: a-m to topic1. In addition, we can partition each topic according to the time interval: 1st hour, 2nd hour, etc.
Cassandra DB
The Cassandra DB easily scales and supports heavy write throuput. The frequencies DB will be sharded by the partition key (query column).
Aggregator workers
The Aggregator service will work in the backgroud by consuming query events from kafka, and process them to compute the frequency of each query and each time interval. This can be implemented as stateless workers like map reduce or spark, which supports high parallalizm to compute large amount of query events. If the workers fail, they can restart and compute again the frequency from the last point they checkpoint. Each time interval of an hour can be a checkpoint in case of failure.
Online vs. Offline Trie update
In this design, I chose to precompute top 10 suggestions in the background so the system will reply back to users with low latency to improve user experience. This cost in RAM and disk storage in order to store top 10 suggestions in each prefix.
Redis instance crashes
In case of a crash, we can retrieve top 10 suggestions by using the replica of the redis partition. The Zookeeper and load balancer will direct traffic to the healthy redis replicas. In case of all replicas of redis unavailable, we can gracefully degrade the service to query the trie snapshot in mongodb. This will increase the request's latency, but it will return to the user suggestions to make the service available.
Aggregator service crash or overload
The aggregator service will process events from kafka and checkpoint the frequency result of each query for every time interval of an hours. Therefore, if it crashes, it just we can just schedule new workers and let them recompute the last time interval and store it in Cassandra. In case of an overload of the aggregator workers, the kafka is used as a buffer, so the user's /api/v1/query API request is not affected. We can also scale the aggregator by adding more workers and splitting the work between them.