Cache an Expensive Service Call, Test It, Then Make It Thread-Safe

A service your code depends on is very expensive to call. Make it cheap to use by putting a cache in front of it. Write the code, then write test cases for it, then write test cases that call it from multiple threads, and discuss whether your code still works when many threads use it at once and what you would change if it does not. The multithreading requirement is introduced only after the first version is written, so do not expect to be told about it up front. Assume an interface such as: ```python class ExpensiveService: def get(self, key: str) -> str: """Slow and costly to call.""" ``` ### Clarifying Questions - Does the value for a key ever change, and if so, how stale may a cached value be? - How many distinct keys are there, and how much memory may the cache use? Which entries should go when it is full? - Should errors from the service be cached, retried, or passed straight to the caller? - Will the cache be called from several threads at once? ### Part 1 — Cache the expensive call Implement a wrapper with the same interface that returns the same results as the service but calls it as rarely as possible. ```hint What is worth keeping Decide what bounds the cache's memory, and which entry should be given up first when that bound is reached. ``` #### What This Part Should Cover - Correct hit and miss handling, with one service call per miss - Bounded memory with a clear eviction policy, and constant-time operations - Expiry or invalidation if values can change, and the treatment of errors ### Part 2 — Test the cache Write test cases for the single-threaded cache. ```hint Replace the expensive part Tests should neither call the real service nor sleep. Think about what you would substitute so that you can count calls and control time. ``` #### What This Part Should Cover - A fake service that counts calls, and a controllable clock - Cases for hits, misses, eviction order, expiry and errors - Tests that are fast and deterministic ### Part 3 — Multiple threads Now many threads call the cache at the same time. Write test cases that run it from multiple threads, then discuss: does your code still work? If not, what fails, and how do you fix it? ```hint Two callers, one missing key Consider what happens between the moment a thread sees a miss and the moment it stores the value, both to the cache's internal structure and to the expensive service. ``` #### Clarifying Questions for this Part - Is it acceptable for two threads that miss on the same key at the same moment to both call the service? #### What This Part Should Cover - The races in the single-threaded version and what each one breaks - A fix with appropriate lock granularity that never holds a lock during the slow call - Deduplicating concurrent misses for the same key, including passing errors to waiting threads - Multithreaded tests that make the races reproducible ### What a Strong Answer Covers - Clarifies staleness, memory limits, error policy and concurrency before coding - A bounded cache with constant-time operations and a stated eviction policy - Tests driven by a fake service and a fake clock rather than real time - Recognizes both the data races and the duplicate concurrent misses, and fixes them without serializing every call behind one lock - Multithreaded tests that reliably expose races, and a discussion of alternatives such as striped locks ### Follow-up Questions - The service is now called from many hosts, each with its own cache. What goes wrong, and when would you move to a shared cache? - A popular key expires and hundreds of threads miss on it at once. What happens to the service, and how do you prevent it? - The value for a key can change in the service. How do you keep the cache from serving stale data for too long? - How would you measure whether the cache is actually making the service cheaper to use?