In-Memory Key-Value Store with TTL & Nested Transactions
This is the single most frequently asked Low-Level Design prompt for Engineering Team Lead and Engineering Manager candidates at Atlassian and Stripe. Here is the full architectural breakdown, trade-off defense, and complete runnable code.
Never Start Coding Immediately. Clarify These 4 Constraints First:
“Should transactions support arbitrary nesting (calling `begin()` multiple times before `commit()`), and can rollbacks discard only the innermost transaction?”
“Are keys and values strictly strings, or should we design the store with generics to support arbitrary serialized payloads?”
“For TTL expiration, is lazy deletion on read acceptable, or do you want an active background eviction worker thread?”
“Should we start single-threaded for the MVP and design our storage layer so that ReadWriteLocks can be injected later?”
The Fatal Mistake: Deep Copying the Root Store on `begin()`
Many candidates attempt to implement transactions by cloning the entire global HashMap when `begin()` is invoked. This fails the senior bar because cloning has an O(N) time and memory footprint per transaction. If your store has 1,000,000 keys, `begin()` will block for hundreds of milliseconds.
Maintain a Stack of delta maps: transactionStack: Stack<Map<String, ValueEntry | null>>. When begin() is called, simply push an empty map onto the stack (O(1)). Writes go to the top active delta. Reads inspect deltas from top to bottom, falling back to committed storage. Deletions write a sentinel `null` to the active delta. `rollback()` simply pops the top delta in O(1) time!
const store = new TransactionalKeyValueStore();Global committed store is empty. No transaction deltas exist on the stack.
Full 250-line code is collapsed to preserve screen focus. Click expand to inspect data structures, transaction deltas, and test assertions.
“In this 45-minute live design, I chose lazy expiration on read access. The trade-off is that expired keys that are never queried again occupy memory until restart. In production, I would augment this with a background worker thread that samples a random subset of keys with TTLs every 100ms to keep idle memory bounded without lock contention.”
“Rather than synchronizing every single method coarsely, I would wrap `globalStore` with a `ReentrantReadWriteLock`. In a read-heavy key-value store, 90%+ operations are reads. ReadWriteLocks allow hundreds of concurrent reader threads to execute without blocking one another, while writes acquire an exclusive lock.”