Design an in-memory database

Q: Design an in-memory database

This is a System Design interview question from OpenAI for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

Question

System Design: In-Memory Key–Value Database for Ultra–Low Latency

Context

You are designing an in-memory, per-node key–value database optimized for ultra–low-latency reads and writes. It must support point lookups, prefix scans, TTLs with automatic expiration, optional transactions with snapshot isolation, and high availability with specified durability targets.

Functional Requirements

Commands:
- SET(key, value[, ttl])
- GET(key)
- DELETE(key)
- MGET(keys)
- SCAN(prefix, limit, cursor)
Optional:
- Transactions with snapshot isolation (MULTI/EXEC)
- Atomic increments (e.g., INCRBY)
- Pub/Sub notifications on key changes

Non-Functional Requirements

Per-node throughput: 50k ops/s
Latency: p99 GET < 2 ms; p99 SET < 5 ms
Availability: 99.99%
Durability targets:
- RPO ≤ 1 s
- RTO ≤ 60 s on crash/restart

Sub-Questions

(a) Choose core data structures (e.g., hash table for point lookups, radix/ART or skip list for prefix scans). Explain complexity, memory overhead, and cache behavior.

(b) Provide durability: write-ahead log (WAL) and periodic snapshots; fsync policy, log compaction, and exact crash-recovery steps.

(c) Scale out: sharding via consistent hashing, leader–follower replication, read replicas, client routing, and failover. State the consistency model and how to achieve it.

(d) Manage memory: allocator strategy, fragmentation control, TTL wheel/timer, and eviction (LRU/LFU) when a memory cap is reached.

(e) Concurrency model: single-threaded event loop vs. multi-threaded; locking, batching, and pipelining trade-offs.

(f) Operations: metrics/slowlog, backups, online config changes, and capacity planning for 100M keys (avg value 200 B) with 64 GB RAM per node.