What Is an LRU Cache?

An LRU cache — Least Recently Used — evicts the entry that has gone untouched the longest when it runs out of room. An LFU cache — Least Frequently Used — evicts the entry that has been accessed the fewest times. Both answer the same question — what should we throw away? — using a different signal: LRU asks when an entry was last used, LFU asks how often.

Which of the two serves you better depends entirely on the shape of your traffic, and it is usually the most consequential decision in a cache eviction policy. Getting it wrong fails silently — the cache still returns correct answers, it just stops returning many of them — so the symptom arrives as unexplained database load, hours or days later, looking nothing like a caching problem.

How an LRU Cache Works

The classic implementation pairs two structures. A hash map gives O(1) lookup from key to entry. A doubly linked list holds the same entries in recency order, most recently used at the head. On a read, the entry is unlinked from its current position and spliced back in at the head; on a write to a full cache, the entry at the tail is dropped. Both operations touch a fixed number of pointers, so get and put are O(1).

The detail that matters in production is easy to skim past: a read mutates the cache. Every successful lookup rewrites the ordering structure. That is why a read-write lock buys an LRU cache nothing — reads are writes, so there are no readers to share it — and it is the reason essentially every high-throughput cache in real use approximates LRU rather than implementing it exactly.

The approximations differ but share an idea: sample a handful of candidates and evict the oldest in the sample rather than the oldest overall, or record recency coarsely enough that concurrent readers rarely contend. Hit rates barely move, at a fraction of the coordination cost.

How an LFU Cache Works

LFU keeps a counter per entry and evicts the lowest one. The naive implementation scans every entry to find the minimum, which is O(n) and unusable at any real size. The standard O(1) structure instead keeps a doubly linked list of frequency buckets, holding only the counts currently in use — if nothing has been read exactly seven times, no bucket for seven exists. Incrementing an entry moves it to the next bucket along, creating that bucket if the neighbor is not at count + 1; evicting takes an entry from the lowest bucket. Implementations that keep each bucket in insertion order get LRU tie-breaking among equals for free.

A textbook LFU has one flaw that makes it unusable as written: counters only ever go up. An entry that was hot last month keeps the count it earned then, and a genuinely popular new entry starting at 1 may never catch it. Left alone, an LFU cache slowly fossilizes around a working set that no longer exists.

Every practical LFU therefore decays, and there are two common mechanisms. Periodic halving divides every counter by two at intervals, so old popularity fades geometrically while the relative ordering survives; this is the approach Caffeine takes. Probabilistic logarithmic counting makes each successive increment less likely as the count grows, which bounds the counter's size and stops any one entry running away with it. Redis takes the second and pairs it with a linear decay: an 8-bit counter that increments probabilistically and loses a point for every lfu-decay-time minutes elapsed since it was last touched, stored with a 16-bit timestamp inside the same 24-bit field Redis otherwise uses for LRU.

LRU vs LFU: A Direct Comparison

Given one cache in one state, the two policies routinely pick different victims — and each pick looks like a mistake from the other's point of view.

As an operational rule: if your access pattern shifts continuously, choose LRU. If it is stable and heavily skewed — a few hundred popular products in a catalog of millions, a handful of configuration keys read on every request — choose LFU. If you do not know which you have, start with LRU and measure your hit ratio before changing anything. The measurement is worth more than the policy.

Where Each One Fails

Each policy has a signature way of going wrong, and they are worth recognizing before you meet them in production. LFU gets two entries below because its two failures are opposite in direction, not because it is the weaker policy.

LRU and the nightly batch job. At 03:00 a report generator, a reindexing task or a crawler walks two million rows. Every one of them passes through a cache sized for a hundred thousand entries, and every one of them promotes itself to the head of the recency list on the way through. By 03:20 the cache contains nothing but rows that will never be requested again, and the working set that took all day to build is gone. At 09:00 the traffic peak arrives, finds a cold cache, and lands on the database. The cache reports a hit ratio collapse hours after the job that caused it has finished — which is why this one is diagnosed late, and often misdiagnosed as a capacity problem.

LFU and the launch that never ends. A product sits on the homepage for a week and drives its counter to the ceiling. The promotion ends, traffic moves on, and the entry stays resident for months because nothing newer can climb high enough to displace it. Multiply that by every item that has ever been briefly popular and the cache fills up with history. This is the failure decay exists to prevent, and it is why an LFU cache with decay switched off performs worse than random eviction.

LFU and the new-entry problem. The mirror image, and a subtler one. A freshly inserted entry starts at 1 and competes against incumbents that have been accumulating since the cache warmed up. On the very next eviction the new entry is the lowest, and it goes straight back out — even if it is about to become the most requested key in the system. An LFU cache with a full hot set can be effectively closed to new data.

Those last two are worth reading together, because they are the same property seen from opposite sides. LFU cannot tell a scan from a launch. Its resistance to one is exactly its blindness to the other: a low count means "nobody will ever want this again" and "everybody is about to want this" at the same time, and frequency alone cannot separate them. Fixing that requires deciding what to admit, not just what to evict — which is what W-TinyLFU, below, does.

And you are unlikely to be running either one exactly. Redis and Valkey approximate both policies with sampling and probabilistic counters, because exact ordering costs more than the hit rate it buys — when you configure allkeys-lru you are asking for something LRU-shaped, not for a guarantee about which key leaves. Memcached and Caffeine go further and run different algorithms altogether, which is the subject of the next section.

Beyond LRU and LFU: Segmented LRU and W-TinyLFU

LRU and LFU are the two policies everyone knows, and neither is what a modern cache actually runs. Decades of work — 2Q, LIRS, ARC and others — has gone into combining the recency and frequency signals instead of choosing between them. Two of the results are worth knowing, because you are probably running both already.

Segmented LRU is the cheapest of them. Memcached splits each slab class into HOT, WARM and COLD queues. A new item enters HOT; items are promoted toward WARM once they have been hit a second time, and an item that proves active down in COLD is moved back up. Its documentation states the goal plainly — "to better protect active items from 'scanning'" — which is the batch-job failure above, solved with two flag bits per item. Segmented LRU has been the default in Memcached since 1.5.0. Notably, Memcached offers no LFU mode at all.

W-TinyLFU is the current state of the art for in-process caches and the policy behind Caffeine, the standard Java caching library. It reframes the problem as admission rather than eviction. A small LRU window — 1% of the cache to begin with — receives every new entry. When the window overflows, the candidate leaving it is not admitted to the main region automatically; instead its estimated frequency is compared against the frequency of the main region's own eviction candidate, and the more popular of the two survives. The main region is itself a segmented LRU, starting at 80% protected and 20% probation. Both of those splits are starting points rather than constants: Caffeine samples its own hit rate and resizes the window against the main region as it runs, giving more room to the window on recency-biased traffic and less on frequency-biased traffic.

The frequency estimates come from a Count-Min Sketch of 4-bit counters, which Caffeine documents as costing about eight bytes per cache entry — small enough that the cache can track the popularity of keys it does not currently hold. An aging step periodically halves every counter, which is the decay an LFU needs, applied to a structure cheap enough to make it painless.

Note how the two halves divide the work, because it maps exactly onto the two failures above. The window is what answers LFU's new-entry problem — every new key gets a period of residency in which to earn a frequency, rather than being judged at count 1 and evicted immediately. The admission filter is what answers LRU's scan problem — a key pulled through once by a batch job never accumulates enough estimated frequency to displace anything that matters.

In the sample simulator report published on Caffeine's wiki — a 43.7 million request trace — W-TinyLFU reaches a 45.25% hit rate against 20.24% for LRU, with Bélády's theoretical optimum at 48.09%. Treat that as an illustration rather than a headline: the gap is entirely workload-dependent, narrowing to a few percentage points on some traces and opening much wider on looping ones. The claim that survives generalization is the narrower and more useful one — an admission policy informed by frequency beats pure recency on most real workloads, and rarely costs much on the rest.

LRU and LFU in Java: LinkedHashMap and Caffeine

Java has shipped an LRU cache in the standard library since 1.4, and most developers who write one by hand did not need to. LinkedHashMap takes a third constructor argument, accessOrder; set it to true and the map reorders itself on every get. Override removeEldestEntry to say when the oldest entry should go:

Map<String, Product> cache =
    new LinkedHashMap<String, Product>(capacity, 0.75f, true) {   // accessOrder = true
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Product> eldest) {
            return size() > capacity;
        }
    };

That is a complete, correct LRU cache in six lines, and it is the right answer for a bounded lookup table inside a single object. Two limits stop it being the right answer anywhere else.

It is not thread-safe, and it cannot cheaply be made so. This is the same property as above with a cost attached: because access-order reordering mutates the map on read, wrapping it in Collections.synchronizedMap serializes every lookup behind one lock. The single-threaded version of the same trap catches people first — with accessOrder set, get() structurally modifies the map, so reading entries while iterating over it throws ConcurrentModificationException with only one thread running. It is also why ConcurrentHashMap offers no eviction of its own.

Caffeine is the usual replacement. It is the successor to Guava's CacheBuilder — which was a sharded LRU, one independent LRU per segment, an artifact of its concurrency design rather than a policy choice — and Spring dropped Guava cache support in favour of it in Spring 5.0. Caffeine exposes maximumSize and no LRU-or-LFU switch, because W-TinyLFU adapts on its own. Worth correcting a claim that circulates widely: Caffeine is not Spring Boot's default cache, and it does not ship with spring-boot-starter-cache. Spring Boot works down a fixed list of cache providers and falls back to a ConcurrentHashMap-backed simple manager when none is present. Caffeine sits near the end of that list and auto-configures only once you put the library on the classpath yourself.

Not every library gives you the choice at all. Ehcache 3 removed the LRU/LFU/FIFO setting that Ehcache 2 had — its on-heap store samples eight candidates and evicts the one with the oldest last-access time, and an application can only advise against evicting an entry, advice the cache is not obliged to take.

And a JVM-local cache is still local. It does not survive a restart, it is not shared between instances, and ten application nodes mean ten independent copies making ten independent eviction decisions. That is the point at which the policy question moves out of the process — see Java LRU cache for the Java-specific view, and distributed caching for what changes once the cache is shared.

LRU and LFU in Redis and Valkey

Redis and Valkey both support LRU and LFU, and neither is enabled by default — the default maxmemory-policy is noeviction, which rejects writes once maxmemory is reached. You opt in explicitly, and the choice is server-wide.

Neither policy is exact. Both are sampled: maxmemory-samples (default 5) sets how many candidate keys the server inspects before choosing one, so raising it costs CPU and buys accuracy. On the LFU side, lfu-log-factor (default 10) governs how quickly the probabilistic counter saturates, and lfu-decay-time (default 1 minute) is the decay described earlier, exposed as a knob. The two products have also diverged here — Redis added least-recently-modified policies in 8.6 and now offers ten maxmemory-policy values, while Valkey still has eight. Our guide to Redis eviction policy covers all ten values, the volatile-* trap and how to size maxmemory.

Per-Cache LRU and LFU in Java With Redisson

That server-wide scope has a second consequence, and teams usually run into it later than the first: there is exactly one answer per instance. Sessions are recency-driven and want LRU; a product catalog is skewed and wants LFU; both live in the same Redis. Stock configuration cannot express that, so you either run two instances or you pick one policy and let the other workload live with it.

Redisson, a Java client for Redis and Valkey, sets eviction per collection instead. An RMapCache takes a maximum size and an eviction mode of its own, and two maps on the same server can disagree:

RMapCache<String, Product> catalog = redisson.getMapCache("catalog");
catalog.trySetMaxSize(10_000, EvictionMode.LFU);   // stable, skewed hot set

RMapCache<String, Session> sessions = redisson.getMapCache("sessions");
sessions.trySetMaxSize(50_000, EvictionMode.LRU);  // recency-driven

Both of those are in the free, open-source Redisson. EvictionMode has exactly two values, LRU and LFU, and the single-argument setMaxSize(int) and trySetMaxSize(int) default to LRU.

Worth knowing how it works, because it does not behave like the server-side policy: the bound is enforced by Redisson rather than by the server, through Lua scripts the client ships with each operation, and it does not touch maxmemory-policy at all. Each RMapCache keeps an auxiliary sorted set alongside the hash — access timestamps under LRU, access counts under LFU — which reads and writes both update. Only writes trim it, though, and the practical consequence is worth knowing: a bounded map is brought back under its limit only when something writes to it. A map that goes read-only while over its limit stays over its limit until the next write. (Redisson's background eviction task is a separate mechanism that removes expired entries, not excess ones.)

The same choice exists in the local tier. Near caches built with RLocalCachedMap take an eviction policy for the in-process copy, and two of the five values have no server-side equivalent in either Redis or Valkey:

// org.redisson.api.options.LocalCachedMapOptions — not the deprecated
// org.redisson.api.LocalCachedMapOptions, which has its own EvictionPolicy
LocalCachedMapOptions<String, Product> options =
    LocalCachedMapOptions.<String, Product>name("products")
        .cacheSize(10_000)
        .evictionPolicy(EvictionPolicy.LFU);   // NONE | LRU | LFU | SOFT | WEAK

RLocalCachedMap<String, Product> products = redisson.getLocalCachedMap(options);

SOFT and WEAK hand eviction to the garbage collector through reference types rather than to a size bound, which is only meaningful for a cache living in the JVM heap. Note that with Redisson's own cache provider cacheSize is honoured only for LRU and LFU; the other three ignore it and are unbounded or GC-driven. (Switching the provider to Caffeine applies the bound under every policy.)

The same two settings reach the standard caching abstractions, so you do not have to program against Redisson's own types to get them. Through Spring Cache, a CacheConfig carries both a maximum size and an eviction mode, defaulting to LRU:

Map<String, CacheConfig> config = new HashMap<>();
CacheConfig catalog = new CacheConfig();
catalog.setMaxSize(10_000);
catalog.setEvictionMode(EvictionMode.LFU);
config.put("catalog", catalog);

Hibernate, MyBatis and Micronaut expose the size bound too — hibernate.cache.redisson.[REGION].eviction.max_entries and their equivalents — though those three wire it through the single-argument call and so are LRU only. One trap worth knowing if you use the native-hash variants: on that path the size bound is accepted and silently ignored rather than rejected, so a configured maximum does nothing and logs nothing.

Both RMapCache and RLocalCachedMap are available in the free edition. Redisson PRO adds the data-partitioned variants, which spread a single map — and its eviction work — across every master in a cluster, along with a byte-based size limit rather than an entry count. It can be evaluated with a free trial.

LRU and LFU Caches: Frequently Asked Questions

What Is an LRU Cache?

An LRU (Least Recently Used) cache is a fixed-size cache that evicts the entry which has gone untouched the longest when it needs room for a new one. It is typically built from a hash map for O(1) lookup plus a doubly linked list that maintains recency order, with every read moving its entry to the front. LRU is the most widely used eviction policy and a sensible default for most workloads.

What Is an LFU Cache?

An LFU (Least Frequently Used) cache evicts the entry that has been accessed the fewest times, tracking a counter per entry rather than a timestamp. It suits workloads with a stable, heavily skewed hot set, where a small fraction of keys serves most requests. Practical implementations decay counters over time, because counters that only increase cause the cache to fill with entries that were popular long ago.

What Is the Difference Between LRU and LFU Cache?

They use different signals. LRU asks when an entry was last used and evicts the oldest; LFU asks how often it has been used and evicts the least popular. LRU adapts quickly when the working set changes but is flushed by sequential scans. LFU resists scans and protects a stable hot set but adapts slowly and can hold stale entries unless its counters decay.

When Should You Use LFU Instead of LRU?

Use LFU when your access distribution is heavily skewed and stable — a few hundred popular items in a catalog of millions, or configuration keys read on every request — and especially when bulk jobs periodically sweep large amounts of data through the cache. Use LRU when the working set shifts continuously. If you are unsure, start with LRU, measure the hit ratio, and change only if the data says to.

Does Redis Use LRU or LFU?

Both, but neither by default. Redis and Valkey default to noeviction, which rejects writes once maxmemory is reached. You opt in through maxmemory-policy using values such as allkeys-lru or allkeys-lfu. Both implementations sample a handful of candidates rather than maintaining an exact ordering, and the setting applies to the whole instance rather than to individual keys or collections.

What Are the Disadvantages of LFU?

LFU has three main disadvantages. It adapts slowly, because a new entry starts at a count of one and must out-earn established entries. Without decay it fossilizes, holding entries that were popular months ago. And it can be effectively closed to new data: a freshly inserted entry is often the lowest-count entry in the cache and is evicted again immediately, even if it is about to become genuinely hot.

What Is the Difference Between LRU and TinyLFU?

LRU decides what to evict; TinyLFU decides what to admit. It estimates how often keys have been requested using a compact Count-Min Sketch, then compares a new candidate against the entry the cache would otherwise evict and keeps whichever is more popular. W-TinyLFU, used by Caffeine, adds a small LRU window in front so that recency bursts are still served, combining both signals rather than choosing one.

What Is Better Than an LRU Cache?

For in-process Java caches, W-TinyLFU as implemented by Caffeine generally achieves a higher hit rate than LRU on the same memory, because it combines frequency and recency and filters what enters the cache. Older policies such as segmented LRU, 2Q and ARC improve scan resistance in similar ways. The honest caveat is that the advantage is workload-dependent, so measure on your own traffic rather than trusting a benchmark.

Similar terms

• Cache Eviction
• Java LRU Cache
• Cache Miss
• Cache Memory
• Cache Invalidation
• Redis Caching
• Redis Eviction Policy
• Redis TTL
• Distributed Caching
• Near Cache
• Redis Client-Side Caching
• Java Map
• Java ConcurrentHashMap
• JCache
• Spring Cache
• In-Memory Database