LFU Cache, in depth: the O(1) frequency-bucket design, tie-breaking, aging, Redis's approximated LFU and when frequency beats recency

The policy, stated precisely

An LFU cache of capacity n supports get(key) and put(key, value). Each key carries a use count: inserting a key sets it to 1, and every successful get or every put to an existing key adds 1. When a put of a new key finds the cache full, the cache evicts the key with the smallest count. Ties are common, because many keys sit at count 1, so the policy must say how to break them; the standard rule evicts the least recently used key among those with the minimum count.

That tie rule is not a detail. Without it, the order of eviction among equally used keys depends on hash table iteration order, which makes behaviour hard to reason about and impossible to test. With it, LFU degenerates gracefully into LRU when counts are equal.

Two designs that are too slow

The simplest implementation stores a count and a last-use timestamp next to each value and, on eviction, scans every entry for the minimum (count, timestamp) pair. Lookups are O(1) but eviction is O(n), which is fine for a dozen entries and ruinous for a million.

A min-heap keyed by (count, timestamp) makes eviction O(log n), but every get changes a count, and changing a key's priority means either an indexed heap with a position map, as in the indexed priority queue, or lazy deletion, where stale heap entries pile up and are discarded when popped. Either way, every read costs O(log n) and the heap's pointer-chasing is unfriendly to the CPU cache. The observation that removes the logarithm is that counts only ever increase by exactly one.

The O(1) design: buckets by count

Keep three structures. A hash map from key to value and count gives O(1) lookup, as described in hash tables. A second map goes from each count to an ordered collection of the keys that currently have that count, oldest first. And an integer, min_freq, records the smallest count that has any keys.

A hit moves the key from bucket f to the end of bucket f + 1, both O(1) with a linked list or an insertion-ordered dictionary. If bucket f becomes empty and f was min_freq, min_freq becomes f + 1, and that is always correct because the key just moved there. An insert of a new key always goes to bucket 1 and resets min_freq to 1. An eviction pops the oldest key from bucket min_freq. No operation ever needs to search for the new minimum, which is the whole trick: min_freq only increases by one on a hit and only resets to one on an insert.

A complete implementation

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.vals = {}                            # key -> value
        self.freq = {}                            # key -> use count
        self.buckets = defaultdict(OrderedDict)   # count -> keys, oldest first
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None           # newest end of the next bucket

    def get(self, key):
        if key not in self.vals:
            return None
        self._touch(key)
        return self.vals[key]

    def put(self, key, value):
        if self.cap <= 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) >= self.cap:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.vals[victim], self.freq[victim]
        self.vals[key] = value
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1

Python's OrderedDict is a hash map threaded with a doubly linked list, so deleting any key and popping the oldest are both O(1). In Java the same role is played by LinkedHashSet, and in C++ by a std::list per bucket plus a map from key to list iterator. Two edge cases catch people in interviews and in production: a capacity of zero must store nothing, and updating an existing key's value counts as a use. Empty buckets are deleted so the bucket map never grows beyond the number of distinct live counts.

Worked trace

Follow a cache of capacity 2 through ten operations. The state after each step is written as buckets, oldest first.

Step 7 is where the tie rule earns its keep: keys 1 and 3 both have count 2, and key 1 was used less recently, so it goes. In this short trace LRU makes the same choices; the difference appears in longer runs, where a key with count 50 survives any number of one-off inserts under LFU, while LRU drops it as soon as enough new keys arrive.

Testing against a reference

Bucket bookkeeping is easy to get subtly wrong, especially the min_freq update. The best defence is a randomized differential test against a reference that is too slow to ship but simple enough to trust.

import random

class RefLFU:
    def __init__(self, cap):
        self.cap, self.d, self.t = cap, {}, 0     # key -> [value, count, last_use]

    def get(self, k):
        self.t += 1
        if k not in self.d:
            return None
        e = self.d[k]; e[1] += 1; e[2] = self.t
        return e[0]

    def put(self, k, v):
        self.t += 1
        if self.cap <= 0:
            return
        if k in self.d:
            e = self.d[k]; e[0] = v; e[1] += 1; e[2] = self.t
            return
        if len(self.d) >= self.cap:
            victim = min(self.d, key=lambda x: (self.d[x][1], self.d[x][2]))
            del self.d[victim]
        self.d[k] = [v, 1, self.t]

for seed in range(300):
    rng = random.Random(seed)
    cap = rng.randint(0, 5)
    fast, ref = LFUCache(cap), RefLFU(cap)
    for _ in range(2000):
        k = rng.randint(0, 9)
        if rng.random() < 0.5:
            assert fast.get(k) == ref.get(k), (seed, k)
        else:
            v = rng.random()
            fast.put(k, v); ref.put(k, v)

Small key ranges and small capacities force constant evictions and ties, which is where bugs live. The test passes because a key's position in its bucket reflects the time it entered that bucket, which is exactly its last use, the same quantity the reference compares.

What pure LFU gets wrong

Pure LFU has a long memory, and that is its main flaw. A key that was hot yesterday, such as the news story of the day, keeps its huge count after interest moves on, and it occupies space that today's popular keys need. This is called cache pollution. The mirror-image problem is new-key starvation: a newly popular key starts at count 1 and is evicted by the next insert before it can accumulate enough uses to prove itself, so in a full cache with a stale top tier, new entries churn through bucket 1 forever.

Counts also grow without bound. In a long-running process with 32-bit counters, a very hot key can eventually overflow, and even before that, the gap between old and new keys becomes so large that nothing new ever competes. Every production LFU therefore adds some form of aging.

Aging: halving, dynamic aging and sketches

The simplest fix is periodic halving: after every W operations, divide every count by two. Old popularity decays geometrically while relative order is mostly preserved. With the bucket structure, halving is an O(n) rebuild, which is cheap when amortized over W operations.

    def halve(self):
        old, self.buckets = self.buckets, defaultdict(OrderedDict)
        for f in sorted(old):
            nf = max(1, f // 2)
            for key in old[f]:
                self.freq[key] = nf
                self.buckets[nf][key] = None
        self.min_freq = min(self.buckets, default=0)

Halving merges counts 2k and 2k + 1 into one bucket, so recency order inside the merged bucket is only approximate; for a cache that is acceptable. LFU with Dynamic Aging (LFU-DA) avoids the global pass: each entry's priority is its count plus a cache-wide value L, and L is raised to the priority of each evicted entry. New entries therefore start at the level of recent victims rather than at 1, so old counts stop dominating without ever being rewritten. Implementing it needs a priority queue rather than unit-step buckets, because priorities jump.

The third approach separates measuring frequency from storing items. TinyLFU keeps approximate counts for many more keys than the cache holds in a compact count-min sketch, halves the sketch periodically, and uses it only to decide whether a new item deserves to displace the eviction candidate. That admission approach, and its pairing with an LRU window in caches such as Caffeine, is covered in the LRU article. For a self-tuning balance between recency and frequency without parameters, ARC is the other well-known design.

How Redis approximates LFU

Redis has offered allkeys-lfu and volatile-lfu eviction policies since version 4.0, and its implementation shows how to make LFU cheap at scale. Redis keeps no buckets and no lists. Each key carries an 8-bit counter, so values run from 0 to 255, updated as a Morris counter: a logarithmic, probabilistic counter that increments with decreasing probability as it grows. In the Redis source, new keys start at 5 so they are not evicted immediately, and above that the increment probability is 1 / ((counter - 5) x lfu-log-factor + 1). Eviction samples a handful of keys and evicts the one with the lowest counter, the same sampling idea Redis uses for its approximated LRU.

Two settings control behaviour. lfu-log-factor defaults to 10; according to the Redis documentation, at that setting 100 hits give a counter of about 10, 1,000 hits about 18, 100,000 hits about 142, and the counter saturates at 255 around a million hits. lfu-decay-time defaults to 1, meaning the counter is decremented for each minute that has elapsed since the key was last accessed, checked when the key is touched or sampled; 0 disables decay. You can inspect a key's counter with OBJECT FREQ key when an LFU policy is active, and the documentation's advice is to watch keyspace_hits, keyspace_misses and evicted_keys in INFO stats before and after switching policy.

Concurrency and choosing a policy

Like LRU, LFU turns every read into a write, because a hit moves a key between buckets. A single lock around the structure serialises all readers; sharding the cache by key hash, one LFU per shard with its own lock, is the standard fix, and buffering hit events to apply them in batches reduces contention further. The trade-offs mirror those for LRU and are discussed in depth in the LRU article and in caching in system design.

Failure modes

What to do next

1. Implement the bucket design above in your language and run the differential test with small capacities.
2. Replay a day of real access logs through LRU, LFU with halving, and your current policy, and compare hit ratios.
3. Choose an aging period from the replay, not from intuition, and check new-item hit ratio separately.
4. If you run Redis as a cache, try allkeys-lfu on a replica of production traffic and compare INFO stats.
5. Shard the cache before adding threads, and measure lock contention under load.