Katkat
Back

In-Memory Key-Value Store with Nested Begin, Commit, and Rollback Transactions

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A coding question to implement an in-memory key-value store with begin, set, unset, commit and rollback, where transaction blocks can be nested and committed changes can no longer be rolled back. It tests how state is recorded per block, restoring keys that were absent, nested commit semantics, and operation complexity.

Implement an in-memory key-value store that supports transactions:

  • set(key, value) sets key to value.
  • unset(key) removes key.
  • get(key) returns the current value of key, or None if it is not set. A read is needed to observe the store, so implement it too.
  • begin() opens a new transaction block.
  • rollback() undoes every change made in the most recent open block, and closes that block.
  • commit() makes changes permanent. Once a change has been committed, it can no longer be rolled back.

Blocks can be nested: a begin inside an open block opens an inner block. Changes made outside any block take effect immediately and permanently.

Constraints and Clarifications

  • A single client issues commands one at a time; there is no concurrency.
  • Assume keys and values are strings.
  • Reads inside a block see that block's own uncommitted changes.

Clarifying Questions

  • With nested blocks open, does commit make every open block permanent and close them all, or does it only merge the innermost block into its parent?
  • What should rollback and commit do when no block is open?
  • Must get stay fast however deeply blocks are nested, or is a cost proportional to the nesting depth acceptable?

Hints

Hint 1

What rollback needs: For each open block, think about the minimum information you must remember in order to restore the store, and when you need to capture it.

Hint 2

Absent is a state too: Rolling back must also restore keys that did not exist before the block, and keys that the block unset.

Follow-up questions

  • Add `count(value)`, which returns how many keys currently hold `value`. How do you keep it O(1) through rollbacks?
  • How would you make committed data survive a process crash?
  • If several clients each had their own open transactions on a shared store, what isolation would you offer, and how?