Fix a Buggy LRU Cache, Then Make It Durable with a Write-Ahead Log

You are handed an existing in-memory cache implementation that is misbehaving in production. First find and fix its bugs. Then extend it so that its contents survive a process crash and restart. The original code was not reported, so the class below is an illustrative stand-in with the same shape: a least-recently-used (LRU) cache with a fixed capacity. ```python class LRUCache: """Holds at most `capacity` keys; when full, evicts the least recently used key.""" def __init__(self, capacity): self.capacity = capacity self.data = {} # key -> value self.order = [] # keys, from least recently used (front) to most recently used (back) def get(self, key): if key in self.data: return self.data[key] return None def put(self, key, value): if len(self.data) > self.capacity: oldest = self.order.pop() del self.data[oldest] self.data[key] = value self.order.append(key) ``` ### Clarifying Questions - Does reading a key with `get` count as "using" it for eviction purposes? - What should happen when `put` is called on a key that is already present? - Is a capacity of zero allowed? - For durability: must the cache survive only a process crash, or also a machine power loss? - Must the recency order also survive a restart, or only the keys and values? - What extra latency per write is acceptable in exchange for durability? ### Part 1 — Find and fix the bugs Read the code and list every bug, showing for each one a short sequence of calls that exposes it. Then write a corrected implementation, state its time complexity per operation, and write the tests that would have caught these bugs. ```hint Replay small scenarios Run a capacity-2 cache by hand through a handful of sequences: fill it, overfill it, read an old key, then overfill again, and update an existing key. Compare what the code does with what an LRU cache must do at every step. ``` #### What This Part Should Cover - Each bug identified with a concrete reproducing sequence of calls - A corrected implementation with constant-time operations - Correct behavior for updates of existing keys and for small capacities - Targeted tests, one per bug ### Part 2 — Add durability Extend the fixed cache so that after a crash and restart it comes back with the same keys and values it had acknowledged before the crash. Describe what is written to disk and when, how recovery works, and how you keep the on-disk data from growing without bound. ```hint What must reach the disk before you answer Decide at what point a `put` may return to its caller, and what the disk must already contain at that point for recovery to reproduce the change. ``` #### What This Part Should Cover - An on-disk format and the ordering between writing it and updating memory - Recovery, including a partially written record at the end of the file - Keeping recovery consistent with eviction, even though reads are not persisted - Compaction or snapshots, and making the snapshot switch atomic ### What a Strong Answer Covers - Systematic debugging from specification to failing case to fix, rather than rewriting blindly - A precise durability guarantee stated up front, and a design that meets exactly that guarantee - Crash-consistency details: flushing versus syncing to disk, torn writes, and atomic file replacement - Honest discussion of the latency and throughput cost of durability ### Follow-up Questions - Syncing to disk on every `put` is too slow. How would you batch syncs, and what exactly would a crash lose? - How would you make this cache safe for concurrent use by many threads? - Values carry a time-to-live. How does expiry interact with the log and with recovery? - The cache must now survive the loss of the whole machine. What changes?