缓存系统：

1.项目概述

一个基于 C++ 的轻量级缓存库，提供了可扩展的缓存策略实现。核心特性包括：

- 模板化设计：支持任意类型的键（Key）和值（Value） 【泛型设计】

- 多策略支持：提供 LRU、LRU-K 等缓存替换算法

- 线程安全：内置互斥锁保护共享数据

- 数据源支持：使用SQLite模拟底层磁盘数据，模拟操作系统真实取页流程

2.项目结构

本项目采用模块化设计，将缓存策略、数据库模拟与测试代码分层管理，整体目录结构如下：

Cache/ │── testAllPolicy.cpp # 主程序入口，用于功能测试与验证 │ │── include/ # 缓存策略头文件及实现 │ │── CachePolicy.h # 缓存策略基类定义（抽象接口） │ │── LRU_CachePolicy.h # LRU 及其优化版本实现 │ │── LFU_CachePolicy.h # LFU 及其分片优化实现 │ │── data/ # 底层数据模拟模块 │ │── SQLite.h # SQLite 数据库模拟接口头文件 │ │── SQLite.cpp # SQLite 数据库模拟接口实现 │ │── CMakeLists.txt # 使用 CMake在此配置编译流程

• testAllPolicy.cpp：模拟各种实际工作环境，调用缓存策略与数据库接口，进行功能测试与性能验证 。
• include/：包含所有缓存策略的实现文件，便于扩展新的替换策略。
• data/：模拟底层数据库，提供数据读取接口，方便对缓存命中与置换机制进行测试。

3.项目实现-LRU

1.底层数据源：

使用文件式轻量级关系型数据库：SQLite3 真实模拟操作系统取址流程（SQLite下载网址：SQLite Download Page）

使用.dll和.a文件动态链接库

这里对于数据库中的数据，默认所有的数据都是字符串varchar类型，在获取字符串类型后自行转换成缓存中所需要的Key，Value类型。

2.LRU原理

LRU算法，即Least Recently Used（最近最少使用页面算法），在需进行置换时将最近最久未使用的页面予以淘汰。

使用一个特殊的栈来存储各个页面。当一个进程访问一个新的页面时，如果此页面已经在栈中，则把页面置于栈顶；如果没有，则淘汰掉栈底的页面，把页面压入栈顶。

3.LRU及优化算法的实现

LRU：

哈希表让每一次查询时间复杂度控制到O(1)，而双向链表可以便捷的实现页面顺序的调换：若存在对应的表结点则直接找到结点并删去，再从头插入页面结点；若不存在则使用tail删去尾结点，并使用head插入新页结点。

如图，使用哈希表和双向链表结合的数据结构实现了LRU页面置换算法：

LRU-K：

使用继承的方式对LRU算法再次优化，增加阈值K常量定义，在某个页结点访问次数达到K次后再把该页放入缓存中。类中加入一个构造好的LRU缓存对象直接存储所有页结点的历史访问次数。

这里覆写了Value get(Key key)及void put(Key key, Value value)方法，实现了对访问次数的判断后放入。在测试.cpp文件中，通过put的覆写更改了应有的放入逻辑，提高了命中率。

LRU-Hash：

直接继承基类Policy，使用持有vector指针数组的方式对LRU缓存进行优化。对key值取哈希并取模，分入不同的LRU缓存片中，使进程能够同时访问不同的片内键值对。在不同进程请求不同的缓存时，可以在对应的片中同时获取对应的值，提升了缓存系统的并发速率。类中引入vector构造对象存放多个分片LRU缓存指针引用，使用hash函数计算每一个键对应的片区，使用vector中的指针对缓存进行访问。

覆写了所有get、put方法。

4.项目实现-LFU

LFU:

LFU（Least Frequently Used，最不经常使用）算法与 LRU 不同，淘汰缓存时不是看最近使用时间，而是看访问频次：访问次数越少的结点，越容易被淘汰。

本实现中使用了以下数据结构：

• 哈希表 (unordered_map)：保证根据 key 能够 O(1) 时间找到结点；
• 频次链表（NodeList）：每一个频次对应一个双向链表，链表内部维护访问该频次的所有结点，结点用双向链表连接，实现了快速插入和删除；
• 节点结构体 (Node)：结点存储 key、value 以及 freq（访问次数），并带有 pre/next 指针，用于维护在双向链表中的位置。

其核心逻辑为：

1. 新结点插入：访问次数默认为 1，将其放入 freq = 1 的链表尾部；
2. 访问已有结点：将结点从原来的频次链表中移除，freq++ 后插入到更高频次链表的尾部；
3. 淘汰策略：当容量已满时，淘汰 minFreq 对应的链表头部结点（即最少访问次数中最早插入的结点）。

示意图如下：

LFU平均访问频次优化：

为了避免长期运行过程中缓存中的结点频次无限增加，导致新结点无法竞争，本实现引入了 平均访问频次 curAverageNum 和 最大平均访问频次 maxAverageNum 的机制。

当总访问次数 curTotalNum 超过 maxAverageNum 时，触发 handleOverMaxAverageNum()，对所有结点的 freq 整体衰减一半，从而保证缓存保持动态性，避免频次“固化”。

这种方法确保了：

• 老旧的热点数据不至于永远占据缓存；
• 新数据仍有机会进入缓存，提高系统的适应性。

LFU-Hash：

为了进一步提升并发性能，本实现提供了 分片 LFU 缓存 (LFU_HashCache)：

• 将缓存按 哈希分片，每个分片独立维护一个 LFUCache；
• 插入和查询时，先通过 hash(key) % sliceNum 计算出分片，再在对应的 LFU 内部操作；
• 由于分片间独立，可以同时处理多个并发请求，大大提高缓存系统的并行度。

5.运行截图