LRU cache design

Question

Last Use Cache (LRU) should first drop the least used items. How do you design and implement such a cache class? The design requirements are as follows:

1) find the item as fast as we can

2) When the cache misses and the cache is full, we need to replace the least recently used element as quickly as possible.

How to analyze and implement this issue in terms of design and algorithm design?

Answer 1

A linked list + a hash table of pointers to nodes in a linked list is a common way to implement LRU caches. This gives O (1) operations (assuming a decent hash). The advantage of this (being O (1)): you can make a multi-threaded version by simply locking the entire structure. You do not need to worry about granular blocking, etc.

In short, how it works:

When accessing the value, you move the corresponding node in the linked list to the head.

When you need to remove a value from the cache, you delete it from the end.

When you add a value to the cache, you simply put it at the top of the linked list.

Thanks to doublep, here is a site with C ++ implementation: Various container templates .

Answer 2

This is my simple sample C ++ implementation for the LRU cache with a combination of a hash (unordered_map) and a list. Elements in the list have a key for accessing the map, and elements on the map have a list iterator for accessing the list.

#include <list> #include <unordered_map> #include <assert.h> using namespace std; template <class KEY_T, class VAL_T> class LRUCache{ private: list< pair<KEY_T,VAL_T> > item_list; unordered_map<KEY_T, decltype(item_list.begin()) > item_map; size_t cache_size; private: void clean(void){ while(item_map.size()>cache_size){ auto last_it = item_list.end(); last_it --; item_map.erase(last_it->first); item_list.pop_back(); } }; public: LRUCache(int cache_size_):cache_size(cache_size_){ ; }; void put(const KEY_T &key, const VAL_T &val){ auto it = item_map.find(key); if(it != item_map.end()){ item_list.erase(it->second); item_map.erase(it); } item_list.push_front(make_pair(key,val)); item_map.insert(make_pair(key, item_list.begin())); clean(); }; bool exist(const KEY_T &key){ return (item_map.count(key)>0); }; VAL_T get(const KEY_T &key){ assert(exist(key)); auto it = item_map.find(key); item_list.splice(item_list.begin(), item_list, it->second); return it->second->second; }; }; 

Answer 3

Here is my implementation for a simple simple LRU cache.

 //LRU Cache #include <cassert> #include <list> template <typename K, typename V > class LRUCache { // Key access history, most recent at back typedef std::list<K> List; // Key to value and key history iterator typedef unordered_map< K, std::pair< V, typename std::list<K>::iterator > > Cache; typedef V (*Fn)(const K&); public: LRUCache( size_t aCapacity, Fn aFn ) : mFn( aFn ) , mCapacity( aCapacity ) {} //get value for key aKey V operator()( const K& aKey ) { typename Cache::iterator it = mCache.find( aKey ); if( it == mCache.end() ) //cache-miss: did not find the key { V v = mFn( aKey ); insert( aKey, v ); return v; } // cache-hit // Update access record by moving accessed key to back of the list mList.splice( mList.end(), mList, (it)->second.second ); // return the retrieved value return (it)->second.first; } private: // insert a new key-value pair in the cache void insert( const K& aKey, V aValue ) { //method should be called only when cache-miss happens assert( mCache.find( aKey ) == mCache.end() ); // make space if necessary if( mList.size() == mCapacity ) { evict(); } // record k as most-recently-used key typename std::list<K>::iterator it = mList.insert( mList.end(), aKey ); // create key-value entry, linked to the usage record mCache.insert( std::make_pair( aKey, std::make_pair( aValue, it ) ) ); } //Purge the least-recently used element in the cache void evict() { assert( !mList.empty() ); // identify least-recently-used key const typename Cache::iterator it = mCache.find( mList.front() ); //erase both elements to completely purge record mCache.erase( it ); mList.pop_front(); } private: List mList; Cache mCache; Fn mFn; size_t mCapacity; }; 

Answer 4

using a hash table and a doubly linked list to develop an LRU cache

A double linked list can handle this. A map is a good way to track the position of a node according to its key.

 class LRUCache{ //define the double linked list, each node stores both the key and value. struct Node{ Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; }; map<int,Node*>mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer public: //constructor LRUCache(int capacity) { cp = capacity; mp.clear(); head=NULL; tail=NULL; } //insert node to the tail of the linked list void insertNode(Node* node){ if (!head){ head = node; tail = node; }else{ tail->next = node; node->prev = tail; tail = tail->next; } } //remove current node void rmNode(Node* node){ if (node==head){ head = head->next; if (head){head->prev = NULL;} }else{ if (node==tail){ tail =tail->prev; tail->next = NULL; }else{ node->next->prev = node->prev; node->prev->next = node->next; } } } // move current node to the tail of the linked list void moveNode(Node* node){ if (tail==node){ return; }else{ if (node==head){ node->next->prev = NULL; head = node->next; tail->next = node; node->prev = tail; tail=tail->next; }else{ node->prev->next = node->next; node->next->prev = node->prev; tail->next = node; node->prev = tail; tail=tail->next; } } } /////////////////////////////////////////////////////////////////////// // get method /////////////////////////////////////////////////////////////////////// int get(int key) { if (mp.find(key)==mp.end()){ return -1; }else{ Node *tmp = mp[key]; moveNode(tmp); return mp[key]->value; } } /////////////////////////////////////////////////////////////////////// // set method /////////////////////////////////////////////////////////////////////// void set(int key, int value) { if (mp.find(key)!=mp.end()){ moveNode(mp[key]); mp[key]->value = value; }else{ if (mp.size()==cp){ mp.erase(head->key); rmNode(head); } Node * node = new Node(key,value); mp[key] = node; insertNode(node); } } }; 

Answer 5

I see some unnecessary complex implementations here, so I decided to provide my implementation as well. The cache has only two methods, get and set. Hope this reads better and is understandable:

 #include<unordered_map> #include<list> using namespace std; template<typename K, typename V = K> class LRUCache { private: list<K>items; unordered_map <K, pair<V, typename list<K>::iterator>> keyValuesMap; int csize; public: LRUCache(int s) :csize(s) { if (csize < 1) csize = 10; } void set(const K key, const V value) { auto pos = keyValuesMap.find(key); if (pos == keyValuesMap.end()) { items.push_front(key); keyValuesMap[key] = { value, items.begin() }; if (keyValuesMap.size() > csize) { keyValuesMap.erase(items.back()); items.pop_back(); } } else { items.erase(pos->second.second); items.push_front(key); keyValuesMap[key] = { value, items.begin() }; } } bool get(const K key, V &value) { auto pos = keyValuesMap.find(key); if (pos == keyValuesMap.end()) return false; items.erase(pos->second.second); items.push_front(key); keyValuesMap[key] = { pos->second.first, items.begin() }; value = pos->second.first; return true; } }; 

Answer 6

I have an LRU implementation here . The interface follows std :: map, so it shouldn't be that hard to use. In addition, you can provide your own backup handler, which is used if the data is invalid in the cache.

 sweet::Cache<std::string,std::vector<int>, 48> c1; c1.insert("key1", std::vector<int>()); c1.insert("key2", std::vector<int>()); assert(c1.contains("key1")); 

Answer 7

I implemented multithreaded LRU cache two years ago.

LRU is usually implemented using HashMap and LinkedList. You can google implementation details. There are a lot of resources about this (Wikipedia also has a good explanation).

In order to be thread safe, you need to set a lock whenever you change the state of the LRU.

I will embed my C ++ code here for your reference.

Here is the implementation.

 /*** A template thread-safe LRU container. Typically LRU cache is implemented using a doubly linked list and a hash map. Doubly Linked List is used to store list of pages with most recently used page at the start of the list. So, as more pages are added to the list, least recently used pages are moved to the end of the list with page at tail being the least recently used page in the list. Additionally, this LRU provides time-to-live feature. Each entry has an expiration datetime. ***/ #ifndef LRU_CACHE_H #define LRU_CACHE_H #include <iostream> #include <list> #include <boost/unordered_map.hpp> #include <boost/shared_ptr.hpp> #include <boost/make_shared.hpp> #include <boost/date_time/posix_time/posix_time.hpp> #include <boost/thread/mutex.hpp> template <typename KeyType, typename ValueType> class LRUCache { private: typedef boost::posix_time::ptime DateTime; // Cache-entry struct ListItem { ListItem(const KeyType &key, const ValueType &value, const DateTime &expiration_datetime) : m_key(key), m_value(value), m_expiration_datetime(expiration_datetime){} KeyType m_key; ValueType m_value; DateTime m_expiration_datetime; }; typedef boost::shared_ptr<ListItem> ListItemPtr; typedef std::list<ListItemPtr> LruList; typedef typename std::list<ListItemPtr>::iterator LruListPos; typedef boost::unordered_map<KeyType, LruListPos> LruMapper; // A mutext to ensuare thread-safety. boost::mutex m_cache_mutex; // Maximum number of entries. std::size_t m_capacity; // Stores cache-entries from latest to oldest. LruList m_list; // Mapper for key to list-position. LruMapper m_mapper; // Default time-to-live being add to entry every time we touch it. unsigned long m_ttl_in_seconds; /*** Note : This is a helper function whose function call need to be wrapped within a lock. It returns true/false whether key exists and not expires. Delete the expired entry if necessary. ***/ bool containsKeyHelper(const KeyType &key) { bool has_key(m_mapper.count(key) != 0); if (has_key) { LruListPos pos = m_mapper[key]; ListItemPtr & cur_item_ptr = *pos; // Remove the entry if key expires if (isDateTimeExpired(cur_item_ptr->m_expiration_datetime)) { has_key = false; m_list.erase(pos); m_mapper.erase(key); } } return has_key; } /*** Locate an item in list by key, and move it at the front of the list, which means make it the latest item. Note : This is a helper function whose function call need to be wrapped within a lock. ***/ void makeEntryTheLatest(const KeyType &key) { if (m_mapper.count(key)) { // Add original item at the front of the list, // and update <Key, ListPosition> mapper. LruListPos original_list_position = m_mapper[key]; const ListItemPtr & cur_item_ptr = *original_list_position; m_list.push_front(cur_item_ptr); m_mapper[key] = m_list.begin(); // Don't forget to update its expiration datetime. m_list.front()->m_expiration_datetime = getExpirationDatetime(m_list.front()->m_expiration_datetime); // Erase the item at original position. m_list.erase(original_list_position); } } public: /*** Cache should have capacity to limit its memory usage. We also add time-to-live for each cache entry to expire the stale information. By default, ttl is one hour. ***/ LRUCache(std::size_t capacity, unsigned long ttl_in_seconds = 3600) : m_capacity(capacity), m_ttl_in_seconds(ttl_in_seconds) {} /*** Return now + time-to-live ***/ DateTime getExpirationDatetime(const DateTime &now) { static const boost::posix_time::seconds ttl(m_ttl_in_seconds); return now + ttl; } /*** If input datetime is older than current datetime, then it is expired. ***/ bool isDateTimeExpired(const DateTime &date_time) { return date_time < boost::posix_time::second_clock::local_time(); } /*** Return the number of entries in this cache. ***/ std::size_t size() { boost::mutex::scoped_lock lock(m_cache_mutex); return m_mapper.size(); } /*** Get value by key. Return true/false whether key exists. If key exists, input paramter value will get updated. ***/ bool get(const KeyType &key, ValueType &value) { boost::mutex::scoped_lock lock(m_cache_mutex); if (!containsKeyHelper(key)) { return false; } else { // Make the entry the latest and update its TTL. makeEntryTheLatest(key); // Then get its value. value = m_list.front()->m_value; return true; } } /*** Add <key, value> pair if no such key exists. Otherwise, just update the value of old key. ***/ void put(const KeyType &key, const ValueType &value) { boost::mutex::scoped_lock lock(m_cache_mutex); if (containsKeyHelper(key)) { // Make the entry the latest and update its TTL. makeEntryTheLatest(key); // Now we only need to update its value. m_list.front()->m_value = value; } else { // Key exists and is not expired. if (m_list.size() == m_capacity) { KeyType delete_key = m_list.back()->m_key; m_list.pop_back(); m_mapper.erase(delete_key); } DateTime now = boost::posix_time::second_clock::local_time(); m_list.push_front(boost::make_shared<ListItem>(key, value, getExpirationDatetime(now))); m_mapper[key] = m_list.begin(); } } }; #endif 

This is unit tests.

 #include "cxx_unit.h" #include "lru_cache.h" struct LruCacheTest : public FDS::CxxUnit::TestFixture<LruCacheTest>{ CXXUNIT_TEST_SUITE(); CXXUNIT_TEST(LruCacheTest, testContainsKey); CXXUNIT_TEST(LruCacheTest, testGet); CXXUNIT_TEST(LruCacheTest, testPut); CXXUNIT_TEST_SUITE_END(); void testContainsKey(); void testGet(); void testPut(); }; void LruCacheTest::testContainsKey() { LRUCache<int,std::string> cache(3); cache.put(1,"1"); // 1 cache.put(2,"2"); // 2,1 cache.put(3,"3"); // 3,2,1 cache.put(4,"4"); // 4,3,2 std::string value_holder(""); CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2 CXXUNIT_ASSERT(value_holder == ""); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3 CXXUNIT_ASSERT(value_holder == "2"); cache.put(5,"5"); // 5, 2, 4 CXXUNIT_ASSERT(cache.get(3, value_holder) == false); // 5, 2, 4 CXXUNIT_ASSERT(value_holder == "2"); // value_holder is still "2" CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2 CXXUNIT_ASSERT(value_holder == "4"); cache.put(2,"II"); // {2, "II"}, 4, 5 CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2, 4, 5 CXXUNIT_ASSERT(value_holder == "II"); // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"} CXXUNIT_ASSERT(cache.size() == 3); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); CXXUNIT_ASSERT(cache.get(4, value_holder) == true); CXXUNIT_ASSERT(cache.get(5, value_holder) == true); } void LruCacheTest::testGet() { LRUCache<int,std::string> cache(3); cache.put(1,"1"); // 1 cache.put(2,"2"); // 2,1 cache.put(3,"3"); // 3,2,1 cache.put(4,"4"); // 4,3,2 std::string value_holder(""); CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2 CXXUNIT_ASSERT(value_holder == ""); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3 CXXUNIT_ASSERT(value_holder == "2"); cache.put(5,"5"); // 5,2,4 CXXUNIT_ASSERT(cache.get(5, value_holder) == true); // 5,2,4 CXXUNIT_ASSERT(value_holder == "5"); CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2 CXXUNIT_ASSERT(value_holder == "4"); cache.put(2,"II"); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // {2 : "II"}, 4, 5 CXXUNIT_ASSERT(value_holder == "II"); // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"} CXXUNIT_ASSERT(cache.size() == 3); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); CXXUNIT_ASSERT(cache.get(4, value_holder) == true); CXXUNIT_ASSERT(cache.get(5, value_holder) == true); } void LruCacheTest::testPut() { LRUCache<int,std::string> cache(3); cache.put(1,"1"); // 1 cache.put(2,"2"); // 2,1 cache.put(3,"3"); // 3,2,1 cache.put(4,"4"); // 4,3,2 cache.put(5,"5"); // 5,4,3 std::string value_holder(""); CXXUNIT_ASSERT(cache.get(2, value_holder) == false); // 5,4,3 CXXUNIT_ASSERT(value_holder == ""); CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4,5,3 CXXUNIT_ASSERT(value_holder == "4"); cache.put(2,"II"); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // II,4,5 CXXUNIT_ASSERT(value_holder == "II"); // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"} CXXUNIT_ASSERT(cache.size() == 3); CXXUNIT_ASSERT(cache.get(2, value_holder) == true); CXXUNIT_ASSERT(cache.get(4, value_holder) == true); CXXUNIT_ASSERT(cache.get(5, value_holder) == true); } CXXUNIT_REGISTER_TEST(LruCacheTest); 

Answer 8

Is a cache a data structure that supports the value of a key search, such as a hash table? LRU means that the cache has a certain size limit, which we need to periodically discard the least used entries.

If you implement a linked list + a hash table of pointers, how can you perform O (1) key-value retrieval?

I would use a LRU cache with a hash table so that the value of each record is the value + pointer to the previous / next record.

As for multi-threaded access, I would prefer read-write lock (ideally, spin lock is implemented, since approval is usually fast) for monitoring.

Answer 9

LRU page replacement technique:

When linking to a page, the required page may be in the cache.

If in the cache : we need to transfer it to the cache queue.

If NOT in the cache : we cache this. In simple terms, we add a new page to the cache queue. If the cache is full, that is, all frames are full, we delete the page from the back of the cache queue and add a new page to the cache queue.

 # Cache Size csize = int(input()) # Sequence of pages pages = list(map(int,input().split())) # Take a cache list cache=[] # Keep track of number of elements in cache n=0 # Count Page Fault fault=0 for page in pages: # If page exists in cache if page in cache: # Move the page to front as it is most recent page # First remove from cache and then append at front cache.remove(page) cache.append(page) else: # Cache is full if(n==csize): # Remove the least recent page cache.pop(0) else: # Increment element count in cache n=n+1 # Page not exist in cache => Page Fault fault += 1 cache.append(page) print("Page Fault:",fault) 

Input Output

 Input: 3 1 2 3 4 1 2 5 1 2 3 4 5 Output: Page Fault: 10 

Answer 10

This is my simple Java programmer with O (1) complexity.

//

 package com.chase.digital.mystack; import java.util.HashMap; import java.util.Map; public class LRUCache { private int size; private Map<String, Map<String, Integer>> cache = new HashMap<>(); public LRUCache(int size) { this.size = size; } public void addToCache(String key, String value) { if (cache.size() < size) { Map<String, Integer> valueMap = new HashMap<>(); valueMap.put(value, 0); cache.put(key, valueMap); } else { findLRUAndAdd(key, value); } } public String getFromCache(String key) { String returnValue = null; if (cache.get(key) == null) { return null; } else { Map<String, Integer> value = cache.get(key); for (String s : value.keySet()) { value.put(s, value.get(s) + 1); returnValue = s; } } return returnValue; } private void findLRUAndAdd(String key, String value) { String leastRecentUsedKey = null; int lastUsedValue = 500000; for (String s : cache.keySet()) { final Map<String, Integer> stringIntegerMap = cache.get(s); for (String s1 : stringIntegerMap.keySet()) { final Integer integer = stringIntegerMap.get(s1); if (integer < lastUsedValue) { lastUsedValue = integer; leastRecentUsedKey = s; } } } cache.remove(leastRecentUsedKey); Map<String, Integer> valueMap = new HashMap<>(); valueMap.put(value, 0); cache.put(key, valueMap); } }