本地缓存

本地缓存通过把远程数据保存在服务进程内存中提升高并发读取性能，并通过 FIFO、LFU、LRU、W-TinyLFU 等策略管理有限的缓存空间；其中 W-TinyLFU 综合近期访问和访问频率提高命中率，而 SingleFlight 则将同一个 Key 的并发缓存未命中请求合并为一次数据库访问，避免热点数据失效造成缓存击穿。

一、核心主线

本节讲的是高并发读场景的第二种通用方案：本地缓存。

业务服务读取数据时，通常需要通过网络访问数据库或下游服务。将已经读取过的数据缓存在服务进程的内存中，后续相同请求便可以直接从内存获得结果。

1
2
3
4
5
6
7

首次读取：
业务服务 → 网络请求 → 数据库
                    ↓
                 缓存到内存

后续读取：
业务服务 → 本地内存 → 直接返回

本地缓存的本质是：

使用内存空间换取读取时间，将网络访问转化为高效的本地内存访问。

本节重点解决两个问题：

1. 内存有限时，应该淘汰哪些缓存数据；
2. 热点数据失效时，如何避免大量并发请求同时访问数据库。

二、本地缓存的作用

1. 缩短读取链路

未使用本地缓存时：

1
2
3
4
5
6
7

请求
  ↓
业务服务
  ↓ 网络调用
数据库或下游服务
  ↓
返回数据

命中本地缓存时：

1
2
3
4
5

请求
  ↓
业务服务进程内存
  ↓
直接返回

本地缓存不需要额外网络通信，因此读取延迟通常很低。

2. 降低下游压力

如果热门数据被大量重复读取，本地缓存可以避免每次请求都访问数据库：

1
2
3
4
5

大量相同读请求
      ↓
本地缓存命中
      ↓
减少数据库查询

它可以同时减少：

• 网络开销；
• 数据库 QPS；
• 下游服务调用量；
• 请求响应时间。

3. 空间与时间的权衡

本地缓存不能无限增长，因为内存资源有限。

因此，需要在以下两者之间做权衡：

1
2
3

缓存更多数据，提高命中率
            ↕
控制内存占用，避免资源耗尽

这就需要缓存淘汰策略自动清理价值较低的数据。

三、缓存淘汰策略

一个好的淘汰策略应该尽量：

• 保留未来可能继续访问的数据；
• 淘汰不再使用或价值较低的数据；
• 提高缓存命中率；
• 控制算法本身的内存和计算开销。

本节介绍了 FIFO、LFU、LRU 和 W-TinyLFU。

1. FIFO

FIFO 全称为 First In First Out，即先进先出。

1.1 淘汰规则

优先淘汰最早进入缓存的数据：

1
2
3

最早进入 → ... → 最近进入
   ↑
优先淘汰

通常可以使用队列实现。

1.2 优点

• 逻辑简单；
• 实现成本低；
• 维护开销小。

1.3 缺点

数据进入缓存的时间并不能代表它未来是否有价值。

某条数据可能最早进入缓存，但一直被频繁访问。FIFO 仍会优先淘汰它，从而导致热点数据被错误清理。

因此，FIFO 的缓存命中率通常较低，实践中较少单独使用。

2. LFU

LFU 全称为 Least Frequently Used，即最不经常使用。

2.1 淘汰规则

为每条缓存数据维护访问次数：

1
2
3
4
5

数据被访问一次
      ↓
访问计数 +1
      ↓
优先淘汰访问次数最少的数据

2.2 优点

• 能识别高频访问数据；
• 适合访问热度比较稳定的场景；
• 可以长期保留访问频率较高的数据。

2.3 缺点

LFU 过度依赖历史访问次数。

可能出现：

• 新数据访问次数低，刚进入缓存就被淘汰；
• 过去很热门、最近已不再访问的数据长期占用缓存；
• 访问次数会不断累积，旧历史对当前判断影响过大。

3. LRU

LRU 全称为 Least Recently Used，即最近最少使用。

3.1 淘汰规则

优先淘汰最长时间没有被访问的数据。

常见实现是：

1

哈希表 + 双向链表

• 哈希表用于快速定位缓存数据；
• 双向链表按照最近访问时间排列数据；
• 最近被访问的数据移动到链表尾部；
• 链表头部保存最久未访问的数据，淘汰时从头部删除。

1
2
3
4

最久未访问                         最近访问
链表头部 → 数据A → 数据B → 数据C → 链表尾部
   ↑
优先淘汰

3.2 优点

• 能较好地保留近期热点数据；
• 查找和调整数据位置效率较高；
• 适合热点具有时间局部性的场景。

3.3 缺点

一次偶发的冷数据扫描或批量访问，可能把大量冷数据放入缓存，并将真正的热点数据挤出去。

因此，LRU 可能受到缓存污染影响：

1
2
3
4
5
6
7

批量访问冷数据
      ↓
冷数据进入缓存
      ↓
热点数据被淘汰
      ↓
缓存命中率下降

四、W-TinyLFU

1. 设计目标

W-TinyLFU 结合了 LRU 和 LFU 的思想：

• 使用 LRU 识别近期访问的数据；
• 使用访问频率判断数据是否值得长期保留；
• 降低偶发冷数据对热点缓存的污染；
• 在有限内存下提高缓存命中率。

它不是单纯的 LFU，而是一种包含多个缓存区域和准入机制的组合策略。

2. 内存区域划分

W-TinyLFU 将缓存空间划分为两大部分：

1
2
3
4
5

W-TinyLFU
├─ Window LRU
└─ Segment LRU
   ├─ Protected
   └─ Probation

2.1 Window LRU

• 使用 LRU 策略；
• 约占总缓存空间的 1%；
• 接收首次进入缓存的数据；
• 给新数据一个短暂观察机会。

2.2 Segment LRU

Segment LRU 简称 SLRU，进一步分为：

Protected 用于保护较稳定的热点数据，Probation 用于观察可能成为热点的数据。

3. 数据流转过程

3.1 首次访问

首次访问的数据先进入 Window LRU：

1
2
3

新数据
  ↓
Window LRU

3.2 Window LRU 已满

Window LRU 使用 LRU 淘汰候选数据，并将候选数据尝试移入 Probation。

1
2
3

Window LRU 淘汰候选
        ↓
Probation

3.3 Probation 数据再次访问

如果 Probation 中的数据再次被访问，说明它可能是稳定热点，会被提升到 Protected。

1
2
3

Probation
   ↓ 再次访问
Protected

3.4 Protected 已满

Protected 使用 LRU 选择淘汰数据，并将其降级到 Probation。

1
2
3

Protected 淘汰候选
        ↓
Probation

3.5 Probation 已满

当新候选数据要进入已经满的 Probation 时：

1. 从 Probation 中选出一个淘汰候选数据；
2. 比较新候选和旧候选的访问频率；
3. 保留访问频率更高的数据；
4. 淘汰访问频率较低的数据。

1
2
3
4
5
6

新候选数据 X
      ↕ 比较访问频率
旧候选数据 Y
      ↓
高频数据留在缓存
低频数据被淘汰

这种准入比较可以避免一次性访问的冷数据轻易挤走热点数据。

五、Count-Min Sketch

1. 作用

W-TinyLFU 需要记录数据访问频率，但如果为每个 Key 保存完整计数，会占用大量内存。

因此，本节使用 Count-Min Sketch 近似算法，以较小内存估算访问频率。

2. 数据结构

Count-Min Sketch 使用：

1
2
3

M 个哈希函数
        +
M 行 N 列的二维计数数组

每个哈希函数对应数组中的一行。

3. 更新访问频率

某个 Key 被访问时：

1. 使用 M 个哈希函数分别计算哈希值；
2. 每个结果对 N 取模，得到所在行对应的列；
3. 将数组中 M 个位置的计数分别加 1。

1
2
3
4

Key
 ├─ Hash1 → 第1行某列 +1
 ├─ Hash2 → 第2行某列 +1
 └─ HashM → 第M行某列 +1

4. 查询访问频率

查询 Key 的频率时：

1. 使用相同的哈希函数定位 M 个计数位置；
2. 读取 M 个计数；
3. 取其中的最小值作为估算频率。

1

访问频率估算值 = min(多个哈希位置的计数)

取最小值可以尽量减少哈希冲突造成的高估。

5. 低内存计数

书中介绍的实现只使用 4 bit 保存一个位置的计数，因此单个计数最大为 15。

这样可以：

• 显著降低内存占用；
• 保留数据之间的频率差异；
• 不追求绝对精确，只用于比较数据热度。

六、访问频率衰减

1. 为什么需要衰减

如果访问次数只增不减，很多数据最终都会达到计数上限。

这会导致：

• 不同数据的访问频率难以区分；
• 历史热点长期影响当前缓存决策；
• 最近热点难以取代旧热点。

2. 滑动窗口式衰减

W-TinyLFU 维护一个全局计数：

1
2
3

每次更新访问频率
      ↓
全局计数 +1

当全局计数达到阈值时：

1
2

所有访问频率 ÷ 2
全局计数 ÷ 2

这样可以逐渐淡化历史访问记录，让缓存策略更关注近期访问热度。

七、缓存击穿

1. 什么是缓存击穿

缓存击穿通常发生在一条热点数据失效或尚未加载到缓存的瞬间。

假设同时有 100 个请求访问同一个热点 Key，但本地缓存中没有该数据：

1
2
3
4
5

100 个并发请求
      ↓
缓存全部未命中
      ↓
100 次数据库请求

这些请求读取的是同一条数据，却产生大量重复网络调用。

可能导致：

• 浪费网络带宽；
• 增加数据库 QPS；
• 数据库被突发请求击垮；
• 请求延迟升高。

2. 问题本质

缓存击穿的本质是：

同一时刻，对同一个未缓存 Key 的大量并发请求没有被合并。

理想处理方式应该是：

1
2
3
4
5

同一 Key 的大量并发请求
          ↓
只允许一个请求访问数据库
          ↓
其他请求等待并共享结果

八、SingleFlight

1. 核心作用

SingleFlight 可以合并对同一个 Key 的并发请求：

1
2
3
4

请求1 ─┐
请求2 ─┼─ 同一个 Key → 只执行一次数据库查询
请求3 ─┘                     ↓
                         共享查询结果

因此，即使同时有多个请求访问同一条未缓存数据，也只有一个请求真正访问数据库。

2. 基本使用方式

SingleFlight 使用 Key 作为请求合并标识：

1
2
3

data, err, _ := group.Do(key, func() (interface{}, error) {
    return getDataFromDB(key)
})

对于并发执行的相同 Key：

• fn 只会执行一次；
• 其他请求等待执行结果；
• 函数结果被所有等待请求共享。

3. 不同 Key 不会互相阻塞

SingleFlight 只合并相同 Key 的请求：

1
2

Key A 的请求 → 合并为一次调用
Key B 的请求 → 合并为另一次调用

不同数据之间仍然可以并发访问。

九、SingleFlight 实现原理

1. 核心数据结构

SingleFlight Group 维护：

1

Map<Key, Call>

其中：

• Key：正在获取的数据标识；
• Call：保存该 Key 当前正在执行的调用；
• Mutex：保证 Map 并发读写安全；
• WaitGroup：让重复请求等待首次调用完成；
• Value / Error：保存调用结果；
• Dups：记录重复调用数量。

2. 第一个请求

第一个请求访问某个 Key 时：

1. 对 Map 加锁；
2. 发现该 Key 没有正在执行的调用；
3. 创建 Call；
4. 将 WaitGroup 计数设为 1；
5. 把 Key 与 Call 放入 Map；
6. 释放锁；
7. 执行真正的数据查询。

3. 后续并发请求

其他请求访问相同 Key 时：

1. 在 Map 中发现该 Key 已有正在执行的 Call；
2. 不再发起新的数据库查询；
3. 调用 WaitGroup.Wait() 阻塞等待；
4. 首次请求完成后，直接读取共享结果。

4. 查询完成

首次请求执行完成后：

1. 保存查询结果或错误；
2. 调用 WaitGroup.Done()，将计数减为 0；
3. 唤醒所有等待请求；
4. 从 Map 中删除该 Key 的调用信息；
5. 所有请求共享同一份结果。

1
2
3
4

请求1：Add(1) → 查询数据库 → 保存结果 → Done()

请求2：Wait() ───────────────────────→ 被唤醒，读取结果
请求3：Wait() ───────────────────────→ 被唤醒，读取结果

十、缓存淘汰策略对比

十一、核心架构思想

1. 本地缓存通过空间换时间，将网络读取转换为内存读取。
2. 本地缓存可以降低数据库和下游服务的读请求压力。
3. 内存有限，因此缓存必须配合淘汰策略。
4. FIFO 只关注进入时间，容易错误淘汰热点数据。
5. LFU 关注访问频率，但容易被历史热点影响。
6. LRU 关注最近访问时间，但容易受到批量冷数据污染。
7. W-TinyLFU 综合近期访问和访问频率，提高缓存准入质量。
8. Window LRU 给新数据机会，Protected 保护热点，Probation 负责观察和竞争。
9. Count-Min Sketch 用近似计数降低访问频率统计的内存成本。
10. 频率衰减可以淡化历史热点，使策略适应访问模式变化。
11. 缓存击穿来自热点 Key 失效瞬间的大量重复查询。
12. SingleFlight 将相同 Key 的并发请求合并为一次真实调用。
13. SingleFlight 的关键是 Map、互斥锁、WaitGroup 和结果共享。
14. 本地缓存设计需要同时关注命中率、内存占用和缓存失效时的并发保护。