Code an in-memory key-value store with transactions

In one minute

• The store is three ideas stacked: a hash map for committed data, a stack of change sets for open transactions, and a per-value counter so "how many keys hold this value" is not a scan.
• A transaction does not copy the data and does not write into the base. It writes into a small overlay that records only what changed, and a delete is a tombstone entry in that overlay. Rollback then costs nothing: throw the overlay away.
• Reads walk the stack from the newest layer down, so get is O(depth). Commit of an inner layer merges it into its parent in O(size of the layer). Keep these costs explicit; they are the heart of the interview answer.
• The counter must follow the same layering as the data. Store a signed delta per value in each layer, and count is the base count plus the deltas. Otherwise rollback silently corrupts counts.
• The shape is multi-step consistency: several changes must become visible together or not at all. The same stack-of-savepoints idea runs inside SQL databases, ORMs and editor undo.

Requirements

Functional:

• set(key, value), get(key) (absent returns nothing) and delete(key) (reports whether the key existed).
• count(value): how many keys currently hold this value, as seen by the caller inside the current transaction.
• begin() opens a transaction and may be nested to any depth. rollback() discards the innermost open transaction. commit() makes the innermost transaction part of its parent. commit_all() commits every open level at once, which is what a bare COMMIT does in many simple shells.
• rollback() or commit() with no open transaction is an error the caller can see, never a silent no-op.

Non-functional:

• get, set, delete and count cost O(depth) at worst, and O(1) when no transaction is open.
• begin and rollback are O(1). commit is O(changes in the committed layer), never O(store size).
• A transaction sees its own writes and its ancestors' writes, and nobody else's.
• Fully deterministic: no clock is involved, so tests need none.

Out of scope: durability (a write-ahead log), isolation between concurrent clients, TTLs and range scans. Mention them under Extensibility and move on.

Entities and relationships

• Store: the public object. Owns the base map and the stack of layers.
• Base: a map of committed key to value, plus a map of committed value to count.
• Layer: one open transaction. It holds changes (key to new value or a tombstone) and deltas (value to a signed integer).
• Tombstone: a unique marker meaning "deleted in this layer". It is needed because absence from the overlay means "ask the parent", which is a different statement from "deleted".

The stack is the only relationship that matters: layer n can see layers 0 to n-1 and the base, and nothing sees upward. Commit collapses the top of the stack one step; rollback pops it.

Class diagram

classDiagram
    class Store {
        -base: Map
        -baseCounts: Map
        -layers: List~Layer~
        +set(key, value)
        +get(key) value
        +delete(key) bool
        +count(value) int
        +begin()
        +rollback() bool
        +commit() bool
        +commitAll() bool
    }
    class Layer {
        +changes: Map
        +deltas: Map
    }
    class Tombstone
    Store "1" o-- "0..*" Layer : stack
    Layer ..> Tombstone : marks deletes

Key flows

sequenceDiagram
    participant C as Client
    participant S as Store
    participant L1 as Layer 1
    participant L2 as Layer 2
    C->>S: set(a, 1)
    S->>S: write base
    C->>S: begin()
    S->>L1: push empty layer
    C->>S: delete(a)
    S->>L1: changes[a] = tombstone, delta[1] -= 1
    C->>S: begin()
    S->>L2: push empty layer
    C->>S: set(a, 2)
    S->>L2: changes[a] = 2, delta[2] += 1
    C->>S: get(a)
    S->>L2: found 2
    C->>S: rollback()
    S->>L2: drop layer
    C->>S: get(a)
    S->>L1: found tombstone, so absent
    C->>S: commit()
    S->>S: apply L1 to base, a removed

Walk the flow in words. A set first looks up the current visible value of the key, because the delta needs the old value to decrement. It then records the new value in the top layer, subtracts one from the old value's delta and adds one to the new value's delta. A delete is the same with a tombstone as the new value. A get scans layers newest first and returns the first entry it meets, treating a tombstone as "absent" and stopping there. A count sums the base count and every layer's delta for that value.

Design patterns used and why

• Memento-style snapshots, avoided. The obvious way to support rollback is to copy the whole map on begin (Memento stores a snapshot of state). That makes begin O(n) and every nested level another full copy. An overlay stores only the difference, so cost follows the size of the change, not the size of the store.
• Unit of Work. A layer is a small unit of work: it accumulates changes and either flushes them to its parent or is dropped (Fowler).
• Command and undo log, the alternative. Instead of overlays you can write through to the base and push an inverse record per write onto an undo stack (Command objects with an undo). Reads and counts become O(1), but rollback costs O(changes) and the data in the base is uncommitted, which hurts as soon as another reader exists. See the trade-offs table.
• Null Object / sentinel. The tombstone is a sentinel that lets one dictionary say three things: present with a value, deleted, or no opinion.

Concurrency and edge cases

• Delete then set in one layer. delete(a) leaves a tombstone, then set(a, 5) overwrites it. The delta for the old value was already decremented by the delete, so the set must read the visible value as absent and add only the new one. Computing the old value from the stack, not from the layer alone, makes this fall out correctly.
• Setting the same value. set(a, 1) when a is already 1 subtracts one and adds one to the same slot. The net delta is zero, which is right. Do not special-case it away, because special cases are where counts drift.
• Delete of a missing key. It must report false and must not create a tombstone or touch any delta. A phantom tombstone would later decrement a count that was never incremented.
• Commit onto a parent that already has the key. The child's entry replaces the parent's, and the child's deltas are added to the parent's. Replacing the deltas would lose the parent's own changes.
• Tombstones that reach the base. When the outermost layer commits, a tombstone removes the key from the base and is then forgotten. Zero-valued count entries should be dropped so the count map does not grow with every value ever seen.
• Rollback or commit with no transaction. Return an error or false. Silent success hides bugs, and the Rails documentation shows what silence costs (see In the wild).
• Threads. The simplest correct answer is one mutex around every method, which gives one global serial order. A transaction that spans several calls needs its own session object per client, otherwise two clients share one stack. Say that out loud, then keep the single-client design.

In the wild

• GitLab, 2021: SAVEPOINT stalls on replicas. Intermittent minutes-long stalls on GitLab.com produced 500 errors for users. After weeks of investigation GitLab traced them to subtransactions: a SAVEPOINT inside a long-running transaction can degrade PostgreSQL replicas, and the Rails application was using them, for example through requires_new: true. The team instrumented the application to log any transaction issuing more than 32 SAVEPOINT calls and then removed SAVEPOINT queries from the codebase (GitLab blog). Lesson: a nested-transaction stack is cheap in your toy store and not free in a real database.
• Rails, long-standing behaviour: nested transaction blocks that do not roll back. By default a nested transaction block joins the outer one. An ActiveRecord::Rollback raised in the inner block is captured there, the parent does not see it, and the real transaction commits. Asking for a real sub-transaction needs requires_new: true, which creates a savepoint (Rails API docs). The same page notes that on MySQL a DDL statement inside the block releases the savepoint implicitly, so the later release fails.
• Redis, by design: no rollback. A transaction queued with MULTI and run with EXEC executes all queued commands in order, but if one fails the others still run. The docs state that Redis does not support rollback because it would hurt simplicity and performance, and that DISCARD only drops a queue that has not run yet (Redis docs). This is the opposite design choice to the one in this lesson, and a good answer can say when it is reasonable.

Down the stack

Extensibility

• Durability. Append each committed layer as one record to a write-ahead log, then fsync. Recovery replays whole records, so a crash applies a transaction fully or not at all.
• Concurrent clients. Give each client a session with its own layer stack over a shared base. Add a version number to the base and, at commit, abort if a key the transaction read has changed (optimistic concurrency). Redis offers this as WATCH.
• Undo-log variant. Switch to write-through plus an inverse log if reads dominate. Counts stay O(1); rollback costs O(changes).
• Savepoint names. ROLLBACK TO name can unwind several layers at once: pop until the named one. This needs only a name stored on each layer.
• Snapshots without depth cost. Persistent maps (hash array mapped tries) share structure, so begin is O(1) and reads are O(log n) at any depth.

Leadership lens

• Ask in review: what does rollback mean for the counters, caches and indexes derived from the data? Derived state is where most transaction bugs hide.
• Decide whether nested transactions are a feature or an accident. Rails shows the default can be "joins the parent", and a team that assumes savepoint behaviour will lose rollbacks silently.
• Put a cap or a metric on nesting depth. GitLab only found its problem after instrumenting the application to count savepoints per transaction.
• Build first: flat begin/commit/rollback, then nesting, then the counter. Ship the invariant test (rollback restores everything) before any optimisation.
• Cost drivers are memory for open layers and the length of long-lived transactions, not CPU.

Check yourself

1. Why does the layer store a tombstone for a delete instead of removing the key from its own map?

   Show answer

   Absence from a layer means "ask the parent". Removing the entry would make the parent's value visible again, so the delete would be undone.

2. A transaction sets a=1 where a was absent, then deletes a, then rolls back. What is count(1) and why?

   Show answer

   Unchanged from before begin. The set added +1 and the delete added -1 to that layer's delta, and rollback drops the layer anyway.

3. What goes wrong if commit copies the child's deltas over the parent's instead of adding them?

   Show answer

   The parent's own count changes for the same value are lost, so count is wrong after the commit and stays wrong after the base absorbs it.

4. When would you choose an undo log over overlays, and what do you give up?

   Show answer

   Choose it when reads and counts dominate and transactions are short, since reads are O(1). You give up cheap rollback and clean isolation, because uncommitted data sits in the base.

Sources and further study

Primary

• SQLite: SAVEPOINT: precise semantics of nested ROLLBACK TO and RELEASE, the model behind this lesson's rollback and commit.
• SQLite: atomic commit: how a real engine makes a transaction all-or-nothing on disk.
• PostgreSQL: SAVEPOINT: savepoint behaviour and the worked insert example.

Systems docs

• Redis: transactions: MULTI, EXEC, DISCARD, WATCH and the stated reason Redis has no rollback.
• Rails: ActiveRecord transactions: nested blocks, requires_new and the swallowed Rollback.
• Django: database transactions: atomic() and savepoints as nested units.
• GitLab: eliminating PostgreSQL subtransactions: what savepoints cost at production scale.

Books

• Designing Data-Intensive Applications, Kleppmann (1st edition): chapter 7 "Transactions", for atomicity, isolation levels and snapshot isolation.
• Database Internals, Petrov: chapter 5 "Transaction Processing and Recovery", for buffer management, logs and recovery.

Other curricula

• Wikipedia: Nested transaction: the textbook framing of child transactions committing into a parent.

Free resources

• Unit of Work (Martin Fowler): the pattern behind a layer that accumulates changes and flushes them once.
• Memento (Refactoring.Guru): the snapshot approach this lesson argues against, and when it is fine.
• Command (Refactoring.Guru): commands with undo, the basis of the undo-log variant.
• Multiversion concurrency control (Wikipedia): how real databases keep several versions visible to different readers.
• PostgreSQL: MVCC introduction: the next step once several clients share the store.