缓存就像电脑的“小抄”，把常用的东西放在手边，用起来更快！

项目背景介绍

1 什么是缓存？
用更小更快的存储设备作为更大更慢的存储设备的缓冲区，让上层访问数据时速度更快

2 为什么要实现缓存系统？
现在假设一个简单的框架，即

CPU
缓存
磁盘
CPU访问数据时，优先访问缓存，这个速度比直接访问磁盘快很多
当缓存中不存在时，才通过缓存去磁盘中访问
缓存系统旨在提高CPU访问数据的效率，从而提高整个计算机的效率

3 在什么地方加缓存
在需要高速访问数据的设备和读写数据慢的设备之间

缓存系统的调度策略

LRU 最近最少使用 Least recently used

假设：如果数据最近被访问过，那么将来被访问的几率也更高
策略：尽可能将最近访问的数据保存在缓存中

LRU 的直接实现

mermaid 图

graph TD
    A[请求数据] -->|缓存命中| B[返回数据]
    A -->|缓存未命中| C[检查缓存是否满]
    C -->|未满| D[插入数据]
    C -->|已满| E[淘汰最久未使用的数据]
    E --> F[插入数据]
    D --> G[更新数据为最近使用]
    F --> G
    B --> G
    G --> H[完成请求]

具体思路

上述操作包括：查找、记录最近位置、删除节点、插入节点
- 采用双链表来插入的效率较高（单链表的效率低）
- 哈希表的查找效率高
最终选择：哈希表+双向链表

LRU 的缺点

对访问模式不敏感，对于不重复的循环数据，可能出现几乎0命中的情况
缓存污染：某个热门访问的数据在短时间内被冷门数据挤出了缓存
锁的粒度大？

LRU改进1：LRU-k

mermaid 图

graph TD

    A[访问页 P] --> B{P 在缓存队列中?}

    %% 已在缓存队列（Cache Queue）中

    B -- 是 --> C[将 P 移动到 MRU 端（更新缓存顺序）]

    C --> Z[完成请求]

    %% 不在缓存队列中

    B -- 否 --> D{P 在历史队列中?}

    %% 首次或仍未达到 k 次的情况：历史队列（History Queue）

    D -- 否 --> E[插入历史队列，计数 = 1]

    E --> Z

    D -- 是 --> F[历史计数 ++]

    F --> G{计数 ≥ k?}

    %% 仍未达到 k 次，只更新历史队列顺序

    G -- 否 --> H[更新历史队列中 P 的时间顺序]

    H --> Z

    %% 达到 k 次，尝试晋升到缓存队列

    G -- 是 --> I{缓存队列已满?}

    I -- 否 --> J[从历史队列移除 P，并插入缓存队列 MRU 端]

    J --> Z

    I -- 是 --> K[淘汰缓存队列末尾页面（LRU）]

    K --> L[从历史队列移除 P，并插入缓存队列 MRU 端]

    L --> Z

具体思路

解决的问题：热门访问数据被挤出缓存
解决方案：在缓存查不到的数据找到后，不立刻放入缓存，而是等待多几次再放入，避免冷门数据的侵占
利用一个 LRUCache 作为缓存，一个作为次缓存

LRU改进2：HashLRU

mermaid 图

graph TD
    A[访问页 P] --> B{哈希选择分片}
    B --> C[分片N处理]
    
    subgraph 分片N
    C --> D{P 在缓存队列中?}
    %% 已在缓存队列（Cache Queue）中
    D -- 是 --> E[将 P 移动到 MRU 端（带分片锁）]
    E --> Z[完成请求]
    %% 不在缓存队列中
    D -- 否 --> F{P 在历史队列中?}
    %% 首次或仍未达到 k 次的情况：历史队列（History Queue）
    F -- 否 --> G[插入历史队列，计数=1（带分片锁）]
    G --> Z
    F -- 是 --> H[历史计数++（带分片锁）]
    H --> I{计数 ≥ k?}
    %% 仍未达到 k 次
    I -- 否 --> J[更新历史队列顺序（带分片锁）]
    J --> Z
    %% 达到 k 次
    I -- 是 --> K{缓存队列已满?}
    K -- 否 --> L[迁移到缓存MRU端（带分片锁）]
    L --> Z
    K -- 是 --> M[淘汰LRU页面（带分片锁）]
    M --> L
    end

具体思路

加入锁来避免并发问题

引入了锁竞争，临界区外面的等待导致多线程时效率降低
利用 LRU 分片减小临界区，从而解决LRU的锁等待的问题
为什么不用读写锁？

LFU 最不经常使用 Least Frequently Used

假设：最近使用频率高的数据很大概率将会再次被使用，而最近使用频率低的数据，将来大概率不会再使用
策略：尽可能将最近使用频率高的数据保存在缓存中

基本LFU

mermaid 图

graph TD
    A[初始化缓存空间 大小为 n] --> B[接收操作: Get/Put key, value]

    B --> C{Key 是否在缓存中?}
    C -- 是 --> D[更新 Key 对应的 Value]
    D --> E[增加 Key 的访问频数]
    E --> F[操作完成]

    C -- 否 --> G{缓存是否已满?}
    G -- 否 --> H[构造新节点 Freq=1]
    H --> E

    G -- 是 --> I{淘汰策略: 找到访问频数最低的节点}
    I --> J{是否有多个最低频数节点?}
    J -- 是 --> K[淘汰最久未被访问的节点]
    J -- 否 --> L[淘汰该节点]

    K --> M[构造新节点 Freq=1]
    L --> M
    M --> E

具体思路

核心操作 put 和 get
需要记录 key value freq

put 时，如果满了，需要删除一个频率最低的节点，要想 O(1) 删除，则需要记录最低频率的大小
get 时，可以将那一个节点频率直接加 1
put 时，由于始终会有 1 这个最小频率，所以没有查询次小频率的需求

存在的问题？

计数不断增长导致其难以被替换，甚至数值溢出
刚加入的数据容易很快被替换掉
锁的粒度大，多线程高并发访问下锁的同步等待时间过长。

LFU改进1：最大平均访问次数限制

mermaid 图

graph TD
    A[开始] --> B[初始化缓存]
    B --> C[设定最大平均访问次数限制]
    C --> D[监听读写请求]
    D -->|有新请求| E[更新对应项的访问频率]
    E --> F[计算当前平均访问次数]
    F --> G{平均访问次数 > 最大平均值?}
    G -- 是 --> H[对所有项目的访问计数进行全局衰减]
    H --> I[更新后的平均访问次数检查]
    I --> J{平均访问次数 <= 最大平均值?}
    J -- 是 --> K[继续监听读写请求]
    J -- 否 --> H
    G -- 否 --> K
    K --> D

具体思路

如何防止计数不断增大？需要定期清理

引入访问次数平均值概念
当平均值大于最大平均值限制时，对计数进行全局的衰减

LFU改进2：利用hash表来

mermaid 图

graph TD
    A[开始] --> B[初始化分片]
    B --> C[设定分片数量]
    C --> D[为每个分片分配独立锁]
    D --> E[监听读写请求]
    E -->|有新请求| F[计算键的哈希值]
    F --> G[确定分片]
    G --> H[获取对应分片的锁]
    H --> I[执行读写操作]
    I --> J[更新访问频率]
    J --> K[释放锁]
    K --> L[返回结果]
    L --> E

具体思路

利用 LFU 分片来解决 LFU 的锁等待的问题

ARC

mermaid 图

graph LR
    subgraph sg_ARC_Cache ["ARC 缓存"]
        subgraph sg_L1 ["L1 最近使用 (一次)"]
            T1[(T1: 最近一次访问的页面)]
            B1[(B1: T1 的历史记录)]
        end
        subgraph sg_L2 ["L2 频繁使用 (多次)"]
            T2[(T2: 频繁访问的页面)]
            B2[(B2: T2 的历史记录)]
        end
    end

    A[新请求] -->|"T1 和 T2 缓存均未命中"| T1_Check{页面在 B1 中吗?}
    T1_Check -- 是 --> Adapt_Increase_T1["调整: 增加 T1 的目标大小 (加载到 T2 或下次命中时提升到 T2)"]
    T1_Check -- 否 --> T2_Check{页面在 B2 中吗?}
    T2_Check -- 是 --> Adapt_Increase_T2["调整: 增加 T2 的目标大小 (加载到 T2)"]
    T2_Check -- 否 --> New_Page_To_T1["将新页面加载到 T1"]

    A -->|"T1 缓存命中"| Move_T1_to_T2["从 T1 移动到 T2"]
    A -->|"T2 缓存命中"| Move_To_MRU_T2["移动到 T2 的最近使用位置"]

    New_Page_To_T1 --> Evict_Logic{缓存已满吗?}
    Evict_Logic -- "是，T1 满或 (T1+T2 满且 p < |B1|)" --> Evict_From_T1_To_B1["从 T1 驱逐到 B1"]
    Evict_Logic -- "是，T2 满或 (T1+T2 满且 p >= |B1|)" --> Evict_From_T2_To_B2["从 T2 驱逐到 B2"]

    Evict_From_T1_To_B1 --> B1
    Move_T1_to_T2 --> T2
    Move_To_MRU_T2 --> T2
    Evict_From_T2_To_B2 --> B2
    Adapt_Increase_T1 --> T2
    Adapt_Increase_T2 --> T2
    New_Page_To_T1 --> T1

    style sg_L1 fill:#f9f,stroke:#333,stroke-width:2px
    style sg_L2 fill:#ccf,stroke:#333,stroke-width:2px
    style A fill:#bbf,stroke:#333,stroke-width:2px

基本思路

Adaptive Replacement Cache 可调替换缓存
结合 LRU 以及 LFU 两者优点
整体概括

将 ARC 分成 LRU 和 LFU 两部分
LRU 部分

参考资料

https://github.com/youngyangyang04/KamaCache
https://itanken.github.io/ostep-chinese/
https://zhuanlan.zhihu.com/p/71956210
https://blog.csdn.net/liuyun2113/article/details/12705057