Design a Distributed Cache

#Problem Statement

Design a distributed in-memory cache (like Redis Cluster or Memcached) that stores key-value pairs, supports high throughput reads/writes with low latency, and scales horizontally.

📖

Real-world: The unsung hero of this design is consistent hashing, which came out of a 1997 MIT paper and was originally built to solve exactly this — distributing keys across caching nodes so that adding/removing a node only moves ~1/N of the keys instead of reshuffling everything (the same idea later powering Amazon's Dynamo and DynamoDB). The cautionary security tale for caches: for years tens of thousands of Redis and Memcached instances sat exposed to the internet with no authentication (Redis historically had no auth by default and trusted the network), leading to mass data theft and, worse, Memcached becoming the vehicle for record-breaking DDoS amplification in 2018 — a ~1.3 Tbps attack on GitHub — because an unauthenticated UDP cache reflects huge responses to spoofed victims. The lessons: bind to localhost/private networks, require auth, disable UDP, and never treat "it's just a cache" as "it doesn't need security." Also know the failure modes this design must handle: cache stampede, hot keys, and thundering herd.

#Requirements

#Functional

• get(key) → value
• put(key, value, ttl)
• delete(key)
• Configurable eviction policies (LRU, LFU, TTL)
• Cluster mode: data distributed across nodes

#Non-Functional

• P99 latency: < 1ms for get/put
• Throughput: 1M ops/s per cluster
• High availability: no single point of failure
• Horizontal scaling: add nodes without downtime
• Consistency: eventual is acceptable (caches can be stale)

#Core Design

#Single Node Cache

Start simple: an in-memory hash map with LRU eviction.

HashMap<String, Node> map     → O(1) lookup
DoublyLinkedList list          → O(1) LRU move-to-front / evict-from-tail

get(key):
    node = map.get(key)
    if expired: evict, return null
    move node to head of list
    return node.value

put(key, value, ttl):
    if key exists: update value, move to head
    else:
        if at capacity: evict tail
        create node, add to head, add to map

#Consistent Hashing for Distribution

Naive approach: hash(key) % N — when N changes (node added/removed), almost all keys need to be remapped. Bad for a live system.

Consistent hashingplace nodes and keys on a conceptual ring (0 → 2^32). A key belongs to the first node clockwise from its hash position.

Ring: ───── Node A (90°) ──── Node B (180°) ──── Node C (270°) ────
Key K hashes to 120° → assigned to Node B (next clockwise)

Add Node D at 150°:
  Only keys between 120°-150° (previously B's) reassign to D
  All other keys: unchanged

Virtual nodeseach physical node occupies multiple positions on the ring (e.g., 150 virtual nodes per physical node). This ensures uniform key distribution even with heterogeneous hardware.

#Replication for Availability

Each key is replicated to the next N nodes clockwise on the ring (N = replication factor, typically 3).

#Architecture

Client SDK (consistent hash → pick node)
           ↓
    ┌──────────────────────────────────┐
    │ Cache Node A  │ Cache Node B     │
    │ [key1, key3]  │ [key2, key4]     │
    │ replicas of B │ replicas of C    │
    └──────────────────────────────────┘
    ┌──────────────────────────────────┐
    │ Cache Node C  │ Cache Node D     │
    └──────────────────────────────────┘

Coordinator / Config Server:
  - Tracks live nodes
  - Distributes ring membership to clients
  - Health checks

#Client-side vs Proxy-side Routing

Client-side routing (Redis Cluster, Memcached): client library implements consistent hashing, connects directly to correct node. No proxy hop = lower latency. Client must know cluster topology.

Proxy-side routing (e.g., Twemproxy): all clients connect to a proxy; proxy routes to correct node. Simpler clients; proxy is a potential bottleneck.

#Eviction Policies

Active vs lazy expiration

• Lazy: check TTL on access, evict if expired
• Active: background thread periodically scans and evicts expired keys (prevents memory leak from never-accessed expired keys)

#Key Design Decisions

#Security Considerations

AuthenticationRedis in production should always have requirepass or ACL-based auth, and should never be exposed on a public interface without authentication.

#Interview Tips