缓存设计问题杂谈

常见的缓存问题

缓存雪崩

很多使用场景，查询的缓存数据都是由定时任务取刷新，然后缓存查不到从 DB 查了在更新缓存。如果这些 key 在同一时间失效， 那么失效的时候，大量的请求过来。就会直接打到 DB　上，　这个时候　DB 很可能被打垮，即使马上重启也会被新的流量打垮。

这种同一时间大量缓存的失效，导致请求直接打到　DB 上的情况， 就是缓存雪崩。

针对于这种情况，在批量写 Redis 数据的时候， 从缓存的过期时间入口，将原来的固定过期时间，调整为过期时间=基础时间+随机时间，让缓存慢慢过期，避免瞬间全部过期，对DB产生过大压力。

缓存穿透

缓存穿透指的是缓存缓存和数据库中都没有的数据，而用户不断发起请求，让请求直接落再DB上，增加数据库压力，可能导致数据库被击垮。这种请求很可能是攻击者恶意发起的。

针对这种情况首先要做好数据校验，不合法的数据尽量拦截掉.

• 其次如果缓存差不到，数据库也查不到的数据也缓存起来。将 value 存个null， 过期时间短一点(如30s，如果设置太长肯恶搞导致正常的情况数据没法及时更新)。
• 另外还可以使用 Redis 提供的布隆过滤器，可以高效的判断出某个key是否在数据库当中，如果通过布隆过滤器判断出不存在，直接返回，存在了在去DB取数据刷新缓存。

缓存击穿

在平常高并发的系统中，大量的请求同时查询一个 key 时，此时这个key正好失效了，就会导致大量的请求都打到数据库上面去。这种现象我们称为缓存击穿。

针对这种情况可以:

• 异步设置热点key过期时间， 提前续上
• 缓存失效的时候， 加上一个全局的锁再去load db， 避免所有线程都打到db上

hot key 问题

对于某些 key 有非常大的访问量， 容易把 hot key 所在的那台机器打垮。

解决方案:

• 冗余 hot key: 一个缓存节点过载。由于只有一个key，我们可以在key的后面拼上有序编号，比如key#01、key#02。。。key#10多个副本，这些加工后的key位于多个缓存节点上。 每次请求时，客户端随机访问一个即可

big key 问题

当访问缓存时，如果key对应的value过大，读写、加载很容易超时，容易引发网络拥堵。另外缓存的字段较多时，每个字段的变更都会引发缓存数据的变更，频繁的读写，导致慢查询。如果大key过期被缓存淘汰失效，预热数据要花费较多的时间，也会导致慢查询。

解决方案:

• 方案一：设置一个阈值，当value的长度超过阈值时，对内容启动压缩，降低kv的大小
• 方案二：颗粒划分，将大key拆分为多个小key，独立维护，成本会降低不少
• 方案三：大key要设置合理的过期时间，尽量不淘汰那些大key

缓存一致性问题

在另一篇博客有详细的介绍: MySQL与缓存一致性问题

缓存淘汰算法

主要的缓存数据淘汰算法有三种：

• FIFO (Fist in first out): 如果一个数据最先进入缓存中，则应该最早淘汰掉。
• LRU (Least recently used): 如果数据最近被访问过，那么将来被访问的几率也更高。
• LFU (Least frequently used) :如果一个数据在最近一段时间内使用次数很少，使用频率最低，那么在将来一段时间内被使用的可能性也很小。

FIFO

先入先出算法的核心思想是: 最先进来的数据，被认为在未来被访问的概率也是最低的，所以优先淘汰最早进来的数据。

优点: 简单公平， 易于实现

缺点: 缓存命中率低， 常用数据容易被淘汰掉

LRU

最近最久未使用： 如果一个数据最近很少被访问到，那么被认为在未来被访问的概率也是最低的，当规定空间用尽且需要放入新数据的时候，会优先淘汰最久未被访问的数据

优点:

• 有效的对访问比较频繁的数据进行保护，也就是针对热点数据的命中率提高有明显的效果。
• 局部突发流量场景，对突发性的稀疏流量（sparse bursts）表现很好。

缺点:

• 周期性的局部热点数据场景，有大概率可能造成缓存污染。最近访问的数据，并不一定是周期性数据，比如把全量的数据做一次迭代，那么LRU 会产生较大的缓存污染，因为周期性的局部热点数据，可能会被淘汰

最简单的 LRU 算法， 对偶发性、周期性的数据没有良好的抵抗力，很容易就造成缓存的污染(偶发数据占据内存淘汰热点数据)，影响命中率。 因此衍生出了 LRU-K、Two Queues等变种，目的就是当判别数据为偶发或周期的冷数据时，不会存入空间内，从而降低热数据的淘汰率。

LRU-K

如上图，LRU-K有两个队列，新来的元素先进入到历史访问队列中，该队列用于记录元素的访问次数，采用的淘汰策略是LRU或者FIFO，当历史队列中的元素访问次数达到K的时候，才会进入缓存队列。 K 是指数据被访问 K 次，传统LRU与此对比则可以认为传统 LRU 是 LRU-1。

另有一种解法是 Two Queues， 也是两个队列 不同之处在于，Two Queues 的队列一个是缓存队列，一个是FIFO队列， 当新元素进来的时候，首先进入 FIFO 队列，当该队列中的元素被访问的时候，会进入 LRU 队列(类似用 FIFO 队列做了一个缓冲？)

LFU(局部周期性流量场景)

最近最少使用： 如果一个数据在最近一段时间内使用次数很少，使用频率最低，那么在将来一段时间内被使用的可能性也很小。

与LRU的区别在于LRU是以时间先后来衡量，LFU是以时间段内的使用次数衡量

如上图， LFU 增加了元素的访问频次记录， 访问频次高的元素在队列中的位置就优先， 插入新元素的时候淘汰时间窗口内访问频次最低的元素

优点：

• LFU适用于 局部周期性流量场景，在这个场景下，比LRU有更好的缓存命中率。在局部周期性流量场景下， LFU是以次数为基准，所以更加准确，自然能有效的保证和提高命中率

缺点：

1. 因为LFU需要记录数据的访问频率，因此需要额外的空间；
2. 它需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销；
3. 在存在局部突发流量场景下，有大概率可能造成缓存污染， 算法命中率会急剧下降，这也是他最大弊端。 所以，LFU 对突发性的稀疏流量（sparse bursts）是无效的。

LFU 应对突发稀疏流量为何无效

LFU 按照访问次数或者访问频率取胜，这个次数有一个累计的长周期， 导致前期经常访问的数据，访问次数很大，或者说权重很高

新来的缓存数据， 哪怕他是突发热点，但是，新数据的访问次数累计的时间太短， 在旧数据面前， 频次仍然很低

所以，LFU 算法中，老的记录已经占用了缓存，过去的一些大量被访问的记录，在将来不一定会继续是热点数据，但是就一直把“坑”占着了，而那些偶然的突破热点数据，不太可能会被保留下来，而是被淘汰。

所以，在存在突发性的稀疏流量下，LFU中的偶然的、稀疏的突发流量在访问频率上，不占优势，很容易被淘汰，造成缓存污染和未来缓存命中率下降。

TinyLFU

上面说到了 LFU 的三个缺点: 额外空间、额外开销、无法应对突发稀疏流量

tinyLFU 就是解决这个问题

减少访问频率保存带来的额外空间开销以及减少访问记录更新带来的时间开销， 使用的是 Count–Min Sketch 算法： Count-Min Sketch算法，可以看作是布隆过滤器的同源的算法， 假如我们用一个 hashmap 来存储每个元素的访问次数，那这个量级是比较大的，并且hash冲突的时候需要做一定处理，否则数据会产生很大的误差， 如果用hashmap的方式，相同的下标变成链表，这种方式会占用很大的内存，而且速度也不是很快。 其实一个hash函数会冲突是比较低的，布隆过滤器 的优化之一，设置多个hash函数，多个hash函数，个个都冲突的概率就微乎其微了。 Count-Min Sketch算法将一个hash操作，扩增为多个hash，这样原来hash冲突的概率就降低了几个等级，且当多个hash取得数据的时候，取最低值，也就是Count Min的含义所在。