Design della cache LRU

La cache LRU (Least Recently Used) (LRU) utilizzata per prima cosa elimina gli elementi meno utilizzati di recente. Come si progetta e si implementa tale class cache? I requisiti di progettazione sono i seguenti:

1) trova l’object il più velocemente ansible

2) Una volta che una cache manca e una cache è piena, dobbiamo sostituire l’elemento utilizzato meno di recente il più velocemente ansible.

Come analizzare e implementare questa domanda in termini di modello di progettazione e progettazione dell’algoritmo?

Una lista collegata + una lista di puntatori ai nodes della lista collegata è il solito modo di implementare le cache LRU. Questo dà O (1) operazioni (assumendo un discreto hash). Vantaggio di questo (essendo O (1)): puoi eseguire una versione multithread semplicemente bloccando l’intera struttura. Non devi preoccuparti del blocco granulare ecc.

In breve, il modo in cui funziona:

Su un accesso di un valore, si sposta il nodo corrispondente nella lista collegata alla testa.

Quando devi rimuovere un valore dalla cache, lo rimuovi dalla coda.

Quando aggiungi un valore alla cache, lo metti appena all’inizio dell’elenco collegato.

Grazie a doublep, ecco il sito con un’implementazione C ++: vari modelli di container .

Questa è la mia semplice implementazione di esempio in c ++ per cache LRU, con la combinazione di hash (unordered_map) ed elenco. Gli elementi in elenco hanno la chiave per accedere alla mappa e gli elementi sulla mappa hanno un iteratore di elenco per accedere all’elenco.

#include  #include  #include  using namespace std; template  class LRUCache{ private: list< pair > item_list; unordered_map 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; }; }; 

Ecco la mia implementazione per una cache LRU semplice e di base.

 //LRU Cache #include  #include  template  class LRUCache { // Key access history, most recent at back typedef std::list List; // Key to value and key history iterator typedef unordered_map< K, std::pair< V, typename std::list::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::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; }; 

Ho una implementazione LRU qui . L’interfaccia segue std :: map quindi non dovrebbe essere così difficile da usare. Inoltre, è ansible fornire un gestore di backup personalizzato, che viene utilizzato se i dati vengono invalidati nella cache.

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

Ho implementato una cache LRU thread-safe due anni fa.

LRU viene in genere implementato con HashMap e LinkedList. Puoi google i dettagli di implementazione. Ci sono molte risorse a riguardo (anche Wikipedia ha una buona spiegazione).

Per essere thread-safe, è necessario inserire il blocco ogni volta che si modifica lo stato dell’LRU.

Incollerò qui il mio codice C ++ come riferimento.

Ecco l’implementazione.

 /*** 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  #include  #include  #include  #include  #include  #include  template  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 ListItemPtr; typedef std::list LruList; typedef typename std::list::iterator LruListPos; typedef boost::unordered_map 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  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  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(key, value, getExpirationDatetime(now))); m_mapper[key] = m_list.begin(); } } }; #endif 

Ecco i test unitari.

 #include "cxx_unit.h" #include "lru_cache.h" struct LruCacheTest : public FDS::CxxUnit::TestFixture{ 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 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 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 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); 

La cache è una struttura dati che supporta il valore di recupero per chiave come la tabella hash? LRU indica che la cache ha determinate limitazioni di dimensione che è necessario eliminare periodicamente le voci meno utilizzate.

Se si implementa con la lista collegata + hashtable di puntatori, come si può eseguire O (1) recupero del valore per chiave?

Vorrei implementare cache LRU con una tabella hash che il valore di ogni voce è valore + puntatori per prev / prossima voce.

Per quanto riguarda l’accesso multi-threading, preferirei il lock reader-writer (idealmente implementato da spin lock poiché la contesa è solitamente veloce) da monitorare.

Tecnica di sostituzione delle pagine LRU:

Quando si fa riferimento a una pagina, la pagina richiesta potrebbe essere nella cache.

If in the cache : dobbiamo portarlo nella parte anteriore della coda della cache.

If NOT in the cache : lo portiamo nella cache. In parole semplici, aggiungiamo una nuova pagina nella parte anteriore della coda della cache. Se la cache è piena, ovvero tutti i frame sono pieni, rimuoviamo una pagina dal retro della coda della cache e aggiungiamo la nuova pagina nella parte anteriore della coda della cache.

 # 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