LRU Caches: Constant-Time Eviction for Real Systems

An LRU (Least Recently Used) cache is a data store with a fixed capacity that tracks when each entry was last accessed. When the cache is full and new data arrives, the cache makes room by removing the entry that has gone unused for the longest time. This removal rule is called the eviction policy, and LRU is the most widely used one because data that was needed recently tends to be needed again.

We have already covered the two ingredients separately on this blog: HashMaps give us constant-time lookup by key, and linked lists give us constant-time reordering. An LRU cache is the classic payoff for learning both, because it needs each structure to cover the other one's weakness. This post builds one from those parts, shows the short version JavaScript gives you almost for free, and finishes with the workloads where LRU is the wrong choice.

In the full article

• Why Eviction Policy Is the Whole Game
• The Naive Version and Where It Breaks
• The Classic Design: HashMap Plus Doubly-Linked List
• The JavaScript Shortcut: Map Preserves Insertion Order
• A Production-Shaped LRU with TTL
• When LRU Is the Wrong Policy
• Key Takeaways