Versioned Key-Value Store with Out-of-Order Writes, Snapshots and Read Freezing

You are building an in-memory key-value store that a distributed training job uses to checkpoint model metadata. Every key keeps a history of values, each written at a timestamp, so a reader can ask what a key held as of a given time. Each part below adds one requirement, under a set of global constraints. As reported, several of those requirements pull against each other, so agree with the interviewer on how to read them before you write code. ### Constraints and Clarifications - All operations should be O(1). - Memory usage should not grow with the number of versions. - The store must be thread-safe, although you may assume single-threaded access. - If a key does not exist, return `None` or raise an error, whichever is consistent with Part 4. - Not specified: the types of keys, values and timestamps, and who assigns the timestamps. State your assumptions. ### Clarifying Questions - Are timestamps integers such as training steps, or wall-clock times, and does the writer or the store assign them? - Can a key receive two writes with the same timestamp, for example a retried write, or a job that resumed from an earlier checkpoint and writes those steps again? If the values differ, which write wins? - `get` must find the newest version at or before an arbitrary timestamp, yet every operation should be O(1) and memory should not grow with versions. Which old versions must stay queryable, and is a bounded retention window acceptable? - What types are the values, and must a serialized store be readable by another process or by a newer version of the code? ### Part 1 — Versioned set and get Implement `set(key, value, timestamp)` and `get(key, timestamp)`. `get` returns the value that was set at the closest timestamp at or before the given timestamp. Timestamps are strictly increasing per key, but writes may reach the store out of order because of network delay, and the store should handle that gracefully. ```hint Arrival order is not timestamp order A delayed write can land between two versions that are already stored. Pick a per-key structure that stays ordered by timestamp under such inserts, and decide what `get` returns between two versions and before the first one. ``` #### What This Part Should Cover - A per-key structure ordered by timestamp that accepts late writes, and the at-or-before lookup - Behavior for a missing key, a timestamp before the first version, and a repeated timestamp - The actual cost of `set` and `get` compared with the O(1) target, and what would make O(1) possible ### Part 2 — Latest value Add `get_latest(key)`, which returns the most recent value. "Most recent" means the value with the highest timestamp, unless a newer write has been received, in which case it should reflect what the client most recently intended. ```hint Two meanings of newest The highest timestamp and the latest arrival differ exactly when a delayed write lands. Decide which of the two expresses the client's intent, given the per-key timestamp guarantee from Part 1. ``` #### Clarifying Questions for this Part - If a write with a lower timestamp arrives after one with a higher timestamp, is it a delayed older write or a correction that should become the latest value? - Does a call to `get_latest` count as a read for the rule in Part 4? #### What This Part Should Cover - A precise definition of "most recent" and how it follows from the timestamp guarantee - A constant-time `get_latest` that stays correct when late writes arrive - What changes if the client cannot keep timestamps increasing, for example after a resume ### Part 3 — Serialize and resume The store must be serializable so that a crashed job can resume. Implement `serialize()` and `deserialize()`. A deserialized store must behave identically to the original, including for any writes that were in flight at serialization time. ```hint Identical means every future answer List every piece of state that can change the result of a future `set` or `get`, not just the stored values, and decide what "in flight" can mean for a store that applies each write as one step. ``` #### What This Part Should Cover - A snapshot that captures all state affecting future behavior, taken as a consistent cut while writes may be arriving - What happens to writes that were sent but not yet applied, and to writes applied after the last snapshot - A versioned, safe serialization format and an atomic replacement of the snapshot file ### Part 4 — Values freeze once read Values are immutable once read: if `get` returns a value, any later `set` for that key at an earlier timestamp should be rejected. However, backfilling historical data must still be supported. ```hint Which reads can a write change A new version changes the answer of `get` only for some query timestamps. Work out which ones, and what you must remember about past reads to tell whether a write would contradict one of them. ``` #### Clarifying Questions for this Part - Earlier than what: the timestamp the reader asked for, or the timestamp of the version it received? Is a write at exactly the read timestamp also rejected? - May backfill go into any range that no reader has observed, or is it a separate, privileged operation? #### What This Part Should Cover - A rule that rejects exactly the writes that would change a value already returned, while still accepting backfill - The extra state the rule needs and its memory cost - How the rule fits the missing-key choice, `get_latest`, and the snapshot from Part 3 ### What a Strong Answer Covers - Names each conflicting requirement (O(1) against an at-or-before lookup, bounded memory against a full history, thread safety against single-threaded access, frozen reads against backfill) and resolves it explicitly with the interviewer - Correct results under out-of-order, duplicate and conflicting writes - A snapshot that includes the read-tracking and retention state, not only the values - An honest complexity and memory analysis rather than an unsupported O(1) claim - Clean, testable code with tests for late writes, rejected writes and a serialize/deserialize round trip ### Follow-up Questions - How would you scale this to 10,000 GPUs? - A job resumes from step N and writes the steps after N again with different values. How should the store treat those writes? - Because of Part 4, a `get` now changes state. What does that mean for durability, caching and replication? - How would you cap memory per key so that every `get` is either correct or explicitly unavailable?