Katkat
Back

Design an in-memory database

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests the ability to architect a high-performance, in-memory key-value store, focusing on concurrency control, data structures, and durability guarantees.

Problem: In-Memory Key-Value Store

Design a lightweight, in-memory key-value database. Your system should support fast lookups, insertions, and deletions.

Functional Requirements

  • SET(key, value): Stores a value associated with a key.
  • GET(key): Returns the value for a key or null if it doesn't exist.
  • DELETE(key): Removes the key and its associated value.
  • EXPIRE(key, ttl): Sets a time-to-live for a key, after which it is automatically removed.

Non-Functional Requirements

  • Target latency: Sub-millisecond for basic CRUD operations.
  • Concurrency: Must handle multiple simultaneous read and write requests.
  • Durability: The system should periodically persist state to disk to survive crashes.

Assumptions

  • Dataset size: 10 million keys.
  • Average value size: 1 KB.
  • Workload: Read-heavy (90% reads, 10% writes).

Deliverables

  1. Propose the internal data structure for storing keys and values.
  2. Explain the strategy for handling thread safety while minimizing lock contention.
  3. Detail how the EXPIRE functionality is implemented efficiently.
  4. Propose a persistence mechanism that balances data loss risk vs. performance.

Hints

Hint 1

Consider using a Hash Map for O(1) average time complexity and explore reader-writer locks or lock-free data structures to handle concurrency.

Hint 2

For the TTL implementation, a priority queue or a sorted set (ordered by expiration time) can help efficiently identify which keys to clean up.

Hint 3

For durability, consider Write-Ahead Logging (WAL) or snapshotting, and discuss the trade-offs between background asynchronous persistence and blocking synchronous writes.

Follow-up questions

  • How would you scale this system horizontally to support a dataset that exceeds the memory capacity of a single machine?
  • If the system experiences a spike in `EXPIRE` events, how would you prevent the cleanup process from degrading the performance of incoming client requests?
  • How would you implement a 'Watch/Notify' mechanism that allows clients to subscribe to updates for a specific key?