LFU Cache in O(1): Two Maps, Frequency Buckets, and a Minimum That Resets

A cache eviction policy is a bet about the future made with incomplete information about the past. LRU bets that what was just touched is what comes next. That bet is wrong often enough to matter, and the failure is quiet.

The policy is easy to state. Getting it to constant time without a linear scan somewhere in the request path is the part worth understanding, because the same index-inversion trick shows up in job schedulers, rate limiters, and connection pool managers.

The burst that breaks recency

A product detail endpoint caches responses in memory so it does not query Postgres on every request. The cache holds 10,000 entries. Black Friday arrives and one SKU takes tens of thousands of reads per minute.

Now add long-tail browsing. A marketing email goes out, thousands of distinct product IDs are requested, and the cache is full of keys that will each be read exactly once.

LRU evicts by oldest touch. The hot SKU has not been read in the last 200 milliseconds because the request thread spent that time serving other keys. It is now the least recently used key in the cache, and it gets evicted to make room for a product page that will never be requested again.

The next read of the bestseller misses. Postgres takes the hit. The connection pool saturates, and because the database is shared, p99 latency on checkout moves too. The cache did not fail loudly. It simply stopped protecting the one key that mattered while looking healthy on hit rate.

LFU asks a different question. Instead of “what did I touch last”, it asks “what do callers actually want”, measured as a hit count. The cold key has a frequency of 1. The bestseller has a frequency in the thousands. The eviction candidate is obvious.

cache full, need room for a cold key

  key        freq    recency        LRU evicts?    LFU evicts?
  SKU-4471   18,204  200 ms ago     yes            no
  SKU-9012   1       1 ms ago       no             yes
  SKU-3310   1       3 ms ago       no             yes

Within one frequency, ties break by recency, so two keys read equally often evict the one touched longer ago. That is the whole policy. Everything after this is data structure.

Why the obvious implementation is quadratic-ish

The version everyone writes first keeps two maps: key to value, and key to frequency. Eviction is then a loop over the frequency map looking for the smallest number.

evict:
  victim = null
  min    = +infinity
  for each (key, freq) in frequencies:     // O(n)
      if freq < min:
          min    = freq
          victim = key
  remove victim

At 10,000 entries that is 10,000 comparisons per eviction. Eviction only happens on insert-when-full, so the cost is proportional to write traffic against a full cache, and it lands directly in the request that triggered the insert.

The damage is easy to misread. Hit rate does not drop. Latency does, and only on writes, and only when the cache is at capacity. So the symptom is a p99 that degrades with traffic while the average stays flat and no error is raised.

The important part is what this really is. It is not a slow sort. It is a linear scan of the entire working set in the request path, which means the cache has exchanged a database round trip for a memory walk over everything it holds. Both are latency; only one of them scales with entries.

The fix follows directly. If scanning to find the minimum is the problem, then do not scan. Keep a pointer to where the minimum is.

Invert the index

Three pieces of state, plus the node representation:

• keyToNode maps a key to its node, for constant-time lookup.
• freqToBucket maps a frequency to a doubly linked list of every node at that frequency.
• minFreq is the lowest frequency currently present.
• A node carries its key, value, frequency, and two links.

The second map is the part that is not obvious. Grouping keys by frequency gives two things at once: eviction becomes “remove the tail of one list”, and the recency tie-break comes free, because the list is ordered by touch time within the bucket.

keyToNode                freqToBucket
  SKU-4471 -> Node         1 -> [ SKU-9012 <-> SKU-3310 ]
  SKU-9012 -> Node         4 -> [ SKU-1180 ]
  SKU-3310 -> Node       18204 -> [ SKU-4471 ]
  SKU-1180 -> Node
                         minFreq = 1

Head of a bucket is the most recently touched key at that frequency. Tail is the eviction candidate. One list per frequency, not one list for the cache.

Reading a key

A get is four operations, and the order matters:

1. Look up the node. Miss returns immediately without touching any state.
2. Unlink the node from the bucket for its current frequency.
3. If that bucket is now empty and its frequency was the minimum, advance minFreq by one.
4. Increment the node’s frequency and insert it at the head of the next bucket.

Step 3 has a condition that is easy to get wrong, and it is where most broken implementations live. Advancing minFreq on any empty bucket skips past buckets that still hold keys, and the next eviction takes a victim from a higher frequency than it should.

Advancing by exactly one is also safe, and worth understanding why. The only way a bucket at frequency f empties is by moving its last node up to f+1. So if the emptied bucket was the minimum, frequency f+1 necessarily exists immediately after. There is never a gap to search over, and no loop is needed to find the new minimum.

Writing a key

Set has two cases, and only one of them is interesting.

An existing key is an access. Assign the new value and run the same promote step as a get, bumping the frequency exactly once. The alternative policy is to not promote on write, which is defensible for a write-heavy cache where a read should count for more than a write, but it has to be a decision rather than an accident.

A new key needs room:

1. If the cache is at capacity, evict the tail of the minFreq bucket and delete that key from keyToNode.
2. Create a node at frequency 1.
3. Insert it at the head of the frequency-1 bucket.
4. Set minFreq = 1.

A newly inserted key is always the least frequent thing in the cache, so resetting minFreq to 1 is not just convenient, it is the truth.

Eviction touches one node and two map entries. That is the entire claim of the O(1) design, and it holds because the eviction candidate was already located.

The implementation

public sealed class O(1)LfuCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, Node> _keyToNode = new();
    private readonly Dictionary<int, Bucket> _freqToBucket = new();
    private int _minFreq;

    public O(1)LfuCache(int capacity)
    {
        ArgumentOutOfRangeException.ThrowIfNegativeOrZero(capacity);
        _capacity = capacity;
    }

    public int Count => _keyToNode.Count;

    public bool TryGet(TKey key, out TValue value)
    {
        if (!_keyToNode.TryGetValue(key, out var node))
        {
            value = default!;
            return false;
        }

        Promote(node);
        value = node.Value;
        return true;
    }

    public void Set(TKey key, TValue value)
    {
        if (_keyToNode.TryGetValue(key, out var existing))
        {
            existing.Value = value;
            Promote(existing);
            return;
        }

        if (_keyToNode.Count == _capacity) EvictOne();

        var node = new Node(key, value);
        _keyToNode.Add(key, node);
        BucketFor(1).AddToHead(node);
        _minFreq = 1;
    }

    // Move a node out of its current bucket and into the next frequency up.
    private void Promote(Node node)
    {
        var freq = node.Freq;
        var bucket = BucketFor(freq);
        bucket.Unlink(node);

        // minFreq may only advance when the bucket just emptied *was* the
        // minimum. Advancing on any empty bucket skips a populated one.
        if (bucket.Count == 0)
        {
            _freqToBucket.Remove(freq);
            if (freq == _minFreq) _minFreq = freq + 1;
        }

        node.Freq = freq + 1;
        BucketFor(freq + 1).AddToHead(node);
    }

    private void EvictOne()
    {
        var bucket = BucketFor(_minFreq);
        var victim = bucket.RemoveTail();
        _keyToNode.Remove(victim.Key);
        if (bucket.Count == 0) _freqToBucket.Remove(_minFreq);
        // _minFreq can now point at a bucket we just dropped. Set() re-seeds
        // it to 1 immediately, and nothing reads in between.
    }

    private Bucket BucketFor(int freq)
    {
        if (_freqToBucket.TryGetValue(freq, out var bucket)) return bucket;
        bucket = new Bucket();
        _freqToBucket[freq] = bucket;
        return bucket;
    }

    private sealed class Node(TKey key, TValue value)
    {
        public TKey Key { get; } = key;
        public TValue Value { get; set; } = value;
        public int Freq { get; set; } = 1;
        public Node? Prev { get; set; }
        public Node? Next { get; set; }
    }

    private sealed class Bucket
    {
        public int Count { get; private set; }
        private Node? Head { get; set; }
        private Node? Tail { get; set; }

        public void AddToHead(Node node)
        {
            node.Prev = null;
            node.Next = Head;
            if (Head is not null) Head.Prev = node;
            Head = node;
            Tail ??= node;
            Count++;
        }

        public void Unlink(Node node)
        {
            if (node.Prev is not null) node.Prev.Next = node.Next;
            else Head = node.Next;

            if (node.Next is not null) node.Next.Prev = node.Prev;
            else Tail = node.Prev;

            node.Prev = null;
            node.Next = null;
            Count--;
        }

        public Node RemoveTail()
        {
            var node = Tail ?? throw new InvalidOperationException("Bucket is empty.");
            Unlink(node);
            return node;
        }
    }
}

Walking one trace

The trace is where the design stops being abstract. Capacity 2, four keys, counting every bucket and the pointer.

capacity = 2

  op         buckets                 minFreq
  ---------------------------------------------
  set A:f1   1:[A]                   1
  set B:f1   1:[B, A]                1        A is the tail
  get A      1:[B]  2:[A]            1
  set C      evict tail of 1 -> B
             1:[C]  2:[A]            1
  get C      2:[C, A]                2        bucket 1 emptied, minFreq -> 2
  get A      2:[C]  3:[A]            2
  get C      3:[C, A]                3        bucket 2 emptied, minFreq -> 3
  set D      evict tail of 3 -> A
             1:[D]  3:[C]            1

Four things are visible in that table.

B is evicted at set C while A survives, because A has been promoted and B has not. That is the whole reason to prefer frequency over recency.

minFreq moves upward only along promotions between insertions, and resets to 1 when a new key arrives. That qualification belongs in the invariant; the pointer is not globally monotonic.

Empty buckets disappear rather than lingering as empty list objects. Without that cleanup, freqToBucket grows monotonically and a cache that ran hot for a week holds hundreds of dead lists.

The final eviction drops A rather than C even though both are at frequency 3. A is the tail of bucket 3, so A is the least recently touched of the two least frequently used keys. The tie-break is doing real work.

What it costs at runtime

Per operation the cache does two to four hash lookups and a handful of pointer writes. On 64-bit .NET the accounting is roughly:

per node    header 16 + key 8 + value 8 + freq 4 + prev 8 + next 8  = 52 B -> 56 B
per entry   hash 4 + next 4 + key ref 8 + value ref 8               = 24 B
per bucket  header 16 + head 8 + tail 8 + count 4                   = 40 B

10,000 entries, 200 distinct frequencies
  nodes        10,000 x 56 B = 560 KB
  map entries  10,000 x 24 B = 240 KB
  buckets          200 x 40 B =   8 KB
                                     ~808 KB of bookkeeping

That is the overhead before counting the cached values themselves. For a cache of small strings it is real money; for a cache holding 10 MB of serialised responses it is noise. Size the decision against the values, not in the abstract.

The mechanical cost is memory locality rather than arithmetic. A single get walks a dependent chain: the keyToNode bucket array, the node, the bucket for its frequency, and the neighbour pointer for the unlink. Those are three or four cache lines that must resolve in order, because none can be fetched until the previous one lands.

Object size and cache residency depend on runtime version, architecture, generic types, dictionary load factor, and allocator layout. Measure retained bytes with the deployed CLR; a hand-computed 560 KB is illustrative, not a capacity input.

The distribution of frequencies matters more than the count of keys. 200 distinct frequencies means 200 list objects and 200 more indirections. A workload where every key is read exactly once produces one bucket and a list the length of the cache, which is LRU wearing an LFU hat. A workload with a stable hot set produces a handful of buckets and deep, hot, cache-resident lists.

Where the policy fights you

Exact LFU is correct and still the wrong answer in most systems, for reasons that have nothing to do with data structures.

Nothing ages. A key that was hot in January and has not been read since still holds a frequency in the thousands. The key that became hot last week is at 1. LFU keeps serving the dead one and keeps the live one out of the cache, indefinitely. The fix is decay: periodically scale counters down, so a key must keep earning its rank. Redis exposes this as a decay time and a decay factor, and the shipped defaults age counters very slowly on purpose.

Counters saturate or overflow. Redis uses an 8-bit logarithmic counter and a probabilistic increment whose probability changes with the current counter and lfu-log-factor; it is not a fixed one-in-five sample. A separate last-decrement field supports decay. The result is a ranking rather than an exact count.

Scan resistance cuts both ways. LFU is resistant to a scan flooding the cache with one-off keys, which is its main virtue. It is also resistant to the cache learning that a scan is happening. A crawler walking your whole keyspace inflates counters on keys nobody wants, and your genuinely hot keys lose relative rank. Incrementing probabilistically rather than on every access is partly a defence against this.

Cold start is LRU with extra steps. A fresh process has every key at frequency 1, so the policy degenerates to recency until the counters warm. Whatever traffic arrives in the first few minutes decides the winners, and a deploy is a good moment to be unlucky.

Frequency is not importance. A health-check endpoint read every second outranks a checkout endpoint read every hour. LFU is measuring demand, and if your priority is business value, the ranking input is wrong and no data structure fixes it. SLRU, segmented LRU, and window-TinyLFU exist because the common answer is to keep two or three LRU segments and admit entries through a frequency filter rather than trusting one count.

The counters are the cache. At millions of keys, a frequency field per key is a material fraction of memory, and updating it on every read dirties a cache line whether or not the key is useful. This is the point at which an approximate policy maintained by a dedicated system beats an exact one maintained inline.

A production-ready architecture

Exact LFU earns its keep as a local guard in front of an expensive miss, not as a distributed cache. The shape that works is bounded memory, skewed access, and a miss path that costs a database query or a remote call.

   request
      |
      v
  +----------+   hit    +------------------+
  | LFU      | --------> | return value    |
  | guard    |           +------------------+
  | (bounded)|   miss
  +----------+   |
      ^          v
      |     +-----------+   error   +-----------+
      |     | origin    | ---------> | 500      |
      |     | fetch     |            +-----------+
      |     +-----------+
      |          | success
      |          v
      |     +-----------+   stale    +-----------+
      +-----| admit     | ---------> | retry    |
           +-----------+            +-----------+

Things that earn a slot in a local LFU guard: a recommendation service caching feature vectors for the top catalogue, a pricing service caching SKU rows during a promotion, a gateway caching OAuth introspection results for a handful of high-volume clients.

Things that do not: anything shared across instances, because each process would keep a different ranking and the cache would stop agreeing with itself. That is a distributed cache’s job.

In .NET, IMemoryCache supports size limits, priorities, expiration, and compaction heuristics, but it does not promise exact LFU. Redis offers approximate LFU policies, with network/process trade-offs rather than “free at any size.” Hand-roll exact LFU only when the in-process latency requirement, bounded size, and measured skew justify owning concurrency, expiration, and memory accounting.

A delivery checklist:

1. Measure the hit rate and the access skew before choosing a policy. LFU without skew is LRU with extra bookkeeping.
2. Set capacity from a measured retained-memory budget; per-entry overhead depends on the CLR and key/value types.
3. Decide whether a write promotes the key, and write that decision down.
4. Advance minFreq only when the emptied bucket was the minimum.
5. Remove empty buckets, or watch freqToBucket grow for the life of the process.
6. Add aging, or accept that a key’s rank is permanent and design around it.
7. Do not read the cache from metrics, logging, or health-check paths, or instrumentation becomes the hottest key in it.
8. Decide what happens at capacity 0 and capacity 1, and test both.
9. Measure eviction cost directly. If a write-when-full is slow, the scan is still there.
10. Treat the shown structure as non-thread-safe. One lock preserves a global LFU order; independent sharded LFU instances improve concurrency but change eviction semantics. Per-key locks over shared frequency lists are not sufficient.

Failure stories worth testing

Flood the cache with one-off keys while a hot key is being read

This is the reason the policy exists, so it is the test that matters most. Hold one key at a steady request rate, then push 10,000 distinct single-use keys through a full cache. Confirm the hot key is still resident afterwards. If it is not, the implementation is evicting by recency regardless of what the code claims.

Check that minFreq never points at a bucket that is not there

Log minFreq and the live bucket keys on every eviction, through a long randomised run of mixed reads and writes. Any mismatch is a correctness bug that will surface as a wrong eviction rather than an exception. The invariant to assert is that freqToBucket[minFreq] is non-empty at the moment of eviction.

Promote the same key 50,000 times and watch the buckets

Confirm the node appears in exactly one bucket at every step, that its frequency increases by exactly one per access, and that exactly one bucket empties at the end. A node present in two lists at once is the classic double-link bug, and it corrupts eviction order in ways that only show up under load.

Restart the process and immediately test the hot set

Confirm that a cold cache behaves as LRU, then measure how long it takes to reach the ranking you expect. If the answer is “however long the first promotion wave takes”, that is a deploy-time risk, and it belongs in a runbook rather than a surprise.

Grow a key’s frequency, stop reading it for a simulated day, then flood with new hot keys

Plain exact LFU fails this test, and that is the point. A dead key keeps its rank and keeps its cache slot while the genuinely hot keys sit at frequency 1. This test is how you find out whether you need decay, and it is much cheaper to run now than to diagnose in production.

Common mistakes

Mistake	What actually happens	Better decision
Scanning all keys for the minimum frequency	O(n) in the request path, invisible in hit rate, visible in write p99	Keep minFreq and update it on promotion
One linked list for the whole cache	No way to isolate a frequency, so eviction is still a scan	One list per frequency, keyed in a map
Advancing minFreq whenever a bucket empties	Skips a populated bucket and evicts a hotter key	Advance only when the emptied bucket was the minimum
Evicting the head of the minimum bucket	Drops the most recently used key at that frequency	Insert at head, evict from tail
No tie-break inside a bucket	Eviction is arbitrary among equally frequent keys	The list order is the recency order; use it
Leaving empty buckets in the map	freqToBucket grows monotonically for process lifetime	Remove a bucket when its count hits zero
Removing the node but not the keyToNode entry	Key stays visible, value is gone, memory leaks	Unlink from both structures
Set on an existing key does not promote	A write-heavy workload never accumulates frequency	Decide the write policy explicitly
No aging on the counters	A key hot in January outranks everything, forever	Decay counters, or cap them
Exact counters at millions of keys	Counter memory and cache-line traffic dominate	Approximate LFU with probabilistic increments
Reading the cache from metrics or logging	Instrumentation becomes the highest-frequency key	Keep observability off the cached path
Per-key locks over shared buckets	Two keys can still mutate the same list and minFreq	One global lock, or independent cache shards
Unbounded capacity	The cache is a memory leak with a hit-rate metric	Derive capacity from a memory budget
Assuming MemoryCache gives you LFU	It does not; the ranking is recency-based	Measure, then choose a policy deliberately

The complete story in one minute

A get hashes the key, lands on a node, and reads its frequency. The node is unlinked from the list for that frequency and pushed to the head of the list one higher, which makes the most recently used key the head of its bucket and the eviction candidate its tail. If the bucket it left is now empty and it was the minimum, the minimum moves up by one, which is safe because the node just moved guarantees the next bucket exists. Nothing scans.

A set on an existing key is a value assignment plus that same promotion. A set on a new key evicts the tail of the minimum-frequency bucket if the cache is full, then inserts the node at frequency 1, which makes it the least frequent entry and resets the minimum to 1. The node is removed from both the frequency map and the key map, because a cache that forgets to unlink one of them leaks quietly.

Every operation is a constant number of expected-time hash lookups and pointer writes. The implementation shown is a sequential data structure; concurrency needs one lock or truly independent shards. Bookkeeping size must be measured on the deployed CLR. Frequency buckets make eviction expected O(1) and provide an LRU tie-break, so the grouping does double duty.

The policy is the part to distrust. Frequency is a demand signal with no decay, business value, or cold-start memory. Production policies such as Redis LFU and TinyLFU make frequency approximate and age it; TinyLFU commonly uses the estimate for admission rather than making it the entire eviction structure. Use exact LFU when local, bounded, and demonstrably better on a replay of the workload. The data structure is the easy half. The admission and aging contract decides whether it helps.

Technical references

• Redis: LFU eviction, logarithmic counters, and decay
• .NET: ASP.NET Core in-memory caching
• Einziger et al.: TinyLFU—A Highly Efficient Cache Admission Policy