Functional Requirements

Requirement	Description
GET/SET/DELETE	Basic key-value operations with sub-millisecond latency
TTL (Time-to-Live)	Keys expire automatically after a configurable duration
Pub-Sub	Publish/subscribe messaging for real-time event notifications
Transactions	Multi-key atomic operations (EXEC, MULTI, WATCH)
Data Structures	Rich types: strings, hashes, lists, sets, sorted sets, streams
Batch Operations	Pipeline multiple commands in a single round-trip
Keyspace Notifications	Notify clients when keys are created, expired, or deleted

Non-Functional Requirements

Requirement	Target	Rationale
Sub-millisecond Latency	p99 < 1ms	Cache must be faster than the database it accelerates
High Availability	99.99% uptime	Cache outage should not cascade to dependent services
Horizontal Scaling	Linear throughput with nodes	Must handle 1M+ ops/sec across cluster
Fault Tolerance	Survive N-1 node failures per shard	No data loss on single node failure
Data Durability	Optional, configurable	Some use cases need persistence, others don't
Memory Efficiency	Minimal overhead per key	Maximize useful data per GB of RAM

Core Architecture

┌──────────────────────────────────────────────────────────┐
│                    Client Applications                     │
└──────────────┬───────────────────┬──────────────────────┘
               │                   │
       ┌───────▼───────┐   ┌──────▼───────┐
       │  Client SDK   │   │  Client SDK  │
       │  (Connection  │   │  (Connection │
       │   Pool, Hash  │   │   Pool)      │
       │   Routing)    │   │              │
       └───────┬───────┘   └──────┬───────┘
               │                  │
               ▼                  ▼
┌──────────────────────────────────────────────────────────┐
│              Cache Cluster (N nodes)                      │
│                                                          │
│  ┌──────────┐  ┌──────────┐  ┌──────────┐              │
│  │ Shard 0  │  │ Shard 1  │  │ Shard 2  │   ...        │
│  │ ┌──────┐ │  │ ┌──────┐ │  │ ┌──────┐ │              │
│  │ │Primary│ │  │ │Primary│ │  │ │Primary│ │              │
│  │ └──┬───┘ │  │ └──┬───┘ │  │ └──┬───┘ │              │
│  │    │     │  │    │     │  │    │     │              │
│  │ ┌──▼───┐ │  │ ┌──▼───┐ │  │ ┌──▼───┐ │              │
│  │ │Replica│ │  │ │Replica│ │  │ │Replica│ │              │
│  │ └──────┘ │  │ └──────┘ │  │ └──────┘ │              │
│  └──────────┘  └──────────┘  └──────────┘              │
│                                                          │
│  ┌──────────────────────────────────────┐              │
│  │    Cluster Manager (Sentinel/Raft)   │              │
│  │    - Failure detection                │              │
│  │    - Automatic failover               │              │
│  │    - Slot rebalancing                 │              │
│  └──────────────────────────────────────┘              │
└──────────────────────────────────────────────────────────┘
               │
       ┌───────▼───────┐
       │ Persistence   │
       │ Layer (RDB/   │
       │ AOF/Hybrid)   │
       └───────────────┘

Component Responsibilities

Component	Role
Client SDK	Connection pooling, consistent hash routing to correct shard, pipelining, retry logic
Cache Nodes	Store data, handle read/write commands, manage local memory
Shard	A group of primary + replica nodes holding a partition of the total dataset
Cluster Manager	Detects node failures, triggers failover, rebalances slots across shards
Persistence Layer	Optional RDB snapshots and/or AOF for durability across restarts

Technology Choices

Component	Option A	Option B	Trade-off
Cache Engine	Redis	Memcached	Redis: richer data structures, persistence. Memcached: simpler, multi-threaded
Partitioning	Redis Cluster (16384 slots)	Client-side consistent hashing	Cluster: managed by server. Client-side: simpler but manual
Replication	Async primary-replica	Sync (WAIT command)	Async: faster. Sync: stronger consistency
Failover	Redis Sentinel	Raft-based (etcd)	Sentinel: Redis-native. Raft: more robust consensus
Persistence	RDB + AOF hybrid	RDB only	Hybrid: best durability. RDB: simpler, faster restarts

Key Design Decisions:

1. Redis over Memcached: Redis provides richer data structures (sorted sets, hashes, streams), persistence, pub-sub, and built-in clustering. Memcached is simpler but lacks these features.
2. Async replication: Strong consistency (WAIT command) doubles latency. Most cache use cases tolerate eventual consistency.
3. 16384 slots: Redis Cluster uses 16384 hash slots for partitioning. This number is a balance between granularity and memory overhead.
4. Hybrid persistence: RDB snapshots for fast restarts + AOF for durability. Configurable per use case.

Consistent Hashing (Traditional)

       Hash Ring (0 to 2^32 - 1)

              Node A (hash=0x1000)
                  ╱    \
                ╱        \
              ╱            \
    Node D ──              ── Node B
   (0xF000)                  (0x4000)
              ╲            ╱
                ╲        ╱
                  ╲    ╱
              Node C (0x8000)

Key "user:123" → hash = 0x3000 → maps to Node B (next clockwise)
Key "order:456" → hash = 0x9000 → maps to Node C

Problem: Simple consistent hashing leads to uneven distribution. Virtual nodes solve this:

Each physical node gets V virtual nodes (e.g., V = 150):

Node A: hash("A-0"), hash("A-1"), ..., hash("A-149")
Node B: hash("B-0"), hash("B-1"), ..., hash("B-149")
Node C: hash("C-0"), hash("C-1"), ..., hash("C-149")

Result: ~均匀 distribution across all nodes

Redis Cluster Slot-Based Partitioning

Redis Cluster uses a fixed number of 16384 hash slots for more predictable distribution:

Slot Calculation:
  slot = CRC16(key) mod 16384

Example:
  CRC16("user:123") = 5498 → slot 5498
  CRC16("order:456") = 12003 → slot 12003

Slot Distribution Across Shards:
  Shard 0: slots 0 - 5460      (5461 slots)
  Shard 1: slots 5461 - 10922  (5462 slots)
  Shard 2: slots 10923 - 16383 (5461 slots)

Why 16384 slots?

• Enough granularity for balanced distribution across up to 1000 nodes
• Small enough for efficient slot migration (each node broadcasts its slot map)
• Power of 2 minus something: allows efficient bitmask operations

Hash Tagging for Multi-Key Operations

When you need atomic multi-key operations, use hash tags to force keys to the same slot:

Without hash tag:
  SET user:123 → slot 5498 (Shard 0)
  SET user:123:profile → slot 8201 (Shard 2)  ← Different shard!
  MULTI/EXEC won't work across shards

With hash tag:
  SET {user:123}:name → slot 5498 (Shard 0)
  SET {user:123}:profile → slot 5498 (Shard 0)  ← Same shard!
  MULTI/EXEC works atomically

Replication Architecture

Shard 0:
┌─────────────────┐     ┌─────────────────┐
│   Primary Node   │────▶│  Replica Node    │
│   (Slots 0-5460)│     │  (Read-only)     │
│                  │◀────│                  │
│  - All writes    │     │  - Receives RDB  │
│  - Read ops      │     │    snapshots     │
│  - Propagates    │     │  - AOF replay    │
│    to replicas   │     │  - Can serve     │
│                  │     │    read replicas │
└─────────────────┘     └─────────────────┘
        │
        │ (on failure)
        ▼
┌─────────────────┐
│  Sentinel/Raft   │
│  promotes replica│
│  to primary      │
└─────────────────┘

Async Replication Flow

Client WRITE to Primary:
  1. Primary receives SET key value
  2. Primary writes to local memory
  3. Primary returns OK to client (doesn't wait for replicas)
  4. Primary asynchronously propagates write to replicas
  5. Replica receives and applies write

Timeline:
  t=0ms:  Client sends SET to Primary
  t=0.1ms: Primary applies write, returns OK
  t=0.2ms: Replica receives replication stream
  t=0.3ms: Replica applies write
  
  Between t=0.1ms and t=0.3ms: replica is stale

Strong Consistency with WAIT

Client can request synchronous confirmation:
  SET key value
  WAIT 1 500  # Wait for 1 replica to confirm, timeout 500ms

Timeline:
  t=0ms:    Client sends SET to Primary
  t=0.1ms:  Primary applies write
  t=0.1ms:  Primary propagates to replica
  t=0.3ms:  Replica confirms
  t=0.3ms:  Primary returns OK to client
  
  Trade-off: +0.2ms latency for strong consistency

Failover Mechanism

Failure Detection (Gossip Protocol)

Every node periodically:
  1. Sends PING to random subset of nodes
  2. Expects PONG within cluster-node-timeout (e.g., 15 seconds)
  3. If no PONG: mark node as PFAIL (possible failure)
  4. If majority agrees node is PFAIL: mark as FAIL
  5. If primary is FAIL: initiate failover

Gossip Protocol:
  - Each node shares its view of cluster state with random peers
  - Information spreads: O(log N) rounds to reach all nodes
  - No single point of failure for detection

Automatic Failover Sequence

1. Primary P0 fails (detected by gossip)
2. Replica R0 is elected as new primary by sentinel/quorum
3. R0 promotes itself: SLAVEOF NO ONE
4. R0 takes ownership of P0's slots
5. Other nodes update their slot maps
6. Clients receive MOVED redirect to new primary
7. Old P0's data (if it comes back) is discarded or re-synced as replica

Failover time: typically 5-15 seconds

Slot Migration (Rebalancing)

When adding/removing nodes, slots must be migrated:

Before: Shard 0 (slots 0-5460), Shard 1 (slots 5461-10922)
After adding Shard 2:

1. Shard 1 enters IMPORTING state for new slots
2. Shard 0 enters MIGRATING state for slots being moved
3. Migrate keys one by one using MIGRATE command
4. Update slot ownership across cluster
5. Clear MIGRATING/IMPORTING states

Migration is online - reads/writes continue during migration

Data Model (Internal)

# Slot ownership map (each node maintains this)
node_0 slots: 0-5460
node_1 slots: 5461-10922
node_2 slots: 10923-16383

# Replication info
node_0 replicas: [node_3]
node_1 replicas: [node_4]
node_2 replicas: [node_5]

# Gossip state (shared between nodes)
{
  "node_id": "abc123",
  "ip": "10.0.0.1",
  "port": 6379,
  "slots": "0-5460",
  "replicas": ["def456"],
  "epoch": 42,
  "state": "ok"
}

Cache Patterns

Cache-Aside (Lazy Loading)

Most common pattern. Application manages cache explicitly.

Read:
  1. App checks cache for key
  2. Cache HIT → return cached value
  3. Cache MISS → query database
  4. Store result in cache with TTL
  5. Return value

Write:
  1. App writes to database
  2. App invalidates (deletes) cache key
  3. Next read repopulates cache

Pros: Simple, only caches what's requested, handles cold starts
Cons: Cache miss = 3 network calls (cache + db + cache write)

App ──▶ Cache (check) ──miss──▶ Database (query) ──▶ Cache (store) ──▶ Return
         │
         └──hit──▶ Return cached value

Read-Through

Cache itself manages loading from database.

Read:
  1. App requests key from cache
  2. Cache MISS → cache loads from DB automatically
  3. Cache stores result with TTL
  4. Returns value to app

Pros: App code is simpler (just reads cache)
Cons: Cache must know about DB, harder to customize loading logic

Write-Through

All writes go through cache to database synchronously.

Write:
  1. App writes to cache
  2. Cache synchronously writes to database
  3. Returns success to app

Pros: Cache and DB always consistent
Cons: Write latency = cache + DB latency, write amplification

Write-Behind (Write-Back)

Writes go to cache first, DB updated asynchronously.

Write:
  1. App writes to cache
  2. Cache returns success immediately
  3. Cache asynchronously batches writes to DB

Pros: Very fast writes, batch DB updates
Cons: Risk of data loss if cache crashes before DB sync
Use cases: Session data, analytics counters, non-critical writes

Pattern Comparison

Pattern	Read Latency	Write Latency	Consistency	Data Loss Risk	Complexity
Cache-Aside	Miss: 3 RTTs	Write + invalidate	Eventual	Low	Low
Read-Through	Miss: 2 RTTs	Write + invalidate	Eventual	Low	Medium
Write-Through	Read: 1 RTT	Write: 2 RTTs	Strong	None	Medium
Write-Behind	Read: 1 RTT	Write: 1 RTT	Eventual	High	High

Eviction Policies

When memory is full, the cache must evict keys to make room:

Policy	Description	Best For	Memory Overhead
LRU	Least Recently Used - evict key accessed longest ago	General purpose, temporal locality	Low (1 bit per key)
LFU	Least Frequently Used - evict least accessed key	Frequency-based workloads	Medium (counter per key)
TTL-based	Evict keys that have expired	Time-sensitive data	None (natural expiry)
Random	Evict random key	Uniform access patterns	None
No-eviction	Reject writes when full (return OOM)	When data must not be lost	None
Allkeys-LRU	LRU across all keys (not just expiring)	Mixed TTL workloads	Low
Volatile-LRU	LRU only among keys with TTL set	Protect permanent keys	Low

Redis eviction configuration:
  maxmemory 4gb
  maxmemory-policy allkeys-lru

Eviction sample size:
  Redis checks 5 random keys, evicts the one with oldest access time
  (approximation of true LRU, much cheaper than tracking full access order)

LRU vs LFU Decision

Workload Analysis:

  If access pattern has TEMPORAL LOCALITY (recently accessed = likely accessed again):
    → Use LRU
    Example: User session data, recently viewed products

  If access pattern has FREQUENCY LOCALITY (frequently accessed = likely accessed again):
    → Use LFU
    Example: Popular product catalog, reference data

  If access pattern is UNIFORM (all keys equally likely):
    → Use Random or FIFO
    Example: Rate limiting counters, temporary tokens

Consistency Guarantees

Eventual Consistency (Default)

Replica lag timeline:
  t=0ms:   Primary: SET user:123 = {name: "Alice"}
  t=0.1ms: Primary returns OK to client
  t=0.2ms: Replica receives update
  t=0.3ms: Replica applies update
  
  Between t=0.1ms and t=0.3ms:
    Read from primary: {name: "Alice"}  ← correct
    Read from replica: {name: "Bob"}    ← stale (old value)

For most cache use cases: acceptable
  - Stale data is temporary
  - Cache miss falls back to DB (source of truth)

Strong Consistency with WAIT

When consistency matters:
  SET session:abc {data} 
  WAIT 1 500  # Block until 1 replica confirms
  
  Now reading from any node returns {data}
  
  Trade-off:
    Without WAIT: 0.1ms write latency
    With WAIT:    0.3ms write latency
    
  Use for: Financial data, inventory counts, leaderboards

Consistency Patterns

Pattern	Implementation	Use Case
Read-after-write	Read from primary after write	User profile updates
Session stickiness	Route same user to same primary	Session data
Lease-based	Writer holds lease, others read stale	Leader election
Version vectors	Track vector clocks per key	Conflict resolution

Persistence Options

RDB Snapshots

Mechanism: Fork child process, write entire dataset to disk

Schedule: save 900 1      # After 900s if 1 key changed
          save 300 10     # After 300s if 10 keys changed
          save 60 10000   # After 60s if 10K keys changed

Pros:
  - Compact file, fast restart
  - Minimal performance impact during snapshot (copy-on-write)
  - Good for backups

Cons:
  - Data loss between snapshots (up to last snapshot)
  - Fork can cause latency spike with large datasets
  - Large datasets take time to snapshot

AOF (Append-Only File)

Mechanism: Log every write command to file

fsync policy:
  appendfsync always   # fsync after every write (safest, slowest)
  appendfsync everysec # fsync once per second (balanced)
  appendfsync no       # let OS decide (fastest, riskiest)

AOF Rewrite:
  - Periodically rewrite AOF to remove redundant commands
  - E.g., SET key1, SET key1, SET key1 → only keep final SET key1
  - Reduces file size, speeds up restart

Pros:
  - Better durability than RDB
  - Configurable durability level
  - Human-readable log

Cons:
  - Larger files than RDB
  - Slower restart (must replay commands)

Hybrid Persistence (Redis 4.0+)

Combine RDB + AOF:
  1. RDB snapshot provides fast restart baseline
  2. AOF captures writes since last RDB snapshot
  3. On restart: load RDB, then replay AOF

Recovery time: RDB load (fast) + AOF replay (incremental)
Durability: Only lose data from last AOF fsync (typically 1 second)

Memory Management

Redis Memory Architecture:

  ┌─────────────────────────────────────┐
  │            Redis Process             │
  │                                      │
  │  ┌─────────────────────────────┐    │
  │  │      jemalloc allocator     │    │
  │  │  ┌─────┐ ┌─────┐ ┌─────┐  │    │
  │  │  │Key1 │ │Key2 │ │Key3 │  │    │
  │  │  └─────┘ └─────┘ └─────┘  │    │
  │  │  ┌─────┐ ┌─────┐         │    │
  │  │  │Key4 │ │Key5 │         │    │
  │  │  └─────┘ └─────┘         │    │
  │  └─────────────────────────────┘    │
  │                                      │
  │  maxmemory: 4GB                      │
  │  used_memory: 3.2GB (80%)            │
  │  mem_fragmentation_ratio: 1.1        │
  └─────────────────────────────────────┘

Metric	Description	Healthy Range
used_memory	Actual data + overhead	< maxmemory
mem_fragmentation_ratio	RSS / used_memory	1.0 - 1.5
mem_allocator	Memory allocator used	jemalloc (default)
maxmemory_policy	Eviction policy	Based on workload

Fragmentation:

• Ratio > 1.5: memory is fragmented, consider restarting with RDB restore
• Ratio < 1.0: using swap, critical performance issue
• jemalloc reduces fragmentation vs glibc malloc

Client-Side Design

Connection Pooling

Client maintains pool of connections to each node:

  connections_per_node = 5
  total_connections = nodes × connections_per_node
  
  Connection lifecycle:
    1. Create connections on client startup
    2. Reuse connections across requests (no TCP overhead)
    3. Health check idle connections every 30s
    4. Replace failed connections automatically

Benefits:
  - Avoid TCP handshake overhead (~1ms per connection)
  - Limit concurrent connections per node
  - Automatic failover to healthy connections

Pipeline & Batch Operations

Without pipeline (3 round-trips):
  Client → SET key1 ──▶ Node
  Client ◀── OK ────── Node
  Client → SET key2 ──▶ Node
  Client ◀── OK ────── Node
  Client → SET key3 ──▶ Node
  Client ◀── OK ────── Node
  Total: 3 RTTs ≈ 3ms

With pipeline (1 round-trip):
  Client → [SET key1, SET key2, SET key3] ──▶ Node
  Client ◀── [OK, OK, OK] ─────────────────── Node
  Total: 1 RTT ≈ 1ms

MGET for batch reads:
  MGET key1 key2 key3 → [val1, val2, val3]
  Single RTT instead of 3

Client-Side Retry Strategy

Retry flow:
  1. Send command to target node
  2. If MOVED error → update slot map, retry to new node
  3. If ASK error → retry to specified node with ASKING flag
  4. If connection error → retry to next node in pool (up to 3 times)
  5. If all retries fail → return error to application

Timeout settings:
  - Connect timeout: 200ms
  - Read timeout: 500ms
  - Write timeout: 500ms

Complete Request Flow

1. Client: GET user:123
   │
   ▼
2. Client SDK computes slot: CRC16("user:123") mod 16384 = 5498
   │
   ▼
3. Client SDK looks up slot map → Shard 1 (Primary)
   │
   ▼
4. Client sends GET to Shard 1 Primary
   │
   ├── HIT: Return value directly
   │
   └── MISS:
       │
       ├── App queries database
       │
       ├── App stores in cache: SET user:123 {data} EX 3600
       │
       │   (Redis:
       │     1. Compute slot for key
       │     2. Route to Shard 1 Primary
       │     3. Store in memory with TTL
       │     4. Async replicate to replica
       │     5. Return OK)
       │
       └── Return value to app

This design provides sub-millisecond latency, linear horizontal scaling, and fault tolerance suitable for Amazon-scale caching workloads.