Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
Store and serve: Cache frequently accessed web content and return it on repeat requests
Cache invalidation: Support TTL expiry, explicit purge requests, or cache-control headers so stale content isn't served forever
Eviction policy: When cache is full, evict the lates valuable entires (e.g., LRU, LFU, or size-based)
List the key non-functional requirements (performance, scalability, reliability, etc.)...
Low latency: Cache hits should return with p99 latency of 10ms
Horizontal scalability: Add more cache nodes to handle growing traffic should be easy and doesn't break.
Consistency: We can accept a TTL-based eventual consistency.
Availability: The cache should be available 99.99% of time.
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 10 billion requests per day sent to the server, and all of them go through the web server cache.
For read. we would have average QPS of 115K, and peak QPS would be around 230K.
Assuming a cache hit rate of 95%, for the missing 5%, we need to write to cache the updated values. So peak write QPS will be around 11K.
For the cache cluster, since 10 billion requests are sent every day, we assume the working size is 20% of content, so 2 billion entries, where key-value and metadata for each entry is 5KB. We will need 10TB of storage for the cache cluster.
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 are the several APIs.
To read using a key:
GET v1/read_value {
key: String
}
To write/update using a key:
POST v1/write_value {
key: String,
value: String
}
To delete using a key:
DELETE v1/evict_value {
key: String,
}
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.
The web server cache has several components:
Load balancers look at the cache key, a hashing of request URL + headers, and use that to distribute requests evenly across cache servers using consistent hashing.
The cache server processes the request, and tries to fetch the corresponding value from redis cluster, which is sharded also by hashing of the cache key. If the value is available, we return the value to client. If not, we send the request to origin server, computes the results, and sends back the result. We also write the results to the redis cluster as well, with a TTL.
When cache key's TTL expires, redis purges those keys from the cache, we can also send requests manually to redis to purge keys.
If hot keys expire at the same time, we might introduce thundering herd. To mitigate that, we use TTL-jittering plus stale-while-revalidate.
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...
For the cache cluster's storage engine, we will use redis, a in-memory database that is highly scalable.
The data model for redis is:
key: String,
value: String,
headers: String,
TTL: Integer,
updated_at: Timestamp
The key is a hashing of request URL + headers (like Accept-Encoding, Content-Type)
For scalability, we will use consistent hashing of the key to map each key to their corresponding value to ensure an even distribution.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
For the cache cluster's storage engine, we will use redis, a in-memory database that is highly scalable.
The data model for redis is:
key: String,
value: String,
headers: String,
TTL: Integer,
updated_at: Timestamp
The key is a hashing of request URL + headers (like Accept-Encoding, Content-Type)
For scalability, we will use consistent hashing of the key to map each key to their corresponding value to ensure an even distribution.
The web server cache has several components:
Load balancers look at the cache key, a hashing of request URL + headers, and use that to distribute requests evenly across cache servers using consistent hashing.
The cache server processes the request, and tries to fetch the corresponding value from redis cluster, which is sharded also by hashing of the cache key. If the value is available, we return the value to client. If not, we send the request to origin server, computes the results, and sends back the result. We also write the results to the redis cluster as well, with a TTL.
When cache key's TTL expires, redis purges those keys from the cache, we can also send requests manually to redis to purge keys.
If hot keys expire at the same time, we might introduce thundering herd. To mitigate that, we use TTL-jittering plus stale-while-revalidate.
To ensure availability and data durability, we replicate each redis shard as well. When a redis node goes down, the replicas can keep serving traffic. To ensure data consistency, we sync each write to all replicas before acknowledging a write as success. This approach will lead to higher write latency as a tradeoff, but ensures consistency between all replicas. When a node is down, any replica can be picked to be the fallback replica.
If a write fails and triggers a rewrite, the write should be idempotent given same key-value pair and TTL. So this won't cause any data duplication problems.