Low-Level Design (LLD) of an Enterprise Concurrent Cache System
An enterprise-grade cache must do far more than store key-value pairs in memory using a basic Least Recently Used (LRU) algorithm. In high-throughput distributed systems, a cache serves as a front-line facade to a backing database, requiring robust write-propagation strategies, strict thread safety, generic typing, and predictable consistency guarantees. This document details the low-level design of a concurrent, decoupled, strategy-driven cache system capable of enforcing "Read-Your-Own-Writes" consistency through key-based thread affinity.
1. Problem Statement & Functional Requirements
In standard technical interviews, candidates are often asked to implement a basic in-memory LRU cache. However, production systems require handling concurrent operations, interacting with a persistent backing store, and configuring operational behavior dynamically.
Structure & Concept Flow
Functional Requirements
- Generic Key-Value Storage: The cache must support arbitrary types for keys (
K) and values (V) using Java Generics rather than hardcoded primitive types. - Core Operations: Support fast operations for
get(K key),put(K key, V value),remove(K key),containsKey(K key), andsize(). - Pluggable Eviction Policies: When capacity is reached, the cache must evict entries automatically based on an injected strategy (e.g., LRU - Least Recently Used, LFU - Least Frequently Used).
- Pluggable Write Policies: Support multiple write interaction models between the cache and a backing database store (Write-Through, Write-Back, Write-Around).
- Thread Safety & High Concurrency: The system must handle concurrent reads and writes safely without global lock contention.
- Read-Your-Own-Writes Consistency: Operations on the same key must execute sequentially to guarantee that a thread reading a key immediately after writing it receives the latest updated value, even across non-blocking asynchronous calls.
2. Deep Dive: Write Policies (Cache vs. Backing Database)
When a cache sits in front of a backing persistent database (DB), write operations must update both stores according to specific consistency requirements.
Structure & Concept Flow
Strategy Comparison
Conceptually: Write-Through is selected as the primary implementation strategy when data correctness is critical and data loss cannot be tolerated. Writes complete only when both the cache and persistent storage reflect the updated state.
3. Concurrency Challenge & Mental Model: "Read Your Own Writes"
The Race Condition Problem
In a highly concurrent multi-threaded environment where writes to the cache and backing DB are non-blocking or managed asynchronously, execution order can break causality:
Structure & Concept Flow
If write acknowledgments and updates are processed out-of-order across multiple threads, a client updating a key to Val_B after Val_A might read Val_A back—a severe consistency violation.
The Solution: Key-Based Thread Affinity
To enforce Read-Your-Own-Writes without locking the entire cache with global synchronization primitives (which destroys performance), we employ Key-Based Hashing & Routing.
Structure & Concept Flow
The Thread Affinity Mental Model
Think of key-based thread affinity like a dedicated service window at a bank:
- All transactions for a specific account number (the Key) are always handled by the exact same teller (Single-Thread Executor).
- Tellers work completely independently in parallel (handling different accounts simultaneously).
- Because a single teller processes account tasks sequentially from top to bottom, account updates and checks can never execute out of order.
JAVA
// Mathematical mapping of Key to Executor Index
int executorIndex = Math.abs(key.hashCode()) % totalExecutors;
4. Key Architectural Trade-offs & Scope Boundaries
Eviction Mechanics: Synchronous vs. Asynchronous Background Threads
Structure & Concept Flow
- Inline Synchronous Eviction: The thread performing the write handles eviction immediately if capacity is breached. Predictable memory limits are enforced, though write latency spikes slightly during eviction events.
- Background Thread Eviction: A background worker periodically cleans up evicted or expired entries. This keeps client write latency uniform, but introduces temporary memory spikes above maximum capacity.
Explicit Interview Scope Boundaries
During a standard 45-to-60-minute LLD interview, high-level distributed cache concerns should be identified and explicitly marked out-of-scope to focus on object-oriented correctness and multi-threading:
- Request Collapsing (Cache Stampede Prevention): Merging concurrent reads for an uncached key into a single DB query.
- Hot-Loading / Bootup Pre-warming: Pre-populating cache entries from persistent storage on startup.
- Offline Event Logging / Replication: Streaming write logs to secondary replicas.
5. Design Patterns & Class Architecture
The architecture heavily leverages the Strategy Pattern to cleanly decouple data access, write semantics, and eviction logic, adhering to the Single Responsibility and Open/Closed Design Principles.
Structure & Concept Flow
Component Breakdown
Cache<K, V>: The core orchestrator that exposes client-facing APIs and delegates execution to thread-affinity executors.CacheStorage<K, V>: Interface defining basic in-memory map access ( primitive storage).DatabaseStorage<K, V>: Interface abstracting persistent backing store interactions.EvictionPolicy<K>: Strategy interface managing eviction order metadata (keyAccessed,evictKey).WritePolicy<K, V>: Strategy interface controlling cache-to-DB write semantics.KeyBasedExecutor: Concurrency manager routing keys to single-threaded executors based on hash values.
6. Core Data Structures & Algorithmic Complexity
To achieve complexity for Least Recently Used (LRU) evictions, the system combines a Custom Doubly Linked List (DLL) with an In-Memory Hash Map.
Structure & Concept Flow
Mathematical Time & Space Complexity
7. Step-by-Step Production Code Implementation
Step 1: Storage Interfaces & Concrete Implementations
JAVA
package storage;
public interface CacheStorage<K, V> {
void put(K key, V value);
V get(K key);
void remove(K key);
boolean containsKey(K key);
int size();
int capacity();
}
JAVA
package storage;
import java.util.concurrent.ConcurrentHashMap;
public class InMemoryCacheStorage<K, V> implements CacheStorage<K, V> {
private final ConcurrentHashMap<K, V> map;
private final int capacity;
public InMemoryCacheStorage(int capacity) {
this.capacity = capacity;
this.map = new ConcurrentHashMap<>();
}
@Override
public void put(K key, V value) {
map.put(key, value);
}
@Override
public V get(K key) {
return map.get(key);
}
@Override
public void remove(K key) {
map.remove(key);
}
@Override
public boolean containsKey(K key) {
return map.containsKey(key);
}
@Override
public int size() {
return map.size();
}
@Override
public int capacity() {
return capacity;
}
}
JAVA
package storage;
import java.util.concurrent.ConcurrentHashMap;
public interface DatabaseStorage<K, V> {
void write(K key, V value);
V read(K key);
void delete(K key);
}
public class SimpleDatabaseStorage<K, V> implements DatabaseStorage<K, V> {
private final ConcurrentHashMap<K, V> dbMap = new ConcurrentHashMap<>();
@Override
public void write(K key, V value) {
dbMap.put(key, value);
}
@Override
public V read(K key) {
return dbMap.get(key);
}
@Override
public void delete(K key) {
dbMap.remove(key);
}
}
Step 2: Write Strategy Pattern
JAVA
package policy;
import storage.CacheStorage;
import storage.DatabaseStorage;
public interface WritePolicy<K, V> {
void write(K key, V value, CacheStorage<K, V> cacheStorage, DatabaseStorage<K, V> dbStorage);
}
JAVA
package policy;
import storage.CacheStorage;
import storage.DatabaseStorage;
import java.util.concurrent.CompletableFuture;
public class WriteThroughPolicy<K, V> implements WritePolicy<K, V> {
@Override
public void write(K key, V value, CacheStorage<K, V> cacheStorage, DatabaseStorage<K, V> dbStorage) {
// Execute writes to cache and DB, ensuring both complete before returning
CompletableFuture<Void> cacheWrite = CompletableFuture.runAsync(() -> cacheStorage.put(key, value));
CompletableFuture<Void> dbWrite = CompletableFuture.runAsync(() -> dbStorage.write(key, value));
// Block until both write operations finish
CompletableFuture.allOf(cacheWrite, dbWrite).join();
}
}
Step 3: Custom Doubly Linked List & LRU Eviction Policy
JAVA
package eviction;
class DLLNode<K> {
K key;
DLLNode<K> prev;
DLLNode<K> next;
DLLNode(K key) {
this.key = key;
}
}
class DoublyLinkedList<K> {
private final DLLNode<K> head;
private final DLLNode<K> tail;
public DoublyLinkedList() {
head = new DLLNode<>(null);
tail = new DLLNode<>(null);
head.next = tail;
tail.prev = head;
}
public void addLast(DLLNode<K> node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
}
public void detach(DLLNode<K> node) {
if (node.prev != null && node.next != null) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
}
}
public DLLNode<K> getFirst() {
if (head.next == tail) return null;
return head.next;
}
}
JAVA
package eviction;
import java.util.HashMap;
import java.util.Map;
public interface EvictionPolicy<K> {
void keyAccessed(K key);
K evictKey();
}
public class LRUEvictionPolicy<K> implements EvictionPolicy<K> {
private final Map<K, DLLNode<K>> nodeMap = new HashMap<>();
private final DoublyLinkedList<K> dll = new DoublyLinkedList<>();
@Override
public void keyAccessed(K key) {
if (nodeMap.containsKey(key)) {
DLLNode<K> existingNode = nodeMap.get(key);
dll.detach(existingNode);
dll.addLast(existingNode);
} else {
DLLNode<K> newNode = new DLLNode<>(key);
nodeMap.put(key, newNode);
dll.addLast(newNode);
}
}
@Override
public K evictKey() {
DLLNode<K> oldestNode = dll.getFirst();
if (oldestNode == null) return null;
dll.detach(oldestNode);
nodeMap.remove(oldestNode.key);
return oldestNode.key;
}
}
Step 4: Key-Based Thread Affinity Executor
JAVA
package concurrency;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.CompletableFuture;
import java.util.function.Supplier;
public class KeyBasedExecutor {
private final int poolSize;
private final ExecutorService[] executors;
public KeyBasedExecutor(int poolSize) {
this.poolSize = poolSize;
this.executors = new ExecutorService[poolSize];
for (int i = 0; i < poolSize; i++) {
// Assign a SingleThreadExecutor to each pool slot to guarantee sequential execution per slot
this.executors[i] = Executors.newSingleThreadExecutor();
}
}
private ExecutorService getExecutorForKey(Object key) {
int index = Math.abs(key.hashCode()) % poolSize;
return executors[index];
}
public <T> CompletableFuture<T> submit(Object key, Supplier<T> task) {
return CompletableFuture.supplyAsync(task, getExecutorForKey(key));
}
public CompletableFuture<Void> submit(Object key, Runnable task) {
return CompletableFuture.runAsync(task, getExecutorForKey(key));
}
public void shutdown() {
for (ExecutorService executor : executors) {
executor.shutdown();
}
}
}
Step 5: Main Cache Orchestrator
JAVA
package cache;
import storage.CacheStorage;
import storage.DatabaseStorage;
import policy.WritePolicy;
import eviction.EvictionPolicy;
import concurrency.KeyBasedExecutor;
import java.util.concurrent.CompletableFuture;
public class Cache<K, V> {
private final CacheStorage<K, V> cacheStorage;
private final DatabaseStorage<K, V> dbStorage;
private final WritePolicy<K, V> writePolicy;
private final EvictionPolicy<K> evictionPolicy;
private final KeyBasedExecutor keyBasedExecutor;
public Cache(CacheStorage<K, V> cacheStorage,
DatabaseStorage<K, V> dbStorage,
WritePolicy<K, V> writePolicy,
EvictionPolicy<K> evictionPolicy,
int concurrencyLevel) {
this.cacheStorage = cacheStorage;
this.dbStorage = dbStorage;
this.writePolicy = writePolicy;
this.evictionPolicy = evictionPolicy;
this.keyBasedExecutor = new KeyBasedExecutor(concurrencyLevel);
}
public CompletableFuture<V> get(K key) {
return keyBasedExecutor.submit(key, () -> {
if (cacheStorage.containsKey(key)) {
evictionPolicy.keyAccessed(key);
return cacheStorage.get(key);
}
// Cache Miss: Fallback to DB
V dbValue = dbStorage.read(key);
if (dbValue != null) {
cacheStorage.put(key, dbValue);
evictionPolicy.keyAccessed(key);
}
return dbValue;
});
}
public CompletableFuture<Void> put(K key, V value) {
return keyBasedExecutor.submit(key, () -> {
// Check capacity before adding new items
if (!cacheStorage.containsKey(key) && cacheStorage.size() >= cacheStorage.capacity()) {
K evictedKey = evictionPolicy.evictKey();
if (evictedKey != null) {
cacheStorage.remove(evictedKey);
}
}
// Execute write strategy
writePolicy.write(key, value, cacheStorage, dbStorage);
evictionPolicy.keyAccessed(key);
});
}
public void shutdown() {
keyBasedExecutor.shutdown();
}
}
8. Complete Execution Flow Walkthrough & Driver Code
Structure & Concept Flow
JAVA
import cache.Cache;
import storage.InMemoryCacheStorage;
import storage.SimpleDatabaseStorage;
import policy.WriteThroughPolicy;
import eviction.LRUEvictionPolicy;
import java.util.concurrent.ExecutionException;
public class CacheDemo {
public static void main(String[] args) throws ExecutionException, InterruptedException {
int cacheCapacity = 5;
int threadPoolSize = 4;
InMemoryCacheStorage<String, String> cacheStorage = new InMemoryCacheStorage<>(cacheCapacity);
SimpleDatabaseStorage<String, String> dbStorage = new SimpleDatabaseStorage<>();
WriteThroughPolicy<String, String> writePolicy = new WriteThroughPolicy<>();
LRUEvictionPolicy<String> evictionPolicy = new LRUEvictionPolicy<>();
Cache<String, String> cache = new Cache<>(
cacheStorage,
dbStorage,
writePolicy,
evictionPolicy,
threadPoolSize
);
System.out.println("--- Inserting initial entries (A-E) ---");
cache.put("A", "Apple").get();
cache.put("B", "Blueberry").get();
cache.put("C", "Cherry").get();
cache.put("D", "Dragonfruit").get();
cache.put("E", "Elderberry").get();
System.out.println("Fetch Key 'B': " + cache.get("B").get()); // Accesses B, moving it to tail
System.out.println("--- Inserting Key 'F' (Triggers Eviction) ---");
cache.put("F", "Fig").get(); // Capacity full; evicts "A" (least recently used)
System.out.println("Fetch Key 'A' (Should be evicted): " + cache.get("A").get());
System.out.println("Fetch Key 'F': " + cache.get("F").get());
cache.shutdown();
}
}
9. Summary and Key Takeaways
- Decoupled Architecture: Strategy patterns separate storage (
CacheStorage), database sync (WritePolicy), and eviction management (EvictionPolicy), ensuring high extensibility. - Read-Your-Own-Writes Consistency: Key-based thread affinity (
hash(key) % threadPoolSize) guarantees sequential execution for all operations sharing the same key. - Lock-Free Scalability: Concurrent data processing across multiple keys avoids global sync barriers by leveraging isolated
SingleThreadExecutorinstances per partition. - LRU Eviction: Doubly Linked List nodes paired with a Hash Map enable constant-time node removal, tail re-insertion, and head evictions.
- Synchronous Write Integrity:
WriteThroughPolicycombined with Java'sCompletableFutureensures both in-memory cache and persistent backing DB updates finish cleanly before returning to the caller. - Interview Focus: Designing robust enterprise systems requires balancing low-level data structures with concurrency guarantees, thread safety models, and cleanly separated object-oriented boundaries.