In-memory database design

Overview

Designing an in-memory key-value database (a mini Redis) tests data structures, command handling, and transactions. Typical requirements: SET, GET, DELETE, COUNT of keys with a given value, TTL expiry, and nested transactions with BEGIN, ROLLBACK, and COMMIT. Some variants add tables with columns, indexes, and simple queries.

Key design choices: a main hash map for data, a secondary index (value to count or set of keys) for fast COUNT queries, a stack of change logs or overlay maps for nested transactions, a min-heap or lazy checks for TTL, and a command parser mapping commands to handlers (Command pattern). Thread safety and persistence (append-only log, snapshots) are follow-ups.

When to use it

• Interview prompt: 'Design an in-memory key-value store with transactions'.
• Understanding Redis-like systems.
• Machine-coding rounds focused on correctness.

Where it shows up in interviews

Where it is used in real software

Key terms

Primary store

key -> value hash map.

Secondary index

value -> count (or key set) for queries by value.

Undo log

Previous values recorded per transaction to roll back.

Nested transactions

Stack of transaction scopes; rollback affects only the innermost.

Lazy expiration

Expired keys removed when accessed, plus periodic sweeps.

How it works, step by step

1. 1
   Store data

   Map<String, String> for key-value.

2. 2
   Maintain a value-count index

   Update on every set and delete.

3. 3
   Transactions via undo logs

   On first change of a key in a transaction, record its previous value.

4. 4
   ROLLBACK

   Restore previous values from the top log and pop it.

5. 5
   COMMIT

   Clear all logs (changes are already applied).

Command session

Starting empty

Undo logs make GET and COUNT O(1) inside transactions, and rollback costs only the number of keys changed.

Implementation

1class InMemoryDb {2  private data = new Map<string, string>();3  private valueCounts = new Map<string, number>();4  private txLogs: Map<string, string | undefined>[] = []; // stack of undo logs5 6  set(key: string, value: string) { this.record(key); this.write(key, value); }7  delete(key: string) { if (this.data.has(key)) { this.record(key); this.write(key, undefined); } }8  get(key: string) { return this.data.get(key) ?? "NULL"; }9  count(value: string) { return this.valueCounts.get(value) ?? 0; }10 11  begin() { this.txLogs.push(new Map()); }12 13  rollback() {14    const log = this.txLogs.pop();15    if (!log) return "NO TRANSACTION";16    for (const [key, prev] of log) this.write(key, prev);17    return "OK";18  }19 20  commit() {21    if (!this.txLogs.length) return "NO TRANSACTION";22    this.txLogs = [];                                     // changes already applied23    return "OK";24  }25 26  private record(key: string) {27    const log = this.txLogs.at(-1);28    if (log && !log.has(key)) log.set(key, this.data.get(key)); // first change in this tx only29  }30 31  private write(key: string, value: string | undefined) {32    const old = this.data.get(key);33    if (old !== undefined) this.valueCounts.set(old, this.valueCounts.get(old)! - 1);34    if (value === undefined) this.data.delete(key);35    else { this.data.set(key, value); this.valueCounts.set(value, (this.valueCounts.get(value) ?? 0) + 1); }36  }37}38 39// Command parser (Command pattern style dispatch)40function execute(db: InMemoryDb, line: string): string {41  const [cmd, a, b] = line.trim().split(/\s+/);42  switch (cmd.toUpperCase()) {43    case "SET": db.set(a, b); return "";44    case "GET": return db.get(a);45    case "DELETE": db.delete(a); return "";46    case "COUNT": return String(db.count(a));47    case "BEGIN": db.begin(); return "";48    case "ROLLBACK": return db.rollback();49    case "COMMIT": return db.commit();50    default: return "UNKNOWN COMMAND";51  }52}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Recording the previous value on every change in a transaction.

  Fix: Record only the first change per key per transaction.

• Forgetting to update the COUNT index on delete or overwrite.

  Fix: Centralize writes in one method.

• Scanning all values for COUNT.

  Fix: Maintain a value-count index.

Interview questions

Practice problems