Distributed Cache

A distributed cache stores frequently accessed data in memory across multiple servers, enabling sub-millisecond data retrieval. In system design interviews, caching appears in nearly every architecture—it's how you achieve the performance that users expect from modern applications.

This page covers what you need to know for interviews: why caching matters, cache writing and eviction policies, how to design a distributed cache from scratch, and the trade-offs between popular solutions like Redis and Memcached. Understanding these concepts helps you design systems that handle millions of requests without overwhelming your database.

Why Caching Matters

Without caching, every user request hits your database. As traffic grows, the database becomes a bottleneck—queries slow down, and eventually the system fails under load. A cache sits between your application and database, serving frequently accessed data from memory.

Key benefits of distributed caching:

• Reduced latency — RAM access is ~100x faster than SSD, ~1000x faster than network round-trip to database
• Reduced database load — Fewer queries means your database handles more users
• Improved availability — Cache can serve stale data if the database is temporarily down
• Cost efficiency — Scaling cache is cheaper than scaling database

Cache Hit and Miss

When a request arrives:

1. Cache hit — Data exists in cache, return immediately (~1ms)
2. Cache miss — Data not in cache, fetch from database (~10-100ms), store in cache for future requests

The cache hit ratio measures effectiveness:

hit_ratio = cache_hits / (cache_hits + cache_misses)

A 95% hit ratio means only 5% of requests reach the database. Improving from 90% to 95% cuts database load in half.

Caching Layers

Caching happens at multiple levels in a system. Each layer serves different purposes:

What is a Distributed Cache?

A distributed cache is a caching system where multiple cache servers coordinate to store frequently accessed data. Unlike a single-server cache, it:

• Scales horizontally — Add more servers to handle more data and requests
• Provides high availability — No single point of failure
• Supports larger datasets — Combined memory exceeds any single machine

Why Distribute the Cache?

A single cache server has limitations:

• Single point of failure — Server crash loses all cached data
• Memory limits — One machine can only hold so much RAM
• Throughput limits — One server can only handle so many requests

Distributing across multiple servers solves these problems. The challenge becomes: how do you decide which server stores which data?

Cache Writing Policies

When data changes, you need to update both the database and cache. The order and timing of these updates affects consistency and performance.

Write-Through

Write to both cache and database synchronously. The write only succeeds when both complete.

1. Application sends write request
2. Data written to database
3. Data written to cache
4. Success returned only after both complete

Pros:

• Strong consistency between cache and database
• Cache always has latest data
• Simple mental model

Cons:

• Higher write latency (waiting for both writes)
• Every write touches the cache, even for rarely-read data

Use when: Data consistency is critical and you can tolerate higher write latency.

Write-Back (Write-Behind)

Write to cache only. Cache asynchronously writes to database later.

1. Application writes to cache
2. Success returned immediately
3. Cache writes to database asynchronously (batched)

Pros:

• Very low write latency
• Batching reduces database load

Cons:

• Risk of data loss if cache fails before writing to database
• Temporary inconsistency between cache and database

Use when: Write performance is critical and you can tolerate some data loss risk.

Write-Around

Write directly to database, bypassing cache. Cache is populated on read (cache miss).

1. Application writes to database
2. Cache is NOT updated
3. Next read triggers cache miss → data loaded into cache

Pros:

• Avoids cache being filled with data that may never be read
• Database is always the source of truth

Cons:

• First read after write always misses cache
• Not suitable for read-after-write patterns

Use when: Data is written frequently but read infrequently.

Comparison

Eviction Policies

Cache memory is limited. When full, you must evict existing entries to make room for new ones. The eviction policy determines which entries to remove.

Least Recently Used (LRU)

Evict the entry that hasn't been accessed for the longest time. Based on the principle that recently accessed data is likely to be accessed again.

Implementation: Doubly-linked list + hash map

• Hash map provides O(1) lookup by key
• Linked list maintains access order
• On access, move entry to head
• On eviction, remove from tail

Pros: Simple, effective for most workloads Cons: Doesn't consider access frequency—a rarely-used item accessed once becomes "recent"

Least Frequently Used (LFU)

Evict the entry with the fewest accesses. Keeps popular items even if not recently accessed.

Pros: Better for skewed workloads where some items are consistently popular Cons: New items may be evicted before they have a chance to become popular; requires tracking access counts

Time-To-Live (TTL)

Entries expire after a fixed duration, regardless of access patterns.

SET user:123 "data" EX 3600  # Expires in 1 hour

Pros: Ensures data freshness, prevents unbounded memory growth Cons: Popular items may expire unnecessarily; stale data served until TTL

Other Policies

Cache Invalidation

Beyond eviction (removing data to free space), you need invalidation—removing data that has become stale or incorrect.

Why Invalidation Matters

Consider this scenario:

1. User profile cached with user:123 → {name: "Alice"}
2. User updates name to "Alicia" in database
3. Cache still returns "Alice" until entry expires or is evicted

This is a consistency problem. Invalidation strategies address it.

TTL-Based Expiration

Set a time-to-live on cache entries. After TTL expires, entry is considered invalid.

Active expiration: Background process periodically scans for expired entries Passive expiration: Check TTL on access, delete if expired

Most systems use both: passive expiration on reads (immediate), active expiration periodically (cleanup).

SET session:abc123 "user_data" EX 1800  # 30-minute session

Trade-off: Short TTL = fresher data but more cache misses. Long TTL = better hit ratio but staler data.

Event-Based Invalidation

Invalidate cache when data changes. Requires coordination between the component that writes to the database and the cache.

Patterns:

1. Application-level: Application invalidates cache after database write

   db.update(user)
   cache.delete(f"user:{user.id}")
   

2. Database triggers: Database notifies cache of changes (CDC - Change Data Capture)

3. Message queue: Publish invalidation events, cache subscribes

   publish("cache_invalidate", {"key": "user:123"})
   

High-Level Design

Let's design a distributed cache system. We start with requirements, then build the architecture.

Requirements

Functional:

• PUT(key, value) — Store a key-value pair
• GET(key) — Retrieve value by key
• DELETE(key) — Remove entry (optional, usually handled by TTL)

Non-Functional:

• High performance — Sub-millisecond latency for reads and writes
• Scalability — Handle increasing data and traffic by adding servers
• High availability — System remains operational despite failures
• Consistency — Clients see consistent data (eventual consistency acceptable)
• Affordability — Use commodity hardware

Architecture Components

A typical architecture includes a load balancer distributing traffic across application servers, each with a cache client that routes requests to the appropriate cache server.

Cache Client

• Library embedded in application servers
• Determines which cache server to contact using consistent hashing
• All clients use the same algorithm for consistent routing

Cache Servers

• Store cache entries in RAM
• Use hash tables for O(1) key lookup
• Use linked list for LRU eviction
• Communicate via TCP/UDP

Why this separation? Cache clients handle the "smart" routing logic, cache servers handle storage. This keeps servers simple and stateless relative to each other.

Detailed Design

The high-level design has limitations we need to address:

1. How do clients know about all cache servers?
2. What happens when a cache server fails?
3. How do we handle hot keys (popular data on one server)?

Consistent Hashing for Server Selection

Simple hashing (hash(key) % num_servers) breaks when servers are added or removed—most keys get remapped, causing massive cache misses.

Consistent hashing minimizes disruption (this same technique is used for database sharding):

• Servers and keys are hashed onto a ring (0 to 2³²-1)
• Each key is stored on the first server clockwise from its position
• Adding/removing a server only affects keys in one segment

Virtual nodes improve load distribution: each physical server gets multiple positions on the ring, spreading load more evenly.

Configuration Service

Cache clients need to know which servers are available. Three approaches:

1. Configuration file — Simple but requires manual updates and deployment
2. Centralized config — Store server list in shared location (etcd, ZooKeeper)
3. Configuration service — Dedicated service monitors server health, notifies clients of changes

The configuration service is most robust—it automatically detects failures and additions without manual intervention.

Replication for Availability

A single server per shard means data loss on failure. Add replicas:

• Primary — Handles writes, replicates to secondaries
• Secondaries — Handle reads, provide failover

Replication modes:

• Synchronous — Wait for replica acknowledgment (strong consistency, higher latency)
• Asynchronous — Return immediately, replicate in background (eventual consistency, lower latency)

For caching, asynchronous replication is typical—slight inconsistency is acceptable for the performance benefit.

Internal Data Structures

Each cache server uses:

1. Hash map — O(1) lookup by key, stores pointers to linked list nodes
2. Doubly linked list — Maintains access order for LRU eviction
3. TTL metadata — Expiration time for each entry

Hash Map                    Doubly Linked List (LRU order)
┌─────────┬─────────┐      ┌──────┐   ┌──────┐   ┌──────┐
│  Key    │ Pointer │      │ Key3 │←→│ Key1 │←→│ Key2 │
├─────────┼─────────┤      │(head)│   │      │   │(tail)│
│ "key1"  │  ───────┼─────→└──────┘   └──────┘   └──────┘
│ "key2"  │  ───────┼────────────────────────────────┘
│ "key3"  │  ───────┼──┘
└─────────┴─────────┘

On access: Move to head (most recent)
On eviction: Remove from tail (least recent)

Design Evaluation

Let's evaluate our design against the non-functional requirements.

Performance

Our design achieves high performance through:

• Consistent hashing — O(log N) to find server, where N is number of servers
• Hash table lookup — O(1) average to find key within server
• RAM storage — Sub-millisecond read/write latency
• Replication — Distribute read load across replicas

Impact of eviction algorithm on performance:

The eviction algorithm affects cache hit ratio. Consider:

• Cache hit latency: 5ms
• Cache miss latency: 30ms (includes database round-trip)

Improving hit ratio from 90% to 95% reduces effective latency by ~17%.

Scalability

• Horizontal scaling — Add more cache servers to handle more data/traffic
• Consistent hashing — Minimizes data movement when scaling
• Sharding — Data partitioned across servers by key
• Hot key handling — Monitor for hot partitions, add replicas for read-heavy keys

Availability

• Replication — No single point of failure for data
• Failover — Secondary promotes to primary on failure
• Configuration service — Automatic failure detection and client notification
• Graceful degradation — Cache miss falls back to database

Consistency

Trade-off between consistency and performance:

• Within data center — Synchronous replication for strong consistency
• Across data centers — Asynchronous replication (eventual consistency) for performance

Memcached vs Redis

Two dominant distributed cache solutions exist: Memcached and Redis. Both achieve sub-millisecond latency, but they serve different needs.

Memcached

Introduced in 2003, Memcached is a simple, high-performance key-value cache.

Architecture:

• Shared-nothing — Servers don't communicate with each other
• Client-side routing — Clients determine which server to use
• Multi-threaded — Efficiently uses multiple CPU cores

Characteristics:

• Stores only strings (data must be serialized)
• No built-in replication (requires external tools)
• LRU eviction only
• Simple commands: GET, SET, DELETE

Best for: Simple caching with maximum performance, read-heavy workloads, when you need multi-threading.

Redis

Redis is a data structure server that can function as cache, database, and message broker.

Architecture:

• Single-threaded (for data operations) — Avoids locking complexity
• Built-in clustering — Redis Cluster for sharding and replication
• Redis Sentinel — Automatic failover management

Characteristics:

• Supports multiple data types: strings, lists, sets, sorted sets, hashes, streams
• Built-in replication and persistence
• Multiple eviction policies
• Rich command set with atomic operations
• Pipelining for batch operations
• Lua scripting support

Best for: Complex data structures, pub/sub messaging, when you need persistence, write-heavy workloads.

Comparison

When to Choose Each

Choose Memcached when:

• Simple key-value caching is sufficient
• You need multi-threaded performance
• Memory efficiency is critical
• You're already using it (migration cost)

Choose Redis when:

• You need complex data structures (sorted sets for leaderboards, lists for queues)
• You need persistence or replication out of the box
• You need pub/sub or streaming
• You want flexibility in eviction policies

Common Interview Patterns

Cache-Aside (Lazy Loading)

The most common pattern. Application manages cache explicitly:

def get_user(user_id):
    # Check cache first
    user = cache.get(f"user:{user_id}")
    if user:
        return user  # Cache hit

    # Cache miss - load from database
    user = db.query("SELECT * FROM users WHERE id = ?", user_id)

    # Populate cache for next time
    cache.set(f"user:{user_id}", user, ttl=3600)
    return user

Pros: Simple, only caches data that's actually requested Cons: First request always misses, cache misses are slow

Read-Through Cache

Cache sits between application and database. On miss, cache fetches from database automatically.

Pros: Application code simpler, consistent caching behavior Cons: Less control, cache must know how to fetch data

Write-Through / Write-Behind

See Cache Writing Policies section above.

Cache Warming

Pre-populate cache before traffic hits, avoiding cold-start cache misses.

def warm_cache():
    # Load most popular items into cache on startup
    popular_items = db.query("SELECT * FROM items ORDER BY view_count DESC LIMIT 1000")
    for item in popular_items:
        cache.set(f"item:{item.id}", item, ttl=3600)

Use when: You know access patterns upfront, or after cache server restarts.

Common Cache Problems

These problems frequently appear in interviews. Knowing them demonstrates deep understanding of caching systems.

Cache Stampede (Thundering Herd)

When a popular cache entry expires, multiple requests simultaneously hit the database to regenerate it. This can overwhelm the database.

Time 0: Cache entry "popular_item" expires
Time 1: Request A checks cache → miss → queries database
Time 1: Request B checks cache → miss → queries database
Time 1: Request C checks cache → miss → queries database
... hundreds of concurrent requests all hit database

Solutions:

1. Locking (Mutex)

   def get_with_lock(key):
       value = cache.get(key)
       if value:
           return value
   
       # Try to acquire lock
       if cache.set(f"lock:{key}", "1", nx=True, ex=10):
           # We got the lock - fetch from DB
           value = db.query(key)
           cache.set(key, value, ttl=3600)
           cache.delete(f"lock:{key}")
           return value
       else:
           # Another request has the lock - wait and retry
           time.sleep(0.1)
           return get_with_lock(key)
   

2. Probabilistic Early Expiration Randomly refresh entries before they expire, spreading database load.

   def get_with_early_refresh(key, ttl=3600):
       value, expiry_time = cache.get_with_ttl(key)
       remaining_ttl = expiry_time - time.now()
   
       # Probabilistically refresh if close to expiry
       if remaining_ttl < ttl * 0.1:  # Within 10% of expiry
           if random.random() < 0.2:  # 20% chance
               refresh_cache_async(key)
   
       return value
   

3. Request Coalescing Multiple requests for the same key share a single database query.

4. Background Refresh Never let entries expire—background job refreshes them before TTL.

Cache Penetration

Requests for keys that don't exist in both cache and database. Since they never get cached, every request hits the database.

GET user:999999  → Cache miss → DB query → Not found → Nothing cached
GET user:999999  → Cache miss → DB query → Not found → Nothing cached
... infinite database queries for non-existent key

This can be malicious (attackers query random IDs) or accidental (bugs, deleted data).

Solutions:

1. Cache Negative Results Store a placeholder for keys that don't exist.

   def get_user(user_id):
       value = cache.get(f"user:{user_id}")
       if value == "NULL_PLACEHOLDER":
           return None  # Known to not exist
       if value:
           return value
   
       user = db.query(user_id)
       if user:
           cache.set(f"user:{user_id}", user, ttl=3600)
       else:
           # Cache the non-existence with shorter TTL
           cache.set(f"user:{user_id}", "NULL_PLACEHOLDER", ttl=300)
       return user
   

2. Bloom Filter Check a bloom filter before querying. If the bloom filter says "definitely not present," skip the database entirely.

   def get_with_bloom_filter(key):
       if not bloom_filter.might_contain(key):
           return None  # Definitely doesn't exist
   
       # Might exist - check cache and database
       return normal_cache_lookup(key)
   

3. Input Validation Validate request parameters before querying. Reject obviously invalid IDs.

Hot Key Problem

A single key receives disproportionate traffic, overwhelming the cache server responsible for it. Think celebrity tweets, flash sales, or breaking news.

Detection:

• Monitor per-key access rates
• Alert on keys exceeding threshold (e.g., >10,000 QPS)
• Track server-level hotspots

Solutions:

1. Local Caching Cache hot keys in application server memory, reducing distributed cache load.

   local_cache = {}  # In-process cache
   
   def get_hot_key(key):
       if key in local_cache:
           return local_cache[key]
   
       value = distributed_cache.get(key)
       if is_hot_key(key):
           local_cache[key] = value  # Cache locally
       return value
   

2. Read Replicas for Hot Keys Create dedicated replicas for hot keys, spreading read traffic.

3. Key Replication with Random Suffix Store the same value under multiple keys, distributing across servers.

   # Write to multiple keys
   for i in range(10):
       cache.set(f"hot_item:{i}", value)
   
   # Read from random key
   replica = random.randint(0, 9)
   value = cache.get(f"hot_item:{replica}")
   

4. Request Rate Limiting Limit requests per key to prevent abuse.

Cache Monitoring

In production systems, monitoring helps detect problems early. Interviewers may ask how you'd know if your cache is working well.

Key Metrics

Warning Signs

Low hit ratio (< 80%):

• Cache too small (increase memory)
• Poor key design (keys too specific)
• Wrong eviction policy
• TTLs too short

High eviction rate:

• Cache under-provisioned
• Memory pressure from large values
• Possible cache stampede

Latency spikes:

• Hot key problem
• Network issues
• Server overload

Memory near 100%:

• Risk of OOM errors
• Evictions becoming aggressive
• Time to scale

Quick Reference

Writing Policy Selection

Eviction Policy Selection

Interview Checklist

When discussing caching:

• Identified what to cache (hot data, computed results, sessions)
• Chose cache-aside vs read/write-through pattern
• Selected writing policy (write-through default)
• Selected eviction policy (LRU + TTL default)
• Addressed cache invalidation strategy
• Mentioned consistent hashing for distribution
• Discussed replication for availability
• Acknowledged consistency trade-offs
• Named specific technology (Redis default)
• Addressed cache stampede (locking, early expiration)
• Mentioned cache penetration defense (cache negatives, bloom filter)
• Discussed hot key mitigation (local cache, replicas)
• Outlined monitoring approach (hit ratio, latency, evictions)

What Interviewers Look For

1. Understanding of purpose — You know caching reduces latency and database load, not just that "you need a cache."

2. Cache placement awareness — You can explain cache-aside pattern and when to use read-through or write-behind.

3. Consistency trade-offs — You understand that caching introduces staleness and can articulate strategies to manage it.

4. Practical knowledge — You mention Redis by name, know about TTLs and LRU eviction, and can discuss consistent hashing.

5. Right-sizing — You don't over-engineer. Start with a single Redis instance, scale to cluster only when requirements demand it.

Caching is fundamental infrastructure—it enables your design's performance but isn't usually the interesting part. Demonstrate competence quickly: "We'll use Redis with cache-aside pattern, LRU eviction, and 1-hour TTLs. For invalidation, we'll delete cache entries when data is updated." Then move on to the unique aspects of your system.