lfudacache

Python implementation Less Frequently Used with Dynamic Aging (LFUDA).

Rationale

Although I found a lot of LFU implementations for Python, I were unable to get any LFUDA one.

In the other hand, LRU and LFU object-based implementations are quite inefficient for such performance-critical use cases, due to python attribute lookup overhead (thats why python's standard lru_cache implementation is purely functional).

Our implementation follows a hybrid approach: the methods and state are fully object-less functional,

Why Less Frequently Used with Dynamic Aging (LFUDA)

LFUDA evicts less used items when they become too old, rejecting new cache items until then.

In our implementation, an item become too old when its cache hit count lags behind the entire cache misses.

This approach prevents eviction of very used items in favor of potentially less used items.

Why not Less Recently Used (LRU)

LRU is a very simple approach to caching, evicting older unused items.

This approach is optimal when the most relevant items are accessed frequently, but this is not always the case.

The drawback is that very used items will be evicted when a lot of new items are added to cache, even if they will never be accesed again.

This problem is usually minimized increasing the cache size until potentially irrelevant cache items become only a tiny fraction of the entire cache, but this is not a possibility on all cases (ie. caching huge datasets).

Why not Less Frequenty Used (LFU)

LFU is our base algorithm, which evicts less used items.

This approach has one major drawback when cache is full: a new saved item could cause the eviction of an item more frequently used than the new one. This is called cache pollution.

To minimize this problem, it's common to implement two different item storages, with different eviction policies. Please note while this method reduces said cache pollution issue, it does not fix it.