In-Memory Key-Value Store

Requirements & System Scope

Functional Scope (In-Scope)

Basic Operations: Supports standard key-value map GET, SET, and DELETE methods.
Nested Transactions: Support BEGIN transactions inside parent operations recursively.
Read-Your-Writes Consistency: Operations inside an active transaction instantly perceive local dirty changes before committed values.
ACID Rollback Protection: ROLLBACK operations atomically discard all nested mutations, preserving global keys.

Explicit Boundaries (Out-of-Scope)

No Durable Disk Log Persistence: All mutations reside entirely in memory. Out-of-scope to manage write-ahead logs to local file systems.
No Range Queries / Custom Scans: The engine does not evaluate key prefix ranges or conditional sweeps.

Class Diagram & Entity Relationships

Structural layout showing clean isolation of transaction contexts, command logs, and memory stores:

Thread-Local Stack Configuration: InMemoryKVStore tracks active transaction paths using safe stacks, isolating operations cleanly.
Polymorphic Savepoint Pointers: Each Transaction keeps reference to its parent savepoint, forming a clean singly-linked hierarchical list.
Database Commands: Operations are cleanly encapsulated as PutCommand or DeleteCommand classes.

Design Patterns & SOLID Principles

Command Pattern (Database Actions): Encapsulates all modification operations (SET/DELETE) as command objects (PutCommand and DeleteCommand), standardizing how modifications are applied and propagated between active contexts.
Memento Pattern (Savepoint States): Each Transaction operates as an isolated memento, preserving its local buffer and deleted key lists, allowing instant rollback of actions by simply popping the transaction from the execution stack.
Single Responsibility Principle (SRP):Transaction is solely focused on active change sets. InMemoryKVStore coordinates global index commits.
Singly-Linked Stack List Pattern (Nested States): By maintaining hierarchical pointers (parent), transaction states form a clean stack that enables flat commits and savepoint evaluations effortlessly.

Core Execution Workflows

Transaction Life Cycle

Client invokes begin():
1. Create new Transaction instance passing top of stack as parent.
2. Push new instance to stack.
User invokes mutations: set(k, v) or delete(k):
1. Encapsulate action in a DatabaseCommand object.
2. If stack is empty, apply command directly to globalStore under a global lock.
3. Otherwise, apply command on the active transaction buffer.
User queries index: get(k):
1. Search active transaction local buffer, moving up parent hierarchy.
2. On mismatch, fallback to query global committed store under a global read lock.
User triggers commit():
1. Pop active transaction from stack.
2. If stack is now empty, flush all dirty local buffers and deletions directly to the global store under a global write lock.
3. Otherwise, propagate active transaction's deleted keys and put buffers down to the parent transaction using commands.

Concurrency & Thread Safety Strategy

In highly concurrent applications, multiple developer threads invoke keys mutations simultaneously. Without safety plans, commits collide:

Thread-Local Isolation: Wrap transaction stack allocations in Thread-Local variables (ThreadLocal<Stack<Transaction>>) to isolate execution contexts completely per-thread, ensuring uncommitted updates are strictly invisible to other threads.
Global Reentrant Read-Write Locks: Protect global store operations with a read-write lock, permitting high-throughput concurrent reads while serializing commits to maintain absolute global consistency.

Complete Clean Code Blueprint

Thread-safe reference implementations in Java and Python:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantReadWriteLock;

interface DatabaseCommand {
    void execute(Map<String, String> buffer, Set<String> deletes);
}

class PutCommand implements DatabaseCommand {
    private final String key;
    private final String value;

    public PutCommand(String key, String value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public void execute(Map<String, String> buffer, Set<String> deletes) {
        deletes.remove(key);
        buffer.put(key, value);
    }
}

class DeleteCommand implements DatabaseCommand {
    private final String key;

    public DeleteCommand(String key) {
        this.key = key;
    }

    @Override
    public void execute(Map<String, String> buffer, Set<String> deletes) {
        buffer.remove(key);
        deletes.add(key);
    }
}

class Transaction {
    private final Map<String, String> localBuffer = new HashMap<>();
    private final Set<String> deletedKeys = new HashSet<>();
    private final List<DatabaseCommand> commandHistory = new ArrayList<>();
    private final Transaction parent;

    public Transaction(Transaction parent) {
        this.parent = parent;
    }

    public Transaction getParent() { return parent; }
    public Map<String, String> getLocalBuffer() { return localBuffer; }
    public Set<String> getDeletedKeys() { return deletedKeys; }

    public void applyCommand(DatabaseCommand cmd) {
        cmd.execute(localBuffer, deletedKeys);
        commandHistory.add(cmd);
    }

    public String get(String key) {
        if (deletedKeys.contains(key)) return null;
        if (localBuffer.containsKey(key)) return localBuffer.get(key);
        if (parent != null) return parent.get(key);
        return null;
    }
}

class InMemoryKVStore {
    private final Map<String, String> globalStore = new ConcurrentHashMap<>();
    private final ThreadLocal<Stack<Transaction>> transactionStack = ThreadLocal.withInitial(Stack::new);
    private final ReentrantReadWriteLock globalLock = new ReentrantReadWriteLock();

    public void begin() {
        Stack<Transaction> stack = transactionStack.get();
        Transaction parent = stack.isEmpty() ? null : stack.peek();
        stack.push(new Transaction(parent));
        System.out.println("[Thread-" + Thread.currentThread().getId() + "] BEGIN Transaction. Stack depth: " + stack.size());
    }

    public void set(String key, String value) {
        DatabaseCommand cmd = new PutCommand(key, value);
        Stack<Transaction> stack = transactionStack.get();
        if (stack.isEmpty()) {
            globalLock.writeLock().lock();
            try {
                globalStore.put(key, value);
                System.out.println("[Thread-" + Thread.currentThread().getId() + "] Global SET: " + key + " = " + value);
            } finally {
                globalLock.writeLock().unlock();
            }
        } else {
            stack.peek().applyCommand(cmd);
            System.out.println("[Thread-" + Thread.currentThread().getId() + "] Transaction SET: " + key + " = " + value);
        }
    }

    public String get(String key) {
        Stack<Transaction> stack = transactionStack.get();
        if (!stack.isEmpty()) {
            Transaction activeTx = stack.peek();
            String val = activeTx.get(key);
            if (val != null || activeTx.getDeletedKeys().contains(key)) {
                return val;
            }
        }
        globalLock.readLock().lock();
        try {
            return globalStore.get(key);
        } finally {
            globalLock.readLock().unlock();
        }
    }

    public void delete(String key) {
        DatabaseCommand cmd = new DeleteCommand(key);
        Stack<Transaction> stack = transactionStack.get();
        if (stack.isEmpty()) {
            globalLock.writeLock().lock();
            try {
                globalStore.remove(key);
                System.out.println("[Thread-" + Thread.currentThread().getId() + "] Global DELETE: " + key);
            } finally {
                globalLock.writeLock().unlock();
            }
        } else {
            stack.peek().applyCommand(cmd);
            System.out.println("[Thread-" + Thread.currentThread().getId() + "] Transaction DELETE: " + key);
        }
    }

    public void commit() {
        Stack<Transaction> stack = transactionStack.get();
        if (stack.isEmpty()) {
            throw new IllegalStateException("No active transaction to commit");
        }
        Transaction activeTx = stack.pop();
        if (stack.isEmpty()) {
            globalLock.writeLock().lock();
            try {
                for (String key : activeTx.getDeletedKeys()) {
                    globalStore.remove(key);
                }
                globalStore.putAll(activeTx.getLocalBuffer());
                System.out.println("[Thread-" + Thread.currentThread().getId() + "] Transaction committed to global store.");
            } finally {
                globalLock.writeLock().unlock();
            }
        } else {
            Transaction parent = stack.peek();
            for (String key : activeTx.getDeletedKeys()) {
                parent.applyCommand(new DeleteCommand(key));
            }
            for (Map.Entry<String, String> entry : activeTx.getLocalBuffer().entrySet()) {
                parent.applyCommand(new PutCommand(entry.getKey(), entry.getValue()));
            }
            System.out.println("[Thread-" + Thread.currentThread().getId() + "] Transaction committed to parent context.");
        }
    }

    public void rollback() {
        Stack<Transaction> stack = transactionStack.get();
        if (stack.isEmpty()) {
            throw new IllegalStateException("No active transaction to rollback");
        }
        stack.pop();
        System.out.println("[Thread-" + Thread.currentThread().getId() + "] Transaction rolled back.");
    }
}

public class InMemoryKVStoreDriver {
    public static void main(String[] args) throws Exception {
        System.out.println("=== IN-MEMORY KEY-VALUE STORE DRIVER ===");
        InMemoryKVStore store = new InMemoryKVStore();

        // 1. Basic Global Operations
        store.set("a", "100");
        System.out.println("Global GET a: " + store.get("a"));

        // 2. Transaction isolation and nested rollback test
        store.begin();
        store.set("a", "200");
        store.set("b", "300");
        System.out.println("Tx GET a: " + store.get("a")); // 200 (dirty read)
        System.out.println("Tx GET b: " + store.get("b")); // 300

        store.begin();
        store.set("b", "400");
        System.out.println("Nested Tx GET b: " + store.get("b")); // 400

        store.rollback(); // Rollback nested transaction
        System.out.println("Post-rollback Tx GET b: " + store.get("b")); // 300 (restored parent state)

        store.commit(); // Commit main transaction
        System.out.println("Post-commit Global GET a: " + store.get("a")); // 200
        System.out.println("Post-commit Global GET b: " + store.get("b")); // 300

        // 3. Multi-threaded isolation demonstration
        System.out.println("\n--- Concurrent Thread Isolation Simulation ---");
        Thread thread1 = new Thread(() -> {
            store.begin();
            store.set("threadLocalKey", "val1");
            System.out.println("Thread-1 Local GET: " + store.get("threadLocalKey"));
            try { Thread.sleep(100); } catch (InterruptedException e) {}
            store.rollback();
            System.out.println("Thread-1 Post-rollback Local GET: " + store.get("threadLocalKey")); // null
        });

        Thread thread2 = new Thread(() -> {
            store.begin();
            store.set("threadLocalKey", "val2");
            System.out.println("Thread-2 Local GET: " + store.get("threadLocalKey"));
            try { Thread.sleep(200); } catch (InterruptedException e) {}
            store.commit();
            System.out.println("Thread-2 Post-commit Global GET: " + store.get("threadLocalKey")); // val2
        });

        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();

        System.out.println("Global Final GET threadLocalKey: " + store.get("threadLocalKey")); // val2
    }
}

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...

✦Requirements & System Scope

Functional Scope (In-Scope)

Explicit Boundaries (Out-of-Scope)

◫Class Diagram & Entity Relationships

⬡Design Patterns & SOLID Principles

{ }Core Execution Workflows