Module lfuda

Least Frequently Used with Dynamic Aging (LFUDA) cache implementation.

An enhanced LFU cache that addresses the aging problem by dynamically adjusting item priorities based on a global aging factor. Least Frequently Used with Dynamic Aging (LFUDA) Cache Implementation.

The LFUDA cache is an enhancement of the basic LFU algorithm that addresses the “aging problem” where old frequently-used items can prevent new items from being cached even if they’re no longer actively accessed.

Algorithm

LFUDA works by maintaining a global age value that increases when items are evicted. Each item’s priority is calculated using the formula:

priority = access_frequency + age_at_insertion

When an item is accessed, its frequency is incremented. When an item is evicted, the global age value is set to the priority of the evicted item. New items are inserted with the current age value as their initial age, giving them a boost to compete with older items.

Mathematical Formulation

For each cache entry i:

• Let F_i be the access frequency of item i
• Let A_i be the age factor when item i was inserted
• Let P_i = F_i + A_i be the priority value
• On eviction, select item j where P_j = min{P_i for all i}
• After eviction, set global_age = P_j

Performance Characteristics

• Time Complexity:

  • Get: O(1)
  • Put: O(1)
  • Remove: O(1)

• Space Complexity:

  • O(n) where n is the capacity of the cache
  • Slightly more overhead than LRU due to frequency and age tracking

When to Use

LFUDA caches are ideal for:

• Long-running caches where popularity of items changes over time
• Workloads where frequency of access is more important than recency
• Environments where protecting against cache pollution from one-time scans is important

Thread Safety

This implementation is not thread-safe. For concurrent access, wrap the cache with a synchronization primitive such as Mutex or RwLock.

Structs

LfudaCache

An implementation of a Least Frequently Used with Dynamic Aging (LFUDA) cache.