Walkthrough 5 — Design a Distributed Cache (Redis-style)

The brief

Design a distributed in-memory cache supporting GET, SET, DELETE. Must scale horizontally to handle millions of ops/sec across many nodes.

Step 1: Requirements

GET/SET/DELETE key-value.
TTL per key.
Scale: 100M keys, 1M QPS.
Latency: < 1ms per op.
High availability: tolerate node failures.
Eviction when memory full (LRU).

Step 2: Single-node cache

Before distributed, design single-node first:

Hash table for O(1) lookups.
Doubly-linked list for LRU order.
TTL: separate priority queue OR lazy expiration on GET.
Memory cap: when full, evict tail of LRU list.

class Cache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}            # key -> (value, expires_at, lru_node)
        self.lru = DoublyLinkedList()

    def get(self, key):
        if key not in self.data: return None
        value, expires_at, node = self.data[key]
        if expires_at and time.time() > expires_at:
            self._evict(key); return None
        self.lru.move_to_front(node)
        return value

    def set(self, key, value, ttl=None):
        if key in self.data:
            _, _, node = self.data[key]
            self.lru.remove(node)
        if len(self.data) >= self.capacity:
            self._evict_lru()
        expires_at = time.time() + ttl if ttl else None
        node = self.lru.add_to_front(key)
        self.data[key] = (value, expires_at, node)

This is essentially Memcached / Redis single-node.

Step 3: Going distributed

Single node has limits: memory, throughput, availability. Distribute by:

Sharding (partitioning)

N nodes; each holds 1/N of keys.
Client (or proxy) computes shard = hash(key) % N and routes.

Problem with naive modulo: adding/removing nodes shuffles ALL keys (cache invalidation storm).

Consistent hashing

Place nodes on a hash ring (each node has multiple "virtual nodes" for balance).
Key → hash → nearest clockwise virtual node.
Adding/removing a node only affects keys near that node on the ring.

        node1
       /      \
   key_a    node2
     |        |
   node3 - key_b
        \      /
        node4

When node3 leaves, only its keys redistribute to neighbors. Minimal disruption.

Step 4: Replication

For high availability, each shard has replicas:

Primary + 2 replicas = 3-way replication.
Async replication (fast writes; eventual consistency).
On primary failure, promote a replica.

Trade-off: async replication can lose recent writes; sync replication is slower but consistent.

For cache (where freshness matters less than uptime): async is usually fine.

Step 5: Client / Proxy

Two options for routing:

Smart client: client knows the ring; computes shard locally; calls right node. (Memcached pattern.)
Proxy: client calls a proxy; proxy routes. (Twemproxy, Envoy, Redis Cluster has both.)

Trade-offs:

Smart client: faster (no extra hop); harder to update ring info.
Proxy: simpler client; extra hop (~1ms); easier to deploy.

Most production stacks use a proxy or library that abstracts this (Lettuce for Redis, etc.).

Step 6: Coordination

Who tracks node membership?

Static config: simple; ops-heavy when nodes added.
Gossip protocol: nodes share state with each other (Redis Cluster uses this).
ZooKeeper / etcd: centralized coordination; nodes watch for changes.

Redis Cluster uses gossip; this is decentralized and resilient.

Step 7: Operations to handle

Reads

Client hashes key → routes to shard → calls primary (or replica for read scaling).
Replica reads: lower latency in some setups; risk of stale data.

Writes

Client hashes key → routes to primary.
Primary acknowledges; async-replicates to replicas.

Failover

Detect failure via heartbeat.
Promote replica to primary.
Update gossip / coordination layer.
New requests routed to new primary.

Reshard (add/remove nodes)

Update ring (add/remove virtual nodes).
Migrate affected keys from old → new owners.
During migration: redirect to new owner; client retries.

Step 8: Eviction policy

Redis options:

allkeys-lru: evict LRU across all keys.
volatile-lru: evict LRU among keys with TTL.
allkeys-lfu: evict least-frequently-used.
noeviction: error when full (safer in some cases).

LRU is the default; LFU better for workloads with stable hot keys.

Step 9: TTL handling

Two strategies:

Lazy: check on GET; expire if past.
Active: background thread scans samples; expires.

Redis does both: lazy is fast; active prevents memory bloat from cold expired keys.

Step 10: Persistence (optional for cache)

If cache is purely volatile (rebuild from source on restart): no persistence needed.

If used as primary store (Redis often is): persistence to disk:

AOF (Append-Only File): log every write; replay on restart. Durable; slow recovery.
RDB (snapshots): periodic memory snapshots. Fast recovery; some data loss.
Both: hybrid.

For pure cache: skip persistence; rebuild on warm-up.

Common follow-ups

Hot keys: a single user/celebrity key gets 100K req/sec. Solution: replicate hot keys across multiple nodes (read-only replicas).
Cache stampede on miss: lock + single fetch; or stale-while-revalidate.
Large values: limit per-key size (Redis default 512MB max value).
Multi-region: cross-region replication; geo-aware routing.

Self-rubric

Deliverables

Architecture diagram (clients, proxies, nodes, replicas).
Consistent hashing diagram (ring with virtual nodes).
Pseudo-code for single-node LRU + sharding.
Failover flow.

Assignment Instructions