In-memory key-value store with nested transactions

Q: How would this look in Go, and in production?

In Go the undo log is a []map[string]undoEntry where undoEntry holds the old value and an existed bool flag, which replaces the sentinel object. Add a sync.Mutex if more than one goroutine uses the store. Real systems scope transactions per client session rather than per store. In etcd, for example, a transaction is a compare-and-swap submitted in one request, and there is no long-lived open transaction.

hardCaches

Build an in-memory key-value store that supports nested transactions, the same idea as a config store where an operator can stage several edits, inspect them, and then either apply or abandon the whole batch.

API (Java: keys are String, values Object)

◈ DIAGRAM

KVStore()
set(key, value) -> None
get(key) -> value or None
delete(key) -> bool          # True if the key existed
count(value) -> int          # how many keys currently hold this value
begin() -> None              # open a transaction (may be nested)
rollback() -> bool           # undo the innermost open transaction
commit() -> bool             # close the innermost open transaction, keeping its changes

Rules

Reads always see the latest writes, including writes inside open transactions.
rollback restores every key touched in the innermost transaction to its value at begin, including keys that were created (they disappear) or deleted (they come back). It returns False if no transaction is open.
commit closes only the innermost transaction. Its changes become part of the enclosing transaction, so a later rollback of the outer transaction still undoes them. It returns False if no transaction is open.
count must be O(1). set, get and delete must be O(1) no matter how many transactions are open.
rollback may cost time proportional to the number of keys that transaction touched, but not to the size of the store.

Outputs are the return values of the calls that return something (get, delete, count, commit, rollback), in order.

Examples

Example 1

Input: db.set("a", 10) db.begin() db.set("a", 20) db.set("b", 20) db.count(20) db.begin() db.delete("a") db.get("a") db.count(20) db.rollback() db.get("a") db.commit() db.get("a") db.rollback() db.count(20)

Output: 2 true null 1 true 20 true 20 false 2

Explanation: The inner rollback brings back the deleted "a". The commit then closes the only open transaction, so the final rollback has nothing to undo.

Example 2

Input: db.set("x", 1) db.begin() db.begin() db.set("x", 2) db.set("y", 5) db.commit() db.get("x") db.rollback() db.get("x") db.get("y") db.count(5) db.delete("y")

Output: true 2 true 1 null 0 false

Explanation: The inner commit merges its changes into the outer transaction. Rolling back the outer one undoes both writes, so "y" never existed.

Hints

Approach

Keep one live map, a counts map from value to number of keys, and a stack of undo logs, one per open transaction.

Every write goes through one helper, _write(key, value), which updates data and adjusts counts for the old and new values. Having a single write path is what keeps count correct through rollbacks.
Before a set or delete changes a key, _record stores the key's current value in the innermost undo log, but only the first time that transaction touches the key. A missing key is stored as a _MISSING sentinel, because None could be a legitimate value.
rollback: pop the innermost log and _write each saved value back. A _MISSING value deletes the key.
commit: pop the innermost log. If there is a parent transaction, copy each entry into the parent unless the parent already has that key. The parent's older value is the one it must restore to.

The cost of a transaction is proportional to the keys it touches, never to the size of the store.

ComplexityTime O(1) per set/get/delete/count; O(k) per commit/rollback for k touched keysSpace O(n + total touched keys)

Python

from collections import defaultdict
 
_MISSING = object()   # "key did not exist" marker in the undo log
 
 
class KVStore:
    def __init__(self):
        self.data = {}
        self.counts = defaultdict(int)   # value -> number of keys holding it
        self.undo = []                   # one dict per open transaction: key -> value before the tx touched it
 
    def _write(self, key, value):
        old = self.data.get(key, _MISSING)
        if old is not _MISSING:
            self.counts[old] -= 1
        if value is _MISSING:
            self.data.pop(key, None)
        else:
            self.data[key] = value
            self.counts[value] += 1
 
    def _record(self, key):
        if self.undo and key not in self.undo[-1]:
            self.undo[-1][key] = self.data.get(key, _MISSING)   # remember only the first old value
 
    def set(self, key, value):
        self._record(key)
        self._write(key, value)
 
    def get(self, key):
        return self.data.get(key)
 
    def delete(self, key):
        if key not in self.data:
            return False
        self._record(key)
        self._write(key, _MISSING)
        return True
 
    def count(self, value):
        return self.counts[value]
 
    def begin(self):
        self.undo.append({})
 
    def rollback(self):
        if not self.undo:
            return False
        for key, old in self.undo.pop().items():
            self._write(key, old)
        return True
 
    def commit(self):
        if not self.undo:
            return False
        inner = self.undo.pop()
        if self.undo:                       # nested: the parent must still be able to undo these keys
            parent = self.undo[-1]
            for key, old in inner.items():
                parent.setdefault(key, old)
        return True

Follow-up questions

Add snapshot() -> id and restore(id) that work outside transactions. How do you avoid a full copy per snapshot? (Persistent maps or copy-on-write.)
Two clients each have an open transaction. How would you isolate them from each other?
Persist committed changes to disk so a restart does not lose them. What would you write, and when?

Frequently asked questions

A layered design keeps each transaction's writes in its own map and reads by walking layers from the top. It works, but get becomes O(depth) and count gets awkward. The undo log keeps reads O(1), because the live map is always the current truth. Databases use both ideas: undo logs to roll back, and redo or write-ahead logs to replay committed changes after a crash.

In Go the undo log is a []map[string]undoEntry where undoEntry holds the old value and an existed bool flag, which replaces the sentinel object. Add a sync.Mutex if more than one goroutine uses the store. Real systems scope transactions per client session rather than per store. In etcd, for example, a transaction is a compare-and-swap submitted in one request, and there is no long-lived open transaction.