Free lesson · System Design Interviews
Step 6: Deep Dive - Caching Strategy
We've established that the URL shortener is a 100:1 read-heavy system and that Redis cache is the core of the read path. But "put a cache in front of the database" is a one-sentence answer. The deep dive is about getting the details right - cache population, eviction, invalidation, failure handling, and the interaction between cache and database that determines whether your system actually achieves <50ms redirect latency at 100K QPS.
This is the section where you demonstrate to the interviewer that you've operated systems at scale, not just designed them on paper.
The Caching Architecture in Detail
flowchart TB
subgraph READ_PATH["Read Path (Redirect)"]
REQ["GET /a3Xb9k"] --> CACHE_CHECK{"Redis Cache<br/>Key: url:a3Xb9k"}
CACHE_CHECK -->|"HIT (~99%)"| REDIRECT_FAST["302 Redirect<br/>Latency: ~3ms"]
CACHE_CHECK -->|"MISS (~1%)"| DB_READ["Query PostgreSQL"]
DB_READ --> POPULATE["Populate cache<br/>with TTL"]
POPULATE --> REDIRECT_SLOW["302 Redirect<br/>Latency: ~15ms"]
end
subgraph WRITE_PATH["Write Path (Create URL)"]
CREATE["POST /api/v1/shorten"] --> DB_WRITE["Write to PostgreSQL"]
DB_WRITE --> CACHE_WRITE["Write to Redis<br/>(write-through)"]
end
subgraph CACHE_CONFIG["Cache Configuration"]
TTL["TTL: 24 hours<br/>(default for auto-generated)"]
EVICTION["Eviction: LRU<br/>(when memory is full)"]
SIZE["Size: 30-180 GB<br/>(24h cache or hot 20%)"]
end
Detailed caching architecture. On the read path, a redirect request first checks Redis. On a cache hit, which happens about 99% of the time, the redirect completes in about 3 milliseconds. On a cache miss, about 1% of the time, the system queries PostgreSQL, populates the cache with a 24-hour TTL, and redirects in about 15 milliseconds. On the write path, new URL mappings are written to PostgreSQL first, then immediately written to Redis as a write-through operation. Cache TTL is 24 hours, eviction policy is LRU, and total cache size is 30 to 180 gigabytes depending on caching strategy.
Cache Population Strategies
Write-Through (Our Primary Strategy)
When a new URL is created, write it to both the database and the cache in the same operation. This ensures newly created URLs are immediately available in cache - critical because most clicks happen shortly after creation.
def create_short_url(long_url, custom_code=None):
short_code = custom_code or generate_short_code()
# 1. Write to database (source of truth)
db.execute(
"INSERT INTO url_mappings (short_code, long_url, expires_at) "
"VALUES (%s, %s, NOW() + INTERVAL '5 years')",
short_code, long_url
)
# 2. Write to cache immediately (write-through)
redis.setex(
f"url:{short_code}",
ttl=86400, # 24-hour cache TTL
value=long_url
)
return short_code
Cache-Aside (Lazy Population for Old URLs)
For URLs created before the cache existed (or URLs whose cache entry expired), we populate the cache on the first read:
def redirect(short_code):
# Step 1: Check cache
long_url = redis.get(f"url:{short_code}")
if long_url:
return long_url # Cache hit
# Step 2: Cache miss - query database
result = db.query(
"SELECT long_url, expires_at FROM url_mappings "
"WHERE short_code = %s",
short_code
)
if not result or result.expires_at < datetime.now():
return None # Not found or expired
# Step 3: Populate cache for next time
remaining_ttl = min(86400, (result.expires_at - datetime.now()).seconds)
redis.setex(f"url:{short_code}", ttl=remaining_ttl, value=result.long_url)
return result.long_url
The Cache Stampede Problem
What happens when a popular URL's cache entry expires? Suddenly, thousands of concurrent requests for that URL all experience a cache miss simultaneously and all query the database. This is a cache stampede (also called thundering herd).
sequenceDiagram
participant R1 as Request 1
participant R2 as Request 2
participant R3 as Request 3
participant C as Redis
participant DB as PostgreSQL
Note over C: Cache entry for popular URL expires!
R1->>C: GET url:popular
C-->>R1: MISS
R2->>C: GET url:popular
C-->>R2: MISS
R3->>C: GET url:popular
C-->>R3: MISS
R1->>DB: SELECT * FROM url_mappings WHERE short_code = 'popular'
R2->>DB: SELECT * FROM url_mappings WHERE short_code = 'popular'
R3->>DB: SELECT * FROM url_mappings WHERE short_code = 'popular'
Note over DB: 3 identical queries!<br/>With 10,000 concurrent users,<br/>that's 10,000 identical queries.
The cache stampede problem. A popular URL's cache entry expires. Thousands of concurrent redirect requests all check the cache and find a miss. All of them simultaneously query the database for the same short code. The database is hit with thousands of identical queries, which can overwhelm it. The solution is to allow only one request to query the database while the others wait for the cache to be repopulated.
Solving the Stampede: Request Coalescing
Only one request should query the database. All other concurrent requests for the same key should wait for the first request to populate the cache.
import threading
# Lock per short_code to prevent stampede
_locks = {}
_locks_lock = threading.Lock()
def redirect_with_coalescing(short_code):
# 1. Check cache
long_url = redis.get(f"url:{short_code}")
if long_url:
return long_url
# 2. Acquire per-key lock
with _locks_lock:
if short_code not in _locks:
_locks[short_code] = threading.Lock()
lock = _locks[short_code]
with lock:
# Double-check: another thread may have populated the cache
long_url = redis.get(f"url:{short_code}")
if long_url:
return long_url
# Only this thread queries the database
result = db.query(
"SELECT long_url FROM url_mappings WHERE short_code = %s",
short_code
)
if result:
redis.setex(f"url:{short_code}", ttl=86400, value=result.long_url)
return result.long_url
return None
Interview: What to say: "For popular URLs, I'd implement request coalescing to prevent cache stampedes. When a cache miss occurs, the first request acquires a per-key lock and queries the database. All other concurrent requests for the same key wait on the lock. When the first request populates the cache, the waiting requests find a cache hit and return immediately. This prevents thousands of identical database queries during cache expiration of hot keys."
Cache Invalidation
For a URL shortener, cache invalidation is relatively simple because URL mappings rarely change. But there are two cases to handle:
Case 1: URL Expiration
When a URL expires, its cache entry should also be invalid. Two approaches:
Approach A: Set cache TTL to match URL expiration. When caching a URL mapping, set the Redis TTL to the remaining lifetime of the URL. If the URL expires in 30 days, set TTL to 30 days (capped at 24 hours for memory efficiency).
Approach B: Lazy invalidation. Cache the expiration timestamp alongside the long URL. On each cache hit, check if the URL has expired. If so, delete the cache entry and return 404.
# Approach B: Store expiration in cache value
def cache_url(short_code, long_url, expires_at):
cache_value = json.dumps({
"long_url": long_url,
"expires_at": expires_at.isoformat()
})
redis.setex(f"url:{short_code}", ttl=86400, value=cache_value)
def get_cached_url(short_code):
cached = redis.get(f"url:{short_code}")
if not cached:
return None
data = json.loads(cached)
if datetime.fromisoformat(data["expires_at"]) < datetime.now():
redis.delete(f"url:{short_code}") # Expired - remove from cache
return None
return data["long_url"]
Case 2: URL Deletion (If Supported)
If users can delete their URLs, you need to invalidate both the database row and the cache entry:
def delete_url(short_code):
db.execute("DELETE FROM url_mappings WHERE short_code = %s", short_code)
redis.delete(f"url:{short_code}") # Invalidate cache
Cache Failure Handling
What happens when Redis goes down?
flowchart TD
REDIS_DOWN["Redis is DOWN"] --> FALLBACK{"Fallback strategy?"}
FALLBACK -->|"Option A"| DIRECT_DB["All reads hit database<br/>~10K QPS max<br/>Latency: 5-10ms"]
FALLBACK -->|"Option B"| LOCAL_CACHE["Use local in-memory cache<br/>on each API server<br/>Limited size, eventual consistency"]
FALLBACK -->|"Option C"| DEGRADE["Return 503 for non-critical requests<br/>Serve only cached responses<br/>from local cache"]
DIRECT_DB --> IMPACT["Impact: 100K QPS drops to 10K QPS<br/>90% of requests fail or timeout"]
LOCAL_CACHE --> IMPACT2["Impact: Reduced hit rate (~60%)<br/>but system stays operational"]
Cache failure handling options. When Redis goes down, Option A sends all reads directly to the database, but it can only handle about 10,000 QPS - 90% of traffic would fail. Option B falls back to a small local in-memory cache on each API server, providing about a 60% hit rate and keeping the system operational at reduced capacity. Option C degrades gracefully by serving only locally cached responses and returning 503 for the rest. Option B is the best production approach because it maintains partial service.
The production answer: Redis Sentinel for automatic failover.
Redis Sentinel cluster (3 nodes):
- Primary Redis: handles all reads/writes
- Replica 1: synchronous replication
- Replica 2: asynchronous replication
If Primary fails:
1. Sentinel detects failure (within 5 seconds)
2. Promotes Replica 1 to Primary
3. Application reconnects to new Primary
4. Downtime: 5-15 seconds
With Redis Sentinel, the cache layer has no single point of failure. Failover is automatic and takes 5-15 seconds. During those seconds, cache misses fall through to the database - at our scale, 5-15 seconds of database-only operation is manageable.
Tip: In an interview, mention the layered fallback. "Primary protection is Redis Sentinel with automatic failover - downtime is 5-15 seconds. During failover, cache misses go to the database. If the entire Redis cluster is somehow unavailable, each API server has a small local LRU cache (100MB) that covers the hottest URLs. The system degrades gracefully rather than failing entirely."
Cache Sizing and Memory Optimization
Compact Cache Entries
Every byte saved per cache entry is multiplied by hundreds of millions of entries. Optimize the value format:
# Wasteful: store full JSON
redis.set("url:a3Xb9k", '{"long_url": "https://...", "expires_at": "2027-06-14T00:00:00Z", "click_count": 0}')
# ~250 bytes per entry
# Efficient: store only the long URL (everything else is in the DB)
redis.set("url:a3Xb9k", "https://example.com/very/long/path?with=params")
# ~100-200 bytes per entry (just the URL string)
The cache only needs to store what the redirect operation needs: shortCode → longURL. Everything else (creation timestamp, expiration, analytics) lives in the database.
Memory Math
600 million hot URLs × 200 bytes each = 120 GB
With Redis overhead (pointers, hash table): ~180 GB
Redis node with 64 GB RAM:
- 180 GB ÷ 64 GB = 3 nodes minimum
- With replication: 6 nodes (3 primary + 3 replica)
Key Takeaways
-
Write-through for new URLs, cache-aside for old URLs. New URLs are written to cache during creation (write-through) because they get the most immediate traffic. Old URLs are cached on first read (cache-aside) and expire from cache via TTL.
-
Request coalescing prevents cache stampedes. When a hot URL's cache entry expires, only one request should query the database. All others wait for the cache to be repopulated. This prevents database overload during cache expiration events.
-
Redis Sentinel provides automatic failover for the cache layer. 3-node Sentinel cluster with automatic promotion. Failover takes 5-15 seconds. During failover, cache misses fall through to the database.
-
Store only what the redirect needs in cache. The cache value should be just the long URL - not metadata, not analytics, not expiration timestamps. Minimize entry size because you're caching hundreds of millions of entries.
-
Cache entries should have bounded TTL. Even for URLs that don't expire for 5 years, cache the entry for 24 hours. This bounds memory usage and ensures the cache reflects database reality (in case of manual deletions or corrections).
-
Graceful degradation is better than hard failure. If Redis is completely down, fall back to a local in-memory cache on each server. Reduced hit rate is better than total service failure.
Exercise: Exercise 1: A viral tweet contains a short URL. Within 60 seconds, 500,000 users click it. The cache entry for this URL was evicted an hour ago (nobody clicked it before the tweet). Walk through what happens. Does the request coalescing handle 500,000 concurrent misses? What if the database query takes 50ms - how many requests pile up during that 50ms?
Exercise 2: Design a cache warming strategy for URLs that are predicted to go viral. The system notices that a URL's click rate has jumped from 10/minute to 1,000/minute. How do you proactively ensure this URL stays in cache and isn't evicted by LRU? (Hint: consider a separate "pinned" cache for trending URLs.)
Exercise 3: The cache hit rate drops from 99% to 70% after a deployment that accidentally truncated all Redis keys. The database is now handling 30,000 QPS instead of 1,000. Design the cache recovery procedure. Do you warm the cache proactively (batch load from database) or let it refill organically (cache-aside on each miss)? What's the recovery time for each approach?