LRU Cache

LRU caching is built on the principle of temporal locality of reference. This heuristic assumes that if a data block is accessed once, it is highly probable it will be accessed again in the near future. By evicting the item with the oldest access timestamp, the cache retains 'hot' data that reflects the current working set of the application. This makes it highly effective for workloads with recency bias, such as user session data or trending content feeds.

A canonical high-performance LRU cache achieves O(1) time complexity for both get and put operations by combining two data structures:

• Hash Map: Provides constant-time key lookup to directly access cache entries.
• Doubly Linked List: Maintains access order. When an item is accessed, it is detached and moved to the head of the list in O(1) time. The tail of the list always represents the least recently used item, ready for immediate eviction when capacity is exceeded.

The effectiveness of an LRU policy is measured by its cache hit ratio. A high hit ratio indicates the cache is successfully intercepting requests before they reach slower backend storage. LRU excels when the working set size is smaller than the cache capacity. However, a sudden burst of one-time sequential reads—often called a scanning pollution event—can flush the entire cache of frequently used data, causing a sharp drop in hit ratio until the working set is re-established.

LRU eviction is purely access-frequency and recency-based, contrasting with Time-To-Live (TTL) expiration. TTL enforces an absolute expiry timestamp regardless of access patterns, which is essential for stale data prevention. In practice, high-performance retrieval systems often combine both strategies: LRU manages capacity pressure by evicting cold data, while TTL ensures data freshness by purging entries that have exceeded their valid lifespan, even if they are still frequently accessed.

Strict LRU requires locking the entire data structure on every access to move nodes, creating a concurrency bottleneck in multi-threaded environments. To solve this, databases and operating systems often implement approximations like CLOCK (Second Chance). This algorithm uses a circular buffer and a reference bit; a sweeper hand checks entries, clearing the bit if set, and evicting the entry if the bit is already clear. This avoids the overhead of linked-list pointer manipulation under high contention.

The algorithmic logic that determines which entry to purge when a cache is full. While LRU targets temporal locality, other policies optimize for different access patterns. LFU (Least Frequently Used) tracks access counts, ideal for stable reference data. TTL-based eviction uses absolute time-to-live, critical for ensuring freshness of volatile data. FIFO (First In, First Out) offers simplicity but ignores access frequency. Choosing the wrong policy can tank your cache hit ratio and spike backend load.

The percentage of requests served directly from cache versus the origin database. A high ratio (e.g., 95%+) is the primary goal of an LRU implementation. It directly reduces P99 latency by avoiding slow disk reads or network calls. Monitoring this metric reveals if your cache size is adequate for your working set. A sudden drop often signals a cache stampede or a shift in user access patterns that defeats the LRU algorithm's assumptions about temporal locality.

A catastrophic failure mode where a popular, computationally expensive cache entry expires. Without protection, hundreds of concurrent requests simultaneously miss the cache and hammer the backend database to regenerate the value. This often overwhelms the database, causing a cascading outage. Mitigation strategies include probabilistic early recomputation (refreshing the entry before hard expiry) and locking (allowing only one request to regenerate the value while others wait).

An evolution beyond exact key matching. Instead of caching only identical queries, a semantic cache stores query-answer pairs based on vector similarity. When a new query arrives, it's embedded and compared against cached embeddings. If a sufficiently similar query exists (e.g., cosine similarity > 0.95), the cached answer is returned instantly. This is vastly more effective for LLM applications where users phrase the same intent in countless ways, dramatically improving the effective cache hit ratio.

A specific memory mechanism inside transformer models during autoregressive generation. As the model generates each new token, it stores the computed Key and Value tensors from all previous tokens. Without this cache, the model would recompute attention for the entire sequence at every step, causing quadratic time complexity. The KV-Cache makes generation linear with respect to sequence length, directly reducing Time-to-First-Token (TTFT) and inter-token latency. Its memory footprint grows with batch size and sequence length.

A critical flow control mechanism that prevents a fast producer from overwhelming a slow consumer. In a retrieval pipeline, if an LRU cache miss triggers a flood of requests to a vector database that is already saturated, backpressure signals the cache layer to reject or throttle new requests. This prevents the database from crashing under load. Combined with a circuit breaker, it ensures the system fails gracefully rather than suffering a cascading collapse.