In-memory veritabanı: alan bazlı kayıt, TTL ve iç içe transaction

void set(String key, String field, String value);
Optional<String> get(String key, String field);
boolean delete(String key, String field);

set("user:1", "name", "Ada")
get("user:1", "name")     -> Optional[Ada]
get("user:1", "email")    -> Optional.empty
delete("user:1", "name")  -> true
delete("user:1", "name")  -> false

List<String> scan(String key);
List<String> scanByPrefix(String key, String prefix);

set("k", "zeta", "3"); set("k", "alpha", "1"); set("k", "mid", "2")
scan("k")                 -> [alpha(1), mid(2), zeta(3)]
set("k", "ab", "1"); set("k", "abc", "2"); set("k", "b", "4")
scanByPrefix("k", "ab")   -> [ab(1), abc(2)]

void setAt(String key, String field, String value, long timestamp);
void setAtWithTtl(String key, String field, String value, long timestamp, long ttl);
Optional<String> getAt(String key, String field, long timestamp);
boolean deleteAt(String key, String field, long timestamp);
List<String> scanAt(String key, long timestamp);
List<String> scanByPrefixAt(String key, String prefix, long timestamp);

setAtWithTtl("k", "f", "v", 10, 5)   // [10, 15) arasında görünür
getAt("k", "f", 14)                  -> Optional[v]
getAt("k", "f", 15)                  -> Optional.empty
deleteAt("k", "f", 20)               -> false   (zaten süresi dolmuş)

void begin();
void commit();     // aktif transaction yoksa IllegalStateException
void rollback();   // aktif transaction yoksa IllegalStateException

set("k", "f", "old")
begin()
  set("k", "f", "new")
  begin()
    set("k", "g", "x")
  commit()            // iç transaction'ın değişiklikleri dıştakine katılır
rollback()            // ikisi birden geri alınır
get("k", "f")  -> Optional[old]
get("k", "g")  -> Optional.empty

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.TreeMap;

/**
 * In-memory key -> field -> value store.
 * Level 1: set/get/delete, Level 2: ordered scan and prefix scan,
 * Level 3: timestamped operations with TTL, Level 4: nested transactions.
 */
public final class InMemoryDatabase {

    /** A value and the first timestamp at which it is no longer visible. */
    private record Entry(String value, long expiresAt) {
        boolean isAliveAt(long timestamp) {
            return timestamp < expiresAt;
        }
    }

    /** Address of a single field; used as the undo-log key. */
    private record Slot(String key, String field) {}

    private static final long NO_EXPIRY = Long.MAX_VALUE;
    /** Level 1-2 calls have no timestamp; they are treated as happening at time 0. */
    private static final long NO_TIMESTAMP = 0L;

    // TreeMap per key keeps fields sorted, so scans need no extra sort.
    private final Map<String, TreeMap<String, Entry>> records = new HashMap<>();

    // One undo log per open transaction; the top of the stack is the innermost one.
    // Value = entry before the first change in that transaction, null = field did not exist.
    private final Deque<Map<Slot, Entry>> undoLogs = new ArrayDeque<>();

    // ---------- Level 1 ----------

    public void set(String key, String field, String value) {
        setAt(key, field, value, NO_TIMESTAMP);
    }

    public Optional<String> get(String key, String field) {
        return getAt(key, field, NO_TIMESTAMP);
    }

    public boolean delete(String key, String field) {
        return deleteAt(key, field, NO_TIMESTAMP);
    }

    // ---------- Level 2 ----------

    /** Returns "field(value)" items for the key, ordered by field name. */
    public List<String> scan(String key) {
        return scanAt(key, NO_TIMESTAMP);
    }

    public List<String> scanByPrefix(String key, String prefix) {
        return scanByPrefixAt(key, prefix, NO_TIMESTAMP);
    }

    // ---------- Level 3 ----------

    public void setAt(String key, String field, String value, long timestamp) {
        Objects.requireNonNull(value, "value");
        write(key, field, new Entry(value, NO_EXPIRY));
    }

    /** The value is visible in [timestamp, timestamp + ttl). */
    public void setAtWithTtl(String key, String field, String value, long timestamp, long ttl) {
        Objects.requireNonNull(value, "value");
        if (ttl <= 0) {
            throw new IllegalArgumentException("ttl must be positive: " + ttl);
        }
        write(key, field, new Entry(value, Math.addExact(timestamp, ttl)));
    }

    public Optional<String> getAt(String key, String field, long timestamp) {
        Entry entry = liveEntry(key, field, timestamp);
        return entry == null ? Optional.empty() : Optional.of(entry.value());
    }

    public boolean deleteAt(String key, String field, long timestamp) {
        if (liveEntry(key, field, timestamp) == null) {
            return false;
        }
        erase(key, field);
        return true;
    }

    public List<String> scanAt(String key, long timestamp) {
        return scanByPrefixAt(key, "", timestamp);
    }

    public List<String> scanByPrefixAt(String key, String prefix, long timestamp) {
        Objects.requireNonNull(prefix, "prefix");
        TreeMap<String, Entry> fields = records.get(Objects.requireNonNull(key, "key"));
        if (fields == null) {
            return List.of();
        }
        List<String> result = new ArrayList<>();
        // Fields sharing a prefix are contiguous in sorted order and start at the prefix itself.
        for (Map.Entry<String, Entry> e : fields.tailMap(prefix, true).entrySet()) {
            if (!e.getKey().startsWith(prefix)) {
                break;
            }
            if (e.getValue().isAliveAt(timestamp)) {
                result.add(e.getKey() + "(" + e.getValue().value() + ")");
            }
        }
        return result;
    }

    // ---------- Level 4 ----------

    public void begin() {
        undoLogs.push(new HashMap<>());
    }

    /** Makes the innermost transaction's changes part of its parent (or permanent if outermost). */
    public void commit() {
        Map<Slot, Entry> committed = popTransaction();
        Map<Slot, Entry> parent = undoLogs.peek();
        if (parent == null) {
            return;
        }
        // The parent must keep its own, older "before" image if it already has one.
        // putIfAbsent is wrong here: it treats a slot mapped to null as absent.
        committed.forEach((slot, before) -> {
            if (!parent.containsKey(slot)) {
                parent.put(slot, before);
            }
        });
    }

    /** Undoes every change made since the matching begin(). */
    public void rollback() {
        popTransaction().forEach((slot, before) -> {
            if (before == null) {
                removeRaw(slot.key(), slot.field());
            } else {
                putRaw(slot.key(), slot.field(), before);
            }
        });
    }

    public int transactionDepth() {
        return undoLogs.size();
    }

    // ---------- internals ----------

    private Map<Slot, Entry> popTransaction() {
        if (undoLogs.isEmpty()) {
            throw new IllegalStateException("no active transaction");
        }
        return undoLogs.pop();
    }

    private Entry liveEntry(String key, String field, long timestamp) {
        Objects.requireNonNull(key, "key");
        Objects.requireNonNull(field, "field");
        TreeMap<String, Entry> fields = records.get(key);
        if (fields == null) {
            return null;
        }
        Entry entry = fields.get(field);
        return entry != null && entry.isAliveAt(timestamp) ? entry : null;
    }

    private void write(String key, String field, Entry entry) {
        Objects.requireNonNull(key, "key");
        Objects.requireNonNull(field, "field");
        rememberBeforeImage(key, field);
        putRaw(key, field, entry);
    }

    private void erase(String key, String field) {
        rememberBeforeImage(key, field);
        removeRaw(key, field);
    }

    private void rememberBeforeImage(String key, String field) {
        Map<Slot, Entry> current = undoLogs.peek();
        if (current == null) {
            return;
        }
        Slot slot = new Slot(key, field);
        if (!current.containsKey(slot)) {
            TreeMap<String, Entry> fields = records.get(key);
            current.put(slot, fields == null ? null : fields.get(field));
        }
    }

    private void putRaw(String key, String field, Entry entry) {
        records.computeIfAbsent(key, k -> new TreeMap<>()).put(field, entry);
    }

    private void removeRaw(String key, String field) {
        TreeMap<String, Entry> fields = records.get(key);
        if (fields == null) {
            return;
        }
        fields.remove(field);
        if (fields.isEmpty()) {
            records.remove(key);
        }
    }
}

import java.util.List;
import java.util.Map;
import java.util.Optional;

public final class InMemoryDatabaseTest {

    public static void main(String[] args) {
        Map<String, Runnable> tests = new java.util.LinkedHashMap<>();
        tests.put("level1_setGetDelete", InMemoryDatabaseTest::level1_setGetDelete);
        tests.put("level1_overwriteAndMissing", InMemoryDatabaseTest::level1_overwriteAndMissing);
        tests.put("level2_scanIsSortedByField", InMemoryDatabaseTest::level2_scanIsSortedByField);
        tests.put("level2_prefixScanStopsAtFirstNonMatch", InMemoryDatabaseTest::level2_prefixScanStopsAtFirstNonMatch);
        tests.put("level3_ttlBoundaryIsExclusive", InMemoryDatabaseTest::level3_ttlBoundaryIsExclusive);
        tests.put("level3_expiredFieldsAreHiddenFromScanAndDelete", InMemoryDatabaseTest::level3_expiredFieldsAreHiddenFromScanAndDelete);
        tests.put("level3_invalidTtlRejected", InMemoryDatabaseTest::level3_invalidTtlRejected);
        tests.put("level4_rollbackRestoresPreviousState", InMemoryDatabaseTest::level4_rollbackRestoresPreviousState);
        tests.put("level4_nestedCommitThenOuterRollback", InMemoryDatabaseTest::level4_nestedCommitThenOuterRollback);
        tests.put("level4_innerRollbackKeepsOuterChanges", InMemoryDatabaseTest::level4_innerRollbackKeepsOuterChanges);
        tests.put("level4_rollbackRestoresTtl", InMemoryDatabaseTest::level4_rollbackRestoresTtl);
        tests.put("level4_commitWithoutBeginFails", InMemoryDatabaseTest::level4_commitWithoutBeginFails);

        int passed = 0;
        for (var test : tests.entrySet()) {
            test.getValue().run();
            System.out.println("PASS " + test.getKey());
            passed++;
        }
        System.out.println(passed + "/" + tests.size() + " tests passed");
    }

    static void level1_setGetDelete() {
        var db = new InMemoryDatabase();
        db.set("user:1", "name", "Ada");
        check(db.get("user:1", "name").equals(Optional.of("Ada")), "get after set");
        check(db.delete("user:1", "name"), "delete existing returns true");
        check(db.get("user:1", "name").isEmpty(), "get after delete is empty");
        check(!db.delete("user:1", "name"), "second delete returns false");
    }

    static void level1_overwriteAndMissing() {
        var db = new InMemoryDatabase();
        db.set("k", "f", "v1");
        db.set("k", "f", "v2");
        check(db.get("k", "f").equals(Optional.of("v2")), "overwrite");
        check(db.get("missing", "f").isEmpty(), "missing key");
        check(db.get("k", "missing").isEmpty(), "missing field");
    }

    static void level2_scanIsSortedByField() {
        var db = new InMemoryDatabase();
        db.set("k", "zeta", "3");
        db.set("k", "alpha", "1");
        db.set("k", "mid", "2");
        check(db.scan("k").equals(List.of("alpha(1)", "mid(2)", "zeta(3)")), "sorted scan: " + db.scan("k"));
        check(db.scan("unknown").isEmpty(), "unknown key scans empty");
    }

    static void level2_prefixScanStopsAtFirstNonMatch() {
        var db = new InMemoryDatabase();
        db.set("k", "ab", "1");
        db.set("k", "abc", "2");
        db.set("k", "abd", "3");
        db.set("k", "b", "4");
        db.set("k", "aa", "0");
        check(db.scanByPrefix("k", "ab").equals(List.of("ab(1)", "abc(2)", "abd(3)")), "prefix scan");
        check(db.scanByPrefix("k", "x").isEmpty(), "no match");
        check(db.scanByPrefix("k", "").size() == 5, "empty prefix = full scan");
    }

    static void level3_ttlBoundaryIsExclusive() {
        var db = new InMemoryDatabase();
        db.setAtWithTtl("k", "f", "v", 10, 5);   // visible in [10, 15)
        check(db.getAt("k", "f", 10).equals(Optional.of("v")), "visible at start");
        check(db.getAt("k", "f", 14).equals(Optional.of("v")), "visible before end");
        check(db.getAt("k", "f", 15).isEmpty(), "invisible at end");
    }

    static void level3_expiredFieldsAreHiddenFromScanAndDelete() {
        var db = new InMemoryDatabase();
        db.setAt("k", "a", "1", 1);
        db.setAtWithTtl("k", "b", "2", 1, 3);
        check(db.scanAt("k", 2).equals(List.of("a(1)", "b(2)")), "both alive");
        check(db.scanAt("k", 4).equals(List.of("a(1)")), "b expired");
        check(!db.deleteAt("k", "b", 4), "deleting expired field returns false");
        db.setAtWithTtl("k", "b", "new", 5, 10);
        check(db.getAt("k", "b", 6).equals(Optional.of("new")), "set after expiry");
    }

    static void level3_invalidTtlRejected() {
        var db = new InMemoryDatabase();
        expectThrows(IllegalArgumentException.class, () -> db.setAtWithTtl("k", "f", "v", 1, 0));
        expectThrows(NullPointerException.class, () -> db.set("k", "f", null));
    }

    static void level4_rollbackRestoresPreviousState() {
        var db = new InMemoryDatabase();
        db.set("k", "keep", "1");
        db.set("k", "change", "old");
        db.begin();
        db.set("k", "change", "new");
        db.set("k", "added", "x");
        db.delete("k", "keep");
        check(db.scan("k").equals(List.of("added(x)", "change(new)")), "inside tx");
        db.rollback();
        check(db.scan("k").equals(List.of("change(old)", "keep(1)")), "after rollback: " + db.scan("k"));
        check(db.transactionDepth() == 0, "depth 0");
    }

    static void level4_nestedCommitThenOuterRollback() {
        var db = new InMemoryDatabase();
        db.begin();
        db.set("k", "f", "outer");
        db.begin();
        db.set("k", "f", "inner");
        db.set("k", "g", "inner-only");
        db.commit();                                  // inner changes now belong to outer
        check(db.get("k", "f").equals(Optional.of("inner")), "inner committed into outer");
        db.rollback();                                // must undo both levels
        check(db.get("k", "f").isEmpty(), "f did not exist before outer begin");
        check(db.get("k", "g").isEmpty(), "g did not exist before outer begin");
        check(db.scan("k").isEmpty(), "nothing left");
    }

    static void level4_innerRollbackKeepsOuterChanges() {
        var db = new InMemoryDatabase();
        db.begin();
        db.set("k", "f", "outer");
        db.begin();
        db.set("k", "f", "inner");
        db.delete("k", "f");
        db.rollback();
        check(db.get("k", "f").equals(Optional.of("outer")), "inner rollback returns to outer value");
        db.commit();
        check(db.get("k", "f").equals(Optional.of("outer")), "outer commit is permanent");
    }

    static void level4_rollbackRestoresTtl() {
        var db = new InMemoryDatabase();
        db.setAtWithTtl("k", "f", "short", 0, 10);
        db.begin();
        db.setAt("k", "f", "forever", 5);
        db.rollback();
        check(db.getAt("k", "f", 9).equals(Optional.of("short")), "old value back");
        check(db.getAt("k", "f", 10).isEmpty(), "old ttl back");
    }

    static void level4_commitWithoutBeginFails() {
        var db = new InMemoryDatabase();
        expectThrows(IllegalStateException.class, db::commit);
        expectThrows(IllegalStateException.class, db::rollback);
    }

    // ---------- tiny assertion helpers ----------

    static void check(boolean condition, String message) {
        if (!condition) {
            throw new AssertionError(message);
        }
    }

    static void expectThrows(Class<? extends Throwable> expected, Runnable action) {
        try {
            action.run();
        } catch (Throwable t) {
            if (expected.isInstance(t)) {
                return;
            }
            throw new AssertionError("expected " + expected.getSimpleName() + " but got " + t);
        }
        throw new AssertionError("expected " + expected.getSimpleName() + " but nothing was thrown");
    }
}