Practice/xAI/Durable KV Cache

Durable KV Cache

CodingMust

Problem Overview

Design and implement a durable key-value cache that persists data to storage, ensuring that cached data survives process restarts or crashes. Unlike a traditional in-memory cache that loses all data on failure, a durable cache can recover its state by loading data from persistent storage.

This pattern is commonly used in:

• Application state recovery after crashes
• Session caching with persistence guarantees
• Configuration caching with fallback storage
• Edge caching with local disk backup

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 `

Requirements

Your implementation should support:

• get(key): Retrieve the value associated with the key. Returns None if the key does not exist.
• put(key, value): Insert or update a key-value pair, ensuring durability.
• Automatically persist data to the file system
• Recover cached data from storage upon initialization
• Handle stale data appropriately

Clarification Questions to Ask

• Should the storage file format be human-readable (e.g., text) or binary?
• How should we handle concurrent access to the same storage file?
• What happens if the storage file is corrupted or malformed?
• Should put() block until data is persisted, or can it be asynchronous?
• Is there a maximum size limit for keys or values?
• Should we support TTL (time-to-live) for cached entries?

Part 1: Append-Only Log

Implement a DurableKVCache class that uses an append-only log strategy: every put() operation appends a new entry to a log file. On initialization, the cache replays the entire log to restore state.

Note on Terminology: This approach uses an append-only log (also called log-structured storage). Each write appends a record to the log, and the log itself is the persistent storage. This differs from write-through caching (which rewrites the entire file) and Write-Ahead Logging (WAL), which logs operations before applying them to a separate data store.

The key insight is that appending is fast (sequential I/O), but stale entries accumulate over time.

Example

` cache = DurableKVCache("cache.txt") cache.put("key1", "value1") cache.put("key1", "value2") # Update

Storage file now contains:

key1 value1

key1 value2

On recovery, the cache replays all entries and uses the last value

`

Requirements

• Parse the input file on initialization (one entry per line)
• Store entries in format: key\tvalue\n
• Store data in memory for fast get() operations
• Append each put() to the log file immediately
• Handle missing storage file gracefully (create new file)

Part 2: Handling Stale Data with Compaction

As the cache accumulates updates, the storage file grows with stale (outdated) entries. When a key is updated multiple times, all previous values remain in storage, wasting disk space and slowing down recovery time.

The Stale Data Problem

` cache = DurableKVCache("cache.txt") cache.put("counter", "1") # Storage: counter=1 cache.put("counter", "2") # Storage: counter=1, counter=2 cache.put("counter", "3") # Storage: counter=1, counter=2, counter=3

... 1000 more updates

Storage now contains 1003 entries, but only 1 is current!

`

Discussion Questions

What are the tradeoffs of the append-only log approach?

• Pros: Simple, reliable, every write is durable, sequential I/O is fast
• Cons: Storage grows unbounded, recovery time increases, wastes disk space

How would you handle stale data?

• Option A: Periodic compaction (rewrite file with only current values)
• Option B: Use a structured storage format (e.g., SQLite, LevelDB)
• Option C: Append-only log with periodic snapshots

When should compaction happen?

• After N writes
• When file size exceeds threshold
• On graceful shutdown
• Background thread

Example Compaction Strategy

Add a compaction_threshold parameter and trigger compaction after a certain number of writes:

` cache = DurableKVCache("cache.txt", compaction_threshold=100)

After 100 writes, automatically compact:

1. Write current state to temp file

2. Atomically replace old file

3. Reset write counter

`