When you first decide to build a key-value store, your brain immediately goes to the HashMap. It's the obvious choice. You wrap it in an Arc<Mutex<...>> so multiple threads can access it, and suddenly you have a working "database" in about ten lines of code. I've seen plenty of junior devs ship this in early prototypes, and for a few minutes, it feels like a win. It's incredibly fast, and the API is simple.

// The "naive" way
struct SimpleStore {
    data: Arc<Mutex<HashMap<String, String>>>,
}

impl SimpleStore {
    fn set(&self, key: String, value: String) {
        let mut map = self.data.lock().unwrap();
        map.insert(key, value);
    }
}


The Wall of Volatility and Contention
Here is where the naive approach breaks. First, the most glaring issue: your data lives exclusively in RAM. The second you restart your server or the process crashes, every single piece of data is gone. In a real production environment, that's an outage. You might think, "I'll just serialize the whole map to a JSON file every time I update a key," but try doing that with 100,000 keys. Your write latency will spike from nanoseconds to milliseconds as you rewrite the entire dataset to disk for a single change.

Then there's the locking problem. By wrapping the entire HashMap in a single Mutex, you've created a massive bottleneck. Even if two threads are updating completely different keys, they have to wait in line for that one lock. You've essentially turned your multi-threaded Rust application into a single-threaded one whenever it touches the store.

Moving to a Write-Ahead Log (WAL)
To fix this, we need to change how we think about "writing." Instead of trying to keep a perfect image of the data on disk, we use a Write-Ahead Log. In this model, every set operation is simply appended to the end of a file. Appending to a file is an O(1) operation and is incredibly efficient because the disk head doesn't have to jump around.

The HashMap stays in memory, but now it serves as an index rather than the primary source of truth. When the store starts up, it reads the log from beginning to end, replaying every operation to rebuild the map. This gives us durability without sacrificing the speed of the HashMap for reads.

use std::fs::{File, OpenOptions};
use std::io::{Write, BufReader, BufRead};

struct PersistentStore {
    index: Arc<Mutex<HashMap<String, u64>>>, // Maps key to byte offset in file
    writer: Arc<Mutex<File>>,
}

impl PersistentStore {
    fn set(&self, key: String, value: String) {
        let mut writer = self.writer.lock().unwrap();
        let mut index = self.index.lock().unwrap();
        
        // 1. Format the entry: "key:value\n"
        let entry = format!("{}:{}\n", key, value);
        
        // 2. Record the offset where this value starts
        let offset = writer.metadata().unwrap().len();
        
        // 3. Append to disk
        writer.write_all(entry.as_bytes()).unwrap();
        
        // 4. Update index
        index.insert(key, offset);
    }
}


The Trade-off: Read Speed vs. Disk Bloat
I'll be honest with you: this approach introduces a new problem. If you update the key "user_1" a thousand times, your log file now contains a thousand entries for "user_1", even though only the last one matters. Your disk usage will grow linearly regardless of whether you're adding new keys or updating old ones.

This is the classic trade-off in database engineering. We traded "slow writes" (rewriting the whole file) for "fast writes and bloated storage." To solve the bloat, you'd eventually implement compaction—a background process that reads the log and throws away the old versions of keys. But for a basic key-value store, the WAL pattern is the professional leap. You move from a toy that lives in RAM to a system that survives a power outage.

📋 Practical Task

Implement a Log-Based Recovery System

You have been provided with a PersistentStore that can write keys and values to a file, but it currently loses its index every time the program restarts. Your task is to implement the recover() method.

Requirements:

• Create a function recover(log_file: &File) -> HashMap<String, u64>.
• The function must read the log file line by line.
• For each line, it should split the string at the first colon (:) to separate the key from the value.
• It must track the byte offset of the start of each line.
• The final HashMap should contain the last known offset for every key found in the file.

Goal: Ensure that when the store boots up, it can rebuild its in-memory index from the disk log without loading the actual values into RAM—only the offsets.