Caching Strategies and Distributed Caching Questions

Approach

Wrap the same map-plus-doubly-linked-list design in a single lock guarding both structures together, since get and put both need to atomically read AND mutate the ordering; a coarse-grained lock is the simplest correct answer, and is usually fast enough because the critical section is O(1) pointer work, not an expensive computation.

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

public class LRUCache<K, V> {
    private static class Node<K, V> {
        K key; V value; Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);
    private final ReentrantLock lock = new ReentrantLock();

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node<K, V> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void insertFront(Node<K, V> n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }

    public V get(K key) {
        lock.lock();
        try {
            Node<K, V> n = map.get(key);
            if (n == null) return null;
            remove(n);
            insertFront(n);
            return n.value;
        } finally {
            lock.unlock();
        }
    }

    public void put(K key, V value) {
        lock.lock();
        try {
            Node<K, V> n = map.get(key);
            if (n != null) {
                n.value = value;
                remove(n);
                insertFront(n);
                return;
            }
            if (map.size() >= capacity) {
                Node<K, V> lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
            Node<K, V> fresh = new Node<>(key, value);
            map.put(key, fresh);
            insertFront(fresh);
        } finally {
            lock.unlock();
        }
    }
}

Key points

A single ReentrantLock around the whole read-modify-write sequence in both get and put is required because get is not read-only here: moving the accessed node to the front is a write to the ordering structure, so a naive ConcurrentHashMap-only approach (no lock) would race on the linked-list pointers between two threads calling get at once.

Complexity

Time is still O(1) per operation for the same reason as the single-threaded version; the lock adds constant per-call overhead (acquire/release), not asymptotic cost. Under contention, operations serialize, so effective throughput is bounded by however long each O(1) critical section takes times the number of threads waiting.

Edge cases

Do not use a read-write lock naively here, since get mutates ordering; a plain ReentrantReadWriteLock would allow two "readers" (calls to get) to race on the linked-list pointers unless get acquires the WRITE lock, which defeats the purpose of a read-write split. For higher concurrency than a single global lock allows, shard the cache into N independently-locked sub-caches (hash the key to pick a shard) so unrelated keys do not contend on the same lock; this trades a small amount of eviction-precision (least-recently-used, LRU, is now per-shard, not global) for much better concurrent throughput.

Direct answer

Consistent hashing places both cache nodes and keys on a conceptual ring (by hashing each to a point on the ring) and routes a key to the next node clockwise from it, so adding or removing a node only remaps the keys between it and its neighbor, not the entire keyspace the way naive modulo hashing would.

Structured elaboration

• Why modulo hashing fails at scale: routing a key with hash(key) % N means every node-count change (N) reshuffles almost every key's destination node, since the modulo result changes for nearly all keys; that means a near-total cache flush (and a stampede of misses to the origin) on every scale-out or node failure.
• Consistent hashing's improvement: only the keys that fell between the added/removed node and its next neighbor on the ring need to move; on average, adding the Nth node to a ring of N nodes remaps roughly $1/N$ of the keyspace, not close to 100 percent.
• Virtual nodes: mapping each physical node to many points on the ring (e.g., 100 to 200 virtual nodes per physical node) smooths out the otherwise-uneven distribution you'd get from a small number of random hash points, and makes the fraction of keys remapped on a node change proportional to that node's actual share of capacity rather than being lumpy.
• Alternatives: rendezvous hashing (highest-random-weight) computes, for each key, a weighted score against every node and picks the highest, which achieves similar minimal-remapping properties without needing an explicit ring structure. A proxy layer (client-side hashing vs a routing proxy like Twemproxy) changes WHERE the hashing decision is made but not the underlying algorithm choice.
• Hot shards: consistent hashing distributes keys evenly in aggregate but does not know that some keys are read far more than others; a node can still become hot if it happens to own a popular key, which is a separate problem from rebalancing cost (see hot-key mitigation).
• Failover behavior: when a node fails, its portion of the ring is picked up by its neighbor (or, with virtual nodes, spread across several neighbors); this is graceful for read-through/cache-aside caches (a "miss" for a remapped key just refetches from origin) but can look like data loss for a cache that was the system of record for anything.

Worked example

A cluster grows from 10 nodes to 11. Under naive modulo hashing, roughly 91 percent of keys change their target node ($1 - 10/11$), effectively invalidating almost the whole cache at once. Under consistent hashing with virtual nodes, only the keys that fall in the ring segment now owned by the new node move, roughly $1/11 \approx 9\%$ of the keyspace, leaving the other 91 percent of cached entries untouched and avoiding a stampede.

Trade-offs and pitfalls

Too few virtual nodes per physical node produces an uneven distribution (some nodes end up owning noticeably more of the ring than others by chance); 100+ virtual nodes per physical node is a common starting point to smooth this out. Consistent hashing solves REBALANCING cost, not hot-key load; do not expect it to fix a single overloaded key. Client-side hashing requires every client to agree on the exact same ring state, which becomes an operational hazard during a rolling deploy where old and new client versions might briefly disagree on routing; a proxy-side approach centralizes that decision at the cost of an extra network hop.

Direct answer

Compare the three options (grow cache capacity, tune TTLs, scale the database) by estimating the marginal cost and marginal latency/load benefit of each, since they are not mutually exclusive and the cheapest lever that closes the gap is usually the right first move.

Structured elaboration

• Growing cache capacity: if evictions are the bottleneck (the working set does not fit), more memory directly raises hit ratio; the cost is roughly linear in additional cache node memory/count, and the benefit is bounded once the cache is large enough to hold the full working set (beyond that point, more memory buys nothing).
• Tuning TTLs: if the working set fits but TTLs are shorter than necessary for the actual staleness tolerance, extending TTLs raises effective hit ratio for close to zero additional infrastructure cost; the ceiling here is the data's genuine staleness tolerance, not technical capacity.
• Scaling the database: if the cache is already well-sized and well-tuned but query volume is still too high (e.g., a low cache-hit-ratio workload with lots of genuinely unique reads), the database itself needs more capacity (read replicas, bigger instances); this is usually the most expensive lever, both in infrastructure cost and operational complexity.
• A framework for choosing: first check eviction rate (tells you if more cache memory would help), then check whether current TTLs are shorter than the data's actual staleness tolerance (tells you if a free tuning win exists), and only after those are exhausted, model out database scaling cost against the marginal load reduction remaining.

Worked example

A service with a 70 percent cache hit ratio and database cost scaling linearly with query volume: modeling the current state at, say, $Q$ queries per second to the database and cost $C = k \cdot Q$. Raising hit ratio to 85 percent (a plausible outcome of either more cache memory or longer TTLs, depending on root cause) cuts database query volume by $\frac{1 - 0.85}{1 - 0.70} = \frac{0.15}{0.30} = 0.5$, a 50 percent reduction in database cost, versus scaling the database itself, which would only add capacity without reducing the query volume driving that cost at all. If eviction rate is low (cache is not memory-constrained) but TTLs are conservative relative to the data's real staleness tolerance, extending TTLs achieves this improvement essentially for free; if eviction rate is high, the same improvement requires paying for more cache capacity instead.

Trade-offs and pitfalls

Scaling the database without first checking whether cache tuning could achieve the same load reduction for less money is a common and expensive mistake; always rule out the cheaper levers first with actual data (eviction rate, staleness tolerance), not assumption. Pushing TTLs longer than the data's genuine staleness tolerance to chase a cost win trades a real user-facing correctness problem for an infrastructure savings; the framework only works if the staleness ceiling is respected as a hard constraint, not a dial.

Direct answer

When latency rises despite a healthy hit ratio, the cache is doing its job (finding data), so the investigation shifts away from "is data cached" toward "what is slow about serving a cached value": serialization cost, network hops, object size, or an inconsistent-key problem that is quietly generating hidden extra misses within an otherwise-healthy aggregate hit ratio.

Structured elaboration

• Serialization/deserialization cost: a growing or changed payload shape can make encoding/decoding on every cache hit meaningfully slower even though the read itself succeeded; check whether payload size or format changed recently.
• Object size: a larger cached object takes longer to transfer over the network even on a hit; compare current average object size against historical baselines for a regression.
• Network hops / cache network topology: a routing change (a new proxy layer, a cross-availability-zone hop that used to be same-zone) adds latency to every hit without affecting whether it is a hit at all; check whether the cache client's network path to the cache changed recently.
• Cache misses due to inconsistent keys: a subtle bug (a key that includes a field with slightly different formatting on different code paths) can cause SOME requests to always miss while the AGGREGATE hit ratio still looks acceptable if that subset is a small fraction of total traffic; segment hit ratio and latency by endpoint or request shape, not just in aggregate.
• Backend cascading delays: if the "cache hit" path itself calls out to something else after the cache read (a second lookup, an enrichment call), a slowdown there shows up as rising latency without touching the cache's own hit ratio at all.
• Debugging plan: start with distributed tracing to see where time is actually spent within a request (cache read, deserialization, post-cache-hit processing), compare payload sizes and network path over time, and segment metrics by endpoint/request-shape rather than relying purely on aggregate numbers that can hide a localized problem.

Worked example

A service's overall hit ratio holds steady at 92 percent, but p99 latency has crept up over two weeks; tracing shows the cache READ itself is still fast (single-digit milliseconds), but deserialization time for the cached payload has grown from 2ms to 40ms, correlating with a recent change that added several new fields to the cached object; the fix is either trimming the payload to only what is actually needed, or switching to a faster serialization format, not anything related to the cache layer itself.

Trade-offs and pitfalls

Assuming "hit ratio is fine, so the cache isn't the problem" and stopping the investigation there is a common mistake; a hit ratio number says nothing about how expensive it is to USE a cached value once found. Aggregate metrics can hide a localized problem affecting a small but meaningful subset of traffic; segment by endpoint or request type before concluding a metric is uniformly healthy.

Direct answer

Cache warming trades a bounded amount of upfront (or background) load for avoiding a much larger, uncontrolled cold-start spike; the right approach depends on whether you can predict the hot keys ahead of time and how much control you have over the deployment timing.

Structured elaboration

• Proactive/bulk warming: precompute and load the known hot keys before traffic hits the new instance or cluster (a scheduled job at deploy time). This gives the strongest guarantee against cold-start misses but requires knowing which keys will actually be hot ahead of time, and adds deploy-time work.
• Lazy/on-demand warming: let the cache populate naturally as real traffic arrives; simplest to implement (it is just the normal cache-aside miss path), but produces a real, uncontrolled burst of origin load right after a deploy or flush, exactly a cold-start stampede if not otherwise protected.
• Hybrid/synthetic traffic warming: replay a sample of recent real traffic (or synthetic requests mimicking it) against the new instance before it receives production traffic, warming the cache using realistic access patterns without waiting for actual users to trigger it.
• Prioritizing which keys to warm: use recent access logs to identify the actual hot-key distribution rather than guessing; warming the wrong keys wastes the warming budget on cold data while the truly hot keys still cold-start.
• Safety concerns: warming itself generates load against the origin; rate-limit or throttle the warming process so it does not become its own mini-stampede, and have a way to abort a warming job cleanly (restoring previous cache state) if it is causing unexpected load rather than letting it run to a bad outcome.

Worked example

A microservice serving 100,000 requests per second (RPS) with heavy skew to 1 percent of keys (the classic Zipfian hot-key pattern common in real traffic): warming just that top 1 percent of keys from recent access logs, prioritized by request volume, captures the overwhelming majority of the benefit for a small fraction of the warming effort a full-catalog preload would require; a full preload of every key, most of which are rarely read, would waste warming time and origin load on data unlikely to matter for cold-start performance.

Trade-offs and pitfalls

Warming based on stale or unrepresentative access logs (e.g., from before a major traffic-pattern shift) warms the wrong keys and provides a false sense of readiness; refresh the "what's hot" list close to the actual warming event. A warming job that itself is unthrottled can overload the origin just as badly as the cold-start stampede it is meant to prevent; treat warming as a controlled, rate-limited operation with the ability to abort and roll back cleanly, not a fire-and-forget script.