缓存系统

在计算机世界里，Cache无处不在，Cache翻译成中文有两个词汇，一个是在台湾那边翻译为快取，另一个是大陆这边的是缓存。台湾这边的翻译不仅音似更是神似，一语道出了这个玩意的核心功能：快速获取。

缓存的价值

不管缓存系统如何设计，其本质永远是「用空间换时间」，也就是提升数据获取的效率。同时，也可以作为一种兜底降级方案，当源挂掉后可以先用缓存内的数据。

现实中的缓存系统

在现实中，都有哪些很常见的缓存系统呢？

• 计算机CPU缓存：CPU 多级缓存机制，越热的数据存放在获取越快的地方
• dns 系统缓存：使用缓存加速域名解析为ip，对于热点域名不必每次重复解析
• 浏览器缓存：本地缓存策略来加速整个页面展现的速度
• CDN：图片、视频CDN系统本质也是个缓存系统
• Web服务器缓存：程序员基于缓存策略可以开发出高并发的App接口

应用使用缓存的模式

在这里有三个实体：应用系统、缓存系统、数据源。关于他们的交互，有几种比较常见的使用模式。

旁路缓存模式 Cache Aside Pattern

读操作命中缓存后直接返回，否则回源加载数据返回，拿到数据后写入缓存。并且为每份数据设置一定的TTL，超过一定时间后缓存失效，有写操作也可以直接写数据库，然后删除缓存。

这是最常用的缓存模式：

• 优点是实现简单，数据以源为准，缓存和数据库保证最终一致性。
• 缺点是数据一致性不够高，如果是纯粹用 TTL 机制，延迟时间依赖于 TTL 值。同时应用需要同时感知数据源、缓存两个数据存储的存在

读写穿透 Read/Write Thought

缓存层和数据库做好数据同步，应用只需和缓存层做交互，大厂一般都有这类的自研的数据库，集存储和缓存于一身。

优点是应用层友好，只需感知缓存层的存在。

缺点是把设计复杂度腾挪到缓存层，缓存层得保证数据一致性的操作。这大程度也注定了这类缓存层一般无法做得很复杂，多为 KV 类型缓存系统。

回写 Write Back

这种模式应用服务同时也需要感知缓存、源。同时对于读写请求也有不同的机制：

1. 读：读操作如果命中缓存直接返回，否则回源取，写到缓存中
2. 写：写操作只写缓存
3. 数据淘汰：在淘汰数据前将数据写后端回数据库

这种方案优点是写速度快，只写缓存，缺点是系统发生异常容易引发数据不一致的问题。这种策略经常用在操作系统上 Page Cache 中，或者大量写操作的数据库引擎中。

缓存可能存在的问题

使用缓存绕不开几个问题：缓存穿透、缓存击穿、缓存雪崩、数据一致性。

缓存击穿

某个Key 突然失效，这个时候大量的请求打向这个KEY，大量回源请求，瞬间的流量击垮源站，如图所示：

解决办法：

1. 缓存层KEY设置 TTL = 0，KEY 永远不过期防止被击穿
2. 设置互斥锁（singleflight）单进程内只有一个线程回源请求，其他线程等待结果。甚至也可以做分布式的singleflight，全局只有一个进程回源其他进程等待结果。*这个方案的缺陷是会导致更新变慢，并且如果没有线程的库实现代码实现相对复杂。*

缓存穿透

大量请求（特别是恶意请求）请求不存在的KEY，因为KEY不存在直接回源。

解决办法：

非根治：

• 缓存空值，如果源站查不到数据将一个Null值缓存下来
• 布隆过滤器，低成本判断数据是否存在于数据库中，存在才回源

根治：

• 识别恶意请求，从风控角度解决
• 如果非恶意请求，请求量级不大可以不考虑

缓存雪崩

同一时刻大量KEY过期，导致大量的请求回源，最终压垮源站。

解决办法：

1. 打散KEY过期 TTL，不要让KEY都集中在相同时间过期
2. 缓存系统需要做好高可用，不要因为单点故障丢失大量缓存数据（比如 redis 具备高可用特性，单点故障不影响）

数据一致性

并发读写、异构数据同步导致缓存和数据库通常不能保证强一致性，所以使用缓存策略需要结合业务特性来选择。通常情况下，合适的策略是可以保证最终一致性，常用的策略是延迟双删、使用延迟队列这两个方式来保证最终一致性。

淘汰策略/换页策略

通常缓存的大小相比源站小得多的，就好像酱油水瓶不可能装下满池子酱油，所以缓存通常需要有一个淘汰策略，当缓存装不下时自动触发淘汰机制。

根本目的：保证缓存系统的可用性

实现利益最大化：保持热点请求数据存活，淘汰冷数据

常见的缓存淘汰算法：

1. RR - 随机删除，简单粗暴，只保证可用性不考虑缓存利益
2. LRU - 删除最早访问的项目，最长时间没被访问可能是最冷数据
3. LFU - 淘汰掉访问频率最低的项目
4. W-TinyLFU - 利用时间窗口解决LFU痛点，现代的换页策略

下面简单说下几种淘汰算法的实现。

LRU - 最早使用

通常我们用双向链表 + 哈希表来实现 LRU，哈希表是用于快速索引指定数据，判断数据是否存在。双向链表是为了快速删除指定元素。

如图所示，链表中第一个元素表示最早被访问的，最后一个元素是最近被访问的。

通过哈希表判断该元素是否在双链表中，不存在如果双链表长度未溢出，直接插入，否则将第一个元素从缓存中删除并将该元素插入到最后一个元素，如果存在则将元素挪到最后面。

为什么用双向链表，而不用数组、单链表呢？

因为需要频繁地挪到元素，如果是数组涉及到大量的数据移动，成本高，链表修改元素的时间复杂度是 O(1) ，同时由于借助Hash我们能快速定位到元素，但是要挪动元素的话要同时获取到其前后元素，这样也就只有双向链表这个数据结构支持。

LRU 是个简单的性价比很高的算法，但是难以应对突发流量，比如某段时间要把所有的数据回扫一遍就会触发大量不必要的淘汰。

LFU - 最不经常使用

相比 LRU，LFU 的实现就复杂很多了，LRU 是淘汰最早不被使用的元素，而LFU是淘汰一段时间内最不经常使用的元素，因为有些元素虽然这个窗口内不被访问，但是相对来说是比较热门，*所以 LFU 认为淘汰掉请求计数最小的元素才是合理的。*

实现思路大概是这样的：

• 首先有个hash用于快速索引元素，这个和LRU一样
• 然后有个比较复杂的结构用于访问次数计数，最外层是 hash，key 是计数比如，1，2，3 这样子，value 是一个双向链表

这个结构如图所示：

1. 访问：直接通过hash索引到元素，然后在 LFU Cache 中删除该元素，插入到下个 KEY 的尾巴，例如对于图上的 Node2， 删除自己后会加入到 2 这个 KEY 的链表中
2. 插入：判断如果不存在该元素，且缓存没满直接插入到 KEY=1 中，同时记录Hash 索引； 如果缓存满了，删除 KEY=1 中的头元素（最不经常使用且时间最长）然后插入该元素到 KEY = 1

LFU 相比 LRU按照时间来存储可以应对大量数据被回扫导致的频繁换页问题，但是也存在两个比较大的问题；

• 应对稀疏性的突发流量无力，突发量时由于计数还不够，因此不会留在缓存中
• 需要计数，占用大量的存储空间

W-TinyLFU - 改良 LFU

为了解决 LFU 上述的两个缺点于是有了改进版本的算法，简而言之，W-TinyLFU 通过计算时间窗口内的频率来解决一个条目只是因为过去常被使用而长时间留在缓存中，除此之外也有各种优化。

缓存并发问题

缓存内的数据可能被并发读写，我们知道并发读写有可能会导致数据产生奇奇怪怪的问题，所以通常的解法是：

• 加锁，但是性能影响比较大，可以使用读写锁或者分段锁优化锁竞争
• 单线程，比如redis核心处理逻辑使用单线程处理，整体就没有并发问题了

分布式缓存

大型的缓存系统为了提升性能，通常需要部署多个进程服务，这就组件为一套分布式缓存系统了。分布式缓存系统主要可能存在缓存利用率的问题，所以通常对同个 key 的请求打到同个缓存服务上来提升缓存命中率。

最简单的方式是：hash(key) % N

但是这又引入了另外一个致命问题，有一台服务器宕机了，由于总的数量变了所有机器的缓存数据会被再分配（因为 N 变了）。所以这里需要引入*一致性哈希算法*，这样就可以保证节点新增或者宕机只影响到这个节点上的缓存数据，一致性哈希算法引入了虚拟桶可以保证数据是被均匀分布的，同时如果单个节点宕机了，是按照虚拟桶与真实桶的相对位置产生迁移因此影响较小。

总结

缓存的设计与使用在工作中比比皆是，可以说是服务端工程师必备的技能之一。其中的哲学也很多，我们可以在工作中多学习一些优秀、经典的设计案例，比如 Google 的 Loading Cache 框架，Redis 等。