Caching

Instagram:
- 20% of posts receive 80% of views
- A viral post from a celebrity gets millions of views
- A post from a private account gets 50 views
- Caching the top 20% of posts handles 80% of read traffic

YouTube:
- ~10% of videos account for ~90% of views
- "Baby Shark" has 14 billion views
- Most videos have under 1,000 views
- Caching popular videos saves enormous bandwidth

E-commerce (Amazon):
- 20% of products generate 80% of page views
- iPhone listing: millions of views per day
- Obscure industrial part: 3 views per month
- Cache the popular product pages

Good candidates for caching:
- Data that is read frequently and written rarely (user profiles)
- Data that is expensive to compute (feed ranking results)
- Data that doesn't change often (product catalog, configuration)
- Data where slight staleness is acceptable (follower counts)

Bad candidates for caching:
- Data that changes on every read (real-time stock prices with microsecond precision)
- Data that is unique per request (one-time password)
- Data that must always be perfectly consistent (bank balance during transfer)
- Large data that is rarely re-accessed (log entries)

Cache hit rate = cache hits / total requests × 100%

Example:
- 100,000 requests per second
- 80,000 served from cache (hits)
- 20,000 go to database (misses)
- Hit rate: 80%

Impact of hit rate on average latency:
- 70% hit rate: 0.7 × 0.5ms + 0.3 × 50ms = 15.35ms
- 80% hit rate: 0.8 × 0.5ms + 0.2 × 50ms = 10.40ms
- 90% hit rate: 0.9 × 0.5ms + 0.1 × 50ms =  5.45ms
- 95% hit rate: 0.95 × 0.5ms + 0.05 × 50ms = 2.98ms

Every 10% improvement in hit rate roughly halves average latency.
Going from 80% to 90% has more impact than going from 0% to 80%
on per-request latency.

def get_user_profile(user_id):
    # Step 1: Check cache
    cache_key = f"user:{user_id}"
    cached = redis.get(cache_key)

    if cached is not None:
        return json.loads(cached)  # Cache hit, return immediately

    # Step 2: Cache miss, query database
    user = db.query("SELECT * FROM users WHERE user_id = ?", user_id)

    # Step 3: Store in cache for future requests
    redis.setex(cache_key, 300, json.dumps(user))  # TTL = 300 seconds (5 min)

    return user

def update_user_profile(user_id, new_data):
    # Step 1: Write to database
    db.update("UPDATE users SET ... WHERE user_id = ?", user_id, new_data)

    # Step 2: Write to cache (same transaction)
    cache_key = f"user:{user_id}"
    redis.setex(cache_key, 300, json.dumps(new_data))

    # Cache is immediately consistent with database

def update_user_profile(user_id, new_data):
    # Step 1: Write to cache only (fast)
    cache_key = f"user:{user_id}"
    redis.setex(cache_key, 300, json.dumps(new_data))

    # Step 2: Enqueue async write to database
    queue.send({"action": "update_user", "user_id": user_id, "data": new_data})

    # Database is updated later by a background worker

Cache-Aside (most common):
- Read-heavy workloads (social media feeds, user profiles)
- Data where slight staleness is acceptable
- When you want simplicity

Write-Through:
- Data that must be immediately consistent in cache and database
- Read-after-write scenarios (user updates profile, immediately views it)
- When write volume is moderate

Write-Behind:
- Write-heavy workloads (analytics events, counters)
- When write latency must be minimal
- When you can tolerate potential data loss on cache crash
- When the database cannot keep up with write throughput

Cache size: 10 GB (can hold ~10 million user profiles at ~1 KB each)
Total users: 2 billion
Only 0.5% of users fit in cache at any time.

The eviction policy determines WHICH 0.5% stays in cache.
A good policy keeps the most frequently accessed data.
A bad policy evicts popular data and keeps rarely accessed data.

Impact:
- Good policy: 85% cache hit rate
- Bad policy: 40% cache hit rate
- Difference: 4.5x more database load with a bad policy

Evicts the entry with the fewest total accesses.

Advantage over LRU:
- A consistently popular item won't be evicted just because
  it wasn't accessed in the last few minutes
- Better for workloads with stable hot data

Disadvantage:
- New items start with low frequency and get evicted quickly
  (even if they would become popular)
- Must track access count per key (more memory overhead)

Use case: CDN caching where popular content stays popular for weeks

Evicts the oldest entry, regardless of access pattern.

Advantage: Simplest to implement (just a queue)
Disadvantage: Ignores popularity entirely

Use case: Simple TTL-based caches where age is the only factor

Each entry has an expiration timestamp. Entries are removed when expired.

SET user:123 {profile_data} EX 300    # Expires in 300 seconds (5 minutes)

TTL is not strictly an eviction policy. It's typically combined with
another policy (e.g., LRU with TTL). TTL handles staleness, LRU
handles capacity.

Choosing TTL values:
- Session data: 30 minutes
- User profile: 5-15 minutes
- Feed cache: 1-5 minutes
- Configuration: 1-24 hours
- Product catalog: 1 hour

Trade-off: Longer TTL = higher hit rate but more stale data

Option A: Invalidate immediately on every write
- Guarantees freshness
- But: requires knowing every cache key affected by every write
- A single database write might affect 10 different cache keys
  (user profile cache, feed cache, search cache, follower list cache)
- Coordinating all invalidations correctly is error-prone

Option B: Use short TTLs
- Simple (no invalidation logic needed)
- But: frequent cache misses reduce hit rate
- But: data is stale for up to TTL duration

Option C: Never invalidate, always serve stale
- Highest hit rate
- But: completely unacceptable for most use cases

Set an expiration on every cache entry. Data is automatically
removed after the TTL expires.

redis.setex("user:123", 300, profile_data)  # Expires in 5 minutes

Pros: Simple, predictable, no coordination needed
Cons: Data is stale for up to TTL duration
Best for: Data where slight staleness is acceptable (follower count, feed)

def update_user_profile(user_id, new_data):
    # Update database
    db.update("UPDATE users SET ... WHERE user_id = ?", user_id, new_data)

    # Invalidate cache (delete the stale entry)
    redis.delete(f"user:{user_id}")

    # Next read will trigger a cache miss and fetch fresh data

# More aggressive: invalidate AND repopulate
def update_user_profile_v2(user_id, new_data):
    db.update("UPDATE users SET ... WHERE user_id = ?", user_id, new_data)
    redis.setex(f"user:{user_id}", 300, json.dumps(new_data))  # Write-through

Pros: Data is fresh immediately after write
Cons: Must identify and invalidate all affected cache keys
      Risk of bugs (forget to invalidate a key, stale data persists)
Best for: Data where freshness matters (user profile, permissions)

Use event-based invalidation for critical writes (profile update, permission change)
AND set a TTL as a safety net (if invalidation is missed, TTL catches it)

This is the most common production approach.
Event-based handles the common case (immediate freshness).
TTL handles the edge case (if event-based invalidation fails).

All data lives in RAM:
- RAM read: ~100 nanoseconds
- SSD read: ~150 microseconds (1,500x slower)
- HDD read: ~10 milliseconds (100,000x slower)

Single-threaded event loop:
- No locking overhead
- No context switching
- Processes commands sequentially at extreme speed

Optimized data structures:
- Hash tables, skip lists, compressed lists
- Purpose-built for fast in-memory operations

Small (1 app, <10K users):
  Single Redis instance, 1-4 GB RAM

Medium (microservices, 100K-10M users):
  Redis Sentinel: 1 primary + 2 replicas, automatic failover
  16-64 GB RAM per node

Large (Instagram, Twitter scale):
  Redis Cluster: 100-400 nodes
  Data partitioned across nodes by key hash
  Total memory: 1-10 TB across cluster

Scenario:
- Large number of cache entries expire at the same time
- Massive spike in cache misses
- Database suddenly receives all the traffic the cache was absorbing
- Database cannot handle the spike, system degrades or crashes

Cause: Setting the same TTL for all entries loaded at the same time
(e.g., cache warmed up at startup, all entries get TTL=300s,
 all expire exactly 300 seconds later)

1. Locking (Mutex):
   First request acquires a lock, fetches from database, populates cache.
   Other requests wait for the lock, then read from cache.

   def get_with_lock(key):
       value = redis.get(key)
       if value: return value

       if redis.set(f"lock:{key}", 1, nx=True, ex=5):  # Acquire lock
           value = db.query(...)
           redis.setex(key, 300, value)
           redis.delete(f"lock:{key}")
           return value
       else:
           time.sleep(0.05)        # Wait for other request to populate
           return redis.get(key)   # Read from cache

2. Early Refresh:
   Refresh cache before TTL expires. If TTL is 300s, refresh at 270s.
   Cache never actually expires, so stampede never happens.

1. Cache null results:
   If database returns no result, cache a null/empty value with short TTL.
   redis.setex("user:99999999999", 60, "NULL")  # Cache "not found" for 60s

2. Bloom filter:
   Before checking cache or database, check a bloom filter.
   If the bloom filter says "definitely not exists," skip the lookup entirely.
   Bloom filters use minimal memory (~1 byte per entry) and have O(1) lookup.

1. Randomized TTL:
   Instead of TTL=300 for all keys, use TTL=300 + random(0, 60).
   Entries expire at different times, spreading the load.

2. Staggered warm-up:
   When restarting cache, don't load everything at once.
   Load entries gradually over 5-10 minutes.

3. Multi-layer caching:
   If application cache misses, fall back to a secondary cache
   or CDN cache before hitting the database.

Architecture:
- EVCache (based on Memcached): distributed caching layer
- ~3 trillion cache operations per day
- Cache hit rate: 99%+ for user profiles and content metadata
- 1,000+ cache nodes across multiple AWS regions

Impact:
- Without cache: Would need ~100,000 database servers
- With cache: ~1,000 database servers (99% reduction)

Architecture:
- Redis and Memcached for different use cases
- Feed cache: pre-computed feed stored per user in Redis
- Session cache: user sessions in Memcached
- Cache cluster: 100s of instances

Feed caching strategy:
- Cache key: "feed:{user_id}"
- Value: Sorted set of post IDs
- TTL: 5 minutes
- Hit rate: ~80%
- Feed load from cache: ~50-100ms
- Feed load from database: ~300-500ms

Mistake 1: "We'll cache everything"
Problem: Caching has costs (memory, invalidation complexity, staleness).
Not everything should be cached.
Better: "I'll cache the user profile and feed data because they're
read-heavy (100:1 read:write ratio) and slight staleness is acceptable.
I won't cache the payment status because it must always be consistent."

Mistake 2: Not mentioning cache invalidation
Problem: Saying "we'll use Redis to cache" without explaining how
stale data is handled shows incomplete thinking.
Better: "We'll use cache-aside with a 5-minute TTL. On profile update,
we'll invalidate the cache key immediately. The TTL acts as a safety
net if the invalidation fails."

Mistake 3: Ignoring cache failure scenarios
Problem: Not considering what happens when the cache goes down.
Better: "If Redis goes down, we fall back to database reads.
Response times will increase from ~1ms to ~50ms, but the system
remains functional. We'll use Redis Sentinel for automatic failover
to minimize cache downtime."

Mistake 4: Using cache for data that needs strong consistency
Problem: Caching bank balances or inventory counts with a 5-minute TTL.
Better: "For inventory counts, we read directly from the database
within a transaction. Serving a stale inventory count could result
in overselling."

Mistake 5: Not specifying TTL values
Problem: "We'll cache it with a reasonable TTL."
Better: "Feed cache: 5-minute TTL. User profile: 15-minute TTL.
Configuration data: 1-hour TTL. Session: 30-minute TTL."
Specific numbers show practical experience.

- Redis GET/SET latency: ~0.1-0.5ms
- Redis throughput: 100K-500K ops/sec per node
- Target cache hit rate: 80%+ (production systems often achieve 90-99%)
- Typical TTLs: 1-15 minutes for application cache, hours-days for CDN
- Cache vs database speed: 10-100x faster
- Netflix cache hit rate: 99%+

Section 5 (Scaling):     Caching is Stage 5 of the scaling progression
Section 7 (Load Balancing): Load balancer distributes traffic, cache reduces it
Section 8 (CDN):          CDN is a specialized cache at the edge layer
Section 13 (Design Exercise): URL shortener uses cache for most-accessed URLs