Imagine your school bag. It can only hold a few books. Every day you bring new books for new subjects. If the bag is full and you need to add one more book, you must take one out. Which one do you remove? The smart answer is: remove the book you haven’t touched in the longest time — you probably won’t need it again soon.

That simple idea — throw away the thing you used longest ago — is exactly what the LRU (Least Recently Used) cache eviction policy does inside computers. LRU is a rule that decides what to remove from a cache when the cache is full and something new needs to come in.

A cache is a small, fast storage area that keeps copies of data so that future requests for that data can be served faster. Think of it as a “quick shelf” near your desk, versus the “big warehouse” (the main database or disk) far away. Grabbing something from the quick shelf is much faster than walking to the warehouse.

1.1 Why does LRU exist?

Caches are always small compared to the total amount of data that exists. Your laptop’s memory is small compared to the internet. A web server’s cache is small compared to its entire database. Because a cache is limited in size, at some point it becomes full. When that happens, the system must decide: which existing item should I throw away to make room for the new one? That decision‑making rule is called an eviction policy, and LRU is the most famous and widely used one.

1.2 A short history

• 1960sVirtual memory research. Early mainframes had tiny, expensive main memory and needed strategies to decide which pages of a program to keep in memory versus which to write back to slower disk. Researchers like László Bélády formalised the study of “page replacement,” giving us FIFO, LRU, and the theoretical Optimal (Bélády’s) algorithm.
• 1970s–80sOperating systems adopt LRU. Unix‑family kernels and their descendants ship with LRU‑style page replacement (often the “Clock” or “Second‑Chance” approximation) as the default way of choosing which memory pages to swap out.
• 1990sCPU caches and databases. Modern processors bake pseudo‑LRU logic directly into L1/L2/L3 cache hardware. Databases like Oracle and later MySQL InnoDB start using LRU‑based buffer pools to keep hot data pages in RAM.
• 2000sWeb caches & CDNs. Squid, Varnish, and CDNs (Akamai, Cloudflare) adopt LRU‑style eviction to keep the most‑requested URLs cached close to users.
• 2010sDistributed key‑value caches. Redis and Memcached make LRU (and, for Redis, its approximate‑LRU sampling) the standard eviction policy of large‑scale application caches at companies like Twitter, GitHub, and Uber.
• 2020sIn‑process caches & smart variants. Libraries such as Caffeine bring near‑optimal, high‑concurrency LRU‑family algorithms (TinyLFU/W‑TinyLFU) directly inside Java processes, and the field continues to refine variants like ARC, 2Q, and SLRU.

Today, LRU (or a variant of it) sits quietly inside almost every layer of modern software, from the chip in your phone to the servers behind Netflix and Amazon — often without any developer having to name it explicitly.

1.3 Where you meet LRU without even knowing it

You interact with LRU‑style thinking many times a day, even outside computers. Your phone’s recent‑apps switcher shows the apps you touched most recently first, and the ones you haven’t opened in weeks slowly fall off the list. A physical library with limited shelf space near the front desk might keep the most recently returned books there, sending older, untouched books to storage in the back. Your own short‑term memory works similarly — you remember the last few things someone told you clearly, while details from a conversation days ago start to fade unless you kept “using” (recalling) them.

Computer scientists noticed this same pattern was incredibly useful for managing limited, fast storage, and turned it into a formal, precise algorithm that a machine could execute perfectly, every single time, in a fraction of a millisecond.

Let’s understand the exact problem LRU solves, step by step, with no assumed knowledge.

2.1 Why do we even need a cache?

Fetching data from a hard disk, a database, or across the internet takes time — often measured in milliseconds. Fetching data from memory that is already close to the processor takes far less time — often measured in nanoseconds or microseconds. If your application repeatedly asks for the same piece of data (say, a popular product page on an e‑commerce site), it is wasteful to go all the way to the database every single time. Instead, we keep a copy of frequently‑requested data in a fast cache.

2.2 Why can’t the cache just hold everything?

Fast memory is expensive and physically limited. You cannot build a cache the same size as your entire database — that would defeat the purpose (and cost a fortune). So caches are deliberately small, which means they will eventually fill up.

2.3 What happens when the cache is full?

When a full cache needs to store one more new item, it must remove something old first. This removal process is called eviction. The big question is: which item should be evicted? This is where an eviction policy comes in. Choosing badly means we throw away data we will need again very soon, causing a “cache miss” and a slow trip to the database. Choosing wisely means we keep the data we’re most likely to need, and cache misses become rare.

A good eviction policy is really a prediction: predicting what you will need next, based on what has happened so far.

2.4 Why “Least Recently Used” specifically?

LRU is based on a real‑world observation called temporal locality — if a piece of data was accessed recently, it’s likely to be accessed again soon. Think about the last five apps you opened on your phone. There’s a good chance your very next app will be one of those five, not some app you haven’t touched in six months. LRU turns this everyday pattern into a precise computer algorithm: always keep the recently‑touched items, always throw away the item that has been sitting untouched the longest.

2.5 What would happen without any eviction policy at all?

If a system simply kept adding new items to a full cache without ever removing anything, one of two bad things would happen. Either the cache would keep growing forever, eventually consuming all available memory and crashing the application (a memory leak), or the system would have to reject every new item once the cache was full, meaning the cache could never store anything new — including data that might be far more useful than what’s already sitting there. Neither option is acceptable for a real system, which is exactly why a deliberate, well‑thought‑out eviction policy like LRU is necessary.

2.6 The theoretical “best possible” policy — and why it’s impossible

Interestingly, computer science has already identified the mathematically optimal eviction policy: it’s called Bélády’s algorithm, or the “Optimal Replacement Policy.” Its rule is simple to state: always evict the item that will not be needed again for the longest time in the future. The catch is that this requires knowing the future — which item will be requested next, and when — something no real system can know in advance. Bélády’s algorithm is mainly used as a theoretical benchmark, to measure how close a practical policy like LRU comes to perfection. LRU is popular precisely because it approximates this unreachable ideal using only information about the past, which is the only information any real system actually has.

Before going deeper, let’s clearly define every term we will use throughout this tutorial.

3.1 Beginner example

Say your cache can hold only 3 items, and you access pages in this order: A, B, C, A, D.

1. Access A → cache: [A] (A is most recent)
2. Access B → cache: [A, B] (B is most recent)
3. Access C → cache: [A, B, C] (full now, C is most recent)
4. Access A again → A moves to “most recent.” Cache order (least to most recent): [B, C, A]
5. Access D → cache is full. Evict the least recently used item, which is B. Cache becomes: [C, A, D]

Notice that B was evicted — not C — even though B was added before C, because A was re‑accessed and “refreshed” its recency, but B’s recency never got refreshed and it became the oldest.

3.2 Software example

Imagine an online food delivery app. Every time a user opens the app, it needs to show the menu of a nearby restaurant. Fetching a restaurant’s full menu from the database takes, say, 40 milliseconds — noticeable to a human. If the app keeps the last 500 viewed restaurant menus in an LRU cache, then whenever someone reopens a popular restaurant’s page (which happens constantly during lunch hours), the response comes back almost instantly from the cache instead of hitting the database again. As new restaurants get viewed and the cache fills up, the menus nobody has looked at recently quietly get evicted to make room — exactly the behavior you want, since a restaurant nobody is currently browsing is unlikely to be requested again in the next few seconds.

3.3 Production example: Amazon‑style product pages

A large e‑commerce platform might serve millions of product page views per minute. Only a small fraction of the total product catalog — the trending items, deals, and popular categories — accounts for the vast majority of traffic at any given moment (this is sometimes called the “80/20 rule” or a Zipfian distribution). An LRU cache is a natural fit here: the currently trending products stay “hot” in the cache because they keep getting re‑accessed, refreshing their position, while yesterday’s trending products that nobody is looking at anymore naturally age out and get evicted, freeing space for today’s new trends — all without anyone having to manually configure which products should be cached.

To make LRU fast in real software, we need two things working together:

1. A HashMap (or hash table) — for instant lookup: “does this key exist in the cache, and where is it?”
2. A Doubly Linked List — for keeping track of usage order, so we always know which item is least recently used (at the tail) and which is most recently used (at the head).

Why do we need both? A HashMap alone gives us fast lookup (O(1)) but has no idea about order of use. A linked list alone can track order, but finding a specific item inside it would require scanning through it (slow, O(n)). By combining both, we get the best of each: instant lookup and instant reordering.

Fig 4.1 — The HashMap gives O(1) access to any node. The Doubly Linked List keeps nodes ordered from most‑recently‑used (head) to least‑recently‑used (tail), so eviction always removes the tail node in O(1) time.

4.1 Why a doubly linked list, not a singly linked list?

In a singly linked list, each node only points forward to the next node. To remove a node from the middle (which happens every time we re‑access an item), we’d need to know its previous node too — and finding that would require scanning the whole list. A doubly linked list stores both “next” and “previous” pointers on every node, so we can unlink any node instantly, without searching, as long as we already have a direct reference to it (which the HashMap gives us).

Let’s walk through exactly what happens, in plain steps, for the two core operations.

5.1 get(key) — reading data

5.2 put(key, value) — writing data

Here is a sequence diagram showing a realistic request flow through an LRU cache sitting in front of a database — this is the most common real‑world pattern, called cache‑aside.

Fig 6.1 — The cache‑aside pattern. The application always asks the cache first. Only on a miss does it pay the cost of a database round trip, and then it stores the fresh result in the cache for next time.

6.1 A full lifecycle example, step by step

Let’s trace a cache with capacity 3 through a sequence of operations, showing the internal state after each step.

There are two common ways to implement LRU in Java. Let’s look at both.

7.1 Option A: The quick way — using LinkedHashMap

Java’s built‑in LinkedHashMap can maintain access order and has a built‑in hook for eviction, making it perfect for a simple, production‑ready LRU cache in just a few lines.

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder=true (tracks usage order)
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Called automatically after every put(); returning true evicts the oldest entry
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.get(1);          // 1 becomes most recently used
        cache.put(4, "D");     // evicts 2 (least recently used)

        System.out.println(cache.keySet()); // [3, 1, 4]
    }
}

This works because accessOrder=true tells LinkedHashMap to reorder entries every time they are read, and removeEldestEntry is a hook Java calls after every insert, letting us evict automatically.

7.2 Option B: The “from scratch” way — HashMap + Doubly Linked List

This is the version most interview and system‑design discussions expect, because it shows you understand exactly how LRU works internally rather than relying on a library.

import java.util.HashMap;

public class LRUCacheManual {

    class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head; // dummy head (most recently used side)
    private final Node tail; // dummy tail (least recently used side)

    public LRUCacheManual(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertAtHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insertAtHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        Node node = new Node(key, value);
        insertAtHead(node);
        map.put(key, node);

        if (map.size() > capacity) {
            Node lru = tail.prev;      // node just before dummy tail
            remove(lru);
            map.remove(lru.key);
        }
    }
}

Notice the two dummy (sentinel) nodes, head and tail. They exist purely to avoid messy null checks when inserting into or removing from an empty or single‑item list — a very common, clean production trick.

LRU is just one of several eviction strategies. Here’s how it compares to the other common ones.

Fig 9.1 — Different eviction policies branch off from the same trigger — a full cache — but choose the victim using different logic.

10.1 Time complexity

These constant‑time guarantees are exactly why LRU is chosen over naive approaches like scanning an array of “last used timestamps,” which would cost O(n) per operation and quickly become a bottleneck under heavy load.

10.2 Scaling LRU in real systems

• Sharding: Instead of one giant cache, split it into many smaller caches (shards) by key, each with its own LRU list. This reduces lock contention and lets shards run on different machines.
• Sampling‑based approximate LRU: True LRU under massive concurrent load can create contention on the linked list. Systems like Redis use an approximate LRU — sampling a handful of random keys and evicting the “oldest” among that sample, which is nearly as effective but far cheaper at scale.
• Segmented / tiered caches: Combine a small, ultra‑fast in‑process cache (like Caffeine in Java) with a larger, shared distributed cache (like Redis) behind it, each with its own LRU eviction.

10.3 Why not just use a simple array with timestamps?

A beginner’s first instinct is often: “why not just store a ‘last accessed time’ next to every item in an array, and scan the array to find the oldest one when eviction is needed?” This does work correctly, but it doesn’t scale. Scanning an array of size n to find the minimum timestamp takes O(n) time — for every single eviction. With a cache holding a million items, that’s a million comparisons on every eviction, which quickly becomes far too slow for a system handling thousands of requests per second. The HashMap plus doubly‑linked‑list design exists specifically to avoid this scan, replacing it with a small, constant number of pointer operations regardless of how large the cache is. This is a great example of a general lesson in software engineering: the right combination of data structures can turn a slow O(n) operation into a fast O(1) one.

10.4 Benchmarking mindset

When evaluating or tuning any real cache, engineers typically look at three things together, never just one in isolation: the hit rate (is the cache actually useful?), the latency of cache operations themselves (is the cache fast enough to be worth using?), and the cost of the memory it consumes (is the cache size justified by the benefit?). A cache with a 99% hit rate that is itself slow, or a cache that is blazing fast but rarely has what’s needed, are both signs that something needs tuning — either the eviction policy, the cache size, or what’s being cached in the first place.

In real applications, many threads (or many servers) may read and write to the cache at the same time. A naive LRU implementation is not thread‑safe by default, because two threads could try to modify the linked list pointers simultaneously and corrupt it.

11.1 Common solutions

Large applications don’t run an LRU cache on just one machine — they run a distributed cache spread across many servers, often using systems like Redis or Memcached.

12.1 Partitioning (sharding)

Keys are split across multiple cache nodes using a hashing strategy (often consistent hashing), so each node only manages a portion of the keyspace and runs its own local LRU eviction independently.

12.2 Replication

To avoid losing cached data (or, more importantly, to avoid overwhelming the database) if a cache node crashes, data is often replicated to one or more secondary nodes. If the primary node fails, a replica can take over.

Fig 12.1 — A typical distributed LRU cache cluster. Keys are routed to the correct shard, and each shard has its own replica for failover.

12.3 CAP theorem and caching

The CAP theorem says a distributed system can only fully guarantee two out of three: Consistency, Availability, and Partition tolerance. Since network partitions can always happen, real systems must choose between consistency and availability during a partition. Most caching systems lean toward availability — it’s usually fine to serve slightly stale cached data for a moment rather than fail the request entirely, since a cache is a performance optimization, not the source of truth.

12.4 Failure recovery

• Cache warm‑up: After a crash or restart, an empty cache causes a sudden wave of cache misses (called a “cold cache” or “thundering herd”). Systems often pre‑load (“warm”) the cache with the most important keys before routing real traffic to it.
• Graceful degradation: If the cache cluster is unreachable, well‑designed applications fall back to querying the database directly rather than crashing.
• Circuit breakers: Prevent an overloaded or failing cache layer from taking down the whole application by “tripping” and temporarily bypassing the cache.

12.5 Consensus and coordination

In more advanced distributed caching setups, nodes need to agree on things like “who is the current primary for this shard” or “has this replica finished syncing.” This is where consensus protocols (such as Raft, used internally by systems like Redis Sentinel and many cloud‑managed cache services) come in — they help a cluster of machines agree on a single, consistent view of cluster state even when some nodes are slow or temporarily unreachable. You don’t need to implement these yourself when using managed services like AWS ElastiCache or Redis Enterprise, but understanding that this coordination is happening underneath is valuable for reasoning about failure scenarios.

12.6 Consistent hashing, explained simply

When you have multiple cache nodes, you need a way to decide which node stores which key. A naive approach — node_number = hash(key) % number_of_nodes — has a big problem: if you add or remove even a single node, almost every key suddenly maps to a different node, causing a massive, unnecessary wave of cache misses. Consistent hashing solves this by arranging nodes and keys on a conceptual circle (a “hash ring”). Adding or removing a node then only affects the small portion of keys near that node on the ring, leaving the vast majority of key‑to‑node mappings undisturbed. This is why consistent hashing is the standard technique behind virtually every large‑scale distributed cache and load balancer.

13.1 Encryption and network security

When a cache like Redis is deployed as a separate networked service, the connection between the application and the cache should be encrypted (using TLS) and authenticated (using passwords or access control lists), especially in cloud environments where network traffic could otherwise be intercepted by anything else running on a shared network. Cloud providers’ managed cache services generally offer these protections as configuration options — but they are not always turned on by default, so it’s worth explicitly verifying them during setup rather than assuming they’re active.

You cannot improve what you don’t measure. Here are the key metrics engineers track for any LRU‑based cache in production.

Tools like Prometheus + Grafana, Datadog, and Redis’s own INFO command (which reports keyspace_hits, keyspace_misses, and evicted_keys) are commonly used to track these metrics in real time and trigger alerts when hit rate drops or eviction spikes.

14.1 Setting up meaningful alerts

Rather than alerting on every small fluctuation, mature teams typically set alerts on sustained trends: for example, “hit rate has stayed below 70% for more than 10 minutes” or “eviction rate has tripled compared to the same time yesterday.” These kinds of comparative, trend‑based alerts catch real problems — like a sudden traffic pattern change, a misconfigured cache size after a deployment, or a bug that’s generating too many unique cache keys — without paging an engineer for normal, healthy variation. Logging cache key patterns (without logging sensitive values) also helps engineers debug unexpected pollution, such as noticing that a new feature is accidentally generating a unique cache key per user session instead of reusing a shared key, silently flooding the cache with one‑time entries.

LRU eviction shows up across many layers of a real production stack, not just as a standalone cache server.

15.1 Cost optimization

Since fast memory (RAM) costs more than disk, cache sizing is a direct cost decision. Engineers monitor hit rate versus memory cost, and often find a “sweet spot” cache size beyond which adding more memory yields diminishing improvements in hit rate — a classic cost‑performance trade‑off in cloud infrastructure.

16.1 Common caching patterns that use LRU underneath

16.2 Anti‑patterns to avoid

17.1 Best practices

• Choose a cache size based on real traffic analysis, not guesswork — measure hit rate before and after resizing.
• Combine LRU eviction with a TTL so stale data eventually expires even if it stays “recently used.”
• Use meaningful, namespaced cache keys (e.g., user:101:profile) to avoid collisions and simplify invalidation.
• Monitor hit rate continuously — a dropping hit rate is an early warning sign of a problem.
• Prefer proven libraries (Caffeine, Redis) over hand‑rolled caches in production unless you have a very specific need.

17.2 Common mistakes (with fixes)

17.3 A simple approach to capacity planning

A practical way to size an LRU cache is to start by estimating your “working set” — the set of items your application realistically needs at once during normal peak traffic. For example, if your analytics show that 95% of requests over the last week touched only 10,000 unique product IDs, then a cache sized to comfortably hold those 10,000 items (plus a safety margin) is a reasonable starting point. From there, watch the hit rate in production: if it’s consistently above roughly 90% and eviction rate is low, your sizing is likely healthy. If hit rate is low and eviction is constant, either your cache is too small for the workload, or your workload has very low temporal locality and might not benefit much from LRU caching at all — both are useful, actionable signals rather than guesses.

Notice a pattern across all these examples: whether it’s a CPU chip the size of a fingernail or a global network of thousands of servers, the underlying challenge is identical — a small, fast storage space, a much larger pool of possible data, and a need to intelligently decide what stays and what goes. LRU (or one of its refined variants) is one of the most trusted answers to that challenge across the entire computing industry.

Because plain LRU has known weaknesses (like vulnerability to one‑time scans), several improved variants have been developed over the years.

Fig 19.1 — Segmented LRU (SLRU). New items start on probation. Only items proven useful by a second access earn a spot in the safer, protected segment — reducing pollution from one‑time scans.

Let’s step back and look at the big picture one more time. Every computer system, no matter how large or small, faces the same basic tension: fast storage is expensive and limited, while the amount of data that could be stored is essentially unlimited. LRU is one elegant, well‑tested answer to that tension. It doesn’t require predicting the future, doesn’t require complicated statistics, and doesn’t require expensive computation — it simply asks one simple question every time: “what have I not touched in the longest time?” and removes that. This simplicity is exactly why it has survived, largely unchanged in concept, from 1960s mainframe memory management all the way to the phone in your pocket and the servers powering today’s largest websites.

As you continue studying system design or building real applications, you’ll find that understanding LRU deeply — not just being able to recite the definition, but understanding why the HashMap and doubly linked list combination is necessary, why real systems use approximations at scale, and where LRU’s weaknesses show up — will serve you well, whether you’re debugging a slow production system, designing a new caching layer, or answering a technical interview question.

• Takeaway 1LRU evicts the item that has gone unused for the longest time — it is built on the real‑world pattern that recently used things are likely to be needed again soon.
• Takeaway 2The classic efficient implementation combines a HashMap (for instant lookup) with a doubly linked list (for instant reordering), giving O(1) get() and put().
• Takeaway 3LRU powers systems at every layer: CPU caches, operating systems, databases, browsers, CDNs, and distributed caches like Redis.
• Takeaway 4Plain LRU has a known weakness — vulnerability to pollution from one‑time scans — solved by variants like LRU‑K, 2Q, SLRU, and ARC.
• Takeaway 5Production systems combine LRU with TTL expiration, sharding, replication, and monitoring to build reliable, scalable caching layers.
• Takeaway 6Java offers two implementation paths: the quick LinkedHashMap approach, and the manual HashMap + doubly linked list approach expected in interviews and system design discussions.
• Takeaway 7Never treat a cache as a source of truth — it is a performance optimisation. Always keep the durable store authoritative and let the cache be a fast, replaceable copy.