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

Keeping caches coherent across regions means picking, per data class, between a pull model (short time-to-live, TTL, that self-heals without any messaging) and a push model (explicit invalidation events fanned out to every region), and being explicit about the bounded-staleness window you are willing to accept in exchange for lower cost and complexity.

Structured elaboration

• TTL (pull-based): the simplest option. Every region's cache entry expires on its own after a fixed window; no cross-region messaging is required. Staleness is bounded by the TTL itself, cost is near zero, and it self-heals from any missed update (a lost invalidation event just means the entry expires normally at worst-case TTL). The downside is that staleness is guaranteed, not just possible, for the full TTL window.
• Push invalidation via messaging: on write, the writing region publishes an invalidation event (key, and optionally a version or tombstone) to a durable message bus; consumers in every other region apply it to their local cache. This gets close-to-immediate propagation (bounded by replication lag of the message bus, typically under a second) but adds a moving part that can itself fail, reorder, or duplicate, so you still need a TTL as a backstop.
• Versioned keys: instead of invalidating, bump a version token that is part of the cache key (profile:123:v42); old versions simply age out via normal eviction rather than needing an active delete. This avoids race conditions where an invalidation arrives before the write it corresponds to, at the cost of needing a place to look up "what's the current version" (which itself needs to be fast and consistent).
• Fanout updates: instead of invalidating (forcing every region to re-fetch), push the new VALUE itself to every region's cache. This trades more network bandwidth (sending full payloads, not small invalidation markers) for lower read-side latency (no cache-miss round-trip to origin after the update lands), and is worth it for small, very hot objects.
• Bounded staleness as the actual requirement: whichever mechanism you choose, state the staleness bound explicitly (e.g., "under 5 seconds in 99% of cases") and design the propagation pipeline's monitoring around that number, rather than treating "eventually consistent" as sufficient specification.

Worked example

A profile-update event published in the primary write region reaches a message bus with typical cross-region replication lag of 200 to 500 ms, plus consumer processing time of tens of milliseconds per region; a realistic end-to-end propagation time is under 1 second for the median case, with a long tail driven by consumer backlog during traffic spikes. If the product requirement is "profile changes visible within 5 seconds globally," a push-based invalidation pipeline with a 5-second TTL backstop comfortably meets it even if a specific invalidation event is dropped, because the TTL guarantees the bound independently.

Trade-offs and pitfalls

Relying purely on push invalidation without a TTL backstop means any lost, delayed, or duplicated event becomes an unbounded staleness bug with no self-healing mechanism; always pair push invalidation with a TTL ceiling. Fanout-updates for large or rarely-read objects wastes bandwidth pushing data nobody will read in some regions; reserve it for small, universally-hot keys. Versioned keys solve the ordering race but shift complexity to "how fast and how consistent is the version lookup itself," which can become its own single point of failure if not designed carefully.

Direct answer

Cache serialization needs explicit schema versioning so that a deployment change (a field added, removed, or retyped) does not produce a runtime error or silent data corruption when new code reads an old cached format, or old code reads a new one, during a rolling upgrade.

Structured elaboration

• Versioning the serialized format: embed a schema version alongside the serialized payload (either in the value itself, or in the cache key, as covered by the key-versioning pattern) so a reader can detect which shape it is dealing with.
• Schema evolution: prefer additive, backward-compatible changes (new optional fields default sensibly if absent) over breaking changes (renaming or retyping an existing field) wherever possible, since additive changes let old and new code coexist safely without any special handling.
• Backward compatibility during rolling upgrades: during a deploy, old and new application code run simultaneously for some window; if new code writes a new schema version and old code cannot deserialize it, old-code instances will error or silently misbehave on every cache read for that key until the deploy completes, unless the new schema is designed to be backward-readable, or the version is used to explicitly route old code away from new-format entries.
• Lazy migration strategies: rather than migrating every cached entry to a new format immediately, let entries migrate lazily: on a cache miss (or an explicit read-and-rewrite), the new format is written; old-format entries simply age out via their normal time-to-live (TTL), avoiding a disruptive bulk-migration pass.
• Choosing a serialization format: a format with strong built-in support for optional/default fields (protocol buffers, for example) makes additive schema evolution far more natural than a format that requires exact structural matching to deserialize correctly.

Worked example

Adding a new optional field to a cached user-profile object: with a backward-compatible serialization format, old code (not yet aware of the new field) simply ignores it when reading a new-format entry, and new code supplies a sensible default when reading an old-format entry that lacks the field; no special versioning logic is needed at all, because the format itself tolerates the difference. Contrast with renaming an existing field, which is NOT safely backward-compatible under most formats and would require either a version-gated read path or accepting a brief window of cache misses/errors during the rolling deploy.

Trade-offs and pitfalls

Assuming a serialization format is "safe" without checking its specific behavior on missing or extra fields is a common way this bites during a rolling deploy; verify the format's actual compatibility guarantees, do not assume. Skipping explicit versioning "because most changes are additive" works until the first genuinely breaking change arrives unplanned; building the versioning mechanism in from the start costs little and avoids an emergency retrofit later.

Direct answer

Analytics and business intelligence (BI) queries tolerate minutes of staleness in exchange for large latency and cost wins, so lean on materialized views and result caching aggressively, choosing the caching granularity (whole report, per-tile, per-query-result) based on how the dashboard is actually consumed.

Structured elaboration

• Materialized views: precompute and store the results of expensive aggregations on a schedule (or triggered by upstream data changes), so a dashboard read is a fast lookup against already-computed results rather than a live, expensive query against raw data.
• Result caching layers: cache the results of specific, frequently-run queries (a query-result cache keyed by the query and its parameters) for dashboards where the underlying data does not change often enough to justify a full materialized-view pipeline.
• Cache granularity: report-level caching (the whole dashboard's output) is simplest but coarse (any change forces a full recompute); tile-level (each widget/chart cached independently) allows partial invalidation when only some underlying data changed; query-result-level is the finest grain, useful when many different reports share underlying queries.
• Invalidation strategies for BI: time-to-live (TTL) is often sufficient here, since most BI use cases genuinely tolerate a bounded staleness window (minutes, sometimes hours); event-based invalidation (triggered by an upstream data-pipeline completion) is worth the added complexity specifically for dashboards where "as fresh as the last data load" matters more than a fixed time window; manual invalidation (an explicit refresh button) suits ad-hoc analysis tools where users want on-demand control.
• Cache warming/pre-computation: for dashboards viewed at predictable times (a morning operations review, a weekly business report), precomputing results just before that predictable access window avoids making the first viewer of the day pay the full, uncached computation cost.
• Balancing freshness, latency, and cost: the right TTL and caching granularity should map directly to how the business actually uses the dashboard, an operational dashboard checked continuously wants near-real-time and can justify more compute cost; a monthly strategic report tolerates hours of staleness and should be cached aggressively to save cost.

Worked example

A BI platform serving semantic-layer queries: for a query-result cache keyed by the query and its parameters, a report combining multiple underlying queries can serve most of its content from cache (queries that have not changed) while only recomputing the specific queries whose underlying data actually changed, rather than invalidating and recomputing the entire report on any single data update; this per-query granularity captures much of the tile-level caching benefit without needing the dashboard rendering layer itself to be cache-aware.

Trade-offs and pitfalls

Caching at the coarsest (whole-report) granularity for convenience, when the underlying data actually changes at different rates for different parts of the report, wastes the caching opportunity for the parts that rarely change and forces unnecessary staleness or unnecessary recomputation for the rest; choose granularity deliberately based on the actual update-rate heterogeneity within the report. Setting one TTL policy across every dashboard regardless of how it is actually used (operational versus strategic) either wastes freshness-driving compute cost where it is not needed, or under-serves freshness where it genuinely matters; tie the TTL choice to actual usage patterns.

Direct answer

There is no design that gives you both sub-50ms global reads and strong consistency for every write; you choose where the compromise sits. For most globally-distributed services the right default is regional read caches with a single-writer region per key (or per user) plus asynchronous replication, escalating to active-active with conflict resolution only for the specific keys that genuinely need multi-region writes.

Structured elaboration

• Global master with local read caches: writes always go to one authoritative region (chosen per key, e.g., the user's home region); that region's cache is updated synchronously, and other regions' caches are populated by asynchronous replication or event-driven invalidation. Reads in the writer's own region are strongly consistent; reads elsewhere are eventually consistent with a bounded lag (typically under a few seconds for a well-tuned replication pipeline). This is the simplest model to reason about and is the right default unless a specific workload proves it insufficient.
• Active-active with conflict resolution: every region can accept writes to the same key; conflicts are resolved with last-write-wins (using synchronized clocks or hybrid logical clocks), version vectors, or application-specific merge logic. This removes the single-writer bottleneck but pushes real complexity into conflict resolution and makes the failure modes harder to reason about; reserve it for keys where availability during a regional partition matters more than avoiding conflicts (e.g., a shopping cart, where a merge is acceptable).
• CRDT-based approaches: conflict-free replicated data types (structures with a mathematically well-defined merge function, such as a grow-only counter or a last-writer-wins register) let every region write locally and merge automatically without coordination. They are the cleanest fit when the data shape is naturally a CRDT (counters, sets, simple registers) but do not generalize to arbitrary application state.
• Choosing the read-latency-vs-consistency point per requirement: a common pattern is to segment data by freshness requirement. Authentication and permission state gets synchronous, single-region-authoritative reads (correctness matters more than latency). Profile pictures, preferences, and feed content get regional caches with eventual consistency (latency matters more, and staleness of a few seconds is invisible to users).

Worked example

For a service needing sub-50ms p95 reads worldwide with a single global-master design and 150ms average inter-region round-trip time: a user in Singapore reading data whose write-authoritative region is US-East would need a cross-region hop on every uncached read, blowing the 50ms budget by 3x. The fix is not "make replication faster" but "make the region the user reads from also the region their writes update" (their home region is the writer), with cross-region only used for failover. Under active-active with a 5-second bounded staleness target, replication lag has to be monitored per-region-pair and alerted when it exceeds roughly half the staleness budget (2.5s), leaving headroom for the merge/apply step.

Trade-offs and pitfalls

The most common design mistake is picking one consistency model for the whole service instead of per data class; forcing strong consistency on data that does not need it (e.g., a "last seen" timestamp) burns your entire latency budget for no user-visible benefit. Active-active without a clear conflict-resolution policy invites silent data loss (the losing write of a last-write-wins resolution simply disappears); make sure product owners have explicitly signed off on what "conflict" means for each data type before choosing this model. CRDTs remove coordination cost but restrict your data model; retrofitting CRDTs onto an existing schema is usually more work than designing around single-writer-per-key from the start.