Fix a function-cache key function, then make it durable

The starting point. A memoizing decorator keys its cache like this:

def make_key(args, kwargs):
    return hash((args, tuple(kwargs.items())))

and checks if cache.get(key): return cache[key]. Ask what "the same call" means, then list every way this key gets it wrong. Finding them all, with an example for each, is the first half of the round.

The bugs in that key, with a failing call for each. Take def f(a, b=2):

1. Positional versus keyword. f(1, 2) and f(1, b=2) and f(a=1, b=2) are the same call, but give three different keys.
2. Defaults. f(1) and f(1, 2) are the same call; the key does not apply defaults.
3. Keyword order. f(b=2, a=1) and f(a=1, b=2) produce different kwargs.items() tuples.
4. Unhashable arguments. f([1, 2]) raises TypeError: unhashable type: 'list'.
5. Values that compare equal across types. 1 == 1.0 == True and they hash the same, so f(1) and f(True) share an entry and return whichever was computed first. For a cache in front of a function that treats them differently, that is a wrong answer, not a miss.
6. hash() itself. It returns a 64-bit integer, so two different calls can collide and silently share a result. And string hashing is randomized per process (PYTHONHASHSEED), so the key is useless the moment the cache has to survive a restart.
7. The lookup, not the key: if cache.get(key) treats a cached 0, "", [] or None as a miss and recomputes forever.

The fix. Normalize the call with the function's own signature: inspect.signature(fn).bind(*args, **kwargs) maps every argument to its parameter name the way Python itself would, and apply_defaults() fills the rest. Then build the key from parameters in declaration order, with each value converted to a canonical, type-tagged form: lists, tuples, dicts (sorted by key), sets (sorted). Serialize that to JSON and take SHA-256. The result is the same for every spelling of the same call, different across types, collision-resistant, and identical in every process. Use a sentinel object for "missing" so falsy results are hits. Raise a clear error for argument types the cache cannot key (an open file, a lock) instead of guessing.

Making it durable. Entries must survive a restart and the process must recover correctly from a crash in the middle of a write.

• Format: an append-only log. Each record is length (4 bytes) | CRC32 (4 bytes) | payload, where the payload is the pickled (key, value).
• Write: append the record, flush, fsync (configurable: an fsync costs ~1–10 ms on SSDs, so batch it if writes are frequent and losing the last few entries is acceptable; it is a cache).
• Recovery: read records in order. A short header, a short payload or a CRC mismatch means a torn write at the end; truncate the file at the start of that record and stop. Everything before it is intact.
• Invalidation: a cached result is only valid for the code that produced it. Put the function's qualified name and a version string in every key, and bump the version when the function's behavior changes.

import functools
import hashlib
import inspect
import json
import os
import pickle
import struct
import zlib

_MISSING = object()
_HEADER = struct.Struct(">II")  # payload length, crc32


def _freeze(v):
    """A JSON-able, type-tagged canonical form; equal calls give equal forms."""
    if v is None or isinstance(v, bool):
        return [type(v).__name__, v]
    if isinstance(v, int):
        return ["int", v]
    if isinstance(v, float):
        return ["float", repr(v)]
    if isinstance(v, str):
        return ["str", v]
    if isinstance(v, bytes):
        return ["bytes", v.hex()]
    if isinstance(v, (list, tuple)):
        return [type(v).__name__, [_freeze(x) for x in v]]
    if isinstance(v, (set, frozenset)):
        return ["set", sorted((_freeze(x) for x in v), key=json.dumps)]
    if isinstance(v, dict):
        pairs = [[_freeze(k), _freeze(x)] for k, x in v.items()]
        return ["dict", sorted(pairs, key=lambda p: json.dumps(p[0]))]
    raise TypeError(f"cannot build a cache key from {type(v).__name__}")


def make_key(fn, args, kwargs, version="1", signature=None):
    sig = signature or inspect.signature(fn)
    bound = sig.bind(*args, **kwargs)
    bound.apply_defaults()
    parts = [[name, _freeze(bound.arguments[name])] for name in sig.parameters]
    payload = json.dumps([f"{fn.__module__}.{fn.__qualname__}", version, parts], separators=(",", ":"))
    return hashlib.sha256(payload.encode()).hexdigest()


class Cache:
    """In-memory dict, optionally backed by a crash-safe append-only log."""

    def __init__(self, path=None, fsync=True):
        self.data, self.path, self.fsync = {}, path, fsync
        if path:
            self._recover()

    def _recover(self):
        if not os.path.exists(self.path):
            return
        good = 0
        with open(self.path, "rb") as f:
            while True:
                header = f.read(_HEADER.size)
                if len(header) < _HEADER.size:
                    break
                length, crc = _HEADER.unpack(header)
                payload = f.read(length)
                if len(payload) < length or zlib.crc32(payload) != crc:
                    break  # torn or corrupt tail
                key, value = pickle.loads(payload)
                self.data[key] = value
                good = f.tell()
        if good != os.path.getsize(self.path):
            with open(self.path, "r+b") as f:
                f.truncate(good)

    def get(self, key):
        return self.data.get(key, _MISSING)

    def put(self, key, value):
        self.data[key] = value
        if self.path:
            payload = pickle.dumps((key, value), protocol=pickle.HIGHEST_PROTOCOL)
            with open(self.path, "ab") as f:
                f.write(_HEADER.pack(len(payload), zlib.crc32(payload)) + payload)
                f.flush()
                if self.fsync:
                    os.fsync(f.fileno())


def cached(cache=None, version="1"):
    def decorate(fn):
        store = cache if cache is not None else Cache()
        sig = inspect.signature(fn)

        @functools.wraps(fn)
        def wrapper(*args, **kwargs):
            key = make_key(fn, args, kwargs, version, sig)
            hit = store.get(key)
            if hit is not _MISSING:
                return hit
            value = fn(*args, **kwargs)  # exceptions propagate and are not cached
            store.put(key, value)
            return value

        wrapper.cache = store
        return wrapper
    return decorate

pickle.loads runs code from the file, so the cache file must be as trusted as the program itself; for values that are plain data, store JSON instead.

• Key: O(size of the arguments) to freeze and serialize, plus SHA-256 (~1 GB/s). For large arguments (a 100 MB array) keying costs real time; key such objects by an identity the caller provides (a content hash computed once, or a version id).
• Lookup: O(1) dict access after keying.
• Durable write: one append plus an fsync. Recovery: one sequential read of the log, O(file size).
• Space: the log grows with every entry; entries never change for a deterministic function, so it only needs compaction when old versions are retired (rewrite live entries to a new file, then rename it over the old one).

1. Concurrency. Two threads missing on the same key both compute. Keep a per-key lock or an in-flight future map so the second waits for the first (request coalescing). Across processes sharing one log file, append with O_APPEND (atomic for small writes on local filesystems) and take an advisory file lock for compaction.
2. Bounded size. Add LRU eviction in memory; on disk, compaction keeps only entries that are still in the in-memory index, or a TTL per entry.
3. Methods and closures. For a method, self is the first argument; decide whether the instance's identity or its state is part of the key (usually an explicit cache_key() method on the class). Closures capture variables the key does not see: either forbid caching them or include the captured values.
4. Large values. Store big results as separate files named by key (content-addressed), and keep only the key-to-file index in the log; this is how build systems and ML pipeline caches work.
5. Code changes without a version bump. Hashing the function's bytecode catches edits to that function but not to functions it calls; build systems solve this by tracking dependencies. A manual version is the honest, simple answer for an interview.

Mid-level (L4)

• Finds the positional versus keyword and defaults bugs and fixes them with inspect.signature(...).bind and apply_defaults.
• Handles keyword order and unhashable arguments.
• Persists the cache to disk in some form and reloads it.

Senior (L5)

• Finds the subtler bugs: falsy results treated as misses, 1 == True collisions, and why hash() cannot be a persistent key.
• Builds a canonical, type-tagged serialization with a cryptographic hash, and writes tests for each bug.
• Makes the disk format crash-safe (length plus checksum, truncation of a torn tail) and explains fsync costs.

Staff (L6+)

• Covers invalidation (versioning, code hashing and its limits), concurrency (coalescing, file locking) and bounded size.
• Notes the security risk of unpickling and when to use a data-only format.
• Relates the design to real systems (build caches, content-addressed stores) and their trade-offs.