引言

提到缓存系统，我们就不能避免需要接触到操作系统的内存管理

如果大家已经有了解了，可以直接阅读LRU算法

静态地址转换

内存管理的方式有很多种，在最初，我们选择的是静态地址转换技术。这种技术的本质就是直接在物理地址上进行书写，操作很简单，拿到对应物理地址的指针之后，把内容写在内存上。但是这种方式的缺点是很明显的

我们必须要在程序执行之前，也就是在编译的过程中，把地址固定好，从而在程序的运行过程之中，但如果我们的程序需要修改，在内存中的地址要移动的时候，事情会变得非常复杂。所以我们之后变成了动态地址转换。

动态地址转换

什么是动态地址转换，顾名思义，就是地址是可以变化的，也就是相对的。我一个程序我只需要知道每条代码的相对位置，然后对相对的位置进行偏移即可

随着我们的程序越来越多，内存就变得不够了，所以我们引进了内存交换技术。内存交换技术需要我们和磁盘打交道，因为我们不可能把所有的内容都存在内存上。但是因为磁盘I/O是很慢的，而内存与CPU十分接近，所以我们需要把内容转换到内存上面，然后用寄存器去读取代码。

虚拟内存

对于中小的程序来说，交换技术还是说的过去，但是如果程序变大，计算机的内存无法支持整个程序，也就是说一个程序无法完整的保存在内存上面，更何况是多进程的运行程序，我们就需要不停的去交换，每一次的换进换出让效率十分的地下，所以我们就提出了虚拟内存的概念。

分页管理内存

什么是分页管理内存呢？

假设我们使用的是虚拟内存系统，我们将虚拟地址发送到了MMU上面，然后MMU会将这个地址转化成物理地址，再发送到内存总线上进行读写的操作。如图：

所以我们会存在一个页表的结构，这个页表上面记录了物理地址

这个页表上面存储了每个虚拟页面的起始地址和对应的物理内存地址

缓存系统

这其实是一个加速分页的过程，因为我们查询页表是要和内存打交道，虽然是比磁盘要快很多，但是相比于高速缓存来说，还是慢了很多。特别是我们要不停的查询页表，这让效率慢了很多。

FIFO算法（先进先出算法）

这个算法很简单，就是你先进，那么当页满了时候，你就先出，和队列一模一样。虽然实现起来比较简单，但是真正的效果并不好，很可能热门数据第一轮就被送走了，所以我们会优先选择其他的算法。

LRU算法

版本一

最近最少使用算法，如果一个数据最近被访问过，那么将来被访问的可能性也较大。因此，它选择最近最长时间未被访问的页面进行替换。LRU的性能和效率接近OPT，但是对于频繁访问的页面更新开销较大。

潜在问题：淘汰热点数据，如果有个数据在1个小时的前59分钟访问了1万次(可见这是个热点数据),再后一分钟没有访问这个数据，但是有其他的数据访问，就导致了我们这个热点数据被淘汰

那么这个算法需要完成对于数据的增删，还有对于数据是否在缓存系统里面的查询。

如果单单是数据的增删，我们会直接想到链表，但是链表的查询是很慢的，而查询对应数据是否在内存里面我们会想到哈希表。所以我们这里用两个数据结构，一个是链表，一个是unordered_map

我们接着先定义每一个结点的类

template<typename Key, typename Value>
class LruNode {
private:
    Key key_;
    Value value_;
    size_t accessCount_;  // 访问次数
    std::weak_ptr<LruNode<Key, Value>> prev_;  // 改为weak_ptr打破循环引用，避免内存泄漏
    std::shared_ptr<LruNode<Key, Value>> next_;

public:
    LruNode(Key key, Value value) : key_(key), 
                                    value_(value), 
                                    accessCount_(1) 
    {}

    // 提供必要的访问器
    Key getKey() const {return key_;};
    Value getValue() const {return value_;};
    void setValue(Value value){value_ = value;};
    size_t getAccessCount() const {return accessCount_;};
    void incrementAccessCount() {accessCount_++;};
    
    friend class KLruCache<Key, Value>;
};

然后我们要定义我们的缓存系统，其中功能：

对于读的访问get（）要更新结点的位置

对于写的访问put（）要更新结点的位置

如果是新的结点，要addNewNode（），如果链表满了，要evictLeastRecent（）

每一次的加入或者更新结点都是在链表的尾部，每一次删除结点都是在链表的头部

template<typename Key, typename Value>
class KLruCache : public KlCachePolicy<Key, Value>{
public: 
    using LruNodeType = LruNode<Key, Value>;
    using NodePtr = std::shared_ptr<LruNodeType>;
    using NodeMap = std::unordered_map<Key, NodePtr>;

    KLruCache(int capacity) : capacity_(capacity){
        initializeList();
    }

    ~KLruCache() override = default; // 生成一个空的析构函数，override避免重写错误

    // 向缓存中插入或更新键值对
    void put(Key key, Value value) override{
        if(capacity_ <= 0){
            return;
        }
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if(it != nodeMap_.end()){  
            updateExistingNode(it->second, value); // 把这个结点放在尾部
            return;
        }

        addNewNode(key, value);
    }

    // 从缓存中获取指定的key对应的值
    bool get(Key key, Value& value) override{
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if(it != nodeMap_.end()){
            moveToMostRecent(it->second);
            value = it->second->getValue();
            return true;
        }
        return false;
    }

    Value get(Key key) override{
        Value value{}; // 创建Value对象并初始化
        // memset(&value, 0, sizeof(Value)); 
        // memset 是按字节设置内存的，对于复杂类型（如 string）使用 memset 可能会破坏对象的内部结构
        get(key, value);
        return value;
    }

    // 删除指定的元素
    void remove(Key key) override{
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if(it != nodeMap_.end()){
            removeNode(it->second);
            nodeMap_.erase(it);
        }
    }

private:
    // 创建首尾虚拟节点
    void initializeList(){
        // 这里是哨兵结点，没有真实的数据，所以传的是默认值Key()和Value()
        dummyHead_ = std::make_shared<LruNodeType>(Key(), Value());
        dummyTail_ = std::make_shared<LruNodeType>(Key(), Value());
        dummyHead_->next_ = dummyTail_;
        dummyTail_->prev_ = dummyHead_;
    }

    void updateExistingNode(NodePtr node, const Value& value){
        node->setValue(value); // 更新的策略其实就是创造一个和原来一模一样的结点
        moveToMostRecent(node);
    }

    void addNewNode(const Key& key, const Value& value){
        if(nodeMap_.size() >= capacity_){  // 如果缓存已满，就删除结点
            evictLeastRecent(); 
        }

        NodePtr newNode = std::make_shared<LruNodeType>(key, value);
        insertNode(newNode);
        nodeMap_[key] = newNode;
    }

    // 将节点移动到最新的位置
    void moveToMostRecent(NodePtr node){
        removeNode(node);
        insertNode(node);
    }

    void removeNode(NodePtr node){
        /*
        expired() 方法的作用：
        返回 true：weak_ptr 指向的对象已被销毁
        返回 false：weak_ptr 指向的对象仍然存在
        */
        if(!node->prev_.expired() && node->next_){ // 检查prev_和next_是否都存在
            // weak_ptr 本身不能直接访问所指向的对象，必须通过 lock() 获取一个 shared_ptr 后才能使用。
            auto prev = node->prev_.lock();
            prev->next_ = node->next_;
            node->next_->prev_ = prev;
            node->next_ = nullptr;  // 清空next指针，彻底断开结点与链表的连接
        }
    }

    // 从尾部插入结点
    void insertNode(NodePtr node){
        // 如果需要通过weak_ptr来调整结点的位置，和next关联在一起就需要lock（）
        node->prev_ = dummyTail_->prev_;
        node->next_ = dummyTail_;
        dummyTail_->prev_.lock()->next_ = node; // 使用lock获取shared_ptr，再赋值
        dummyTail_->prev_ = node;
    }

    //  驱逐最近少访问的
    void evictLeastRecent(){
        NodePtr leastRecent = dummyHead_->next_; // 把头部的结点删除
        removeNode(leastRecent);
        nodeMap_.erase(leastRecent->getKey());
    }

private:
    int capacity_;   // 缓存容量
    NodeMap nodeMap_;  // key -> Node
    std::mutex mutex_;  // 互斥锁，用于线程安全
    NodePtr dummyHead_;  // 虚拟头节点
    NodePtr dummyTail_;  // 虚拟尾节点
};

这个就是我们大致的结构，但是我们回头看这个算法的时候，会发现有很多的问题：

1、有可能在一分钟之内加载了很多冷门的数据，反而把热门的数据全部挤走

2、锁的粒度太大，导致每一次多线程高并发的访问下，同步等待将是一笔极大的时间开销

3、如果是循环的一次性遍历大量不重复的数据（如A->B->C->D->A->B->...），LRU可能逐步清空，几乎无法命中

版本二

所以我们要改变我们的算法，这次是从结构上进行改变。

我们加入了k这一个变量，只有访问次数达到k次，才可以加入到缓存系统之中，而剩下的数据都放在历史链表里面，其实不管是缓存系统，还是历史链表，结构都是与版本一差不多的，所以我们这里直接继承版本一的代码并加以更改

版本一所创建的缓存系统里面value在历史链表里面就变成了访问或者写入的次数，所以就是size_t

类型作为区分，而缓存系统还是没变，所以这里主要的就是创建历史链表和处理历史链表和缓存系统之间的关系

Value get(Key key){
        // 首先尝试从主缓存获取数据
        Value value{};
        bool inMainCache = KLruCache<Key, Value>::get(key, value);
        
        // 获取并更新访问的历史记录
        size_t historyCount = historyList_->get(key); // 获取这个点的历史访问次数
        historyCount++; // 增加访问次数
        historyList_->put(key, historyCount); // 更新历史记录

        // 如果在主缓存中，直接返回值
        if(inMainCache){
            return value; // 直接返回默认的值，也就是0，在历史记录之中重新统计
        }

        // 如果不在主缓存中，但访问次数达到了k次
        if(historyCount >= k_){
            // 检查是否有历史记录
            auto it = historyValueMap_.find(key); 
            if(it != historyValueMap_.end()){
                // 有历史值，将其添加到主缓存
                Value storedValue = it->second;

                // 从历史记录移除
                historyList_->remove(key); // 因为加入到了主缓存，所以把历史的记录都删除
                historyValueMap_.erase(it);

                // 添加到主缓存
                KLruCache<Key, Value>::put(key, storedValue);

                return storedValue;
            }
            // 如果没有历史记录，无法添加到缓存，返回默认值
        }

        return value;
    }

    // 处理写入的数据
    void put(Key key, Value value){
        // 检查是否在主缓存里面
        Value existingValue{};
        bool inMainCache = KLruCache<Key, Value>::get(key, existingValue);

        if(inMainCache){
            // 已在主缓存，直接更新在主缓存的位置
            KLruCache<Key, Value>::put(key, value);
            return;
        }
        
        // 获取并更新访问的历史记录
        size_t historyCount = historyList_->get(key);
        historyCount++; 
        historyList_->put(key, historyCount);

        // 保存值到历史记录映射，供后续的get操作使用
        historyValueMap_[key] = value;

        // 检查是否达到k次访问阈值
        if(historyCount >= k_){
            // 达到阈值，添加到主缓存
            historyList_->remove(key);
            historyValueMap_.erase(key);
            KLruCache<Key, Value>::put(key, value);
        }
    }

版本三

template<typename Key, typename Value>
class KHashCache{
public:
    /*
    std::thread::hardware_concurrency()
    返回当前系统支持的硬件并发线程数量
    */
    KHashCache(size_t capacity, int sliceNum)
        : capacity_(capacity)
        , sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency()) // 如果sliceNum小于等于0，默认使用CPU 核心数
    {
        // std::ceil()向上取整函数
        size_t sliceSize = std::ceil(capacity_ / static_cast<double>(sliceNum_)); // 获取每个分片的大小
        for(int i = 0; i < sliceNum_; i++){
            lruSliceCaches_.push_back(std::make_unique<KLruCache<Key, Value>>(sliceSize));
        }
    }
    
    void put(Key key, Value value){
        // 获取key的hash值，并计算出对应的分片索引
        size_t sliceIndex = Hash(key) % sliceNum_;
        lruSliceCaches_[sliceIndex]->put(key, value);
    }

    bool get(Key key, Value& value){
        // 获取key的hash值，并计算出对应的分片索引
        size_t sliceIndex = Hash(key) % sliceNum_;
        return lruSliceCaches_[sliceIndex]->get(key, value);
    }

    Value get(Key key){
        Value value{};
        get(key, value);
        return value;
    }
private:
    // 将key转换为对应的hash值
    size_t Hash(Key key){
        std::hash<Key> hashFunc;
        return hashFunc(key);
    }

private:
    int capacity_; // 缓存容量
    int sliceNum_; // 分片数量  
    std::vector<std::unique_ptr<KLruCache<Key, Value>>> lruSliceCaches_; // 切片LUR缓存
   };