LRU 캐시 설계

LRU 캐시 설계

---

LRU (Least Recent Used) 캐시는 가장 최근에 사용한 항목을 먼저 버리는 것입니다. 이러한 캐시 클래스를 어떻게 설계하고 구현합니까? 설계 요구 사항은 다음과 같습니다.

1) 가능한 한 빨리 항목을 찾으십시오.

2) 캐시가 누락되고 캐시가 가득 차면 가장 최근에 사용한 항목을 최대한 빨리 교체해야합니다.

디자인 패턴 및 알고리즘 디자인 측면에서이 질문을 분석하고 구현하는 방법은 무엇입니까?

---

연결 목록 + 연결 목록 노드에 대한 포인터의 해시 테이블은 LRU 캐시를 구현하는 일반적인 방법입니다. 이것은 O (1) 연산을 제공합니다 (괜찮은 해시라고 가정). 이것의 장점 (O (1)) : 전체 구조를 잠그는 것만으로 다중 스레드 버전을 수행 할 수 있습니다. 세분화 된 잠금 등에 대해 걱정할 필요가 없습니다.

간단히 말해서 작동 방식 :

값에 액세스하면 링크 된 목록의 해당 노드를 헤드로 이동합니다.

캐시에서 값을 제거해야하는 경우 꼬리 끝에서 제거합니다.

캐시에 값을 추가 할 때 연결 목록의 맨 앞에 놓기 만하면됩니다.

doublep 덕분에 여기에 C ++ 구현이있는 사이트가 있습니다. Miscellaneous Container Templates .

---

이것은 Hash (unordered_map) 및 목록의 조합을 사용하여 LRU 캐시에 대한 간단한 샘플 C ++ 구현입니다. 목록에있는 항목은 맵에 액세스 할 수있는 키가 있고 맵의 항목에는 목록에 액세스 할 수있는 목록의 반복자가 있습니다.

#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;
        };

};

---

다음은 기본적이고 간단한 LRU 캐시에 대한 구현입니다.

//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;
    };

---

여기에 불필요한 복잡한 구현이 몇 가지 있으므로 구현도 제공하기로 결정했습니다. 캐시에는 get 및 set의 두 가지 메서드 만 있습니다. 더 잘 읽고 이해할 수 있기를 바랍니다.

#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;
    }
};

---

여기에 LRU 구현이 있습니다 . 인터페이스는 std :: map을 따르므로 사용하기 어렵지 않습니다. 또한 캐시에서 데이터가 무효화되는 경우 사용되는 사용자 지정 백업 처리기를 제공 할 수 있습니다.

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"));

---

2 년 전에 스레드로부터 안전한 LRU 캐시를 구현했습니다.

LRU는 일반적으로 HashMap 및 LinkedList로 구현됩니다. 구현 세부 사항을 Google로 볼 수 있습니다. 그것에 대한 많은 리소스가 있습니다 (Wikipedia에도 좋은 설명이 있습니다).

스레드로부터 안전하려면 LRU의 상태를 수정할 때마다 넣기 잠금이 필요합니다.

참조 용으로 여기에 C ++ 코드를 붙여 넣겠습니다.

다음은 구현입니다.

/***
    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

다음은 단위 테스트입니다.

#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);

---

캐시는 해시 테이블과 같은 키로 값 검색을 지원하는 데이터 구조입니까? LRU는 캐시에 가장 적게 사용되는 항목을 주기적으로 삭제해야하는 특정 크기 제한이 있음을 의미합니다.

연결 목록 + 포인터 해시 테이블로 구현하면 키로 값을 O (1) 검색하는 방법은 무엇입니까?

각 항목의 값이 값 + 이전 / 다음 항목에 대한 포인터라는 해시 테이블을 사용하여 LRU 캐시를 구현합니다.

멀티 스레딩 액세스와 관련하여, 저는 독자-작성기 잠금 (경쟁이 일반적으로 빠르기 때문에 스핀 잠금에 의해 이상적으로 구현 됨)을 모니터링하는 것을 선호합니다.

---

LRU 페이지 교체 기술 :

페이지가 참조되면 필요한 페이지가 캐시에있을 수 있습니다.

If in the cache: 캐시 대기열의 맨 앞으로 가져와야합니다.

If NOT in the 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:
3
1 2 3 4 1 2 5 1 2 3 4 5

Output:
Page Fault: 10

---

이것은 복잡성이 O (1) 인 간단한 Java 프로그래머입니다.

//

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);
  }


}

참고URL : https://stackoverflow.com/questions/2504178/lru-cache-design