0

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

by Frontier Interview· about 4 hours ago· ⑂ 0 remixes

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

Companies: Anthropic

Difficulty: Medium

Problem statement

A small memoizing cache for arbitrary callables has a broken key function that mishandles positional versus keyword arguments and defaults. Fix the keying first, then extend the cache so entries survive a process restart and recover correctly.

  • Level 1: fix the keying so every spelling of the same call shares one entry, different calls never do, and falsy results are cache hits.
  • Level 2: make the cache survive a restart, and recover cleanly if the process died in the middle of a write.
import functools


def make_key(fn, args, kwargs, version="1", signature=None):
    # Buggy: find every way this gets "the same call" wrong.
    return hash((args, tuple(kwargs.items())))


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

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

    def put(self, key, value):
        self.data[key] = value


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

        @functools.wraps(fn)
        def wrapper(*args, **kwargs):
            key = make_key(fn, args, kwargs, version)
            if store.get(key):
                return store.get(key)
            value = fn(*args, **kwargs)
            store.put(key, value)
            return value

        wrapper.cache = store
        return wrapper
    return decorate

Approach

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.

Code

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.

Complexity

  • 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).

Test cases

from solution import Cache, cached, make_key


def counting(**opts):
    calls = []

    @cached(Cache(), **opts)
    def f(a, b=2, *rest, **kw):
        calls.append((a, b, rest, kw))
        return 0 if a == 0 else (a, b, rest, kw)

    return f, calls


def test_every_spelling_of_one_call_shares_an_entry():
    f, calls = counting()
    f(1)
    f(1, 2)
    f(1, b=2)
    f(a=1)
    f(b=2, a=1)
    assert len(calls) == 1
    f(1, 3)
    assert len(calls) == 2


def test_keyword_order_and_extra_kwargs():
    f, calls = counting()
    f(1, x=1, y=2)
    f(1, y=2, x=1)
    assert len(calls) == 1


def test_unhashable_arguments_and_types_are_kept_apart():
    f, calls = counting()
    f([1, 2])
    f([1, 2])
    f((1, 2))
    assert len(calls) == 2
    f({"k": [1]})
    f({"k": [1]})
    assert len(calls) == 3
    f(1)
    f(True)
    f(1.0)
    assert len(calls) == 6


def test_falsy_results_are_hits_and_errors_are_not_cached():
    f, calls = counting()
    assert f(0) == 0 and f(0) == 0
    assert len(calls) == 1

    attempts = []

    @cached(Cache())
    def flaky(x):
        attempts.append(x)
        if len(attempts) == 1:
            raise ValueError("first call fails")
        return x

    try:
        flaky(5)
    except ValueError:
        pass
    assert flaky(5) == 5 and len(attempts) == 2


def test_unsupported_argument_types_fail_loudly():
    f, _ = counting()
    try:
        f(object())
    except TypeError as e:
        assert "cannot build a cache key" in str(e)
    else:
        assert False


def test_key_ignores_spelling():
    def g(a, b=2):
        return a

    assert make_key(g, (1,), {}) == make_key(g, (), {"b": 2, "a": 1})

import os
import tempfile

from solution import Cache, cached, make_key


def test_entries_survive_a_restart():
    path = os.path.join(tempfile.mkdtemp(), "cache.log")
    calls = []

    def build():
        @cached(Cache(path))
        def square(x):
            calls.append(x)
            return x * x
        return square

    assert build()(4) == 16
    assert build()(4) == 16  # a new Cache reads the log
    assert calls == [4]


def test_torn_tail_is_truncated_and_writes_continue():
    path = os.path.join(tempfile.mkdtemp(), "cache.log")
    c = Cache(path)
    c.put("a", 1)
    c.put("b", 2)
    good_size = os.path.getsize(path)
    with open(path, "ab") as f:
        f.write(b"\x00\x00\x00\x40garbage")  # header claims 64 bytes; only 7 follow
    c2 = Cache(path)
    assert c2.data == {"a": 1, "b": 2}
    assert os.path.getsize(path) == good_size
    c2.put("c", 3)
    assert Cache(path).data == {"a": 1, "b": 2, "c": 3}


def test_corrupt_record_stops_recovery_there():
    path = os.path.join(tempfile.mkdtemp(), "cache.log")
    c = Cache(path)
    c.put("a", 1)
    first = os.path.getsize(path)
    c.put("b", 2)
    with open(path, "r+b") as f:
        f.seek(first + 10)
        f.write(b"X")  # flip a byte inside the second payload
    assert Cache(path).data == {"a": 1}


def test_keys_are_stable_across_processes_and_versions():
    def g(a, b="x"):
        return a

    g.__module__, g.__qualname__ = "demo", "g"
    # A fixed digest: the same in every process, whatever PYTHONHASHSEED is.
    expected = "332d9a5a259c9a06368136095bb31748ce058af568f7d0ef5392d7c9744ba504"
    assert make_key(g, ("hello",), {}) == expected
    assert make_key(g, (), {"a": "hello", "b": "x"}) == expected
    assert make_key(g, ("hello",), {}, version="2") != expected

Follow-ups

  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.

Interviewer expectations

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.

Sign in to comment, vote or remix.