This question evaluates a candidate's skills in single-node cache design, including in-memory key/value storage, eviction policy management (e.g., LRU), durability considerations, concurrency control, and techniques for reducing contention such as sharding or striping.
## Scenario
Design a **single-machine** cache used by a web service to handle read/write requests.
The cache should:
- Store key/value pairs in memory (fast reads)
- Support typical operations: `Get(key)`, `Put(key, value)`, `Delete(key)`
- Enforce an eviction policy such as **LRU** when memory capacity is reached
- Optionally provide **durability** so that after a process crash/restart, the cache can recover its contents
The interviewer expects:
- A concrete design with data structures
- Pseudocode-level APIs and key internal logic
- Discussion of concurrency (locks), minimizing critical sections, avoiding deadlocks
- How to scale on a single machine (e.g., sharding/striping to reduce lock contention)
Overview: This question evaluates a candidate's skills in single-node cache design, including in-memory key/value storage, eviction policy management (e.g., LRU), durability considerations, concurrency control, and techniques for reducing contention such as sharding or striping.
Design a single-machine in-memory cache used by a web service to serve concurrent read and write requests. This is a deliberately low-level system design question (closer to "implement the cache" than "draw boxes for a distributed system"): the interviewer wants concrete data structures, pseudocode-level APIs, and detailed reasoning about locks.
The cache should:
Store key/value pairs
in memory
for fast reads.
Support the typical operations
Get(key)
,
Put(key, value)
, and
Delete(key)
.
Enforce an
eviction policy
(e.g.
LRU
) when the configured memory capacity is reached.
Optionally provide
durability
, so that after a process crash or restart the cache can recover its contents.
Produce a concrete design: name the data structures, sketch the operations as pseudocode, reason explicitly about concurrency (which locks are held, how to keep critical sections small, how to avoid deadlock), and explain how the design scales across the cores of a single machine.
Constraints & Assumptions
Single process, many worker threads.
The web service's request handlers all hit the cache concurrently; the design must scale with cores on one box (no second machine).
Latency:Get
/
Put
/
Delete
should be roughly
O(1)
and must never block on disk I/O inside a critical section.
Bounded memory:
enforce a hard capacity. Assume the cap is by
byte count
(values are variable-sized) — an entry-count cap is the trivial special case.
Per-key consistency:
a
Get
ordered after a successful
Put
/
Delete
on the same key observes that write. No cross-key transactions are in scope.
Durability is optional / configurable
, not always-on. When enabled, "recover contents after restart" is the goal; the strength (lose-nothing vs. lose-last-few-ms) is a knob to discuss, not a fixed requirement.
Clarifying Questions to Ask Guidance
What does the
capacity cap
measure — number of entries, or total bytes (keys + values + overhead)?
How
strong
must durability be:
fsync
-before-ack (survive OS / power loss) or best-effort async flush (may lose the last few milliseconds)?
Is
exact
LRU required, or is approximate recency (e.g. CLOCK / sampled LRU) acceptable in exchange for cheaper reads?
What are the
value semantics
— immutable blobs, or mutable? (This decides whether a reader can hold a reference while another thread evicts the entry.)
Is the read/write mix
read-heavy
? (Read-heavy traffic changes whether it's worth optimizing the read path's locking.)
Are any
multi-key atomic operations
in scope (e.g. an atomic multi-
Put
), or is every operation single-key?
What a Strong Answer Covers Guidance
A strong answer treats this as an implementation problem and goes deep on the following dimensions:
Core data structure:
the
O(1)
LRU built from a hash map plus an intrusive doubly linked list, with a clear justification for why the list must be
doubly
linked and why the node stores its own key.
Operation pseudocode:
correct
Get
/
Put
/
Delete
/ eviction logic, including byte-accurate capacity accounting (a
Put
that updates an existing key adjusts by the
delta
).
Concurrency model:
progression from a naive global lock to
sharded / striped
locking; quantitative intuition for why striping helps; and the explicit tradeoff that sharding gives up
global
LRU for
per-shard
LRU.
Critical-section discipline:
keeping the locked region to pure pointer surgery, doing allocation / hashing / disk I/O outside the lock, and the read-path nuance that
Get
mutates recency.
Deadlock reasoning:
why single-key ops can't deadlock, and the invariant (single lock per op, or a strict global lock-acquisition order) for any multi-lock operation — the interviewer will probe this hard.
Durability:
a WAL with self-describing, corruption-detecting records; sync vs. async commit modes; a recovery procedure; and snapshots / compaction to bound log growth. The subtle correctness point — log order must match in-memory apply order per key — earns strong signal.
Edge cases & bottlenecks:
a single value larger than a shard's cap, use-after-free when a read races an eviction, hot keys concentrated in one shard, and the read-vs-recency tradeoff.
Follow-up Questions Guidance
The interviewer asks you to
eyeball a potential deadlock
in a multi-key operation. What invariant guarantees deadlock freedom, and how would you enforce it across all code paths?
"Can the critical section be made even smaller?" — for the
Get
path that mutates recency, what specifically can you move outside the lock, and what must stay inside?
How do you take a
snapshot without freezing the entire cache
, and why is a per-shard "fuzzy" snapshot still correct given concurrent writes?
If you log evictions to the WAL vs. not logging them, how does recovered state differ — and which would you choose for this cache?