Durable KV Cache

Build a key-value cache that survives process restarts by persisting writes to disk, then discuss stale log cleanup, compaction, and large-file storage tradeoffs. Durable Key-Value Cache Problem Requirements The goal is to build a durable key-value cache. This means the cache must save its data to a storage drive (like a hard disk). If the program crashes or restarts, the data should not be lost. This is different from a normal cache. Normal caches live only in memory (RAM) and lose everything if the computer turns off or the program stops. Where is this used? Recovering an app after a crash. Saving user login sessions. Saving settings that must not disappear. Core Features You need to build a class with two main functions: get(key): Find and return the value for a key. If the key is missing, return None. put(key, value): Save a key and value. This must be saved to the disk so it is safe. Other Rules: The code must save data to a file automatically. When the code starts, it must look at the file to load old data. It must handle old, useless data (stale data) correctly. Usage Example # Create a durable cache backed by a file cache = DurableKVCache(storage_path="cache_data.txt") cache.put("user:123", '{"name": "Alice", "role": "admin"}') cache.put("config:theme", "dark") print(cache.get("user:123")) # {"name": "Alice", "role": "admin"} # After process restart... cache2 = DurableKVCache(storage_path="cache_data.txt") print(cache2.get("user:123")) # {"name": "Alice", "role": "admin"} (recovered!) print(cache2.get("config:theme")) # dark Part 1: The Append-Only Log The Task Build a DurableKVCache class. Use a strategy called an append-only log. This means every time you call put(), you add a new line to the end of a file. When the class starts, it reads the whole file to remember what is stored. What is an Append-Only Log? You simply "append" (add to the end) of the file. You never delete or change old lines. Write-through caching: Usually rewrites the whole file every time data changes. This is slow. Our approach: We just add one line. This is very fast. However, the file gets bigger and bigger over time. class DurableKVCache: def __init__(self, storage_path: str): """ Start the cache. If a file exists, load data from it. """ pass def get(self, key: str) -> str | None: """ Find the value for a key. Return None if not found. """ pass def put(self, key: str, value: str) -> None: """ Save the key and value to memory and the file. """ pass How to Test It import os # Test 1: Basic put and get cache = DurableKVCache("test_cache.txt") cache.put("key1", "value1") assert cache.get("key1") == "value1" assert cache.get("nonexistent") is None # Test 2: Persistence across restarts cache = DurableKVCache("test_cache.txt") cache.put("persistent_key", "persistent_value") del cache # Simulate program closing cache2 = DurableKVCache("test_cache.txt") assert cache2.get("persistent_key") == "persistent_value" # Test 3: Update existing key cache = DurableKVCache("test_cache.txt") cache.put("key", "old_value") cache.put("key", "new_value") assert cache.get("key") == "new_value" # Cleanup os.remove("test_cache.txt") Part 2: Cleaning Up Old Data The Challenge If you update the same key many times, the file gets full of old data. This is called "stale data." It wastes space on the hard drive and makes the cache slow to start up. The Stale Data Problem # Scenario: Updating the same key many times cache = DurableKVCache("cache.txt") cache.put("counter", "1") # File has: counter=1 cache.put("counter", "2") # File has: counter=1, counter=2 cache.put("counter", "3") # File has: counter=1, counter=2, counter=3 # ... 1000 more updates # The file has 1003 lines, but we only need the last one! Questions to Think About What are the Good and Bad parts of appending? Good: It is simple and fast. Data is safe immediately. Bad: The file grows forever. Restarting takes longer because you have to read junk data. How do we fix the file size? Option A: Compaction (Rewrite the file with only the newest data). Option B: Use a database like SQLite. When should we clean the file? After N number of writes. When the file gets too big (e.g., 10MB). When the program closes. Example Solution for Cleanup class DurableKVCache: def __init__(self, storage_path: str, compaction_threshold: int = 1000): self.storage_path = storage_path self.compaction_threshold = compaction_threshold self.write_count = 0 self.cache = {} self._load_from_storage() def put(self, key: str, value: str) -> None: self.cache[key] = value self._append_to_storage(key, value) self.write_count += 1 # Check if we have written too many times if self.write_count >= self.compaction_threshold: self._compact() def _compact(self) -> None: """Rewrite the file to keep only the newest values.""" # 1. Write current cache map to a temp file # 2. Swap the old file with the new temp file # 3. Reset the counter pass Part 3: Handling Large Files The Challenge What if the values are very large (like big text files or ML models)? Loading the whole file into memory is slow. Rewriting the whole file to clean it up is very slow. Optimization: One File Per Key Instead of one big file, use one file for each key. Inside that file, we still append new data. cache_storage/ ├── user_123.log # History for "user:123" ├── user_456.log # History for "user:456" └── config_theme.log # History for "config:theme" Each line in the file has a timestamp and a value: 1703520000.123456 {"name": "Alice", "role": "user"} 1703520100.789012 {"name": "Alice", "role": "admin"} <- This is the latest one Why do this? To get the data, we only read the last line of the file. We don't need to rewrite huge files every time. We can load data "lazily" (only read the file when someone asks for that key). Questions to Think About How do you read only the last line efficiently? When should you clean up these individual files? What if a file for one key gets huge? Comparison Table Feature Single File File-Per-Key Startup Speed Slow (reads everything) Fast (reads nothing at start) Writing Speed Fast (append) Fast (append) Reading Speed Fast (from RAM) Fast (reads last line) Space Usage Grows fast Grows slower per key Safety Good Good Solution Details Questions to Ask the Interviewer Should the file be readable text (JSON) or binary? Will multiple people/processes use this cache at the same time? What if the file gets corrupted (broken)? Should put() wait for the disk save to finish? Step 1: Basic Log Implementation Plan: Use a Python Dictionary (HashMap) for memory. Append every put() to a text file. Read the text file line-by-line when starting. import os class DurableKVCache: def __init__(self, storage_path: str): self.storage_path = storage_path self.cache = {} self._load_from_storage() def get(self, key: str) -> str | None: return self.cache.get(key) def put(self, key: str, value: str) -> None: self.cache[key] = value self._append_to_storage(key, value) def _load_from_storage(self) -> None: """Read all lines from the file into memory.""" if not os.path.exists(self.storage_path): return with open(self.storage_path, 'r') as f: for line in f: line = line.strip() if not line: continue # Split line by tab: key [TAB] value parts = line.split('\t', 1) if len(parts) == 2: key, value = parts self.cache[key] = value def _append_to_storage(self, key: str, value: str) -> None: """Add a new line to the end of the file.""" with open(self.storage_path, 'a') as f: # We use a tab to separate key and value f.write(f"{key}\t{value}\n") Complexity: get(): O(1) - Very fast. put(): O(1) - Very fast (adding to end of file). Step 2: Adding Cleanup (Compaction) Plan: Count how many times we write. If we write too many times (e.g., 100 times), rewrite the file so it only contains the current data. import os import tempfile import shutil class DurableKVCache: def __init__(self, storage_path: str, compaction_threshold: int = 100): self.storage_path = storage_path self.compaction_threshold = compaction_threshold self.write_count = 0 self.cache = {} self._load_from_storage() def get(self, key: str) -> str | None: return self.cache.get(key) def put(self, key: str, value: str) -> None: self.cache[key] = value self._append_to_storage(key, value) self.write_count += 1 # Check if we need to clean up if self.write_count >= self.compaction_threshold: self._compact() def delete(self, key: str) -> None: """Remove a key.""" if key in self.cache: del self.cache[key] # Write a special marker to say this is deleted self._append_to_storage(key, "__DELETED__") self.write_count += 1 if self.write_count >= self.compaction_threshold: self._compact() def _load_from_storage(self) -> None: """Load data, handling deletions.""" if not os.path.exists(self.storage_path): return with open(self.storage_path, 'r') as f: for line in f: line = line.strip() if not line: continue parts = line.split('\t', 1) if len(parts) == 2: key, value = parts if value == "__DELETED__": self.cache.pop(key, None) else: self.cache[key] = value def _append_to_storage(self, key: str, value: str) -> None: with open(self.storage_path, 'a') as f: f.write(f"{key}\t{value}\n") def _compact(self) -> None: """Save only the fresh data to a new file.""" # Create a temp file first temp_fd, temp_path = tempfile.mkstemp() try: with os.fdopen(temp_fd, 'w') as f: for key, value in self.cache.items(): f.write(f"{key}\t{value}\n") # Swap the temp file with the real file shutil.move(temp_path, self.storage_path) self.write_count = 0 except Exception: os.unlink(temp_path) raise Step 3: One File Per Key Plan: Make a folder for storage. Each key gets a file (e.g., keyname.log). Append updates with a timestamp. To read, jump to the end of the file and read backwards. import os import time class DurableKVCache: def __init__(self, storage_dir: str): self.storage_dir = storage_dir self.cache = {} # key -> (timestamp, value) os.makedirs(storage_dir, exist_ok=True) def get(self, key: str) -> str | None: # Check memory first if key in self.cache: return self.cache[key][1] # If not in memory, try to load from disk (Lazy Load) filepath = self._key_to_filepath(key) if os.path.exists(filepath): timestamp, value = self._read_latest_entry(filepath) self.cache[key] = (timestamp, value) return value return None def put(self, key: str, value: str) -> None: timestamp = time.time() self.cache[key] = (timestamp, value) # Add line to the specific file for this key filepath = self._key_to_filepath(key) with open(filepath, 'a') as f: f.write(f"{timestamp}\t{value}\n") def _key_to_filepath(self, key: str) -> str: """Create a safe filename from the key.""" safe_key = key.replace(":", "_").replace("/", "_") return os.path.join(self.storage_dir, f"{safe_key}.log") def _read_latest_entry(self, filepath: str) -> tuple[float, str]: """ Read only the last line of the file. This is much faster than reading the whole file. """ with open(filepath, 'rb') as f: # Go to the very end of the file f.seek(0, 2) file_size = f.tell() if file_size == 0: return (0.0, '') # Read backwards character by character to find the newline pos = file_size - 1 while pos > 0: f.seek(pos) if f.read(1) == b'\n' and pos < file_size - 1: break pos -= 1 # Read from the start of the last line to the end f.seek(pos + 1 if pos > 0 else 0) last_line = f.read().decode().strip() if not last_line: return (0.0, '') parts = last_line.split('\t', 1) if len(parts) == 2: return (float(parts[0]), parts[1]) return (0.0, '') def compact_key(self, key: str) -> None: """ Clean up just ONE key's file. Only keeps the newest value. """ if key not in self.cache: filepath = self._key_to_filepath(key) if os.path.exists(filepath): timestamp, value = self._read_latest_entry(filepath) self.cache[key] = (timestamp, value) if key in self.cache: timestamp, value = self.cache[key] filepath = self._key_to_filepath(key) # Rewrite the file with only the latest line temp_path = filepath + ".tmp" with open(temp_path, 'w') as f: f.write(f"{timestamp}\t{value}\n") os.rename(temp_path, filepath) Extra Topics for Interview Pros and Cons of Append-Only Log Pros: Simple: Easy to code and understand. Safe: Data is saved immediately. Fast Writes: Hard drives are faster at adding data to the end than jumping around. Cons: Slower than pure RAM: Writing to disk is always slower than writing to memory. Wasted Space: The file keeps growing if you don't clean it. Slow Recovery: If the file is huge, reading it at startup takes time. Real World Problems Crash Recovery: What if the power fails while writing? Solution: Write to a temp file first, then rename it. This is "atomic". Concurrency (Multi-User): What if two programs try to write at the same time? Solution: Use file locks. Memory Limits: What if you have too much data for RAM? Solution: Use an LRU (Least Recently Used) policy to remove old items from memory, but keep them on disk. Comparison Summary Method Safety Speed Complexity In-Memory Only None (Data lost on crash) Fastest Simplest Rewrite File Every Time Good Slow Simple Append-Only Log Good Fast Writes Simple Append + Cleanup Good Balanced Medium Using a Database (SQLite) Good Balanced Low (if allowed)