Design a Distributed Cache

Java — Consistent hash ring with virtual nodes

// Simplified consistent hash ring — illustrative, not Redis Cluster internals
import java.util.SortedMap;
import java.util.TreeMap;
import java.security.MessageDigest;

public class ConsistentHashRing {

    private static final int VIRTUAL_NODES = 150;
    private final SortedMap<Long, String> ring = new TreeMap<>();

    public void addNode(String node) {
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            long hash = hash(node + "#" + i);
            ring.put(hash, node);
        }
    }

    public void removeNode(String node) {
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            ring.remove(hash(node + "#" + i));
        }
    }

    /** Returns the node responsible for the given key. */
    public String getNode(String key) {
        if (ring.isEmpty()) throw new IllegalStateException("No nodes in ring");
        long hash = hash(key);
        SortedMap<Long, String> tail = ring.tailMap(hash);
        // wrap around to the start of the ring if no node is clockwise
        long position = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(position);
    }

    private long hash(String input) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(input.getBytes());
            // use first 8 bytes as a long
            long h = 0;
            for (int i = 0; i < 8; i++) {
                h = (h << 8) | (digest[i] & 0xFF);
            }
            return h;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

Java — LinkedHashMap LRU and Caffeine L1 cache

// Java LinkedHashMap as a simple LRU cache — mirrors Redis LRU eviction semantics
import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    /**
     * @param capacity maximum number of entries before LRU eviction kicks in
     */
    public LruCache(int capacity) {
        // accessOrder=true: iteration order is LRU order (least recently accessed first)
        super(capacity, 0.75f, /* accessOrder= */ true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // LinkedHashMap calls this after every put(); return true to evict eldest
        return size() > capacity;
    }

    // Usage example — thread-safe wrapper
    public static <K, V> Map<K, V> threadSafe(int capacity) {
        return java.util.Collections.synchronizedMap(new LruCache<>(capacity));
    }
}

// Caffeine (production-grade LRU/LFU in-process cache)
import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;

Cache<String, String> l1Cache = Caffeine.newBuilder()
    .maximumSize(10_000)          // LFU eviction via TinyLFU algorithm
    .expireAfterWrite(Duration.ofSeconds(30))
    .recordStats()                // exposes hit/miss ratio via cache.stats()
    .build();

Java — Mutex lock and Probabilistic Early Recomputation

// Mutex lock — only one thread fetches from DB on cache miss
@Service
public class CacheService {

    private static final Duration LOCK_TTL = Duration.ofSeconds(5);
    private static final Duration CACHE_TTL = Duration.ofMinutes(10);
    private static final String LOCK_PREFIX = "lock:";

    private final RedisTemplate<String, String> redis;
    private final UserRepository db;

    public String getUser(String userId) {
        String cacheKey = "user:" + userId;
        String cached = redis.opsForValue().get(cacheKey);
        if (cached != null) return cached;

        // Attempt to acquire a distributed mutex
        String lockKey = LOCK_PREFIX + cacheKey;
        Boolean acquired = redis.opsForValue()
            .setIfAbsent(lockKey, "1", LOCK_TTL);

        if (Boolean.TRUE.equals(acquired)) {
            try {
                // Double-check after acquiring lock — another thread may have populated
                cached = redis.opsForValue().get(cacheKey);
                if (cached != null) return cached;

                String value = db.findById(userId).orElseThrow();
                redis.opsForValue().set(cacheKey, value, CACHE_TTL);
                return value;
            } finally {
                redis.delete(lockKey);
            }
        }

        // Could not acquire lock — return stale value or wait briefly
        // For simplicity, fall back to DB directly here (acceptable under lock contention)
        return db.findById(userId).orElseThrow();
    }
}

// Probabilistic Early Recomputation (PER) — background refresh before expiry
public String getUserWithPER(String userId) {
    String cacheKey = "user:" + userId;
    CachedValue<String> cached = redis.opsForValue().get(cacheKey); // value + embedded expiresAt
    if (cached == null) return fetchAndCache(userId, cacheKey);

    double beta = 1.0;
    double remainingTtl = cached.expiresAt() - System.currentTimeMillis() / 1000.0;
    // Probabilistically decide whether to refresh early
    if (-beta * Math.log(Math.random()) > remainingTtl) {
        CompletableFuture.runAsync(() -> fetchAndCache(userId, cacheKey)); // async, non-blocking
    }
    return cached.value();
}

Java — Lettuce Cluster client with replica reads and hash tags

// Lettuce Redis Cluster client — Spring Boot configuration
import io.lettuce.core.cluster.RedisClusterClient;
import io.lettuce.core.cluster.api.StatefulRedisClusterConnection;
import io.lettuce.core.cluster.api.sync.RedisAdvancedClusterCommands;

@Configuration
public class RedisClusterConfig {

    @Bean
    public RedisClusterClient redisClusterClient() {
        // Provide seed nodes — Lettuce discovers the full topology via CLUSTER INFO
        return RedisClusterClient.create(List.of(
            RedisURI.create("redis://node-a:6379"),
            RedisURI.create("redis://node-b:6379"),
            RedisURI.create("redis://node-c:6379")
        ));
    }

    @Bean
    public StatefulRedisClusterConnection<String, String> clusterConnection(
            RedisClusterClient client) {
        StatefulRedisClusterConnection<String, String> conn = client.connect();
        // Allow reads from replicas — eventual consistency, higher read throughput
        conn.setReadFrom(ReadFrom.REPLICA_PREFERRED);
        return conn;
    }
}

// Using hash tags to co-locate related keys on the same slot
// Both keys hash using only the content inside {}, i.e. "user:42"
// → guaranteed same slot → safe to use MGET or pipelined operations
String profileKey = "{user:42}:profile";
String cartKey    = "{user:42}:cart";
String sessionKey = "{user:42}:session";

RedisAdvancedClusterCommands<String, String> commands = connection.sync();
List<KeyValue<String, String>> values = commands.mget(profileKey, cartKey, sessionKey);

Java — Cache-aside, write-through, and write-behind patterns

// Cache-aside pattern — standard Spring Boot service
@Service
public class ProductService {

    private static final Duration TTL = Duration.ofMinutes(15);
    private final RedisTemplate<String, Product> redis;
    private final ProductRepository db;

    public Product getProduct(String productId) {
        String key = "product:" + productId;

        // 1. Cache hit
        Product cached = (Product) redis.opsForValue().get(key);
        if (cached != null) return cached;

        // 2. Cache miss — fetch from DB
        Product product = db.findById(productId)
            .orElseThrow(() -> new ProductNotFoundException(productId));

        // 3. Populate cache
        redis.opsForValue().set(key, product, TTL);
        return product;
    }

    // Write-through — keep cache consistent on every update
    public Product updateProduct(String productId, ProductUpdateRequest req) {
        Product product = db.save(db.findById(productId)
            .orElseThrow()
            .applyUpdate(req));

        // Synchronously update cache — never serve stale data after a write
        redis.opsForValue().set("product:" + productId, product, TTL);
        return product;
    }
}

// Write-behind — fire-and-forget DB flush for counters
@Service
public class ViewCountService {

    private final RedisTemplate<String, Long> redis;
    private final ApplicationEventPublisher events;

    public void recordView(String productId) {
        String key = "views:" + productId;
        Long count = redis.opsForValue().increment(key); // in-memory, sub-millisecond

        // Async flush to DB every 100 views or on a scheduled task
        if (count != null && count % 100 == 0) {
            events.publishEvent(new FlushViewCountEvent(productId, count));
        }
    }
}