LFU Cache
Least Frequently Used (LFU) cache algorithms work by ejecting the least frequently accessed items by keeping track of how frequently the item is accessed or used.
Uses of LFU
-
Database cache
LFU caching can be used to keep track of the frequently queried database results.
Redis supports LFU caching in its eviction policy. Redis can be configured to use LFU eviction in addition to other eviction strategies like LRU (Least Recently Used).
Oracle Database offers LFU caching support through its SQL query cache.
Apache Cassandra has a cache configuration system where LFU can be employed for certain cache types. -
Web cache
A variety of web caching solutions like Varnish Cache, Squid Proxy Cache and Apache Traffic Server use LFU (Least Frequently Used) cache algorithms.
Program to implement LFU (Least Frequently Used) Cache
#include<iostream>
#include<map>
#include<list>
#include<vector>
using namespace std;
class LFUCache {
int size; // Size of LFU cache
int count; // keys track of the elements that are pushed.
map <int, pair<int, int>> cache; // LFU cache table stores < key, < value, frequency > >
// Table stores list of keys based on their frequency. The first element of the list is the LRU key.
map <int, list<int>> freq_table;
public:
LFUCache (int arg_size) : size (arg_size), count(0) { }
// Update the frequency of the key
void Update_FrequencyTable (int freq, int key) {
// Update would involve deleting the previous pair <frequency, <key>> from the list.
if (freq > 1) { // Element should be already be present at previous frequency. So remove it.
freq_table[freq-1].remove(key);
}
freq_table[freq].push_back(key);
cout << "Frequency Table" << endl;
cout << "===============" << endl;
for (int freq=1; freq<=count; freq++) {
cout << "Freq [" << freq << "] : ";
list<int> :: iterator it;
for (it = freq_table[freq].begin(); it != freq_table[freq].end(); ++it)
cout << *it << " ";
cout << endl;
}
}
int Get (int key) {
cout << "\nOperation GET : " << key << endl;
if (cache.find(key) != cache.end()) {
cache[key].second += 1;
int freq = cache[key].second;
Update_FrequencyTable (freq, key);
cout << "Return ----> ";
return cache[key].first;
}
return -1;
}
void Put (int key, int value) {
if (size == 0)
return;
cout << "\nOperation PUT : [" << key << ":" << value << "]" << endl;
if (cache.find(key) != cache.end()) { // Key is found in the cache
cache[key].first = value;
cache[key].second += 1;
int freq = cache[key].second;
Update_FrequencyTable (freq, key);
} else { // Key not found in the cache
count++;
if (cache.size() == size) { // Cache is already full
cout << "Cache is full !!" << endl;
for (int freq=1; freq<=count; freq++) {
if (freq_table.find(freq) != freq_table.end() and freq_table[freq].size() > 0) {
int key = freq_table[freq].front();
cout << "Erasing key : " << key << endl;
cache.erase(key);
freq_table[freq].pop_front();
break;
}
}
}
cache[key].first = value;
cache[key].second = 1;
Update_FrequencyTable (1, key);
}
}
};
int main() {
LFUCache cache(2);
cache.Put(1,1);
cache.Put(2,2);
cout << cache.Get(1) << endl;
cache.Put(3,3);
cout << cache.Get(2) << endl;
cout << cache.Get(3) << endl;
cache.Put(4,4);
cout << cache.Get(1) << endl;
cout << cache.Get(3) << endl;
cout << cache.Get(4) << endl;
return 0;
}
Output
Operation PUT : [1:1]
Frequency Table
===============
Freq [1] : 1
Operation PUT : [2:2]
Frequency Table
===============
Freq [1] : 1 2
Freq [2] :
Operation GET : 1
Frequency Table
===============
Freq [1] : 2
Freq [2] : 1
Return ----> 1
Operation PUT : [3:3]
Cache is full !!
Erasing key : 2
Frequency Table
===============
Freq [1] : 3
Freq [2] : 1
Freq [3] :
Operation GET : 2
-1
Operation GET : 3
Frequency Table
===============
Freq [1] :
Freq [2] : 1 3
Freq [3] :
Return ----> 3
Operation PUT : [4:4]
Cache is full !!
Erasing key : 1
Frequency Table
===============
Freq [1] : 4
Freq [2] : 3
Freq [3] :
Freq [4] :
Operation GET : 1
-1
Operation GET : 3
Frequency Table
===============
Freq [1] : 4
Freq [2] :
Freq [3] : 3
Freq [4] :
Return ----> 3
Operation GET : 4
Frequency Table
===============
Freq [1] :
Freq [2] : 4
Freq [3] : 3
Freq [4] :
Return ----> 4