Build a Durable Key-Value Cache

Durable Key-Value Cache

You are asked to design a simple in-memory key-value store that survives system crashes. The store should support put(key, value) and get(key) operations.

Because an in-memory map is lost when a process restarts, you must implement a Write-Ahead Log (WAL) on disk. Every put operation must be persisted to the log before the in-memory map is updated. When the system restarts, it must be able to reconstruct the map by replaying the log.

Requirements:

1. put(key: str, value: str): Persist the operation to a file and update the memory state.
2. get(key: str) -> str: Return the value for the key from memory.
3. recover(): On startup, scan the log file and rebuild the memory map.

Constraints:

• Assume key and value are strings.
• Use a file-based log (e.g., store.log).
• Implement a mechanism to detect and handle partial writes (e.g., a crash occurring in the middle of writing a log entry).

Example:

# Execution 1
cache = DurableCache("store.log")
cache.put("user_1", "alice")
cache.put("user_2", "bob")
# Process crashes

# Execution 2
cache = DurableCache("store.log")
print(cache.get("user_1")) # Output: "alice"

Considerations:

• How will you define the format of your log entries to ensure you can identify the start and end of a record?
• How do you verify the integrity of an entry (e.g., if the process crashed while writing)?
• What is the performance impact of writing to disk on every put?