Design a Globally Versioned Key-Value Store

Design a versioned key-value store with a version number shared globally across keys. A historical read uses `get(key, version)` to retrieve the value associated with that key at the requested version. Explain how writes should be recorded and how binary search can locate the relevant entry in a key's history. Clarify whether “at a version” means the latest write no later than the requested global version, rather than the write with the smallest absolute distance. State assumptions about how writes allocate versions, missing keys, and reads before a key's first write; those API details are unspecified. ### What a Strong Answer Covers - One global ordering of writes, with sparse per-key histories when other keys consume intervening versions. - The difference between exact-match lookup, predecessor lookup, and nearest-by-distance lookup. - An append-only history representation and the binary-search boundary needed for the chosen read semantics. - A consistent publication order between allocating a version, storing a write, and making it visible to readers. - Write, historical-read, and storage complexity, including the cost of retaining old values. ```hint Gaps belong to other keys A key may have writes at widely separated global versions. Decide what a read between those versions means before choosing the binary-search result. ``` ### Follow-up Questions - How would simultaneous writers preserve a meaningful global version order? - What historical information must remain if the store introduces a retention cutoff?