LFU

LFU, or Least Frequently Used, is a cache eviction policy that removes the item that has been accessed the fewest times. It uses frequency counts to guide which entry to drop when space is needed, aiming to keep items that are accessed more often in the cache.

In a typical LFU implementation, each cached item stores a counter representing its access frequency. On every access, the counter for that item is incremented. New items usually receive an initial frequency (often 1). When the cache is full, LFU evicts the item with the smallest frequency. If multiple items share the same minimum frequency, a tie-breaker is applied, commonly based on recency or insertion time to avoid removing older items unnecessarily.

Efficient LFU implementations often use a two-level data structure: a map from keys to their values and metadata, and a structure that groups items by frequency (for example, a set of doubly linked lists, one per frequency). A separate tracker keeps the current minimum frequency. Accessing or inserting an item requires moving it between frequency groups and updating the minimum frequency as needed. This design allows constant or near-constant time operations for get and put, with eviction performed by removing an item from the minimum-frequency group.

Variants and related concepts include LFUDA (LFU with aging), which decays frequencies over time to prevent stale items from dominating, and approximate LFU methods that use sampling or probabilistic counters to reduce memory usage. LFU is often contrasted with LRU (Least Recently Used) and other caching policies, each with trade-offs depending on workload characteristics.

Applications include web caches, database buffers, and memory management systems where access frequency is a meaningful predictor of future use.