Difficulty: Advanced
Design a distributed caching system like Redis Cluster or Memcached. How would you handle data partitioning, replication, and eviction?
A distributed cache stores data across multiple nodes to provide fast access, horizontal scalability, and fault tolerance.
Core design decisions: 1. Partitioning: How to distribute keys across nodes (consistent hashing) 2. Replication: How many copies of each key (primary + replicas) 3. Eviction: What to remove when memory is full (LRU, LFU, TTL) 4. Consistency: How to keep replicas in sync (async replication, quorum reads) 5. Failure handling: What happens when a node dies (failover, data redistribution)
Redis Cluster approach: - 16384 hash slots distributed across nodes - Each key maps to a slot: CRC16(key) mod 16384 - Each slot has a primary and one or more replicas - Automatic failover: replica promoted to primary on node failure
// Distributed cache node
class CacheNode {
constructor(maxMemory = 1024 * 1024 * 1024) { // 1GB default
this.store = new Map();
this.maxMemory = maxMemory;
this.usedMemory = 0;
this.accessOrder = new Map(); // For LRU tracking
}
get(key) {
const entry = this.store.get(key);
if (!entry) return null;
// Check TTL
if (entry.expiresAt && entry.expiresAt < Date.now()) {
this.delete(key);
return null;
}
// Update LRU access time
this.accessOrder.set(key, Date.now());
return entry.value;
}
set(key, value, ttlSeconds) {
const size = this.estimateSize(key, value);
// Evict if necessary
while (this.usedMemory + size > this.maxMemory) {
this.evictLRU();
}
const entry = {
value,
size,
expiresAt: ttlSeconds ? Date.now() + ttlSeconds * 1000 : null,
createdAt: Date.now()
};
// Update memory tracking
if (this.store.has(key)) {
this.usedMemory -= this.store.get(key).size;
}
this.store.set(key, entry);
this.usedMemory += size;
this.accessOrder.set(key, Date.now());
return true;
}
delete(key) {
const entry = this.store.get(key);
if (entry) {
this.usedMemory -= entry.size;
this.store.delete(key);
this.accessOrder.delete(key);
}
}
evictLRU() {
let oldestKey = null;
let oldestTime = Infinity;
for (const [key, time] of this.accessOrder) {
if (time < oldestTime) {
oldestTime = time;
oldestKey = key;
}
}
if (oldestKey) this.delete(oldestKey);
}
estimateSize(key, value) {
return key.length + JSON.stringify(value).length;
}
}Each cache node manages its own memory with LRU eviction. When memory is full, the least recently accessed entry is removed. TTL-based expiry runs lazily on access (no background scanner needed for simple cases).
// Distributed cache cluster using consistent hashing
class CacheCluster {
constructor() {
this.hashRing = new ConsistentHash(150); // 150 virtual nodes
this.nodes = new Map(); // nodeId -> CacheNode
this.replicationFactor = 2; // primary + 1 replica
}
addNode(nodeId, node) {
this.nodes.set(nodeId, node);
this.hashRing.addServer(nodeId);
}
removeNode(nodeId) {
this.hashRing.removeServer(nodeId);
this.nodes.delete(nodeId);
// Keys naturally redistribute to remaining nodes
// on next cache miss + refill
}
// Get the primary and replica nodes for a key
getNodesForKey(key) {
const allNodes = this.hashRing.getServerList(key, this.replicationFactor);
return {
primary: allNodes[0],
replicas: allNodes.slice(1)
};
}
async get(key) {
const { primary } = this.getNodesForKey(key);
const node = this.nodes.get(primary);
return node.get(key);
}
async set(key, value, ttl) {
const { primary, replicas } = this.getNodesForKey(key);
// Write to primary
const primaryNode = this.nodes.get(primary);
primaryNode.set(key, value, ttl);
// Async replication to replicas
for (const replicaId of replicas) {
const replicaNode = this.nodes.get(replicaId);
if (replicaNode) {
replicaNode.set(key, value, ttl); // Fire and forget
}
}
return true;
}
async delete(key) {
const { primary, replicas } = this.getNodesForKey(key);
this.nodes.get(primary)?.delete(key);
for (const replicaId of replicas) {
this.nodes.get(replicaId)?.delete(key);
}
}
}
// Usage
const cluster = new CacheCluster();
cluster.addNode('node-1', new CacheNode());
cluster.addNode('node-2', new CacheNode());
cluster.addNode('node-3', new CacheNode());
await cluster.set('user:123', userData, 300);
const user = await cluster.get('user:123');The cluster uses consistent hashing to distribute keys across nodes. Each key is replicated to multiple nodes for fault tolerance. When a node fails, its keys are still available on replicas.
// Cache warming: pre-populate cache on deployment
class CacheWarmer {
async warmUp(cluster) {
console.log('Warming cache...');
// 1. Load hot keys from access logs
const hotKeys = await db.query(`
SELECT cache_key, access_count
FROM cache_access_log
WHERE timestamp > NOW() - INTERVAL '1 hour'
GROUP BY cache_key
ORDER BY SUM(access_count) DESC
LIMIT 10000
`);
// 2. Pre-populate cache
for (const { cache_key } of hotKeys) {
const value = await fetchFromSource(cache_key);
if (value) {
await cluster.set(cache_key, value, 3600);
}
}
console.log(`Warmed ${hotKeys.length} keys`);
}
}
// Monitoring metrics
class CacheMonitor {
constructor(cluster) {
this.hits = 0;
this.misses = 0;
this.evictions = 0;
}
recordHit() { this.hits++; }
recordMiss() { this.misses++; }
recordEviction() { this.evictions++; }
getStats() {
const total = this.hits + this.misses;
return {
hitRate: total > 0 ? (this.hits / total * 100).toFixed(2) + '%' : 'N/A',
missRate: total > 0 ? (this.misses / total * 100).toFixed(2) + '%' : 'N/A',
totalRequests: total,
evictions: this.evictions,
memoryUsage: this.getMemoryUsage()
};
}
getMemoryUsage() {
let total = 0;
let used = 0;
for (const node of cluster.nodes.values()) {
total += node.maxMemory;
used += node.usedMemory;
}
return {
used: `${(used / 1e9).toFixed(2)}GB`,
total: `${(total / 1e9).toFixed(2)}GB`,
percentage: `${(used / total * 100).toFixed(1)}%`
};
}
}
// Key metrics to alert on:
// - Hit rate < 80% -> cache is not effective
// - Memory > 90% -> risk of excessive evictions
// - Eviction rate spike -> possible cache thrashing
// - Latency p99 > 10ms -> network or memory issuesCache warming pre-loads frequently accessed data after a deployment or node restart, avoiding a thundering herd of cache misses. Monitoring hit rate, memory usage, and eviction rate ensures the cache is performing effectively.
Distributed Cache, Consistent Hashing, Eviction Policies, Cache Coherence, Redis Cluster