Make a Dict-Based Memoization Cache Safe for Concurrent Threads

A slow, expensive function is wrapped in a module-level dictionary that memoizes its results: ```python cache = {} def compute(x): if x in cache: return cache[x] result = expensive(x) cache[x] = result return result ``` `compute` is now called from many threads at the same time. What problems does that cause, and how would you change the code? ### Clarifying Questions - Is `expensive(x)` deterministic and free of side effects, or is running it twice for the same `x` harmful (for example, it calls a paid external service or writes data)? - Can `expensive(x)` raise, and should a failure be remembered or retried on the next call? - Is the set of distinct inputs bounded, or can the cache grow without limit? - Which runtime is this: CPython with its global interpreter lock, a free-threaded build, or a language whose plain hash map is not safe for concurrent writers? - Is `expensive` mostly waiting on I/O, or mostly using the CPU? ### Part 1 — What goes wrong Explain what can happen when several threads call `compute` concurrently, using concrete interleavings. ```hint Interleave two threads Step two threads through `compute` with the same new key, one line at a time, and look for the window between the check and the write. Then repeat with two different keys. ``` #### What This Part Should Cover - The check-then-act window, and what happens when several callers miss the same key together - Which guarantees the runtime's dictionary does and does not give under concurrent access - The consequences when `expensive` is slow, non-deterministic, or has side effects ### Part 2 — Fix it and choose the lock scope Make `compute` safe for concurrent callers. Compare at least two places to put the lock, and say what each one costs when many threads ask for different keys versus the same key. ```hint Two jobs for one lock A lock here could do two separate jobs: protect the dictionary, and stop the same key from being computed twice. Ask whether one lock has to do both, and what it blocks while `expensive` runs. ``` #### What This Part Should Cover - Whether each candidate prevents duplicate computation, and whether it keeps the dictionary consistent - What each lock scope serializes, and the effect on throughput - What happens to waiting callers when the computation raises, so that a failure neither poisons the cache nor leaves threads blocked ### What a Strong Answer Covers - A concrete interleaving that demonstrates the race, rather than a general claim that the code "is not thread-safe" - The difference between the dictionary's own safety and the logical race on a key - A fix that computes each key once without holding a global lock while `expensive` runs - Exception handling, memory growth and deadlock risks of the chosen design - Working code, with a clear statement of what it does and does not guarantee ### Follow-up Questions - How would you add a size limit or expiry without evicting an entry that other threads are waiting on? - If `expensive(x)` itself calls `compute` for other keys, can your design deadlock? - How would the design change if the callers were separate processes, or separate machines sharing one cache?