Cracking The Coding Interview Together – Problem 9.5: Distributed Cache

Picture this: you are sitting in a system design interview, and the interviewer throws a massive, open-ended scaling challenge your way. Imagine you are building a web server for a high-throughput search engine. Your system relies on 100 different machines working in parallel to respond to incoming search queries. Every single query involves heavy lifting—parsing, tokenization, index lookups, and ranking. If every query hits the underlying storage or index layer directly, your system will buckle under the load.

We need a caching mechanism. But we cannot just slap a local HashMap on each machine and call it a day. With 100 machines, we face the ghosts of distributed systems past: cache fragmentation, memory exhaustion, duplication, and node churn. Today, we are going to break down how to design a resilient, high-performance distributed caching mechanism from the ground up. Let's dive in.

Problem Statement

Our operational goal is to design a caching mechanism for a search engine web server cluster consisting of 100 machines. We need to define how search queries and their corresponding results are stored, evicted, and retrieved across this distributed environment. Specifically, our design must address data partitioning, eviction policies, fault tolerance, and network overhead.

Analyze the Problem Together

Let's break down the constraints and requirements before writing a single line of code. When we have 100 machines, our first instinct might be to replicate the entire cache on every machine. Let's evaluate that.

The "Aha!" conflict here is scale versus consistency. A centralized cache forms a bottleneck, while fully replicated caches waste precious RAM. The sweet spot is a Distributed Partitioned Cache utilizing consistent hashing.

Questions for the Interviewer

Before we jump into architecture, a senior engineer always clarifies the operational parameters by asking:

• What is the read-to-write ratio of search queries, and what is the typical payload size of a query result?
• How critical is strict cache consistency, or is eventual consistency acceptable during node failures?
• Are we expected to handle dynamic scaling (adding or removing machines from the 100-machine cluster dynamically)?
• What is our target latency SLA for cache hits?

Think About the Solution

Our architecture will feature a partitioned cache layer across our 100 machines. Instead of routing requests randomly, we will use Consistent Hashing with virtual nodes to map search queries to specific cache servers evenly. Each machine will maintain a local in-memory store (like a ConcurrentHashMap) coupled with an eviction policy—such as Least Recently Used (LRU)—to prevent Out-Of-Memory errors.

When a web server node receives a search query, it hashes the query string to determine which of the 100 cache machines owns that key, and fetches or populates the cache accordingly.

Write Code and Explain

Let's write a production-ready Java implementation demonstrating the core caching node logic, including thread-safe storage and an LRU eviction mechanism.

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class SearchCacheNode {
    private final int capacity;
    private final Map cacheMap;
    private final ReentrantReadWriteLock lock;

    public SearchCacheNode(int capacity) {
        this.capacity = capacity;
        // Setting accessOrder to true configures LinkedHashMap for LRU ordering
        this.cacheMap = new LinkedHashMap(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > SearchCacheNode.this.capacity;
            }
        };
        this.lock = new ReentrantReadWriteLock();
    }

    public V get(K key) {
        lock.readLock().lock();
        try {
            return cacheMap.get(key);
        } finally {
            lock.readLock().unlock();
        }
    }

    public void put(K key, V value) {
        lock.writeLock().lock();
        try {
            cacheMap.put(key, value);
        } finally {
            lock.writeLock().unlock();
        }
    }

    public int size() {
        lock.readLock().lock();
        try {
            return cacheMap.size();
        } finally {
            lock.readLock().unlock();
        }
    }
}

Walkthrough of the Code:

• We extend Java's LinkedHashMap with access-order tracking enabled, giving us an out-of-the-box LRU eviction policy when capacity is exceeded.
• We wrap our operations in a ReentrantReadWriteLock to ensure thread safety across concurrent search queries while maximizing read concurrency.

Time & Space Complexity

Let's analyze the performance characteristics of our caching node operations:

• Time Complexity: O(1) for both get and put operations, as underlying hash table lookups and doubly linked list pointer updates execute in constant time.
• Space Complexity: O(C) where C represents the maximum capacity assigned to the cache node, ensuring predictable memory bounds per machine.

Why This Problem Matters (The Senior Perspective)

Designing caches at scale is a foundational skill in distributed systems engineering. Real-world systems like Redis, Memcached, and CDN edge caches rely on these exact principles. When scaling to 100 machines, network partitions, split-brain scenarios, and hot-key mitigation become critical production considerations. Mastering consistent hashing and thread-safe data structures bridges the gap between theoretical algorithms and bulletproof backend architecture.

Final Thoughts

Tackling system design problems like this sharpens our intuition for trade-offs between memory, network, and consistency. As you continue exploring distributed systems, try experimenting with consistent hashing ring implementations. Keep building, keep learning, and happy coding!