Distributed Cache

Consistent Hashing

Consistent hashing distributes keys across cache nodes while minimizing key redistribution when nodes are added or removed.

Problem with Simple Hashing

Simple Hashing (mod N):

node = hash(key) % num_nodes

Problem: Adding/removing a node rehashes ALL keys!

Before: node = hash(key) % 4 → node 2
After:  node = hash(key) % 5 → node 4 (different!)

Result: Massive cache miss spike during scaling

Consistent Hashing Solution

Consistent Hash Ring:

        Node A
         |
    ----+----+----
   /     |    |    \
  /      |    |     \
Node D   |    |   Node B
  \\      |    |     /
   \\     |    |    /
    ----+----+----
         |
        Node C

Keys are mapped to positions on the ring.
Keys go to the next node clockwise.

Adding Node E between B and C:
- Only keys between B and E move to E
- All other keys stay put!

Implementation

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, virtual_nodes=150):
        self.ring = {}
        self.sorted_keys = []
        self.virtual_nodes = virtual_nodes
        
        if nodes:
            for node in nodes:
                self.add_node(node)
    
    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_node(self, node):
        """Add node with virtual nodes"""
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:v{i}"
            hash_val = self._hash(virtual_key)
            self.ring[hash_val] = node
            bisect.insort(self.sorted_keys, hash_val)
    
    def remove_node(self, node):
        """Remove node and its virtual nodes"""
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:v{i}"
            hash_val = self._hash(virtual_key)
            del self.ring[hash_val]
            self.sorted_keys.remove(hash_val)
    
    def get_node(self, key):
        """Get node for a key"""
        if not self.ring:
            return None
        
        hash_val = self._hash(key)
        idx = bisect.bisect_right(self.sorted_keys, hash_val)
        
        if idx >= len(self.sorted_keys):
            idx = 0
        
        return self.ring[self.sorted_keys[idx]]

# Usage
ring = ConsistentHashRing(['cache-1', 'cache-2', 'cache-3'])
node = ring.get_node('user:123')  # Returns cache-2
ring.add_node('cache-4')  # Only ~25% of keys redistributed

Virtual Nodes

Without Virtual Nodes:
- Uneven distribution possible
- Hot spots on some nodes

With Virtual Nodes (150 per physical node):
- Better distribution
- ~equal load across nodes
- Trade-off: More memory for ring lookup

Cache Replication

Replication copies cache data across multiple nodes for high availability and read scaling.

Replication Strategies

1. Master-Slave (Redis Default):

   [Master] ──replicate──→ [Slave 1]
      │                     [Slave 2]
      ↓
   Write Operations
   (slaves are read-only)

2. Multi-Master:

   [Master A] ←──sync──→ [Master B]
      ↓                      ↓
   [Slave A1]            [Slave B1]

3. Client-Side Replication:

   App writes to: Node A, Node B, Node C
   App reads from: Any node

Redis Replication

# Slave configuration
# redis.conf
replicaof 192.168.1.100 6379
masterauth your_password

# Check replication status
INFO replication

# Manual failover
CLUSTER FAILOVER

Replication Monitoring

class ReplicationMonitor:
    def __init__(self, redis_clients):
        self.masters = redis_clients
    
    def check_lag(self):
        """Check replication lag across all masters"""
        lags = {}
        for master_name, client in self.masters.items():
            info = client.info('replication')
            for slave in info.get('slaves', []):
                lag = slave.get('lag', 0)
                if lag > 10:  # Alert threshold
                    alert(f"High replication lag: {master_name} slave lag={lag}s")
                lags[f"{master_name}:{slave['ip']}"] = lag
        return lags

# Monitor replication health
monitor = ReplicationMonitor(redis_clients)
lags = monitor.check_lag()

Trade-offs

Strategy	Consistency	Availability	Performance
Async Replication	Eventual	High	Best
Sync Replication	Strong	Lower	Slower writes
Semi-Sync	bounded delay	High	Good

Cache Failure Handling

Failure Scenarios

1. Single Node Failure:
   - Cache miss spike
   - Need fallback mechanism

2. Network Partition:
   - Split-brain risk
   - Inconsistent data

3. Cluster Failure:
   - Complete cache outage
   - DB must handle all traffic

4. Cascading Failure:
   - Cache failure → DB overload → System failure

Failure Handling Patterns

class ResilientCache:
    def __init__(self, primary_cache, fallback_cache=None):
        self.primary = primary_cache
        self.fallback = fallback_cache
        self.circuit_breaker = CircuitBreaker(
            failure_threshold=5,
            recovery_timeout=30
        )
    
    def get(self, key):
        """Get with fallback"""
        try:
            if self.circuit_breaker.is_open:
                # Circuit open, use fallback
                return self._get_fallback(key)
            
            value = self.primary.get(key)
            self.circuit_breaker.record_success()
            return value
        except Exception as e:
            self.circuit_breaker.record_failure()
            return self._get_fallback(key)
    
    def _get_fallback(self, key):
        """Fallback to secondary cache or DB"""
        if self.fallback:
            return self.fallback.get(key)
        return db.query(key)  # Direct DB fallback
    
    def set(self, key, value, ttl=3600):
        """Write to both caches"""
        try:
            self.primary.set(key, value, ttl)
        except:
            pass  # Log but don't fail
        
        if self.fallback:
            try:
                self.fallback.set(key, value, ttl)
            except:
                pass

Circuit Breaker Integration

class CircuitBreaker:
    def __init__(self, failure_threshold=5, recovery_timeout=30):
        self.failure_threshold = failure_threshold
        self.recovery_timeout = recovery_timeout
        self.failure_count = 0
        self.last_failure_time = None
        self.state = 'closed'  # closed, open, half-open
    
    @property
    def is_open(self):
        if self.state == 'open':
            if time.time() - self.last_failure_time > self.recovery_timeout:
                self.state = 'half-open'
                return False
            return True
        return False
    
    def record_success(self):
        self.failure_count = 0
        self.state = 'closed'
    
    def record_failure(self):
        self.failure_count += 1
        self.last_failure_time = time.time()
        if self.failure_count >= self.failure_threshold:
            self.state = 'open'

Best Practices

1. Monitor cache health (hit ratio, latency, errors)
2. Implement circuit breakers to prevent cascading failures
3. Use fallback caches or direct DB access
4. Plan for cache warming after recovery
5. Test failure scenarios regularly