Distributed Cache System Design (HLD & LLD)

Problem Statement

Design a distributed cache system similar to Redis or Memcached that:

• Stores frequently accessed data in memory
• Reduces database load
• Provides very low latency reads (<1 ms)
• Scales horizontally
• Supports TTL and eviction policies

Functional Requirements

1. Put data into cache
2. Get data from cache
3. Delete cache entry
4. Support TTL (expiration)
5. Evict entries when memory is full
6. Distribute data across multiple nodes
7. Replicate data for fault tolerance

Non-Functional Requirements

• Very low latency
• High availability
• Horizontal scalability
• Eventual consistency
• Handle millions of requests per second

High-Level Architecture

flowchart TD
    C[Client]
    R[Cache Client / Routing Layer]
    N1[Cache Node 1]
    N2[Cache Node 2]
    N3[Cache Node N]
    RP1[Replica]
    RP2[Replica]
    RP3[Replica]

    C --> R
    R --> N1
    R --> N2
    R --> N3
    N1 --> RP1
    N2 --> RP2
    N3 --> RP3

Core Components

Cache Client (Routing Layer)

Responsible for deciding which node stores a key.

Simple routing:

node = hash(key) % number_of_nodes

Preferred approach: Consistent Hashing, which minimizes key movement when nodes are added or removed.

Cache Nodes

Each node stores:

Key -> Value

Internally:

In-memory HashMap

Example:

user:101 -> UserObject
product:55 -> ProductObject

Replication

Write flow:

Client -> Primary -> Replica

Read flow:

Client -> Primary

Eviction Policies

Policy	Description
LRU	Least Recently Used
LFU	Least Frequently Used
FIFO	First In, First Out
TTL	Expire after configured time

LRU is the most common.

TTL Expiration

Each entry contains:

key
value
expiryTime

Approaches:

• Lazy expiration (check on read)
• Active expiration (background cleanup)

Data Model

CacheEntry
-------------
key
value
ttl
createdTime
lastAccessTime
accessCount

API Design

PUT(key, value, ttl)

GET(key)

DELETE(key)

EXISTS(key)

CLEAR()

Example:

PUT("user:101", userObject, 5 minutes)

Low-Level Design

Cache Interface

public interface Cache<K,V> {

    void put(K key, V value, long ttl);

    V get(K key);

    void delete(K key);

    boolean exists(K key);
}

CacheEntry

class CacheEntry<V> {

    private V value;
    private long expiryTime;
    private long lastAccessTime;
    private int accessCount;

}

Local Cache Node

public class CacheNode<K,V> implements Cache<K,V> {

    private Map<K, CacheEntry<V>> cacheMap;

    private EvictionPolicy<K> evictionPolicy;

    public void put(K key, V value, long ttl) {
        CacheEntry<V> entry = new CacheEntry<>(value, ttl);
        cacheMap.put(key, entry);
        evictionPolicy.keyAccessed(key);
    }

    public V get(K key) {

        CacheEntry<V> entry = cacheMap.get(key);

        if(entry == null) return null;

        if(entry.isExpired()){
            cacheMap.remove(key);
            return null;
        }

        evictionPolicy.keyAccessed(key);

        return entry.getValue();
    }
}

Eviction Policy Interface

public interface EvictionPolicy<K> {

    void keyAccessed(K key);

    K evictKey();
}

LRU Implementation

public class LRUEvictionPolicy<K> implements EvictionPolicy<K> {

    private Deque<K> deque = new LinkedList<>();

    public void keyAccessed(K key) {
        deque.remove(key);
        deque.addFirst(key);
    }

    public K evictKey() {
        return deque.removeLast();
    }
}

Routing Layer

public class CacheRouter {

    private List<CacheNode> nodes;

    public CacheNode getNode(String key){

        int hash = key.hashCode();

        int index = hash % nodes.size();

        return nodes.get(index);
    }
}

Better implementation:

ConsistentHashRing

Write Flow

sequenceDiagram
    participant Client
    participant Router
    participant Primary
    participant Replica

    Client->>Router: PUT(key, value)
    Router->>Primary: Route request
    Primary->>Primary: Store in memory
    Primary->>Replica: Replicate

Read Flow

sequenceDiagram
    participant Client
    participant Router
    participant Cache

    Client->>Router: GET(key)
    Router->>Cache: Locate node
    Cache-->>Client: Return value

Scaling Strategy

Adding a new node with consistent hashing redistributes only a small percentage of keys.

Fault Tolerance

1. Read from replica
2. Rebuild cache from database
3. Rebalance keys

Cache Invalidation Strategies

Cache-Aside

Application -> Cache

Cache miss
    -> Read Database
    -> Populate Cache

Write-Through

Write Database + Cache simultaneously

Write-Back

Write Cache
      |
      v
Persist to Database asynchronously

Real-World Technologies

• Redis
• Memcached
• Hazelcast
• Apache Ignite

Typical Spring Boot architecture:

Spring Boot
    |
    v
Redis Cluster

Using:

Spring Cache + Redis

Common Interview Follow-Up Questions

1. How do you prevent cache stampede?
2. What is cache penetration?
3. What is cache avalanche?
4. How does Redis Cluster sharding work?
5. Local cache vs distributed cache?
6. How does consistent hashing work internally?

Key Takeaways

• Distributed caches improve latency and reduce database load.
• Consistent hashing enables efficient horizontal scaling.
• TTL, replication, and eviction policies are fundamental building blocks.
• LRU is a common eviction strategy and can be abstracted via an eviction policy interface.
• Cache-aside is the most widely used cache invalidation pattern in microservices.