系统设计：一种LRU缓存的C++11实现

---

目标

• 缓存的概念
• 缓存的数据淘汰策略
• LRU策略的实现
• 时间和空间复杂度分析
• 优化的可能性
• 近似LRU算法
  Using Redis as an LRU cache

image.png

题目示例

LeetCode 146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put

get(key)

• Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value)

• Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

基本概念

• 什么是缓存，缓存有什么特点？
  举个例子，去图书馆查资料，一般情况下我们会集中把我们有可能查阅的几本书从书架取下来，放在我们的桌面上，以便交叉查阅，从而避免频繁的从座位上跑到书架旁去取书。在这个例子里，书桌所扮演的就是缓存的角色。

缓存有两个特点：

• 能在某种程度上降低访问数据的成本；
• 其容量远小于外部存储的容量，如本例子中，书桌上能容纳的书本数就远小于书架的。

体现的思想

• 空间换时间

• LRU是什么？

LRU缓存是一种以LRU策略(距离当前最久没使用过的数据应该被淘汰)为缓存策略的缓存。
而所谓的缓存策略，就是当缓存满了之后，又有新数据需要加入到缓存中时，我们怎么从缓存中删除旧数据为新数据腾出空间的策略。
LRU，Least Recently Used的简写，即近期最少使用算法。该算法依据于程序的局部性原理， 其淘汰旧数据的策略是，距离当前最久没有被访问过的数据应该被淘汰。

实现原理

• 实现LRU的数据结构设计
  unordered_map + double linked list
  （1）维护一个双向链表，该链表将缓存中的数据块按访问时间从新到旧排列起来（由于双向链表节点的交换代价很低，所以使用双向链表作为主要数据结构）
  节点为包含key,value的结构体（一条记录）
  （2）使用哈希表（map）保证缓存中数据的访问速度（由于引入哈希表可以提高查询速度，所以使用哈希表作为辅助数据结构）
  map中的一个元素包含键值key以及链表中键值为key的迭代器（指针），通过key查找记录的地址，即可O(1)时间内访问链表中访问的记录

接口描述

int get(int key)；

• 功能
  在哈希表中查找键值为key的元素，如果不存在返回-1；如果存在返回该key对应的value值；
• 实现
  这里说存在key的情况，如何get：
  step1: 将键值为key的记录与链表首元交换位置;
  step2: 更新哈希表中键值为key的迭代器

void put(int key, int value)；

• 功能与实现
  将key,value这条记录放入缓存，如果该记录已经在缓存中，更新该记录到缓存链表头部；如果不在缓存中且缓存未满，插入缓存链表头部，如果缓存满，删除尾部数据。

代码细节

class LRUCache {
private:
    typedef int key_t;
    typedef int value_t;
    typedef struct{
        key_t key;
        value_t value;
    } Node_t;
    typedef list<Node_t> cacheList_t;
    typedef map<key_t,cacheList_t::iterator> map_t;
    
    int m_capacity;
    cacheList_t m_cacheList;
    map_t m_mp;
    
    
    
public:
    LRUCache(int capacity) : m_capacity(capacity){
        
    }
    
    int get(int key) {
        auto it = m_mp.find(key);
        // not cached
        if(it == m_mp.end()) return -1;
        // cached
        else{
            auto list_it = m_mp[key];
            Node_t node = {key,list_it->value};
            m_cacheList.erase(list_it);
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            return m_cacheList.begin()->value;
        }
    }
    
    void put(int key, int value) {
        auto it = m_mp.find(key);
        // cached
        if(it != m_mp.end()){
            auto listIt = m_mp[key];
            // delete the cached node, and then insert it to the list head
            Node_t node = {key, value};
            m_cacheList.erase(listIt);
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            
        }
        // not cached
        else{
            // cache is full
            if(m_cacheList.size() == m_capacity){
                m_mp.erase(m_cacheList.back().key);
                m_cacheList.pop_back();
            }
            // cache is not full
            Node_t node = {key,value};
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            
        }
        
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

优化的可能性

• get命中数据时，可以用移动构造的方式替代临时对象的拷贝