Katkat
Back

In-Memory Key-Value Store with Constant-Time Nested Transactions

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Build an in-memory key-value store with get, set and delete plus nested begin, commit and rollback, aiming for constant-time operations. Follow-ups extend it to concurrent threads, keys with a time to live, and reads of a key's value at an earlier point in time.

Implement an in-memory key-value store with transactions. It supports get, set and delete, plus begin, commit and rollback, and the question asks for every operation in constant time. The follow-ups then extend the store: several threads using it at once, keys that expire after a time to live, and "time travel" reads of a key's value at an earlier time.

store = TxStore()
store.set("a", 1)
store.begin()
store.set("a", 2)
store.delete("b")
store.get("a") # 2
store.rollback()
store.get("a") # 1

Clarifying Questions

  • Can transactions be nested, and does commit close only the innermost transaction or all open ones?
  • What do commit and rollback do when no transaction is open?
  • What does get return for a missing or deleted key?
  • Is constant time required for each call in the worst case, or is amortized constant time acceptable, and does that include rollback?
  • In the threaded version, does each thread run its own transactions, and may one thread see another's uncommitted writes?

Part 1 — Transactions

Implement get(key), set(key, value), delete(key), begin(), commit() and rollback(). A rollback undoes every change made since the matching begin; a commit keeps them.

What This Part Should Cover

  • The data structures, and the cost of each operation, stated honestly
  • Correct undo of a key that did not exist before the transaction
  • Nested transactions: what a nested commit hands to the enclosing transaction

Part 2 — Several threads

Make the store safe when several threads call it at once.

What This Part Should Cover

  • What a lock protects and how long it is held
  • Whether transactions are per thread, and how their writes are isolated
  • What happens when two transactions write the same key

Part 3 — Time to live

Add set(key, value, ttl): the key disappears ttl seconds after it was set.

What This Part Should Cover

  • How reads treat expired keys
  • How expired keys are eventually removed, and the cost of doing so
  • How the clock is supplied so that expiry can be tested

Part 4 — Time travel

Add get(key, at_time), which returns the value the key had at an earlier time.

What This Part Should Cover

  • The history kept per key and the lookup cost
  • How deletes and transactions show up in the history
  • How the history is bounded in memory

Hints

Hint 1

Where do writes go: Decide whether a write inside a transaction changes the main map right away or is kept aside, and what that choice costs for reads, for commits and for rollbacks.

Hint 2

What one thread may see: Separate keeping the data structures intact from deciding when one thread's changes become visible to the others.

Hint 3

Expire on demand or in the background: Consider what a read must check, and what keeps keys that are never read again from filling memory.

Hint 4

Keep history per key: Think about what has to be kept for each key so that a read at any past time is fast.

Follow-up questions

  • The process may crash. How do you make committed data survive a restart?
  • Add `count(value)`, the number of keys currently holding a value, in constant time, and keep it correct across rollbacks.
  • Memory is capped. Which keys do you evict, and how does eviction interact with open transactions?
  • Two long transactions keep conflicting. How would you choose between locking and optimistic validation?