Build a Thread-Safe Cache with One Lock per Key

Your web app caches expensive results, such as one rendered report per customer. On a miss, it computes the report and stores it. Two threads can both see the miss for one customer and both do the expensive work. The GIL does not stop that, because a thread can pause between the check and the store. On the free-threaded build from the previous article, the two threads can even run those steps at the same instant.

One lock around the whole cache fixes the race, but then every customer waits for the slowest report. A lock per key is better. Callers for the same key wait for the first one, and callers for different keys compute at the same time.

cache: MemoCache[str, str] = MemoCache()
cache.get_or_compute("alpha", lambda: "ALPHA")  # calls the lambda: 'ALPHA'
cache.get_or_compute("alpha", lambda: "other")  # cached: 'ALPHA'
cache.view                                      # mappingproxy({'alpha': 'ALPHA'})

Write the cache

Complete MemoCache[K, V]. Its method get_or_compute(key, compute: Callable[[], V]) -> V follows these rules:

1. For any one key, at most one callback runs at a time. Once a callback succeeds, store its value. Return it to every later caller for that key without calling their callbacks.
2. Never run a callback while you hold a lock that callers for other keys need. A shared bookkeeping lock that you hold only briefly is fine. Release it before you call compute or wait for a key's lock.
3. If a callback raises, the exception reaches that caller and the key stays uncached. Release the key's lock so another caller can try again. More than one callback can therefore run for one key in total, when some of them fail.
4. The cache stores any value, including None, False and 0. Test whether the key is in the dictionary, not whether the value is truthy.

If callers pass different callbacks for one key, the first to succeed decides the value. Add no eviction or expiry.

The view property returns a read-only Mapping[K, V] snapshot. Copy the dictionary while you hold the bookkeeping lock, and wrap the copy in types.MappingProxyType. A proxy over the live dictionary would show later inserts. The values are not copied, so a cached list is still the same list.

Keep each key's lock once you create it. Deleting it while a thread waits on it would give two threads different locks for one key. You can assume that keys hash consistently. Per-key locks cannot prevent a deadlock where a callback asks the cache for its own key, or for a key whose callback is waiting on it. You can assume no callback does that. Make the code pass mypy --strict.

Write the driver

solve(*, key, threads, distinct_keys, flaky_key) runs three checks, each on a new cache, and returns (hot_calls, hot_value, overlap_flag, flaky_calls, flaky_value).

• Same key. Start threads threads that each call get_or_compute for key. The callback counts its calls under a lock and returns key.upper(). Wait for every thread, and let unexpected exceptions propagate. Then call get_or_compute for key once more. With threads=0, that last call is the one that computes. hot_calls must be 1.
• Different keys. Make distinct_keys keys named k0, k1 and so on, and run one thread per key, all at once. Each callback waits on a threading.Barrier(distinct_keys) with a two-second timeout, then returns its key. If one lock covered every callback, they could never all reach the barrier. overlap_flag is True if every thread gets through and False if the barrier breaks. Let other exceptions propagate. With one key, the flag is True.
• Retry. For flaky_key, the callback raises RuntimeError on its first call and returns flaky_key.upper() on its second. Catch the first failure and call again. Then call a third time to check that the value stayed cached. flaky_calls must be 2.

Raise ValueError if threads is negative or distinct_keys is below 1. The tests start at most 64 threads in each check.