Skip to main content
abstractalgorithms.dev
← PROBLEMS / SYSTEM-DESIGN
A system design interview walkthrough

Design a High-Concurrency LRU
& W-TinyLFU Cache.

A classic HashMap + Doubly Linked List LRU serializes every read behind a global write lock; sharding and batched promotion restore multi-core scalability.
Start the walkthrough30 min · 8 RESHADED stages
EDGELOGICSTORESYSTEM-DESIGN
REQUIREMENTS. ARCHITECTURE. SCALE.
Difficulty: mediumFocus: lru-doubly-linked-list-hashmap, sharded-lock-stripingFramework: RESHADED 8-step guide
Less boilerplate. More understanding.
01 Learn the idea02 Follow the visual03 Know the limits
RESHADEDRequirements → Estimation → Storage → High-level design → API → Detailed design → Evaluation → Discussion.
R

Define the boundaries.

Requirements · 4 minutes
SAY THIS: “Before proposing a topology for Design a High-Concurrency LRU & W-TinyLFU Cache, I’ll clarify the core functional requirements, burst characteristics, data volume, and availability SLOs to define rigid system boundaries.”
Every get() hit must mutate prev/next pointers to move the node to MRU, requiring an exclusive write lock on 100% of cache hits.

What the system does

  • Deliver O(1) amortized get(key) and put(key, val, ttl) with >1,200,000 ops/sec across 64 cores.
  • Eliminate global write-lock contention on the 95% read path.
  • Support bounded memory capacity (max_entries or max_bytes) and active/lazy TTL expiration.
  • Prevent sequential scans (e.g., 100k one-hit keys) from evicting hot working-set entries.

What to agree on

  • Maximum cache memory budget is 8 GB (~800 bytes/entry average for 10M entries).
  • Must run in-process with zero external network calls.
  • p99 get() latency must stay under 50 microseconds.
E

Size the critical path.

Estimation · 3 minutes
SAY THIS: “Let’s establish order-of-magnitude sizing for peak throughput, memory footprint, and network ingress to size the critical latency path before making technology choices.”
100k+PEAK THROUGHPUT
≤ 10 msP99 LATENCY TARGET
10M+SCALE TARGET

At an illustrative 200 bytes per record/session, high-volume state requires dedicated primary in-memory partitions. Add replicas, allocator overhead, policy indexes, and headroom.

throughput = peak_qps × (1 + headroom_margin) state_ram ≈ active_entities × per_record_bytes × replication_factor

Always validate throughput and p99 latency targets under skewed traffic distributions and replica failovers.

S

Keep state shared and partitioned.

Storage · 3 minutes
SAY THIS: “I’ll separate low-latency ephemeral cache state from authoritative durable storage, ensuring strict consistency where needed and partitioning for scale.”

Cache / Ephemeral state

state:{partitionKey}:activeWindow

  • In-memory key-value cache (Redis Cluster / Memcached).
  • TTL expiration matching window validity bounds.
  • Hash tags to co-locate keys for atomic Lua scripts or transactions.

Durable / Authoritative store

  • Distributed NoSQL / relational database (DynamoDB, PostgreSQL).
  • Durable write-ahead log with replica failover.
  • Cache-aside pattern: read misses warm cache from durable store.
  • Asynchronous CDC / event streaming to telemetry sinks.

Local-only node state is not a shared cluster quota: N nodes could admit roughly N × the configured limits. Ensure state co-location and transactional boundaries align with partition keys.

H

Make the decision at ingress.

High-level design · 4 minutes
SAY THIS: “The gateway tier authenticates incoming traffic, validates payloads, and routes requests to decoupled services backed by partitioned caching and authoritative storage tiers.”
Partition 10M capacity across 64 independent ReentrantLock-guarded LinkedHashMap(cap, 0.75f, true) shards with bit-mixed key hashes.

Use tight timeouts, circuit breakers, and rate-limiting middleware at ingress to protect downstream services from cascading collapse.

A

Define the contract.

API · 3 minutes
SAY THIS: “The API contract establishes idempotent mutation semantics, clear error taxonomy, and explicit status codes so upstream clients can safely retry.”
execute(requestId, payload, idempotencyKey) → { status, resourceId, metadata }

Success Path

Forward the request or return HTTP 200/201. Include standard tracking and rate/quota telemetry headers in the response.

Failure & Fallback

Use explicit HTTP status codes: 400 for invalid input, 429 for quota violations, and 503 with Retry-After during maintenance or partitions.

View example API payload contract
HTTP · APPLICATION CONTRACT
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: max-age=300

{
  "status": "success",
  "data": { "id": "res_98a7f", "processedAt": "2026-11-11T12:00:00Z" }
}

Include idempotency keys on write endpoints to guarantee at-most-once processing across network retries.

D

Make state mutations atomic.

Detailed design · 7 minutes
SAY THIS: “For the critical execution path, we enforce idempotency and concurrency controls using atomic primitives, avoiding lock contention and split-brain states.”
  1. Mix key.hashCode() with h ^ (h >>> 16) to avoid power-of-2 modulo clustering.
  2. Store (value, expireAtNanos) in each entry and evict expired entries lazily on get() + via removeEldestEntry.
STRATEGY / PATTERNWHY CHOOSE IT?TRADE-OFF / COST
Pattern 1Caffeine W-TinyLFU with StripedBuffer.Coordinate partition dependencies
View reference production code implementation
JAVA · REFERENCE IMPLEMENTATION
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class ShardedLruCache<K, V> {
    private static final class Entry<V> {
        final V value;
        final long expireAtNanos;
        Entry(V v, long exp) { this.value = v; this.expireAtNanos = exp; }
    }

    private static final class Shard<K, V> {
        final ReentrantLock lock = new ReentrantLock();
        final LinkedHashMap<K, Entry<V>> map;
        Shard(int maxEntries) {
            this.map = new LinkedHashMap<>(16, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, Entry<V>> eldest) {
                    return size() > maxEntries;
                }
            };
        }
    }

    private final Shard<K, V>[] shards;
    private final int mask;

    @SuppressWarnings("unchecked")
    public ShardedLruCache(int totalCapacity, int numShardsPowerOf2) {
        this.shards = new Shard[numShardsPowerOf2];
        this.mask = numShardsPowerOf2 - 1;
        int perShard = Math.max(1, totalCapacity / numShardsPowerOf2);
        for (int i = 0; i < numShardsPowerOf2; i++) shards[i] = new Shard<>(perShard);
    }

    private Shard<K, V> shardFor(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);
        return shards[h & mask];
    }

    public V get(K key) {
        Shard<K, V> s = shardFor(key);
        s.lock.lock();
        try {
            Entry<V> e = s.map.get(key);
            if (e == null) return null;
            if (System.nanoTime() > e.expireAtNanos) {
                s.map.remove(key);
                return null;
            }
            return e.value;
        } finally {
            s.lock.unlock();
        }
    }

    public void put(K key, V value, long ttlNanos) {
        Shard<K, V> s = shardFor(key);
        s.lock.lock();
        try {
            s.map.put(key, new Entry<>(value, System.nanoTime() + ttlNanos));
        } finally {
            s.lock.unlock();
        }
    }
}

Avoid client-side read-modify-write loops without concurrency control. Use atomic scripts, row-level locks, or conditional mutations at the storage tier to guarantee linearizability.

E

Stress-test the design.

Evaluation · 6 minutes
SAY THIS: “The biggest operational risks involve node failover, partition skew, network isolation, and cascading downstream backpressure. Here is how we mitigate each.”
Architectural Trade-Off

Checking if (!node.visited) node.visited = true; avoids even dirtying the CPU cache line on repeated hot-key reads.

Operational Hazard

Forgetting to periodically halve CMS counters lets historically hot keys permanently block new hot keys.

D

Close with the trade-offs.

Discussion · 5 minutes
SAY THIS: “In closing, we optimized for sub-millisecond p99 latency and high availability under partition. We trade strict distributed linearizability for predictable throughput and operational simplicity.”

If the interviewer asks…

  • “Need stronger consistency?” Introduce synchronous consensus or linearizable leases; accept higher tail latency.
  • “Need lower cross-region latency?” Route reads to local replicas with asynchronous replication; accept bounded staleness.

Keep the conclusion focused

  • What guarantees are strictly enforced at runtime?
  • What happens during network partitions or node failures?
  • Which CAP trade-off was intentionally chosen and why?
The 30-second summary

A classic HashMap + Doubly Linked List LRU serializes every read behind a global write lock; sharding and batched promotion restore multi-core scalability.

“Achieve O(1) operations at 1M+ ops/sec across 64 cores by sharding into 64+ segments or using read-ring-buffer deferred promotion with W-TinyLFU scan resistance.”

Interactive knowledge check

ACID Transaction Fundamentals: fundamentals

When is ACID Transaction Fundamentals the right default for a production team?

Recommended Practice Flow← All Problems Catalog