Design a thread-safe key-value store
Company: Netflix
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
You are working on infrastructure for an AI platform. Inside a single process, many worker threads need to share a simple in-memory key–value store; any thread can concurrently read, write, or delete keys.
Design and discuss a thread-safe key–value store class with the following requirements:
- **Environment:** Single process, multiple threads (no multi-machine / distributed concerns).
- **Operations:**
- `put(key, value)`: insert or overwrite the value for `key`.
- `get(key)`: return the current value for `key`, or `null` / `None` if absent.
- `delete(key)`: remove `key` if it exists.
- **Correctness:**
- Operations must be safe under arbitrary concurrent usage (no lost updates, no corrupted internal state).
- Each operation should appear atomic to callers.
- **Performance:**
- Aim to minimize lock contention; a single global lock is allowed but you should consider and discuss alternatives.
- **Data model:**
- Keys can be assumed to be strings; values can be arbitrary objects (or generics).
Answer the following sub-questions:
1. What internal data structure(s) would you use to store the key–value pairs, and why?
2. What synchronization strategy would you apply (e.g., a single global lock, per-bucket or per-key locks, lock striping, or a language-provided concurrent map)? Discuss the trade-offs.
3. Suppose you must implement this in a language **without** a built-in concurrent map (for example, Python with a normal `dict`). How would you implement your chosen synchronization strategy there? Describe or sketch the implementation of `put`, `get`, and `delete`.
4. How would you test / validate that your implementation is correct and free from race conditions? Consider unit tests, concurrent stress tests, and any tools or techniques you might use.
5. If this store were to be used in production, what additional concerns would you consider (e.g., validation of inputs, logging, metrics, capacity limits, performance tuning, or persistence)?
Overview: This question evaluates knowledge of concurrent programming and thread-safety, including the choice of in-memory data structures for a key–value store and synchronization techniques that ensure atomic put/get/delete operations without internal corruption.
Community answers
Answer by todd.k.blake
Planning
A hashmap / dictionary is a logical choice for an in-memory key/value store as all operations are O(1) constant. Values as arbitrary objects / generics requires atomic overwrites and potentially setting a memory limit per value. If key sorting / traversal is required the data structure may need to change to enforce ordered keys or even linked lists (e.g. LRU cache)
A single global lock on any operation is easy, but quickly blocks unrelated keys. A lock on operations per key creates far less parallel lock contention, but increases the memory space of locks. A bucketed approach is a reasonable middle ground, keys as strings makes a hash -> bucket approach straightforward.
In Python, I would build a concurrent cache object, with a threading.Lock which is a thread-safe, process level lock. Based on (1) this would require either a single class level lock, a pool of "bucketed" locks for keyspaces, or a lock per key. I would implement a pool of locks as a starting place, with configurable number of locks. In order for this to remain process safe, this will need to be class state or I need a singleton instance shared by the entire process. For the lock pool, I'd need another small dictionary to store the "bucket" and each lock as a value. The bucket per key can be resolved using a simple hash and modulo by the lock count.
import os
class ConcurrentCache:
singleton = null
@classmethod
def new(cls):
if not cls.singleton:
cls.singleton = ConcurrentCache(lock_count = os.getenv("