Least frequently used

As explained in Advanced Algorithms and Data Structures

A least frequently used cache is a cache that evicts the entry with the lowest access frequency, using a tie-breaking rule when frequencies are equal.

A least frequently used cache evicts the entry with the lowest access count. It suits workloads where recently popular items should survive temporary request spikes better than purely recency-based eviction. section 7.5

Develop an LFU cache by tracking each entry’s frequency and priority:

• Initialize a new entry with counter 1 and record its insertion time for tie-breaking. section 7.5.2
• On a cache hit or update, increment the counter and update the entry’s priority. section 7.5.2
• Use a hash table for constant-time key lookup, while a priority queue identifies the next entry to evict. section 7.5.2
• Prefer newer entries when frequencies tie; with a heap, insertion and updates require logarithmic time, while lookup remains constant-time. section 7.5 section 7.7.3

Why recency alone can fail

A temporary request peak can fill a cache with newly popular items and displace established best sellers under LRU. LFU is more likely to retain the frequently accessed items, though its slower turnover can preserve an obsolete item for a long time. section 7.5 section 7.5.4

Figure 7.9 An example of a possible situation where LRU eviction policy would purge most “best-selling” items from a cache, in favor of the more recently viewed ones which become popular during a peak of requests. In the figure, items are ordered according to their most recent view; the number of views is shown only to display how most recent views during a peak can wipe out normal best-selling products. While LRU policy never guarantees that best-selling items will stay in the cache, the higher frequency with which they are accessed makes it more likely that they will stay in the cache (because it is likely they will go to the head of the queue before being purged). During a peak, if the number of items that suddenly become popular is large enough, they could fill the cache and force the usual items to be purged. This would be a temporary side effect that will regress after the peak. In some situations, this could also be desirable, because items popular during a peak should be accessed faster than the regular best-selling ones. LRU has a more dynamic turnaround than LFU, as we will see.

Compare a temporary popularity spike with longer-term access frequency and see why LRU and LFU retain different entries. section 7.5

How Advanced Algorithms and Data Structures covers it

How deep it goes

Develops LFU from an LRU design through pseudocode, priority queues, tie-breaking, complexity, and long-lived-cache trade-offs.

Examples

Uses request peaks, best-selling items, stale products, counters, timestamps, heaps, and LFU cache pseudocode.

What it assumes

Builds from an LRU cache and assumes familiarity with priority queues, heaps, hash tables, and dynamically ordered entries.

What you can do after

Build it from scratch with a hash table and priority queue, then evaluate complexity, tie-breaking, staleness, and alternative frequency metrics.

How it connects

Connects LFU with LRU cache, hash tables, priority queues, heaps, FIFO queues, and concurrent data structures.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

• LRUcontrasts with · LRU is a cache replacement policy that evicts the item whose most recent access occurred furthest in the past.
• heapuses · A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.
• cachingconfigures · Caching is the practice of storing reusable data or computation results so later access can avoid repeating retrieval or computation.
• priority queueuses · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
• Mapuses · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.