In-Memory LRU Cache — System Design Academy

Complete System Design Tutorial

The design separates the latency-sensitive online path, the correctness-critical durable transition, and asynchronous projection or repair work. Each chapter below explains one decision shown in the diagrams.

1. Requirements and scope

Functional requirements

Execute the primary in-memory lru cache workflow and return an observable result.
Expose the concrete operations shown below with stable retry identities.
Allow operators to inspect, disable, repair, or replay ambiguous state.
Keep derived analytics and notifications off the correctness-critical path.

Non-functional requirements

Design for Millions ops/s · bounded entries · thread-safe option.
Protect the named business invariant under concurrency and partial failure.
Scale by an explicit aggregate/partition key without one global mutex.
Degrade intentionally when cache, queue, store, or regional ownership is unavailable.

Primary invariant: every object transition is legal and atomic at one aggregate boundary.

↑ top

2. Capacity assumptions

State assumptions before choosing technology. The supplied workload is Millions ops/s · bounded entries · thread-safe option. Convert it into peak throughput, retained records, bandwidth, and failure budget; then connect each number to a component.

Dimension	Working estimate	Design implication
Traffic	Millions ops/s · bounded entries · thread-safe option	Separate online compute, durable state, and asynchronous consumers.
Peak factor	5–10× average	Admission control, autoscaling headroom, and hot-key protection.
Stored state	write rate × retention × record bytes	Partition count, indexes, compaction, backup, and archival tier.
Network	peak operations × payload size	Batching, compression, edge placement, and egress budget.
Availability	99.9–99.99%	Multi-zone replicas, tested failover, and dependency error budgets.
Recovery	RPO/RTO by invariant	Ack boundary, replay retention, reconciliation, and operator runbooks.

Do not cargo-cult the numbers: show the arithmetic, name the uncertain variable, and say which production metric will replace the interview estimate.

↑ top

3. API and data model

get(key) → value/miss

put(key,value,ttl) → prior/evictions

compute_if_absent(key,loader)

invalidate(key) / resize(capacity)

Authoritative records and indexes

Node(key, value, weight, expires_at, prev, next)

Map<key, Node> for O(1) lookup

List head=MRU, tail=LRU

InFlight<key, promise> for loader coalescing

Command and event envelopes

# Command envelope
operation: get(key) → value/miss
request_id: req_01J...
idempotency_key: idem_7f2...
aggregate_key: lru-cache_123
expected_version: 17
payload: {...}

# Durable event
event_id: evt_01J...
aggregate_key: lru-cache_123
event_type: lru_cache_committed
schema_version: 3
trace_id: tr_8ac...

The authoritative aggregate and idempotency record share a transactional or conditional-write boundary. Event streams, search indexes, caches, analytics, and dashboards are rebuildable projections.

↑ top

4. Why this architecture and what it costs

The boxes are not a shopping list. Each boundary exists because it owns a different invariant, scaling dimension, data lifecycle, security policy, or failure domain. The table makes those choices explicit and shows when the design should remain simpler.

Component	Owned responsibility	Why separate it	Rejected alternative	Cost and evolution trigger
Cache Caller	Serves a low-latency, disposable projection with authoritative fallback. In this design it participates in: Under one consistency boundary, find node in hash map.	Removes repeated work from the latency-critical path. It prevents the external caller from also owning the contract and failure behavior of Cache API.	Read authoritative storage for every request. Simpler initially, but latency and source-of-truth load scale together and a hot key becomes a database incident. Here that simpler choice would couple “TTL heap contains stale update entries” to the external caller.	Costs invalidation, staleness, stampede protection, and memory. Add or split it only after the workload (Millions ops/s · bounded entries · thread-safe option) proves repeated reads dominate. Measure the latency, saturation, lag, or mismatch at the Cache Caller boundary before extracting or scaling it.
Cache API	Owns authentication, validation, quotas, deadlines, and routing. In this design it participates in: If expired remove map/list/weight and return miss; otherwise move node to MRU.	Removes repeated work from the latency-critical path. It prevents Cache Caller from also owning the contract and failure behavior of Key Hash Map.	Read authoritative storage for every request. Simpler initially, but latency and source-of-truth load scale together and a hot key becomes a database incident. Here that simpler choice would couple “Eviction callback reenters cache” to Cache Caller.	Costs invalidation, staleness, stampede protection, and memory. Add or split it only after the workload (Millions ops/s · bounded entries · thread-safe option) proves repeated reads dominate. Measure the latency, saturation, lag, or mismatch at the Cache API boundary before extracting or scaling it.
Key Hash Map	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Put updates or inserts node, updates total weight, and links at head.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Cache API from also owning the contract and failure behavior of Entry Node.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Large value evicts entire working set” to Cache API.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Key Hash Map boundary before extracting or scaling it.
Entry Node	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Evict from tail until entry/byte capacity holds; notify outside the lock.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Key Hash Map from also owning the contract and failure behavior of Doubly Linked List.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Concurrent get races remove” to Key Hash Map.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Entry Node boundary before extracting or scaling it.
Doubly Linked List	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: compute_if_absent registers one in-flight loader so concurrent misses share result.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Entry Node from also owning the contract and failure behavior of Head / MRU.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Loader fails while callers wait” to Entry Node.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Doubly Linked List boundary before extracting or scaling it.
Head / MRU	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Under one consistency boundary, find node in hash map.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Doubly Linked List from also owning the contract and failure behavior of Tail / LRU.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “TTL heap contains stale update entries” to Doubly Linked List.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Head / MRU boundary before extracting or scaling it.
Tail / LRU	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: If expired remove map/list/weight and return miss; otherwise move node to MRU.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Head / MRU from also owning the contract and failure behavior of Capacity Accountant.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Eviction callback reenters cache” to Head / MRU.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Tail / LRU boundary before extracting or scaling it.
Capacity Accountant	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Put updates or inserts node, updates total weight, and links at head.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Tail / LRU from also owning the contract and failure behavior of TTL Min-Heap.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Large value evicts entire working set” to Tail / LRU.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Capacity Accountant boundary before extracting or scaling it.
TTL Min-Heap	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Evict from tail until entry/byte capacity holds; notify outside the lock.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Capacity Accountant from also owning the contract and failure behavior of Expiry Sweeper.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Concurrent get races remove” to Capacity Accountant.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the TTL Min-Heap boundary before extracting or scaling it.
Expiry Sweeper	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: compute_if_absent registers one in-flight loader so concurrent misses share result.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents TTL Min-Heap from also owning the contract and failure behavior of Loader Coalescer.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Loader fails while callers wait” to TTL Min-Heap.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Expiry Sweeper boundary before extracting or scaling it.
Loader Coalescer	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Under one consistency boundary, find node in hash map.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Expiry Sweeper from also owning the contract and failure behavior of Concurrency Lock.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “TTL heap contains stale update entries” to Expiry Sweeper.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Loader Coalescer boundary before extracting or scaling it.
Concurrency Lock	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: If expired remove map/list/weight and return miss; otherwise move node to MRU.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Loader Coalescer from also owning the contract and failure behavior of Eviction Listener.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Eviction callback reenters cache” to Loader Coalescer.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Concurrency Lock boundary before extracting or scaling it.
Eviction Listener	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Put updates or inserts node, updates total weight, and links at head.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Concurrency Lock from also owning the contract and failure behavior of Hit / Miss Metrics.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Large value evicts entire working set” to Concurrency Lock.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Eviction Listener boundary before extracting or scaling it.
Hit / Miss Metrics	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Evict from tail until entry/byte capacity holds; notify outside the lock.	Proves correctness and supports controlled recovery. It prevents Eviction Listener from also owning the contract and failure behavior of operators and repair tooling.	Infer correctness from request logs. Logs do not prove durable business state, detect silent drift, or safely repair ambiguous outcomes. Here that simpler choice would couple “Concurrent get races remove” to Eviction Listener.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Hit / Miss Metrics boundary before extracting or scaling it.

Decision 01

Chosen boundary vs simpler monolith

Combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction are O(1).

A single deployable with one transactional store is the right starting point for a small in-memory lru cache workload. The proposed boundary becomes justified when combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction are o(1). Separating it contains the named failure “TTL heap contains stale update entries” without placing unrelated work on the critical path.

Decision 02

Correctness vs availability

Define capacity by entries or bytes; large values make entry-count limits misleading.

The design coordinates only where every object transition is legal and atomic at one aggregate boundary. Everywhere else it accepts bounded staleness or asynchronous propagation. The alternative—strong coordination for every projection—simplifies the mental model but increases tail latency and turns partitions into broad write unavailability.

Decision 03

Operational cost and evolution

For concurrency, choose one lock, segmented locks, or an admission policy; explain consistency of recency order.

This choice adds dashboards, ownership, schema compatibility, capacity planning, and recovery runbooks. Start with the minimum topology that supports “Put updates or inserts node, updates total weight, and links at head.” and extract another service only when measured throughput, blast radius, data lifecycle, or team ownership changes independently.

Why this design: the synchronous path contains only the decisions required to protect every object transition is legal and atomic at one aggregate boundary. Durable projections, notifications, indexing, analytics, and repair are isolated so their load or failure cannot corrupt the acknowledged operation.

Correctness boundary

Combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction are O(1).

Scale boundary

Define capacity by entries or bytes; large values make entry-count limits misleading.

Operational boundary

For concurrency, choose one lock, segmented locks, or an admission policy; explain consistency of recency order.

↑ top

5. Critical flow and algorithm

Under one consistency boundary, find node in hash map.

If expired remove map/list/weight and return miss; otherwise move node to MRU.

Put updates or inserts node, updates total weight, and links at head.

Evict from tail until entry/byte capacity holds; notify outside the lock.

compute_if_absent registers one in-flight loader so concurrent misses share result.

Retry-safe mutation skeleton

identity = authenticate(request)
prior = idempotency.get(identity, request.key)
if prior: return prior.result

current = authoritative_store.read(partition_key)
next_state, events = domain.transition(current, request)
authoritative_store.compare_and_set(current.version, next_state)
idempotency.commit(request.key, next_state.result)
outbox.append(events)
return next_state.result

Exactly-once business effect: the network can duplicate requests. Stable identities, conditional state transitions, immutable event IDs, and reconciliation make the user-visible effect happen once.

↑ top

6. Caching, hot keys, and backpressure

Cache policy

Cache immutable or slowly changing reads with versioned keys, TTL jitter, short negative entries, and request coalescing.

Hot partition or tenant

Measure per-key and per-tenant skew. Replicate safe reads, isolate the offender, salt only when ordering permits, and enforce budgets.

Backpressure

Bound queues, buffers, connection pools, and concurrency. Shed low-priority work and scale from lag/oldest-item age rather than CPU alone.

Stampede and retry storms

Use single-flight/coalescing, jittered expiry, bounded retries, exponential backoff, and circuit breakers so one dependency failure does not multiply traffic.

Cache outage rule: never allow every miss to fall through simultaneously. Use local protection, request coalescing, circuit breakers, bounded pools, and controlled fallback.

↑ top

7. Partitioning and consistency

partition = stable_hash(primary_or_aggregate_key) → shard owner
write = conditional_update(expected_version)
read_projection = versioned and rebuildable

Strong boundary

every object transition is legal and atomic at one aggregate boundary. Use a uniqueness constraint, serializable/conditional write, expected version, or fencing token at this boundary.

Eventual boundary

Analytics, notifications, search, read models, and operational dashboards may lag when freshness is observable and replay exists.

Operation	Consistency	Reason
Authoritative mutation	Conditional / serializable	Protect uniqueness, ownership, money, inventory, order, or legal state transition.
Read after own write	Primary, session token, or cache warm	The caller must observe the result it just committed.
Ordinary read projection	Bounded stale where safe	Replicas and caches improve latency when version/freshness is visible.
Analytics and operations	Eventual + replay	Freshness is less important than isolating the online path.

Route every mutation for one aggregate to one owner/partition epoch.
Use cursors rather than offsets for changing ordered collections.
Retain tombstones until replication and repair windows close.
Move shard ownership through versioned maps and dual-read verification.

↑ top

8. Failure drills and recovery

Failure	Runtime behavior	Recovery proof
TTL heap contains stale update entries	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Eviction callback reenters cache	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Large value evicts entire working set	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Concurrent get races remove	Resolve at source of truth with uniqueness, expected version, lease generation, or monotonic cursor.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Loader fails while callers wait	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.

Recovery checkpoint

# Recovery checkpoint
scenario: TTL heap contains stale update entries
operation_id: op_01J...
aggregate_key: lru-cache_123
last_durable_version: 18
projection_checkpoint: partition-07@offset-482901
retry_policy: same_identity / bounded_backoff
reconciliation_status: pending
owner: Hit / Miss Metrics

Every dependency needs a timeout, retry budget, circuit policy, and explicit fail-open, fail-closed, stale, or read-only mode. “Highly available” is incomplete until degraded behavior is named.

↑ top

9. Security, regions, and observability

Security and abuse

Authenticate at ingress and authorize the exact resource/tenant on every operation.
Encrypt transport and durable data; tokenize or isolate sensitive material.
Rate-limit by tenant, actor, resource, and network; detect enumeration and anomalous fan-out.
Redact secrets and personal data before logs or analytical storage.
Audit privileged mutations, support access, policy changes, and forced recovery.

Signals that prove correctness

User-visible success rate and p50/p95/p99 latency.
Timeouts, circuit state, saturation, and replica health by dependency.
Queue lag, oldest-item age, retries, and dead-letter growth.
Conflict, duplicate-suppression, and reconciliation mismatch counts.
Business drill: TTL heap contains stale update entries — alert before the user-visible invariant is violated.

Regional evolution

Begin multi-zone with tested failover, backups, and reconciliation.
Add global stateless ingress and regional read projections.
Keep one write owner per aggregate or partition where coordination is expensive.
Move ownership with epochs/fencing; avoid silent simultaneous writers.
Use expand/contract schemas, canaries, shadow reads, and reversible cutovers.

↑ top

10. Interviewer follow-ups

How do TTL and LRU interact?

Combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction are O(1). Walk the concrete lifecycle step “Under one consistency boundary, find node in hash map.” Then test it against “TTL heap contains stale update entries”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How do you make it thread-safe?

Define capacity by entries or bytes; large values make entry-count limits misleading. Walk the concrete lifecycle step “If expired remove map/list/weight and return miss; otherwise move node to MRU.” Then test it against “Eviction callback reenters cache”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How does LFU differ?

For concurrency, choose one lock, segmented locks, or an admission policy; explain consistency of recency order. Walk the concrete lifecycle step “Put updates or inserts node, updates total weight, and links at head.” Then test it against “Large value evicts entire working set”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How do cache loaders prevent stampedes?

Combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction are O(1). Walk the concrete lifecycle step “Evict from tail until entry/byte capacity holds; notify outside the lock.” Then test it against “Concurrent get races remove”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How do you bound by memory size?

Define capacity by entries or bytes; large values make entry-count limits misleading. Walk the concrete lifecycle step “compute_if_absent registers one in-flight loader so concurrent misses share result.” Then test it against “Loader fails while callers wait”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

Answer pattern: state the invariant, choose a mechanism, walk one failure, name the recovery signal, and explain the cost of the alternative.

↑ top

11. How to present this in 45 minutes

Time	What to cover
0–5 min	Clarify scope, workload, SLOs, and the correctness invariant.
5–10 min	Estimate throughput/storage and define concrete APIs and records.
10–20 min	Draw online, durable-write, and asynchronous/repair paths.
20–30 min	Explain the exact lifecycle, partition key, and concurrency control.
30–38 min	Discuss caching, hot keys, replication, and backpressure.
38–43 min	Run failure drills, security, observability, and regional evolution.
43–45 min	Summarize the five most important choices and trade-offs.

Final decision summary

Invariant	every object transition is legal and atomic at one aggregate boundary.
Partitioning	Stable aggregate/key hash with versioned ownership and measured hot-key isolation.
Commit	Expected version or uniqueness at the authoritative state boundary.
Async work	Durable outbox/log, idempotent consumers, checkpoints, and replay.
Recovery	Same operation identity, durable truth lookup, and business reconciliation.

Closing summary

CLOSING “The design protects every object transition is legal and atomic at one aggregate boundary. The online path stays bounded, authoritative state is versioned and partitioned, and asynchronous work is replayable and observable.”

↑ top

Cache Caller

Cache API

Key Hash Map

Entry Node

Complete System Design Tutorial

1. Requirements and scope

Functional requirements

Non-functional requirements

2. Capacity assumptions

3. API and data model

Authoritative records and indexes

Command and event envelopes

4. Why this architecture and what it costs

Chosen boundary vs simpler monolith

Correctness vs availability

Operational cost and evolution

5. Critical flow and algorithm

Retry-safe mutation skeleton

6. Caching, hot keys, and backpressure

7. Partitioning and consistency

Strong boundary

Eventual boundary

8. Failure drills and recovery

Recovery checkpoint

9. Security, regions, and observability

Security and abuse

Signals that prove correctness

Regional evolution

10. Interviewer follow-ups

11. How to present this in 45 minutes

Final decision summary

Closing summary