Hand-Write a Bounded Cache for a Database-Backed Backend Service

In a one-hour hands-on coding round, you work in a remote development environment (an editor connected over SSH) that already contains a small backend project skeleton. The scope announced in advance was backend and database work, and the core of the round was writing a cache by hand. The exact skeleton was not recorded. Assume it has a service layer whose reads and writes go straight to a database through a repository object, and that database reads are slow enough that repeated reads of the same record are worth avoiding. Adapt the names to whatever the skeleton actually provides: ```python class Repository: def get(self, key: str) -> dict | None: ... # reads one record from the database, None if absent def put(self, key: str, record: dict) -> None: ... # inserts or updates one record def delete(self, key: str) -> None: ... # removes one record ``` Implement a cache in front of this repository and wire it into the service, so that repeated reads of a key are served without going to the database and the cache still behaves correctly when records are written or deleted. Explain each policy you choose, and show how you would test the result. ```hint Decide what a write does first Before writing the cache class, decide what `put` and `delete` must do to the cached copy of that key, and in which order relative to the database write. Then picture a read that runs at the same moment as that write. ``` ```hint Bound the memory Ask what stops the cache from growing without limit, which entry should leave first when it is full, and which data structure makes both the lookup and that removal cheap. ``` ### Constraints and Clarifications - Writing the cache by hand means no third-party caching library. Standard-library data structures are fine. - The database remains the source of truth: the cache may be emptied at any moment without losing data. - Assume a single service process for the core task. Several instances are a follow-up. ### Clarifying Questions - How large is the key space compared with the memory available, and should capacity be counted in entries or in bytes? - What does the access pattern look like, and which eviction policy suits it: least recently used, least frequently used, or something else? - Should entries also expire after a time-to-live, and how stale may a read be allowed to be? - Can anything other than this service write to the database? If so, how would the cache learn about those writes? - Does the service handle requests on several threads at once, so the cache must be safe for concurrent access? - Should a lookup for a key that does not exist in the database also be cached? ### What a Strong Answer Covers - A named caching pattern: where reads fill the cache, and how writes and deletes update or invalidate it, with the ordering against the database write justified - Bounded memory with an eviction policy, the data structure behind it, and the cost of each operation - Expiry and staleness handling that matches the freshness requirement agreed in the clarifying questions - Behavior under concurrent requests, including many requests that miss on the same key at the same time - Tests for hits, misses, eviction order, invalidation after writes and expiry that run deterministically, without sleeping - How to judge the cache in operation, such as hit rate and database load, and how that feeds back into sizing ### Follow-up Questions - The service now runs as several instances behind a load balancer, each with its own in-process cache. How do you stop one instance from serving stale data after another instance writes? - One key is extremely hot and its entry expires. What happens to the database at that moment, and how do you prevent it? - A nightly batch job reads every key once. What does that do to a least-recently-used cache, and how would you change the policy? - When would you move the cache out of the process into a shared cache service, and what new failure modes would that introduce?