Katkat
Back

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

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement an in-memory key-value store, make it recover from a log file after a crash, including a half-written final record, and make it correct and fast under many concurrent threads. It tests write-ahead logging, crash consistency, compaction, and lock design with group commit.

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.

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.

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.

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

Hints

Hint 1

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.

Hint 2

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.

Hint 3

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.

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?