System Design Bible

Chapter 65: Design Distributed Cache (Redis Cluster)

1. Requirements

Functional Requirements

Non-Functional Requirements

Scale Estimation

Operations per second: 10M ops/sec
Average key size: 50 bytes
Average value size: 1 KB
Total keys: 1 billion keys
Storage: ~1 TB in-memory data
Cluster size: 50 nodes (20 GB per node)
Replication factor: 3 (1 primary + 2 replicas)
Interview Tip: Start by clarifying use cases (session store, rate limiter, leaderboard, pub/sub). Different use cases have different consistency and persistence requirements.

2. High-Level Design

graph TB subgraph Client Layer Client1[Client 1] Client2[Client 2] Client3[Client 3] end subgraph Redis Cluster subgraph Shard 1 - Slots 0-5460 M1[Master 1
Port 7000] R1A[Replica 1A
Port 7001] R1B[Replica 1B
Port 7002] end subgraph Shard 2 - Slots 5461-10922 M2[Master 2
Port 7003] R2A[Replica 2A
Port 7004] R2B[Replica 2B
Port 7005] end subgraph Shard 3 - Slots 10923-16383 M3[Master 3
Port 7006] R3A[Replica 3A
Port 7007] R3B[Replica 3B
Port 7008] end end Client1 --> M1 Client2 --> M2 Client3 --> M3 M1 -.->|Async Repl| R1A M1 -.->|Async Repl| R1B M2 -.->|Async Repl| R2A M2 -.->|Async Repl| R2B M3 -.->|Async Repl| R3A M3 -.->|Async Repl| R3B M1 <-.->|Gossip| M2 M2 <-.->|Gossip| M3 M3 <-.->|Gossip| M1

Core Components

Why 16384 Slots?

3. Hash Slot Assignment

CRC16 Hashing

Redis Cluster uses CRC16 to map keys to hash slots:

slot = CRC16(key) mod 16384

// Example:
key = "user:1234:session"
CRC16("user:1234:session") = 52341
slot = 52341 % 16384 = 3189

Hash Tags for Multi-Key Operations

Multi-key operations (MGET, MSET) require all keys to be on the same slot. Use hash tags:

// Without hash tag (different slots):
user:1234:name     -> slot 7234
user:1234:email    -> slot 9012
user:1234:session  -> slot 3189

// With hash tag (same slot):
user:{1234}:name     -> slot based on "1234"
user:{1234}:email    -> slot based on "1234"
user:{1234}:session  -> slot based on "1234"

// Hash tag rule: Use substring between first { and first }
Interview Tip: Explain why consistent hashing is NOT used in Redis Cluster. Consistent hashing minimizes key movement but creates uneven distribution. Hash slots provide predictable, even distribution with controlled resharding.

Slot Distribution Example

Node Slots Count Percentage
Master 1 0 - 5460 5461 33.3%
Master 2 5461 - 10922 5462 33.3%
Master 3 10923 - 16383 5461 33.3%

4. Data Partitioning Strategies

Client-Side Partitioning

Client knows the full cluster topology and routes requests directly to the correct node.

sequenceDiagram participant Client participant Master1 participant Master2 Client->>Client: slot = CRC16(key) % 16384 Client->>Client: Lookup slot -> node mapping Client->>Master2: GET key (direct to correct node) Master2-->>Client: value

Pros: No extra hop, lowest latency
Cons: Client must maintain topology, handle resharding

Proxy-Based Partitioning

Proxy layer (Twemproxy, Envoy) handles routing. Client unaware of cluster topology.

sequenceDiagram participant Client participant Proxy participant Master2 Client->>Proxy: GET key Proxy->>Proxy: slot = CRC16(key) % 16384 Proxy->>Master2: GET key Master2-->>Proxy: value Proxy-->>Client: value

Pros: Dumb client, centralized logic
Cons: Extra hop (latency), proxy is bottleneck/SPOF

Redis Cluster Mode (Hybrid)

Client initially connects to any node. If wrong node, receives redirect (MOVED/ASK).

sequenceDiagram participant Client participant Master1 participant Master2 Client->>Master1: GET key (wrong node) Master1-->>Client: MOVED 3189 127.0.0.1:7003 Client->>Client: Update slot mapping Client->>Master2: GET key Master2-->>Client: value

Pros: Eventually optimal routing, no proxy overhead
Cons: Initial redirects, client must handle MOVED/ASK

Interview Tip: Compare with other partitioning schemes (range-based, consistent hashing). Hash slots combine benefits: even distribution like consistent hashing + simple range-based migration.

5. Replication

Asynchronous Replication

Redis uses async replication for performance. Master doesn't wait for replica ACKs.

// Master flow:
1. Client sends SET key value
2. Master applies write to in-memory store
3. Master returns OK to client immediately
4. Master async sends write to replicas
5. Replicas apply write and ACK (master doesn't wait)

Replication Flow

sequenceDiagram participant Client participant Master participant Replica1 participant Replica2 Client->>Master: SET user:1234 "Alice" Master->>Master: Write to memory Master-->>Client: OK par Async to Replica1 Master->>Replica1: Replication stream Replica1->>Replica1: Apply write Replica1-->>Master: ACK and Async to Replica2 Master->>Replica2: Replication stream Replica2->>Replica2: Apply write Replica2-->>Master: ACK end

Replica Promotion (Failover)

When master fails, cluster automatically promotes a replica to master.

  1. Failure Detection: Nodes ping each other via gossip. If majority marks master as FAIL, trigger failover
  2. Replica Election: Replicas with most up-to-date replication offset compete
  3. Vote Process: Replicas request votes from other masters
  4. Promotion: First replica to get majority votes becomes new master
  5. Topology Update: New master takes over hash slots, broadcasts via gossip
  6. Client Update: Clients receive MOVED redirects to new master

Replication Lag

Interview Tip: Discuss trade-offs between async (fast but data loss risk) vs sync replication (durable but slower). Redis prioritizes performance; use AOF + fsync for durability if needed.

6. Cluster Communication (Gossip Protocol)

Gossip Protocol Purpose

Gossip Message Format

// Heartbeat message every 1 second
{
  "sender": "node_id_1",
  "slots": [0, 1, 2, ..., 5460],  // Bitmap of owned slots
  "nodes": [
    {"id": "node_id_1", "ip": "10.0.0.1", "port": 7000, "flags": "master"},
    {"id": "node_id_2", "ip": "10.0.0.2", "port": 7001, "flags": "replica"},
    {"id": "node_id_3", "ip": "10.0.0.3", "port": 7002, "flags": "master,fail"}
  ],
  "epoch": 42  // Configuration version
}

Failure Detection

  1. PFAIL (Possible Fail): Node A doesn't receive heartbeat from Node B for NODE_TIMEOUT (default 15s). A marks B as PFAIL locally.
  2. FAIL (Definite Fail): If majority of masters mark B as PFAIL, they broadcast FAIL. All nodes mark B as FAIL.
  3. Failover Trigger: B's replicas detect FAIL, start election
graph TD A[Node A: Healthy] B[Node B: No heartbeat] C[Node C] D[Node D] A -->|No response 15s| B A -.->|Mark PFAIL| B C -.->|Mark PFAIL| B D -.->|Mark PFAIL| B A -->|Gossip: B is PFAIL| C C -->|Gossip: B is PFAIL| D D -->|Majority reached| Broadcast[Broadcast FAIL]

Split Brain Prevention

7. Client Routing and Redirects

Smart Client with Caching

Redis clients cache the slot-to-node mapping to route requests directly.

// Client-side slot mapping cache
slot_map = {
  0-5460: "10.0.0.1:7000",
  5461-10922: "10.0.0.2:7003",
  10923-16383: "10.0.0.3:7006"
}

// Client logic:
def get(key):
  slot = crc16(key) % 16384
  node = slot_map.lookup(slot)
  return node.get(key)

MOVED Redirect

Sent when client contacts wrong node for a slot (after resharding).

// Client sends to wrong node:
Client -> Master1: GET user:5678
Master1 -> Client: -MOVED 12000 10.0.0.3:7006

// Client updates cache and retries:
Client updates slot_map[12000] = "10.0.0.3:7006"
Client -> Master3: GET user:5678
Master3 -> Client: "Alice"

ASK Redirect

Sent during resharding when slot is being migrated. Temporary redirect.

// Slot 5000 is migrating from Master1 to Master2
Client -> Master1: GET key_in_slot_5000

// If key not yet migrated:
Master1 -> Client: value

// If key already migrated:
Master1 -> Client: -ASK 5000 10.0.0.2:7003

// Client sends ASKING + retry (doesn't update cache)
Client -> Master2: ASKING
Client -> Master2: GET key_in_slot_5000
Master2 -> Client: value

Difference: MOVED vs ASK

Aspect MOVED ASK
Meaning Slot permanently moved Slot being migrated
Client Action Update slot map cache Do NOT update cache
Retry Direct retry to new node Send ASKING flag first
Duration Permanent Temporary (until migration done)
Interview Tip: Mention CLUSTER SLOTS command - clients use it to fetch the full slot mapping at startup. Smart clients (like redis-py-cluster, Jedis) handle redirects transparently.

8. Eviction Policies

When to Evict

When memory usage reaches maxmemory limit, Redis evicts keys based on policy.

Eviction Policies

Policy Description Use Case
noeviction Return error on writes Never lose data
allkeys-lru Evict least recently used General purpose cache
allkeys-lfu Evict least frequently used Workloads with few hot keys
volatile-lru LRU among keys with TTL Mix of cache + persistent data
volatile-lfu LFU among keys with TTL Frequency-based TTL keys
volatile-ttl Evict shortest TTL first Expire-sensitive data
volatile-random Random among TTL keys Simple, fair eviction
allkeys-random Random among all keys Testing, uniform access

LRU Implementation Details

LFU Implementation

Interview Tip: Compare LRU vs LFU. LRU better for recency-sensitive workloads (session cache). LFU better when few keys are consistently hot (rate limiter counters).

9. Hot Key Mitigation

Hot Key Problem

A single key receiving millions of requests can overwhelm one master node (since Redis is single-threaded).

Mitigation Strategies

1. Local Client-Side Cache

// Local cache in application memory
local_cache = {}

def get(key):
  if key in local_cache and not expired(local_cache[key]):
    return local_cache[key].value

  value = redis_cluster.get(key)
  local_cache[key] = {"value": value, "ttl": 60}
  return value

Pros: No Redis load, sub-microsecond latency
Cons: Stale data, memory per app instance

2. Key Splitting (Hash Tag Trick)

// Split hot key across multiple slots
// Instead of: user:celebrity:followers -> single slot
// Use: user:celebrity:followers:{0}, user:celebrity:followers:{1}, ...

def incr_followers(celebrity_id):
  shard = random.randint(0, 9)  // 10 shards
  key = f"user:{celebrity_id}:followers:{{{shard}}}"
  redis.incr(key)

def get_followers(celebrity_id):
  total = 0
  for shard in range(10):
    key = f"user:{celebrity_id}:followers:{{{shard}}}"
    total += int(redis.get(key) or 0)
  return total

Pros: Distributes load across nodes
Cons: Aggregation overhead, not atomic

3. Read Replicas

// Route hot key reads to replicas (eventual consistency ok)
def get_read_heavy_key(key):
  slot = crc16(key) % 16384
  master = slot_map[slot]
  replicas = get_replicas(master)

  # Round-robin across replicas
  replica = replicas[random.choice(len(replicas))]
  return replica.get(key)

4. In-Memory Multi-Threaded Proxy

Interview Tip: Also discuss hot key detection - monitor via redis-cli --hotkeys or custom latency tracking. Set up alerts when a key exceeds QPS threshold.

10. Consistency Model

Single-Master Consistency

All writes for a hash slot go to one master - linearizable within a shard.

// Client 1 writes, Client 2 reads from same master:
Client1 -> Master1: SET x 10
Master1 -> Client1: OK

Client2 -> Master1: GET x
Master1 -> Client2: 10  // Guaranteed to see latest write

Eventual Consistency (Replicas)

Replicas lag behind master due to async replication.

// Write to master, read from replica:
Client1 -> Master1: SET x 10
Master1 -> Client1: OK

// Replication lag (e.g., 100ms)
Client2 -> Replica1: GET x
Replica1 -> Client2: (old value or key not found)

// After replication:
Client2 -> Replica1: GET x
Replica1 -> Client2: 10

Read-Your-Writes Consistency

Ensure user sees their own writes by routing their reads to master or using sticky sessions.

WAIT Command (Semi-Sync)

// Block until N replicas acknowledge write
SET key value
WAIT 2 1000  // Wait for 2 replicas, timeout 1000ms

// Use case: Critical writes (payment, inventory)
// Trade-off: Latency increase (p99 can double)

Cluster-Wide Consistency

Interview Tip: Compare with strong consistency systems (ZooKeeper, etcd). Redis trades strong consistency for extreme performance. For use cases requiring strong consistency, use Redis + distributed lock (Redlock) or different system.

11. Scalability and Resharding

Adding Nodes to Cluster

  1. Add Empty Node: Start new Redis instance, join to cluster
  2. Reshard Slots: Move some hash slots from existing masters to new node
  3. Migrate Keys: For each slot, iterate keys and move them
  4. Update Topology: Broadcast new slot mapping via gossip

Online Resharding Process

sequenceDiagram participant Admin participant Master1 participant Master4 participant Client Admin->>Master1: CLUSTER SETSLOT 5000 MIGRATING Master4 Admin->>Master4: CLUSTER SETSLOT 5000 IMPORTING Master1 loop For each key in slot 5000 Admin->>Master1: MIGRATE key to Master4 Master1->>Master4: Transfer key end Admin->>Master4: CLUSTER SETSLOT 5000 NODE Master4 Master4->>Master4: Gossip: slot 5000 -> Master4 Client->>Master1: GET key_in_slot_5000 Master1-->>Client: ASK 5000 Master4 Client->>Master4: ASKING + GET key

Resharding Commands

// Step 1: Mark slot as migrating
redis-cli --cluster reshard 127.0.0.1:7000
  --cluster-from node_id_1
  --cluster-to node_id_4
  --cluster-slots 1000

// Step 2: Migrate keys
CLUSTER GETKEYSINSLOT slot count  // Get keys in slot
MIGRATE target_ip target_port key 0 timeout  // Move key

// Step 3: Finalize
CLUSTER SETSLOT slot NODE node_id_4  // Transfer ownership

Handling Resharding in Clients

Removing Nodes

  1. Reshard slots away from node to be removed
  2. Wait for all slots to be empty (0 keys)
  3. Remove node from cluster: CLUSTER FORGET node_id
  4. Shutdown node

Scaling Reads vs Writes

Workload Scaling Strategy
Read-Heavy Add more replicas per master (2 -> 5 replicas)
Route reads to replicas
Write-Heavy Add more master nodes (shards)
Reshard to distribute write load
Balanced Add master+replica pairs
Reshard evenly across new masters

Monitoring and Observability

Interview Tip: Discuss trade-offs of pre-sharding (start with many nodes) vs dynamic sharding (reshard as needed). Pre-sharding avoids resharding but wastes resources. Dynamic sharding efficient but complex.

Summary

Designing a distributed cache like Redis Cluster requires careful consideration of:

Redis Cluster achieves sub-millisecond latency at massive scale by prioritizing performance over strong consistency and using specialized data structures optimized for in-memory operations.