In-Memory Key-Value Store with Crash Recovery from a Log and Concurrent Access

Implement a key-value store that keeps its data in memory, can rebuild that data from a log file after the process goes down unexpectedly, and is safe to use from many threads at once. Candidates report that writing the core quickly matters, because the recovery and concurrency follow-ups take most of the time. ### Clarifying Questions - Which operations are required: `get`, `set` and `delete` only, or also operations such as increment or compare-and-set? - Are keys and values strings, or arbitrary bytes? How large can they be? - What durability guarantee is expected: must a write that has returned survive a process crash, a machine power loss, or neither? - Is the workload read-heavy or write-heavy, and how many threads access the store concurrently? - Can the log grow without bound, or must it be compacted? ### Part 1 — In-memory store Implement `get(key)`, `set(key, value)` and `delete(key)` backed by an in-memory structure. ```hint Keep the core tiny The first part should take minutes; decide now what a missing key returns and what deleting a missing key does, so later parts do not have to change the interface. ``` #### What This Part Should Cover - Correct operations and clearly defined behavior for missing keys - Constant-time operations on average ### Part 2 — Recovery from a log file Make the store durable: every change is appended to a log file, and when the store starts it rebuilds its state from that file. The process can die at any moment, including in the middle of writing a log record. ```hint Assume the worst possible crash moment Imagine the process dying halfway through writing a record, then ask what the next startup reads and how it can tell a complete record from a partial one. ``` #### What This Part Should Cover - The order of writing the log and updating memory, and what an acknowledged write guarantees - A record format that lets recovery detect a partially written or corrupted final record - Replay on startup, and truncation of the damaged tail - Keeping the log from growing forever through snapshots and compaction ### Part 3 — Concurrency Many threads now call the store at the same time. Make it correct, then make it fast. ```hint Two orders must agree With concurrent writers, the order of records in the log and the order in which changes hit memory must be the same; consider what breaks if they differ, and what that implies about locking. ``` #### What This Part Should Cover - Correctness: log order matching the order changes are applied, and no lost updates - A locking strategy and its effect on throughput, such as a single lock, reader-writer locks or striping - Batching log writes from many threads into one sync (group commit) - Recovery still correct under concurrent writers ### What a Strong Answer Covers - A working core delivered quickly, with a clean path to the follow-ups - A precisely stated durability guarantee, and a design that provably meets it - Crash-safety details: flushing versus syncing, torn records and atomic snapshot replacement - A concurrency design whose correctness argument is explicit, not just "add a lock" ### Follow-up Questions - How would you add a time-to-live to keys, and how does expiry interact with recovery? - How would you replicate the store to a second machine so it survives machine loss? - How would you support a range scan over keys in sorted order? - The data no longer fits in memory. What changes?