Implement a Versioned Key-Value Store

Approach 1: Replay and Scan Previous Writes Since the batch contains every operation in order, the simplest mental model is to replay the sequence from left to right. A get operation should only see writes that have already occurred, so when we reach a get, we can scan every earlier operation and keep the best matching version for that key. For a query timestamp q, a candidate write is valid if: its operation is put, its key matches the key being queried, and its timestamp…