Transactional Key-Value Store

The problem

A transactional key-value store lets a caller make a group of tentative edits and either retain or discard them. Its basic state is a mapping from string keys to string values. The interesting responsibility is defining which view a read observes and which edits a rollback removes. A missing key must remain distinguishable from a key holding the empty string.

Nested transactions add another boundary. An inner commit should merge into its immediate parent, not bypass it and write to the base store. If that parent later rolls back, the inner transaction's committed changes must disappear with it. Transaction depth therefore belongs to the store's explicit state.

Naive approach

A dictionary supports expected constant time set, get, and delete. To add rollback, save the dictionary when begin() is called and restore it later. A first attempt might assign saved = current, expecting this to preserve the earlier view. Both names actually reference the same mutable dictionary, so subsequent writes change the supposed checkpoint too.

Assignment does not create a checkpoint:

current = {"mode": "base"}
saved = current
current["mode"] = "tentative"
current = saved  # An attempted rollback.
print(current["mode"])
assert current["mode"] == "tentative"

Both names referred to the same dictionary. A shallow copy is enough only because this store’s string values cannot be mutated through shared references.

One global backup also cannot represent nesting. Starting a second transaction overwrites the first backup. An inner commit may appear to work, but the outer rollback no longer knows which state to restore. These are state representation errors, not problems that a more elaborate dispatcher can solve.

Where the naive approach breaks

Start with mode="base". Begin an outer transaction, set mode="outer", begin an inner transaction, and set mode="inner". Committing the inner transaction leaves the visible value "inner" at depth one. Rolling back the outer transaction must restore "base" at depth zero. A commit that writes straight to the base dictionary violates this trace.

Deletion has its own trap. If a transaction is represented as a dictionary of changed values with fallback reads from its parent, simply removing a local key does not hide a key in the parent. Such a design needs an explicit deletion marker. A copied full view avoids that complication, at the cost of copying more state.

A better design

For a small store, use a stack of complete dictionary views. Keep one base view at depth zero. begin() pushes a shallow copy of the current view. This is sufficient because keys and values are strings, which are immutable. Reads and writes always use the top view; callers never receive that dictionary itself.

The stack’s nesting rule is small enough to inspect directly:

views = [{"mode": "base"}]
views.append(views[-1].copy())  # Begin outer.
views[-1]["mode"] = "outer"
views.append(views[-1].copy())  # Begin inner.
views[-1]["mode"] = "inner"
child = views.pop()
views[-1] = child             # Commit into the parent only.
views.pop()                  # Roll back outer.
print(views[-1]["mode"])
assert views == [{"mode": "base"}]

The inner commit remains tentative relative to the base. These frame operations omit public argument checks and depth-zero errors; they illustrate nested ownership, not isolation between independent database sessions.

With N visible keys, beginning a transaction takes O(N) time and space. Point reads and writes are expected O(1) within a view. Replacing a frame reference is constant time conceptually, although Python may spend time releasing discarded dictionaries. D nested full views can retain O(DN) entries. Snapshot filtering scans N keys and sorts the matches. For larger workloads, change-only frames or undo logs reduce copying but require tombstones, careful merge rules, and more complex reads.

Real-world usage

Nested rollback boundaries are useful in configuration editing, interactive tools, and tests that temporarily modify shared setup. They also help explain savepoint-like behavior, but this exercise is a single-session model. Copied dictionaries do not provide isolation between concurrent sessions, crash recovery, or the durability of a database transaction. Named savepoints and concurrent writers are intentionally outside its contract.