Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
Store and serve frequently accessed content: The cache stores static or dynamic web content (HTML pages, images, API responses) keyed by URL or content hash. Repeat requests are served directly from fast in-memory storage, completely bypassing the origin server. This is the fundamental value proposition: trade memory for speed.
Cache invalidation on origin changes: When the original content changes, the cache must update or remove affected entries. This happens through TTL expiry, explicit purge API calls, or event-driven invalidation via pub/sub. Without this, users receive stale content indefinitely.
Eviction when cache reaches capacity: The cache has finite memory. When it fills up, a replacement policy (LRU, LFU, or a practical approximation) removes the least valuable entries to make room for new ones. The choice of eviction policy directly affects hit ratio.
List the key non-functional requirements (performance, scalability, reliability, etc.)...
Sub-millisecond cache hits: Cache hits must return in under 1ms. The entire point of caching is speed. If the cache adds significant latency, services would skip it and go directly to the origin.
Horizontal scalability: The cache cluster grows by adding nodes. Consistent hashing distributes keys across servers so that adding or removing a node only redistributes a small fraction of keys, not the entire dataset.
Consistency with origin data: Mechanisms like TTL, invalidation events, and write-through policies ensure users do not receive stale content beyond an acceptable window. The system trades strict consistency for performance, but staleness must be bounded.
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
100K requests per second: A large web application serving millions of users. Not all requests hit the cache; some are cache misses that go to the origin. The target is a 95% cache hit ratio, meaning 95K requests per second are served from cache and only 5K reach the origin.
Read-to-write ratio: 100:1: Most cache operations are reads (get). Writes (put) happen only on cache misses or explicit updates. This tells us the architecture must be heavily optimized for read throughput.
Target: 1TB of cached content: Assume the total content corpus is 10TB, but only 10% is frequently accessed (the working set). Caching this 1TB working set achieves a 95%+ hit ratio because popular content follows a Zipf distribution.
Server sizing: A modern server has 64GB of available RAM for caching. To store 1TB: 1,024GB / 64GB = 16 cache servers. In practice, deploy 20 servers to account for replication overhead and memory fragmentation.
Average entry size: 10KB: This covers HTML responses, JSON API payloads, and small images. Larger assets (videos, large images) are typically served by a CDN, not the in-memory cache.
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...
PUT /cache
Headers: Content-Type, X-Cache-TTL (seconds)
Body: {
key: string (URL or content hash),
value: bytes (response body),
headers: map (response headers),
ttl: number (optional, seconds until expiry)
}
Response: 200 OK { key: string, stored_at: ISO-8601, expires_at: ISO-8601 }
The TTL is optional. If omitted, the entry lives until evicted by the replacement policy. Setting a TTL is recommended for dynamic content where freshness matters. The headers field stores the original response headers so the cache can return them verbatim to the client, preserving Content-Type, Cache-Control, and ETag values.
GET /cache/:key
Response (hit): 200 OK { value: bytes, headers: map, cached_at: ISO-8601 }
Response (miss): 200 OK { value: bytes, headers: map, cached_at: ISO-8601, source: "origin" }
On a cache hit, the proxy returns the stored response immediately. On a miss, the proxy fetches the content from the origin server, stores it in the cache with a TTL, and returns it to the client. The client always receives a 200 with the requested content; it never needs to know whether the response came from cache or origin. This read-through proxy pattern keeps cache-population logic centralized in the proxy rather than spread across every calling service.
DELETE /cache/:key
Response: 200 OK { key: string, deleted: boolean }
Removes a specific entry immediately. Used when the origin content changes and the stale cached version must not be served. For bulk invalidation (all entries matching a URL prefix), a separate admin endpoint accepts pattern-based purges.
GET /cache/stats
Response: 200 OK {
hit_count: number,
miss_count: number,
hit_ratio: number,
total_entries: number,
memory_used_bytes: number,
eviction_count: number
}
The stats endpoint enables monitoring dashboards and alerting. A dropping hit ratio triggers investigation; rising eviction counts signal the cache needs more capacity.
Cache Entry
key STRING URL or content hash
value BYTES Response body
headers MAP Original response headers
created_at NUMBER Unix timestamp (ms)
ttl NUMBER Seconds until expiry
Both Redis and Memcached provide sub-millisecond reads for cached data. The choice depends on feature needs:
Memcached is simpler: pure key-value with no data structures, no persistence, and no replication. It uses a slab allocator for predictable memory management and multi-threaded architecture for high throughput. Choose Memcached for pure caching where simplicity and raw throughput matter most.
Redis adds data structures (hashes, lists, sorted sets), optional persistence (RDB snapshots, AOF), and built-in replication. Choose Redis when you need features beyond simple key-value lookup, such as storing metadata alongside cached values or replicating data for fault tolerance.
For this design, we choose Redis because replication provides fault tolerance (cached data survives a single node failure) and the hash data structure lets us store value, headers, and metadata in a single key without serialization overhead.
cache_config (PostgreSQL)
config_id SERIAL Primary Key
policy VARCHAR Eviction policy name
max_memory_mb INTEGER Per-node memory limit
default_ttl_sec INTEGER Default TTL for entries
updated_at TIMESTAMP Last config change
PostgreSQL stores cache policies, access logs, and audit data. This is not on the hot read path; it is read once at startup and on configuration changes. Decoupling configuration from the cache engine allows tuning policies without restarting cache nodes.
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 to Cache Proxy: A web service sends a request to the cache proxy. The proxy computes a hash of the cache key (typically the URL) and consults the consistent hashing ring to determine which cache node owns that key.
Cache Proxy to Cache Node: The proxy checks the owning Redis node. On a miss (key not found or expired), the proxy fetches the content from the origin server.
Origin Fetch and Store: The proxy retrieves the response from the origin, stores it in the cache node with a TTL, and returns the response to the client. Subsequent requests for the same key hit cache.
Cache Proxy to Cache Node: The proxy hashes the key, routes to the correct node, and finds the entry. The cached response (body plus headers) is returned directly to the client. The origin is never contacted. This path completes in under 1ms.
Origin to Pub/Sub: When origin data changes, the origin publishes an invalidation message to a message broker (Redis Pub/Sub or Kafka). All cache proxies subscribe to this channel. On receiving an invalidation message, the proxy deletes the affected key from the owning cache node.
ZooKeeper / etcd: Stores the consistent hashing ring configuration: which cache nodes are alive, their positions on the ring, and health status. When a node joins or leaves, ZooKeeper updates the ring and notifies all proxies. This ensures all proxies route keys consistently.
Cache hit: proxy hashes the key, routes to the correct Redis node, and returns the cached response in under 1ms.
Step 1: Client sends request: A web service sends a GET request for a URL to the cache proxy. The request includes the cache key (typically the URL or a hash of URL plus relevant headers like Accept-Language).
Step 2: Proxy computes key hash: The proxy hashes the cache key using the same hash function as the consistent hashing ring (such as MurmurHash3). This determines which cache node owns the key.
Step 3: Proxy queries cache node: The proxy sends a GET command to the owning Redis node. Redis looks up the key in its hash table, an O(1) operation that completes in microseconds.
Step 4: Hit found, response returned: The cached value (response body plus headers) is returned to the proxy, which forwards it to the client. Total latency: under 1ms. The origin server is never contacted.
Cache miss: proxy detects the miss, fetches from origin, stores the response in cache, and returns to the client.
Step 1: Client sends request: Same as the hit flow.
Step 2: Proxy queries cache node: The key is not found in Redis (either never cached or expired and evicted).
Step 3: Proxy fetches from origin: The proxy makes a request to the origin server. This is the expensive step: origin latency is typically 50-200ms depending on the backend service.
Step 4: Origin returns response: The origin sends the response body and headers back to the proxy.
Step 5: Proxy stores in cache: The proxy writes the response to the owning Redis node with a TTL. This populates the cache so the next request for this key is a hit.
Step 6: Proxy returns response to client: The client receives the same response it would have received from a cache hit, just with higher latency for this first request.
Cache invalidation: origin publishes change event, proxies delete stale entries, next request triggers fresh fetch.
Interview Tip
Why delete-then-lazy-refetch beats eager refresh: the invalidation signal may fire for content nobody is requesting right now. Eagerly fetching new content from the origin wastes bandwidth and cache memory on entries that may never be read. Delete and let the next actual request repopulate on demand.
Step 1: Origin data changes: A write operation updates content on the origin server.
Step 2: Origin publishes invalidation: The origin sends a message to the pub/sub channel with the affected cache key.
Step 3: Proxies receive invalidation: All subscribed cache proxies receive the message and delete the key from the owning cache node.
Step 4: Next request triggers fresh fetch: The next client request for that key is a cache miss, triggering a fresh fetch from the origin with the updated content.
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...
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
The core engineering challenge (the GATE of this problem) is building a key distribution system that scales horizontally without invalidating the entire cache when nodes are added or removed. Consistent hashing with virtual nodes is the mechanism that makes this possible.
Key Insight
The GATE insight: the entire system hinges on consistent hashing. When a cache node joins or leaves the cluster, only the keys in the affected arc of the hash ring are redistributed. Virtual nodes ensure even distribution across physical machines. This is what makes horizontal scaling practical: adding a node to a 16-node cluster remaps roughly 6% of keys, not 100%.
Consistent hashing: keys map to positions on a ring. Each node owns the arc between it and the previous node. Adding a node redistributes only the affected arc.
The hash ring maps both cache nodes and keys to positions on a circular space (0 to 2^32 - 1). A key is assigned to the first node encountered when walking clockwise from the key's hash position. When a node joins, it takes ownership of a portion of its clockwise neighbor's arc. Only keys in that portion need to move; all other keys remain on their current nodes.
Virtual nodes: Each physical node is mapped to 100-200 positions on the ring. Without virtual nodes, a 5-node cluster creates 5 arcs that can vary wildly in size. With 500 virtual nodes (100 per physical node), the standard deviation of key distribution drops from roughly 40% to under 5%.
Node addition: When a new physical node joins, its virtual nodes are placed on the ring. Keys that now fall in the new node's arcs are migrated from their previous owners. At 100 virtual nodes per physical node in a 16-node cluster, roughly 6% of keys are redistributed (1/17 of the total), preserving 94% of cached data.
Node removal: When a node fails, its virtual nodes are removed from the ring. Keys that were owned by the failed node are redistributed to their new clockwise neighbors. These keys experience cache misses until repopulated from the origin.
Strict LRU requires a doubly linked list maintained on every access. In a high-throughput cache processing 100K operations per second, the pointer updates (remove from current position, insert at head) become a bottleneck due to lock contention.
Pseudo-LRU (used by Redis) eliminates the linked list. Each key stores a timestamp of its last access. On eviction, Redis randomly samples 5-10 keys and evicts the one with the oldest timestamp. This approximates true LRU with O(1) overhead per access (just updating a timestamp) and no linked list maintenance.
The accuracy of pseudo-LRU improves with sample size: at sample size 10, it is nearly indistinguishable from true LRU in practice. Redis defaults to sample size 5, which provides a good balance between eviction accuracy and CPU cost.
Each cache entry is replicated to one backup node (the next node clockwise on the hash ring). If the primary node fails, the replica serves requests for the affected keys while the failed node is replaced. Replication doubles memory usage but prevents cache data loss on single-node failures.
Write-through replication: every cache write goes to both primary and replica synchronously. This adds 1-2ms of write latency but guarantees the replica is always up to date. For a read-heavy workload (100:1 read-to-write ratio), this write penalty is negligible.
A viral URL cached on a single node can overwhelm it while other nodes sit idle. Detection: monitor per-node QPS; if one node exceeds 2x the average, a hot key exists. Mitigation strategies:
L1 in-process cache: The cache proxy maintains a small local cache (Caffeine or Guava, 100MB) for the hottest keys. This absorbs repeat requests without hitting the Redis node at all. The L1 cache uses a very short TTL (5-10 seconds) to stay fresh.
Key replication: Replicate the hot key to multiple nodes. The proxy randomly distributes reads across all replicas, spreading the load. This requires tracking which keys are replicated and invalidating all copies on update.