LRU缓存

LRU Cache(Least Recently Used)：即最近最少使用，它是一种Cache的替换算法。

• 是一种常见的缓存淘汰算法
• 用于在有限的缓存空间中管理数据对象
• LRU Cache 的核心思想是基于时间局部性原理，即最近被访问的数据在未来可能会被再次访问

草图：

实现

使用list和unordered_map(hash表)实现$O(1)$的get和put

1. 上面草图是list头部作为最久未使用的缓存，最尾部的座位最近使用的缓存
   • 其实大部分都是反过来的，头部作为最近使用的，最尾部作为最久未使用的缓存，思路都一样
2. 当在hash表里面找到对应key的键值对
3. 存在就代表缓存命中，把对应key的键值对移动到队尾，代表最近使用，返回数据
4. 不存在就代表未命中
   • 缓存长度到max就把最久未使用(头部)的缓存删除，把新读取到的硬盘数据读到缓存里面(list的尾部)，同时hash表也会把对应的key的键值对删掉，新增对应的键值对
   • 缓存长度没有到max，直接把硬盘上的数据读到缓存(list的尾部),同时hash表新增对应的键值对
   • 处理完后返回数据

代码

/**
 * @brief 读取块返回数据，命中->返回数据，未命中->加载硬盘数据
 * 
 * @param chunk_id 
 * @return std::shared_ptr<const ChunkData> 
 */
std::shared_ptr<const ChunkData> FileCacheManager::readChunk(uint64_t chunk_id){
    
    auto map_it =  lru_map.find(chunk_id);

    if(map_it != lru_map.end()){ // 缓存命中
        
        auto currentChunk = find(lru_list.begin(),lru_list.end(),chunk_id);

        // 把缓存中的内容移到最后表示最近使用
        if (currentChunk != lru_list.end()){
            uint64_t id = *currentChunk; 
            lru_list.erase(currentChunk);
            lru_list.push_back(id);
        }
        

        //命中次数+1
        _hitCount++;

        // 返回缓存数据
        return map_it->second;

    }
    
    // 未命中

    //未命中次数+1
    _missCount++;
    
    std::shared_ptr<const ChunkData> newChunkData = loadFromDisk(chunk_id); //从硬盘加载数据

    if (!newChunkData){
        return nullptr; // 加载失败
    }

    if (lru_list.size() >= _max_chunks){ //如果超出max_chunks就去掉第一个，也就是最远的
        uint64_t minimumUsage_id = lru_list.front();
        lru_list.pop_front();
        lru_map.erase(minimumUsage_id);
    }

    // 将硬盘的数据存入缓存中
    lru_map[chunk_id] = newChunkData;
    lru_list.push_back(chunk_id);

    // 返回缓存数据
    return newChunkData;

}