Versioned Key-Value Store

System Design Data Structure Versioning

Design and implement a versioned key-value store that supports snapshot queries. The data structure should handle the following operations:

  1. set(key, value)

    • Store the key-value pair in the current active state.

  2. snapshot() -> version_id

    • Create a snapshot of the current state and return a unique version identifier. Snapshots should capture all previous set operations up to that point.

  3. get(key, version_id)

    • Retrieve the value associated with the given key as it was at the time of the specified snapshot. If the key did not exist in that version, return an appropriate response (e.g., null or a similar indicator).

Requirements:

  • The system should support multiple snapshots, and the get operation should correctly retrieve historical values based on the provided version identifier.
  • Optimize for scenarios where there are many more reads (get) than writes (set and snapshot).
  • Consider how your design scales with a large number of keys and frequent snapshot operations.

Your solution can be implemented in any language of your choice. Provide well-structured code and include brief instructions on how to run and test your implementation.