LFUDA

LFUDA, or Least Frequently Used with Dynamic Aging, is a cache replacement policy designed to improve upon classic LFU by incorporating an adaptive aging mechanism. The goal is to keep genuinely popular items in the cache while allowing old or rarely used items to fade away as workloads change.

In LFUDA, each cached item maintains a frequency counter that reflects how often it has been accessed, along with an aging component that increases with time. When an item is accessed, its frequency counter is incremented. Periodically, the aging process reduces the influence of past accesses across all cached items, so that older popularity does not lock in indefinitely. The aging mechanism is dynamic, meaning the rate or method of aging can adapt to the workload or cache state.

Eviction in LFUDA is driven by the item's current popularity adjusted by aging. When the cache is full and a new item must be inserted, the policy evicts the item with the lowest effective frequency (the lowest combination of frequency and age) to make room. This approach aims to approximate LFU behavior while remaining responsive to shifts in access patterns.

LFUDA addresses a common problem with LFU: cache pollution by stale data. By decaying frequency counts over time, the policy allows recently popular items to regain prominence and helps the cache adapt to evolving workloads.

LFUDA has been discussed in caching research and has been implemented or experimented with in various caching frameworks and systems. It is one of several alternatives to LRU and standard LFU, offering a balance between historical popularity and recent relevance.