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.

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.

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.

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