Redis Data Structures, Caching Patterns & Atomic Rate Limiting

High-scale Python web applications rely on Redis as an in-memory key-value data store, caching engine, and distributed lock manager. Understanding Redis data structures (Strings, Hashes, Sorted Sets ZSET), caching strategies (Cache-Aside, Write-Through), Cache Stampede Mitigation (Probabilistic Early Expiration / Mutexes), and Atomic Token Bucket Rate Limiting using Lua scripts is critical for system architecture interviews.

This chapter details Redis internal data structures, Cache-Aside pattern, Cache Stampede solutions, and atomic Token Bucket rate limiting in Python.

1. Redis Core Data Structures & Use Cases

Data Structure	Internal Implementation	O(1) / O(N)	Key Production Use Cases
String	Simple Dynamic String (`sds`)	$O(1)$	Session tokens, raw JSON string caching, atomic counters (`INCR`).
Hash	ZipList / Dict	$O(1)$	User profile objects (`HSET user:100 name "Alice" age 30`).
List	QuickList (Linked List of ZipLists)	$O(1)$ head/tail	Background worker job queues (`LPUSH` / `BRPOP`).
Set	IntSet / HashTable	$O(1)$	Unique IP tracking, tag matching (`SADD`, `SINTER`).
Sorted Set (`ZSET`)	SkipList + HashTable	$O(\log N)$	Leaderboards, Sliding Window Rate Limiters (`ZADD`).

2. Enterprise Caching Strategies

1. CACHE-ASIDE (Lazy Loading - Most Popular):
   - Read Path: App checks Redis -> If HIT, return. If MISS, query DB -> Store in Redis -> Return.
   - Write Path: App updates DB directly -> Invalidates (deletes) cache key in Redis.

2. WRITE-THROUGH:
   - App writes to Cache -> Cache synchronously writes to DB before returning success.

3. WRITE-BEHIND (Write-Back):
   - App writes to Cache -> Cache asynchronously flushes writes to DB in background batches.

3. The Cache Stampede Problem & Solutions

A Cache Stampede (or Thundering Herd) occurs when a hot cache key expires under high traffic (e.g. 10,000 requests/sec). All 10,000 concurrent workers experience a cache miss simultaneously, overwhelming the primary SQL database with duplicate queries!

Cache Stampede Execution Spike:

[ Hot Cache Key Expires! ]
           |
           ├── Worker 1 Miss ──> [ Query Primary DB ] ──┐
           ├── Worker 2 Miss ──> [ Query Primary DB ] ──┼──> [ DATABASE CRASHES! ]
           └── Worker N Miss ──> [ Query Primary DB ] ──┘

Solutions:

Mutex Locking (Distributed Lock): The first worker acquiring SET key:lock uuid NX PX 5000 queries the DB and populates the cache; other workers wait or return stale data.
Probabilistic Early Expiration (XFetch): As the TTL approaches expiration, requests probabilistically re-compute the cache early based on read frequency and computation time:

Recompute If: -beta * delta * ln(rand()) > TTL

4. Atomic Rate Limiting in Python with Redis Lua Scripts

Rate limiting protects APIs from abuse. Implementing Token Bucket or Sliding Window rate limiters requires Atomicity so concurrent requests don’t bypass limits due to race conditions.

Redis executes Lua scripts atomically within a single thread:

# Atomic Token Bucket Rate Limiter via Redis Lua Script
import redis

redis_client = redis.Redis.from_url("redis://localhost:6379/0")

# Lua Script: Atomically checks and decrements token bucket
TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local ttl = tonumber(ARGV[2])

local current = tonumber(redis.call('get', key) or "0")

if current + 1 > limit then
    return 0 -- Limit Exceeded!
else
    redis.call('INCRBY', key, 1)
    if current == 0 then
        redis.call('EXPIRE', key, ttl)
    end
    return 1 -- Request Allowed!
end
"""

rate_limit_script = redis_client.register_script(TOKEN_BUCKET_LUA)

def is_request_allowed(user_id: str, limit: int = 100, window_seconds: int = 60) -> bool:
    key = f"rate_limit:{user_id}"
    # Executes Lua script atomically on Redis server!
    allowed = rate_limit_script(keys=[key], args=[limit, window_seconds])
    return bool(allowed)

⚡

Revision Mode Active Condensed for 5-minute review. Focused on 30-second pitches, mental anchors, and high-frequency interview traps.

⚡ 30-Second Elevator Pitch

“Redis stores data in-memory across 5 core structures (Strings, Hashes, Lists, Sets, ZSET SkipLists). Use Cache-Aside for general caching, invalidating keys on write. Mitigate Cache Stampedes using Mutex locks or Probabilistic Early Expiration. Execute rate limiting atomically using Redis Lua scripts to prevent race condition bypasses.”

🧠 Under The Hood & Mental Model

ZSET SkipList: Implements $O(\log N)$ insertions and range queries, powering sliding-window rate limiters and leaderboards.
Cache-Aside Invalidation: Delete cache keys on SQL write rather than updating them, avoiding stale data race conditions under concurrent writes.
Cache Stampede Mutex: SET lock_key uuid NX PX 5000 guarantees only 1 worker re-populates the expired cache key.
Atomic Lua Execution: Redis executes Lua scripts as single atomic commands, eliminating read-modify-write race conditions.

💻 High-Yield Code & Gotcha

# ❌ ANTI-PATTERN: Non-Atomic Rate Limiting in Python
def rate_limit(user_id):
    count = redis_client.get(f"limit:{user_id}")  # Step 1: Read
    if int(count or 0) > 100:                     # Step 2: Check
        return False
    redis_client.incr(f"limit:{user_id}")         # ❌ TRAP: Race condition under 100 concurrent requests!
    return True

# ✅ PRODUCTION PATTERN: Atomic Lua Script Rate Limiting
# SAFE: Executed atomically inside Redis single-threaded execution engine!
allowed = rate_limit_script(keys=[f"limit:{user_id}"], args=[100, 60])

⚠️ GOTCHA: Updating Cache vs Invalidating Cache on Write

Inside Cache-Aside write handlers, always delete the cache key (redis.delete(key)) instead of updating it (redis.set(key, new_val)). Under concurrent writes, updating the cache causes race conditions where an older write overwrites a newer write in Redis!

⚖️ Trade-Offs & Comparison

+ Redis In-Memory Operations: Sub-millisecond read/write latencies; atomic Lua script execution.
- RAM Limitations: All data must fit in RAM; volatile data requires configuring appropriate eviction policies (allkeys-lru).

🌟 My Experience (STAR Anchor)

“A flash-sale endpoint suffered database crashes when hot product caches expired, causing a Cache Stampede of 15,000 queries. I implemented a Redis Mutex lock combined with Probabilistic Early Expiration, eliminating database spikes and stabilizing cache re-population.”

Python Interview Handbook