Design an in-memory database
Company: OpenAI
Role: Machine Learning Engineer
Category: System Design
Difficulty: hard
Interview Round: Technical Screen
Design an in-memory key–value database for ultra–low latency reads and writes.
Functional requirements:
- Commands: SET(key, value[, ttl]), GET(key), DELETE(key), MGET(keys), SCAN(prefix, limit, cursor).
- Optional transactions with snapshot isolation (MULTI/EXEC) and atomic increments.
- TTL with automatic expiration; optional pub/sub on key changes.
Non-functional requirements:
- Per-node: 50k ops/s; 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 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.
Quick Answer: Design an in-memory database evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.