The Computing Series
Algorithm Engineering › Memoization Is Caching › The Concept

The Concept

Memoization in Book 1:

def fib(n: int, memo: dict = {}) -> int:
    if n in memo:
        return memo[n]           # cache hit
    if n <= 1:
        return n
    result = fib(n-1, memo) + fib(n-2, memo)
    memo[n] = result             # cache fill
    return result

Infrastructure caching in production:

import redis

r = redis.Redis()

def get_user_profile(user_id: int) -> dict:
    cache_key = f"user:{user_id}:profile"
    cached = r.get(cache_key)
    if cached:
        return json.loads(cached)      # cache hit
    profile = db.query(f"SELECT * FROM users WHERE id={user_id}")
    r.setex(cache_key, 300, json.dumps(profile))  # cache fill, TTL=300s
    return profile

The structure is identical. The difference: - fib(n) is a pure function: the same input always produces the same output. The memo table never needs invalidation. - get_user_profile(user_id) reads from a mutable database: the user can update their profile. The cached value can become stale.

That one difference — mutability of the underlying data — is the source of all the complexity in production caching.

Read in the book →