Free lesson · System Design Interviews

Step 6: Deep Dive - Caching Design

Hard15 min readsystem-designinterview-prep

Caching for Pastebin is nothing like caching for URL Shortener, and this is where candidates who reuse their URL Shortener caching strategy get caught. With URL Shortener, every cached entry is 300 bytes - you can cache a billion mappings in 300 GB of Redis and call it a day. With Pastebin, cached entries range from 100 bytes (metadata) to 10 MB (full paste content). If you try to cache everything the same way, you'll either blow your Redis memory budget on a handful of large pastes or waste cache capacity on metadata-only caching that misses the content.

I once watched a candidate design a Pastebin cache that stored all paste content in Redis with no size limits. I asked "what's your Redis memory budget?" and they said "64 GB." Quick math: 64 GB / 10 KB average = 6.4 million pastes cached. That's fine for a day's worth of pastes. But then I asked "what happens when someone pastes a 10 MB log file and it gets popular?" One viral 10 MB paste cached 100 times across different cache nodes burns 1 GB of cache memory - the same memory that could have cached 100,000 small pastes. The candidate hadn't thought about this. Don't be that candidate.

The solution is tiered caching - different caching strategies for different content sizes. Let me show you how to build it.

The Caching Challenge: Variable Content Size

URL Shortener has uniform-size cache entries. Pastebin doesn't. This single difference forces a fundamentally different caching architecture.

flowchart TD
    subgraph URL_SHORTENER["URL Shortener Cache (Uniform)"]
        US_ENTRY1["Entry: 300 bytes"]
        US_ENTRY2["Entry: 300 bytes"]
        US_ENTRY3["Entry: 300 bytes"]
        US_NOTE["Every entry is the same size.<br/>One caching strategy fits all."]
    end
    
    subgraph PASTEBIN["Pastebin Cache (Variable)"]
        PB_ENTRY1["Metadata: 200 bytes"]
        PB_ENTRY2["Small paste: 5 KB"]
        PB_ENTRY3["Medium paste: 100 KB"]
        PB_ENTRY4["Large paste: 5 MB"]
        PB_NOTE["10,000x size variance.<br/>One strategy does NOT fit all."]
    end

The fundamental caching challenge for Pastebin compared to URL Shortener. URL Shortener has uniform cache entries - every entry is about 300 bytes. One caching strategy works for all entries. Pastebin has variable-size entries ranging from 200 bytes for metadata to 5 megabytes for large paste content - a 10,000x variance. A single caching strategy either wastes memory on large pastes or under-serves small pastes. The solution is tiered caching with different strategies for different content sizes.

The content size distribution from our estimation:

Three-Tier Caching Architecture

flowchart TB
    REQUEST["View paste request"] --> CDN{"Tier 1: CDN Cache<br/>(CloudFront edge)"}
    
    CDN -->|"HIT"| CDN_RESPONSE["Content served from<br/>nearest edge node<br/>Latency: 5-15ms"]
    
    CDN -->|"MISS"| REDIS{"Tier 2: Redis Cache<br/>(application layer)"}
    
    REDIS -->|"Metadata HIT +<br/>Content HIT<br/>(small paste)"| REDIS_FULL["Full response from cache<br/>Latency: 20-40ms"]
    
    REDIS -->|"Metadata HIT +<br/>Content MISS<br/>(large paste)"| S3_CONTENT["Tier 3: S3 Origin<br/>Fetch content from S3<br/>Latency: 50-150ms"]
    
    REDIS -->|"Metadata MISS"| DB_LOOKUP["PostgreSQL lookup<br/>then populate cache"]
    DB_LOOKUP --> S3_CONTENT

Three-tier caching architecture for Pastebin. Tier 1 is the CDN - CloudFront edge nodes cache paste content globally. A CDN hit serves content in 5 to 15 milliseconds. Tier 2 is Redis at the application layer. Redis caches metadata for all pastes and content for small pastes under 50 kilobytes. A full Redis hit serves in 20 to 40 milliseconds. For large pastes, Redis provides metadata but content comes from S3 - Tier 3 - at 50 to 150 milliseconds. If metadata isn't in Redis, it's loaded from PostgreSQL and cached for future requests.

Tier 1: CDN Caching (CloudFront)

The CDN is the most effective caching layer for Pastebin because paste content is immutable and static - perfect for edge caching.

What the CDN caches:

CDN cache invalidation on delete:

When a paste is deleted (via delete token), the CDN cache must be invalidated. CloudFront invalidation takes 5-10 minutes to propagate globally. During this window, the deleted paste may still be served from edge caches.

def invalidate_cdn_cache(paste_id):
    cloudfront.create_invalidation(
        DistributionId=CDN_DISTRIBUTION_ID,
        InvalidationBatch={
            'Paths': {
                'Quantity': 2,
                'Items': [
                    f'/api/v1/pastes/{paste_id}',
                    f'/api/v1/pastes/{paste_id}/raw'
                ]
            },
            'CallerReference': f'delete-{paste_id}-{int(time.time())}'
        }
    )

CDN cache key design:

The cache key must include the Accept-Encoding header to serve the right compression variant:

Cache key: {paste_id} + {Accept-Encoding: gzip | br | identity}

This means CloudFront stores separate cached copies for clients that accept gzip, brotli, or no compression. Most modern browsers send Accept-Encoding: gzip, br, so the brotli variant will be the most commonly cached.

Interview: What to say: "The CDN is the most valuable cache tier for Pastebin because paste content is immutable - once created, it never changes. I'd cache raw content at the edge for 1 hour. The only cache invalidation scenario is paste deletion, which I'd handle through CloudFront invalidation. The 5-10 minute propagation delay is acceptable for a public paste service."

Tier 2: Redis Caching (Application Layer)

Redis caches two categories of data with different strategies:

Category 1: Metadata (all pastes)

Every paste's metadata is cached in Redis as a small JSON object:

# Cache key format
METADATA_KEY = "paste:meta:{paste_id}"

# Cached data (~200-300 bytes per paste)
{
    "paste_id": "x7Kf2mBp",
    "title": "My Script",
    "language": "python",
    "content_size": 4096,
    "compressed_size": 1234,
    "s3_key": "pastes/x7Kf2mBp",
    "created_at": "2026-06-14T14:30:00Z",
    "expires_at": "2026-06-21T14:30:00Z",
    "visibility": "unlisted"
}

Metadata entries are tiny - 200-300 bytes each. Even caching 10 million metadata entries uses only 2-3 GB of Redis memory. This is always cached, no size-based filtering needed.

Category 2: Content (small pastes only)

Here's where the size-based tiering happens:

CONTENT_SIZE_THRESHOLD = 50 * 1024  # 50 KB

CONTENT_KEY = "paste:content:{paste_id}"

def cache_paste_content(paste_id, content, content_size):
    """Only cache content in Redis if it's below the size threshold."""
    if content_size <= CONTENT_SIZE_THRESHOLD:
        redis.setex(
            CONTENT_KEY.format(paste_id=paste_id),
            time=3600,  # 1 hour TTL
            value=content  # Already gzip-compressed
        )
    # Large pastes are NOT cached in Redis - served from CDN/S3

Why 50 KB as the threshold? Let's do the math:

Redis memory budget: 16 GB
Metadata cache: 10 million entries × 300 bytes = 3 GB
Remaining for content: 13 GB

At 50 KB threshold:
- 70% of pastes are < 10 KB → average cached content = 5 KB (compressed ~1.5 KB)
- 15% of pastes are 10-50 KB → average cached content = 25 KB (compressed ~8 KB)
- Weighted average cached content: ~3 KB compressed

13 GB / 3 KB = ~4.3 million paste contents cached
Daily views: 25 million
If top 4.3 million pastes cover 80% of views (Zipf distribution) → 80% cache hit rate

flowchart LR
    subgraph REDIS["Redis Memory Budget: 16 GB"]
        META["Metadata Cache<br/>3 GB<br/>10M entries × 300 bytes"]
        SMALL["Small Paste Content<br/>13 GB<br/>~4.3M entries × 3 KB avg"]
    end
    
    subgraph NOT_CACHED["NOT in Redis"]
        LARGE["Large pastes (>50 KB)<br/>Served from CDN / S3"]
    end
    
    HIT_RATE["Expected hit rate: ~80%<br/>for metadata + content combined"]

Redis memory allocation for Pastebin. With a 16 gigabyte Redis budget, 3 gigabytes are allocated to metadata - caching 10 million paste metadata entries at 300 bytes each. The remaining 13 gigabytes cache small paste content - about 4.3 million entries at an average of 3 kilobytes compressed each. Large pastes over 50 kilobytes are never stored in Redis - they're served from CDN or S3 directly. With a Zipf-like access distribution where popular pastes are viewed much more often, the expected combined hit rate for metadata plus content is about 80 percent.

Tier 3: S3 Origin (Cache Miss)

When both CDN and Redis miss, the content is fetched from S3:

def fetch_paste_content(paste_id, s3_key, content_size):
    """Fetch content from S3 - the origin of truth."""
    response = s3.get_object(
        Bucket="paste-content",
        Key=s3_key
    )
    content = response['Body'].read()
    
    # Backfill Redis cache if the paste is small enough
    if content_size <= CONTENT_SIZE_THRESHOLD:
        redis.setex(f"paste:content:{paste_id}", time=3600, value=content)
    
    return content

S3 latency for content retrieval is 50-150ms depending on object size and region. This is acceptable for cache misses - the CDN and Redis layers handle the common case.

The Complete Read Flow with Caching

Let me trace through the full read path for different scenarios:

def view_paste(paste_id):
    # Note: CDN check happens before this code - CDN hit never reaches the API server
    
    # Step 1: Check Redis for metadata
    metadata = redis.get(f"paste:meta:{paste_id}")
    
    if not metadata:
        # Step 1b: Cache miss - load from PostgreSQL
        metadata = db.query(
            "SELECT * FROM paste_metadata WHERE paste_id = %s AND deleted_at IS NULL",
            paste_id
        )
        if not metadata:
            return 404  # Paste doesn't exist
        
        if metadata.expires_at and metadata.expires_at < datetime.now():
            return 410  # Paste has expired (lazy expiration)
        
        # Populate metadata cache
        ttl = calculate_ttl(metadata.expires_at)
        redis.setex(f"paste:meta:{paste_id}", time=min(ttl, 3600), value=json.dumps(metadata))
    
    # Step 2: Content retrieval (size-dependent)
    if metadata['content_size'] <= CONTENT_SIZE_THRESHOLD:
        # Small paste - try Redis content cache
        content = redis.get(f"paste:content:{paste_id}")
        if not content:
            # Redis miss - fetch from S3 and backfill
            content = s3.get_object(Bucket="paste-content", Key=metadata['s3_key'])['Body'].read()
            redis.setex(f"paste:content:{paste_id}", time=min(ttl, 3600), value=content)
        return {"metadata": metadata, "content": decompress(content)}
    else:
        # Large paste - return CDN URL for client-side fetch
        content_url = f"https://cdn.paste.ly/{metadata['s3_key']}"
        return {"metadata": metadata, "content_url": content_url}

def calculate_ttl(expires_at):
    """Cache TTL should not exceed the paste's expiration time."""
    if expires_at is None:
        return 3600  # 1 hour for never-expire pastes
    
    remaining = (expires_at - datetime.now()).total_seconds()
    return max(int(remaining), 0)

Tip: Cache TTL must respect paste expiration. If a paste expires in 10 minutes, caching it for 1 hour would serve expired content from cache. Always set the cache TTL to min(default_ttl, time_until_expiration). This prevents serving stale expired content - a subtle but critical correctness issue.

Cache Population Strategies

Write-Through for Paste Creation

When a paste is created, immediately populate both the metadata and content caches:

def create_paste(content, **kwargs):
    paste_id = generate_paste_id()
    compressed = gzip.compress(content.encode())
    
    # 1. Store in S3 (source of truth)
    s3.put_object(Bucket="paste-content", Key=f"pastes/{paste_id}", Body=compressed)
    
    # 2. Store metadata in PostgreSQL
    db.execute("INSERT INTO paste_metadata ...", ...)
    
    # 3. Write-through: populate Redis cache immediately
    redis.setex(f"paste:meta:{paste_id}", time=3600, value=json.dumps(metadata))
    
    if len(compressed) <= CONTENT_SIZE_THRESHOLD:
        redis.setex(f"paste:content:{paste_id}", time=3600, value=compressed)
    
    return paste_id

Why write-through instead of lazy population?

For Pastebin, a paste is typically viewed within minutes of creation (the creator shares the URL immediately). Write-through ensures the first view - often the most latency-sensitive because the creator is watching - hits the cache.

Cache Invalidation on Delete

When a paste is deleted, all cache entries must be invalidated:

def delete_paste(paste_id):
    # ... verify delete token, soft-delete in DB ...
    
    # Invalidate all cache tiers
    # Tier 2: Redis
    redis.delete(f"paste:meta:{paste_id}")
    redis.delete(f"paste:content:{paste_id}")
    
    # Tier 1: CDN (async - takes 5-10 minutes)
    invalidate_cdn_cache(paste_id)

Cache Invalidation on Expiration

The cleanup worker invalidates cache entries for expired pastes:

def cleanup_expired():
    expired_ids = db.query(
        "SELECT paste_id FROM paste_metadata "
        "WHERE expires_at < NOW() AND deleted_at IS NULL "
        "LIMIT 10000"
    )
    
    for paste_id in expired_ids:
        redis.delete(f"paste:meta:{paste_id}")
        redis.delete(f"paste:content:{paste_id}")
        # CDN invalidation for expired pastes is usually not worth the cost
        # - the CDN TTL (1 hour) will handle it naturally

Interview: A nuance to mention: "I wouldn't issue CDN invalidations for expired pastes. CDN invalidation costs $0.005 per path, and if thousands of pastes expire hourly, the invalidation costs add up. Since CDN cache TTL is 1 hour, expired content naturally drops out of CDN cache within an hour of expiration. The worst case is someone views an expired paste from CDN cache and gets the content - but then the next request hits the API server, which checks expiration and returns 410."

Cache Stampede Protection

A cache stampede happens when a popular paste's cache entry expires and hundreds of simultaneous requests all miss the cache and hit the database/S3 at the same time. For Pastebin, this is less severe than for URL Shortener (250 QPS vs 100K QPS), but still worth addressing.

flowchart TD
    EXPIRE["Popular paste cache entry<br/>expires at 14:00:00"] --> REQUESTS["50 simultaneous requests<br/>at 14:00:01"]
    
    REQUESTS --> WITHOUT{"Without protection"}
    REQUESTS --> WITH{"With protection"}
    
    WITHOUT --> STORM["50 S3 GETs +<br/>50 DB queries<br/>(cache stampede)"]
    
    WITH --> LOCK["1 request acquires lock<br/>49 requests wait"]
    LOCK --> FETCH["1 S3 GET +<br/>1 DB query"]
    FETCH --> POPULATE["Cache repopulated"]
    POPULATE --> SERVE["All 50 requests<br/>served from cache"]

Cache stampede protection. When a popular paste's cache entry expires, many simultaneous requests may miss the cache at once. Without protection, all requests hit S3 and the database simultaneously - a stampede. With protection, one request acquires a lock and fetches the content while the other requests wait briefly. Once the cache is repopulated, all waiting requests are served from cache. For Pastebin's moderate traffic of 250 QPS, a stampede involves tens of requests, not thousands - less severe than URL Shortener, but still worth preventing.

Implementation with Redis distributed lock:

def get_with_stampede_protection(paste_id, fetch_fn, ttl=3600):
    """Fetch from cache with stampede protection using Redis SETNX lock."""
    cache_key = f"paste:content:{paste_id}"
    lock_key = f"lock:paste:{paste_id}"
    
    # Try cache first
    cached = redis.get(cache_key)
    if cached:
        return cached
    
    # Cache miss - try to acquire lock
    lock_acquired = redis.set(lock_key, "1", nx=True, ex=10)  # Lock for 10 seconds
    
    if lock_acquired:
        try:
            # We have the lock - fetch from S3 and populate cache
            content = fetch_fn(paste_id)
            redis.setex(cache_key, time=ttl, value=content)
            return content
        finally:
            redis.delete(lock_key)
    else:
        # Another request has the lock - wait and retry
        for _ in range(20):  # Wait up to 2 seconds
            time.sleep(0.1)
            cached = redis.get(cache_key)
            if cached:
                return cached
        
        # Timeout - fetch directly (fallback)
        return fetch_fn(paste_id)

Hot Paste Handling

Unlike URL Shortener where a "hot key" is a popular redirect, Pastebin's hot key is a popular paste that might be 1 MB. The bandwidth impact is much larger.

Scenario: A paste with 500 KB of code goes viral on Hacker News. It gets 10,000 views per hour - 2.8 views per second. Each view returns 500 KB of content.

Bandwidth: 2.8 views/sec × 500 KB = 1.4 MB/sec from this single paste

This is manageable for a single Redis node, but if the paste is 5 MB and gets 100 views/sec:

Bandwidth: 100 views/sec × 5 MB = 500 MB/sec - this would overwhelm Redis

The CDN handles this naturally for the raw content endpoint. But the API endpoint (which includes metadata) doesn't go through CDN unless you configure it to. Solutions:

# Local in-memory LRU cache on each API server
from functools import lru_cache
import time

# Cache the top 100 paste contents in process memory
# Entries evicted after 5 minutes
HOT_PASTE_CACHE = {}

def get_hot_paste(paste_id, content_size):
    """Local memory cache for viral pastes."""
    cached = HOT_PASTE_CACHE.get(paste_id)
    if cached and time.time() - cached['timestamp'] < 300:  # 5 min TTL
        return cached['content']
    
    # Only cache in local memory if the paste is being accessed frequently
    # AND is small enough to not blow up process memory
    if content_size <= 100_000:  # 100 KB max for local cache
        content = redis.get(f"paste:content:{paste_id}")
        if content:
            HOT_PASTE_CACHE[paste_id] = {
                'content': content,
                'timestamp': time.time()
            }
            # Evict oldest entries if cache exceeds 100 MB
            while sys.getsizeof(HOT_PASTE_CACHE) > 100 * 1024 * 1024:
                oldest_key = min(HOT_PASTE_CACHE, key=lambda k: HOT_PASTE_CACHE[k]['timestamp'])
                del HOT_PASTE_CACHE[oldest_key]
        return content
    
    return None  # Large hot pastes go through CDN, not local cache

Warning: Don't cache large content in Redis or local memory to solve hot-paste problems. The correct answer for large hot pastes is CDN. The CDN is designed to serve static content at scale from edge nodes. Trying to solve this at the application layer (Redis or in-memory) means you're fighting the problem at the wrong layer. Tell the interviewer: "For large hot pastes, the CDN is the right caching tier. It's purpose-built for serving static content at scale."

Cache Memory Budget Planning

Let me lay out the complete Redis memory allocation:

Total Redis memory: 16 GB (1 × r6g.xlarge instance)

Breakdown:
├── Metadata cache:          3 GB   (10M entries × ~300 bytes)
├── Small paste content:    11 GB   (~3.6M entries × ~3 KB compressed avg)
├── Operational overhead:    1.5 GB  (Redis internal data structures, fragmentation)
└── Headroom:               0.5 GB  (buffer for spikes)

Hit rate estimation:
- Metadata: ~90% (most viewed pastes are recent → cached)
- Content (small pastes): ~75% (Zipf distribution - popular pastes stay cached)
- Overall read path: ~80% of requests fully served from cache
- Remaining 20%: metadata from cache + content from CDN/S3

flowchart LR
    subgraph BUDGET["Redis 16 GB"]
        META_BUDGET["Metadata<br/>3 GB<br/>10M entries"]
        CONTENT_BUDGET["Content<br/>11 GB<br/>3.6M small pastes"]
        OH["Overhead<br/>2 GB"]
    end
    
    subgraph PERFORMANCE["Performance"]
        META_HIT["Metadata hit rate:<br/>~90%"]
        CONTENT_HIT["Content hit rate:<br/>~75%<br/>(small pastes only)"]
        OVERALL["Overall: ~80%<br/>of reads fully<br/>served from cache"]
    end

Redis memory budget for Pastebin. Out of 16 gigabytes total, 3 gigabytes are allocated to metadata caching - holding about 10 million entries. 11 gigabytes are allocated to small paste content - holding about 3.6 million compressed entries. The remaining 2 gigabytes cover Redis internal overhead and fragmentation. The expected metadata hit rate is about 90 percent because most viewed pastes are recent. The content hit rate for small pastes is about 75 percent following a Zipf distribution. Overall, about 80 percent of read requests are fully served from cache without touching S3.

Caching Architecture Comparison: URL Shortener vs Pastebin

Interview: How to summarize the caching design: "Pastebin uses three caching tiers. Tier 1 is CloudFront CDN for global content delivery - it caches raw paste content at edge nodes for 1 hour, which handles viral pastes and global latency. Tier 2 is Redis for metadata and small paste content under 50 KB - this covers 85% of pastes and gives 20-40ms latency. Tier 3 is S3 as the origin. The key design insight is size-based tiering - I don't cache 5 MB pastes in Redis because one viral large paste would evict thousands of small cached pastes. Large pastes go through CDN, small pastes go through Redis."

Key Takeaways

1. Tiered caching by content size is the defining design choice. Small pastes (under 50 KB) are cached in Redis. Large pastes are served from CDN/S3. This prevents a few large pastes from monopolising cache memory.

2. Three tiers: CDN → Redis → S3. CDN handles global distribution and bandwidth spikes. Redis handles low-latency metadata and small content. S3 is the origin of truth. Each tier solves a different problem.

3. Cache TTL must respect paste expiration. A paste expiring in 10 minutes must not be cached for 1 hour. Always set TTL to min(default_ttl, time_until_expiration).

4. CDN is the answer for large hot pastes, not Redis. When a 1 MB paste goes viral, the CDN absorbs the bandwidth at edge nodes. Trying to handle this in Redis or local memory is fighting at the wrong layer.

5. Write-through caching prepares for the creator's immediate view. The creator shares the URL right after creation. Populating the cache on write ensures the first view is a cache hit - a small latency investment on the write path that improves the most latency-sensitive read.

6. Cache stampede protection is simpler than for URL Shortener. At 250 QPS, a stampede involves tens of requests, not thousands. A simple Redis lock with polling fallback is sufficient - no need for probabilistic early expiration or background refresh.

Exercise: Exercise 1: Design a cache warming strategy for Pastebin. When a new API server starts up, its local cache is cold. Should it pre-load popular pastes from Redis? How would you identify the "popular" pastes to warm? (Hint: maintain a sorted set in Redis tracking view counts, and warm the top N entries on server startup.)

Exercise 2: Calculate the CDN cost for Pastebin. CloudFront charges $0.085/GB for the first 10 TB/month of data transfer. At 250 read QPS with 10 KB average content (3 KB compressed), what's the monthly data transfer? What's the monthly cost? How does this compare to serving everything from the origin?

Exercise 3: The product team wants to add a "trending pastes" page showing the most-viewed public pastes in the last 24 hours. Design the caching strategy for this feature. Where do you store view counts? How do you rank pastes by views in the last 24 hours? Can you use Redis sorted sets? What's the cache invalidation strategy for the trending page?

Back to System Design Interviews