Distributed Caching & Eviction Policies

Caching is one of the most effective ways to optimize application response times and reduce load on database systems. By storing frequently accessed data in a fast memory layer (usually RAM), we avoid expensive disk reads or complex computations.

Why Caching Matters

In a typical web application, database reads represent the primary performance bottleneck. While disk access takes milliseconds, memory access takes nanoseconds. By placing a cache between your application servers and database, you can achieve sub-millisecond response times.

[ Client ] ---> [ Application Server ] ---> [ Cache (Redis) ]
                                                   | (Cache Miss)
                                                   v
                                            [ Database (PostgreSQL) ]

Cache Write Policies

How you update your cache relative to your main database depends heavily on your data access patterns and consistency requirements.

1. Cache-Aside (Lazy Loading)

The application handles both the database and the cache.

• Read Path: The app queries the cache. On a cache miss, it queries the database, writes the result to the cache, and returns it.
• Write Path: The app updates the database directly and invalidates (deletes) the cache entry.
• Pros: Resilient to cache failures; only requested data is cached.
• Cons: Initial read is a miss; double round-trip on miss.

2. Write-Through

The application treats the cache as the main data store. The cache is responsible for writing to the database.

• Write Path: The app writes to the cache. The cache synchronously updates the database.
• Pros: Data in the cache is never stale.
• Cons: High write latency because of synchronous dual-writes.

3. Write-Back (Write-Behind)

Similar to Write-Through, but writes to the database are asynchronous.

• Write Path: The app writes to the cache. The cache queues the write and updates the database asynchronously.
• Pros: Extremely fast write performance. Good for write-heavy workloads.
• Cons: Risk of data loss if the cache crashes before the data is persisted to the database.

Cache Eviction Policies

Since memory is expensive and limited, caches must eventually evict old entries to make room for new ones.

,[object Object],

| Eviction Policy | Description | Best For | |---|---|---| | LRU (Least Recently Used) | Evicts the item that has not been accessed for the longest time. | General-purpose workloads with temporal locality. | | LFU (Least Frequently Used) | Evicts the item with the lowest access count. | Static files or search results with stable popularity. | | FIFO (First In First Out) | Evicts the oldest item based on insertion time. | Simple queues or time-sequenced batch data. |

LRU Cache Implementation Concept

An LRU cache is typically implemented using a combination of a Hash Map (for $O(1)$ lookup) and a Doubly Linked List (for $O(1)$ updates to the access order).

// A conceptual LRU update workflow
function get(key) {
  if (!map.has(key)) return null;
  const node = map.get(key);
  moveToHead(node); // Mark as most recently used
  return node.value;
}

Distributed Caching Challenges

When scaling horizontally across multiple machines, local memory caches (in-memory maps) become problematic because each server has a different view of the data.

To solve this, we use a distributed caching cluster like Redis or Memcached.

1. Cache Avalanche

Occurs when a large portion of the cache expires simultaneously, causing a sudden surge of traffic to hit the database.

• Solution: Add a random jitter to the TTL (Time-To-Live) values so expirations are spread out.

2. Cache Stampede (Dogpiling)

Occurs when a popular cached item expires, and multiple parallel requests attempt to recalculate the same item and write it to the database at the same time.

• Solution: Use mutual exclusion locks (mutex) to allow only one thread/process to update the cache on a miss.

3. Cache Penetration

Occurs when requests query keys that do not exist in the database (e.g., malicious requests for non-existent IDs). Since the key is never found, every request hits the database.

• Solution: Cache empty or null values with a short TTL, or use a Bloom Filter to check if the key exists before querying the database.