Transactional Key-Value Store

Ownership and transitions

An inner commit merges into its immediate parent, so the outer transaction can still roll back that committed child. A stack of full map copies makes these boundaries explicit; delta maps need tombstones to hide parent keys. Strings make a shallow map copy sufficient. Begin costs O(N) time/space; D full frames retain O(DN); point operations remain expected O(1).

Java boundaries

Use the supplied nested records as immutable value carriers. A record is only shallowly immutable: copy every retained mutable input and every outward list/map, including lists inside records. Absence is null; validation failures use IllegalArgumentException, missing-key purchase errors use NoSuchElementException, and invalid transaction boundaries use IllegalStateException. Java primitive types already exclude booleans from numeric inputs. Numeric values use long where signatures say long and all computations must fit signed 64-bit values. Calls in these service exercises are serialized.

An inner commit remains tentative relative to an outer transaction. Distinct frame ownership makes that nesting visible:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Map<String, String> base = new HashMap<>(Map.of("mode", "base"));
        Map<String, String> outer = new HashMap<>(base);
        Map<String, String> inner = new HashMap<>(outer);
        inner.put("mode", "inner");
        outer = inner; // inner commit replaces only its immediate parent
        assert base.get("mode").equals("base");
        assert outer.get("mode").equals("inner");
    }
}

The base frame is unchanged, so discarding outer can still restore base. Assigning outer=base at begin would instead alias the same map and make rollback impossible.

Design boundary

Copied complete views trade memory for simple semantics. A more compact overlay design must represent deletion explicitly; absence from an overlay cannot mean both inherit-parent and delete-parent. This single-session contract provides rollback boundaries, not isolation across concurrent sessions or disk durability.