Katkat
Back

Design a Globally Versioned Key-Value Store

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Design a globally versioned key-value store with sparse key histories, binary-search reads, atomic version publication, and correct history retention.

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.

Hints

Hint 1

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?