关于后端:关于缓存的一些总结

常见的缓存模式

Cache aside patten

过程：

• 读操作：先读缓存，若缓存存在，间接返回。缓存不存在，则从 DB 加载，而后写到缓存
• 写操作：更新 DB, 而后删除缓存

为什么不先更新缓存，在更新 DB。如果有两个并发写操作，将导致缓存和 DB 不统一。也即 线程 1 先更新缓存，线程 2 后更新缓存，然而线程 2 更新 DB 提前返回，线程 1 更新 DB 后返回导致缓存和 DB 不统一。

先更新 DB 在删除缓存也有并发问题，不过是升高了缓存不统一的概率。线程 1 读取缓存，缓存不存在，而后从 DB 读取数据，此时线程 2 更新 DB 并更新了缓存，这是线程 1 又把过期的数据加载到缓存了。然而实际上 DB 的写操作个别比读操作慢，所以这种产生的概率较低。

无奈解决的问题：

无奈解决更新 DB 后删除缓存失败的场景，要保障缓存 DB 的一致性问题只能通过 2PC 或 Paxos 一致性协定来保障. 然而对于这个 2PC 太慢，Paxos 太简单，所以个别通过设置缓存的有效期，让其最终统一。

反对 XA 事务的缓存有 Ehcahe

什么又是提早双删（罕用，举荐应用）？

在更新操作的时候先删除缓存，而后再更新 DB, 在延时肯定的工夫从新删除缓存。

先删除缓存能够保障新的过程不会读到旧的数据。延时删除的作用是，能够保障在更新 DB 过程中（更新的线程记为线程 1）可能有并发读操作（记为线程 2）从 DB 读到了旧的数据，若没有延时间接删除，那么线程 1 删除了缓存，此时线程 2 读到的旧数据可能从新载入缓存，导致不统一。

Read/write through patten

比照与 cache aside patten, 当缓存中不存在时，须要调用方本人去 DB 查问，而后加载到缓存，也即调用方须要负责缓存和 DB 数据。

对于 read/write through patten 则认为 cache 和 DB 是对立的存储。存储外部本人负责 DB 和缓存的统一。

read through

过程：

​ 若缓存存在，间接返回，缓存不存在，则由缓存本人从 DB 中加载数据，而后返回给调用方

write through

过程：

​ 若缓存存在，则更新缓存，又缓存将数据更新到 DB。若缓存不存在，则间接更新 DB, 而后返回。

​

Write behind caching patten

write behind 又叫 write back (写回)。相似于操作系统的 page cache.

过程：

读操作：若数据在缓存中，间接返回，不在缓存则从 DB 加载后写入缓存，并将数据标识 非脏页。

写操作：间接写入缓存，并将该缓存标记为 脏数据，而后返回。

当缓存用完了，LRU 算法淘汰旧的缓存，如果发现数据是脏数据，则须要写回 DB, 否则间接淘汰。当零碎优雅敞开，须要将脏数据写回 DB. 若宕机，则有数据失落的危险。

缓存策略

• LRU(Lease Rencently Used)：最近起码应用, 淘汰最久未应用的数据 ( 基于拜访工夫)

  解决方案：链表（解决新老关系）+ 哈希（解决查问）

• LFU(Lease Frequently Used)：应用频率起码, 淘汰拜访频率起码的数据（基于拜访次数）

  解决方案：堆排序（解决频率排序）+ 哈希（解决查问）

别离实用什么场景

• LRU : 实用于最近被拜访的数据在未来很有可能被再次拜访的假如。针对突发流量，能够很好缓存数据对外服务，也不须要统计频率数据（LFU 须要），毛病它可能会将之前的热点数据（高频的数据）淘汰，导致缓存命中率降落，也即缓存净化。
• LFU: 只有数据拜访模式的概率分布随工夫放弃不变，其命中率就会十分高。哪怕有突发的大量冷门数据拜访，也不会将原高频数据淘汰，毛病就是新的热点数据无奈很好的缓存，老的热点数据无奈淘汰

什么是缓存雪崩 / 穿透 / 击穿

• 缓存雪崩: 大量数据无奈再缓存中找到，导致申请发送到 DB,DB 压力激增

  • 缓存数据同时过期（设置了雷同的过期工夫。批改缓存的过期工夫，减少 1~3min 随机值；或者服务降级，针对外围数据，持续查 DB, 非核心数据返回空值或预定义数据）
  • 缓存集群故障（redis 故障。设置服务熔断或前端限流，保障数据库失常运行；这就须要利用监听 redis 负载状况，如 CPU，QPS，内存使用率等；做好 redis 集群的高可用，如应用 sentinel 机制）

• 缓存击穿: 某些频繁拜访的热点数据，无奈再缓存中解决，从而发送到 DB, 导致 DB 压力变大

  • 热点数据不要设置过期工夫

• 缓存穿透 ：数据既不在缓存，也不在 DB。 缓存空值；或应用布隆过滤器；前端参数合法性校验

  • 业务误操作
  • 歹意攻打

Mysql buffer pool 的缓存设计

若 MySQL 采纳原始原始的 LRU 算法，那么若一条 SQL 扫描了一张大表，将导致，缓存中的热点数据全副被淘汰掉，是缓存命中率降落，咱们来看看 Innodb 是如何改良 LRU 算法。

在 Innodb 中将 LRU 链表分为 yong 区 (5/8) 和 old 区（3/8）, 其中用去凑近链表头部，如上图所示。尾部是 old 区。

• 若拜访 yong 区数据页，则将其挪动到链表头部
• 若拜访不存在的数据也，则淘汰 pm(链表尾部)数据页，并将新的数据放入 LRU_old 处

• 若再次拜访 old 区数据时，

  • 若数据在链表中超过 1s, 则移到链表头部
  • 如小于 1s, 则放弃不变

这样就能够保障在大表扫描时，因为数据在 old 区域，没有机会进入 yong 区，不会净化缓存

Redis 淘汰策略

redis 能够设置最大的内存容量 maxmemory, 当超过最大内存时，通过maxmemory-policy 淘汰策略来淘汰数据，腾出新的空间给新的数据。其中有 allkeys-lru 和volatile-lru应用 LRU 算法，有 allkeys-lfu 和volatile-lfu应用 LFU 算法, 上面介绍下在 redis 中如何应用这两种策略

• LRU

咱们晓得 redis 中每个键值对的值都是 redis Object, 它下面有个 lru 变量 24bit,LRU 策略会在下面记录上次的拜访工夫戳

• LFU

当咱们须要记录频率，不能简略的通过拜访次数来统计，须要用工夫 + 次数的形式来统计频率。redisObject 下面有个 lru 变量 24bit，在 LRU 策略中是记录上次应用的工夫戳。因为 LFU 是 redis 4.0 引入的，故其复用了这个 lru 变量，其中 16bit(准确到分钟) 记录上次访问工夫戳，后 8bit（初始值 5, 如果这里取值 0, 很可能马上就被淘汰掉，也就是让它存活一段时间）记录人拜访次数。

1. 依据上次的拜访时长，衰减拜访次数.

   如本来 0 - 5 分钟拜访 10 次，那么 freq= 2 次 / 分钟，后 5 -10 分钟没有拜访，在 10-15 分钟拜访，须要将原来的 freq 衰减为 1 次 / 分钟。在默认状况下（lfu_decay_time 管制），拜访次数的衰减大小就是等于上一次拜访间隔以后的分钟数（若拜访次数曾经为 0，不衰减）

2. 依据以后的拜访更新拜访次数

   因为拜访次数最大 255，若曾经是最大值，则不更新。

   其实 redis 不是每次拜访值就间接将拜访次数加一，这样 255 下限就太小了。所以它的策略是，拜访肯定的次数，才将拜访次数加一。相当于将理论记录的拜访次数范畴变大了。

   计算时会计算一个阈值 p，以及一个取值为 0 到 1 之间的随机概率值 r。如果概率 r 小于阈值 p，那么 才会将拜访次数加 1。否则的话，拜访次数不变。而阈值 p 的值大小，其实是由两个因素决定的。一个是以后拜访次数和宏定义 LFU_INIT_VAL 的差值 baseval，另一个是 redis.conf 文件中定义的配置项 lfu-log-factor。

   r=random(0~1)

   p =1/(baseval * lfu-log-factor+1)

   若 r <p, 拜访次数加一，否则拜访次数不变

   baseval 反映了拜访多少次，当拜访很屡次后，在减少他的至难度会变大；

   Lfu-log-factor 反映了拜访次数的减少难度，越大难度越高，也即 拜访次数理论示意的拜访频率越高

能够看到 lfu-log-factor 在取值为 10 时，拜访频率 255 理论能够示意 1M 的拜访频率。

3. 更新 lru 变量

• LRU 和 LFU 理论的淘汰做法

  redis 淘汰数据并不是针对全副的数据进行淘汰，不然针对 LRU 须要很大空间，通过链表保护拜访工夫前后关系，而针对 LFU 须要很多的空间来保护拜访频率的排序。所以 redis 采纳的是随机采纳的形式，随机一部分数据，数量由 maxmemory-samples 配置，放入EvictionPoolLRU, 而后计算 idle , 将 idle 越大的优先淘汰。针对 LRU , 上次访问工夫越早，idle 越大，越容易淘汰；针对 LFU, 拜访频率越低，idle 越大，越容易淘汰。淘汰最大 idle 的数据后，而后循环将采纳数据放入EvictionPoolLRU, 一直淘汰 pool 中的数据，晓得满足咱们的最大内存限度。

  if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {idle = estimateObjectIdleTime(o);
  } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {idle = 255-LFUDecrAndReturn(o);
  }

Caffine cache (W-tinyLFU)

Caffine cache 是一个高性能的 Java 本地缓存组件，基于 guava cache, 并优化算法为 Window-TinyLFU,W-TinyLFU 中应用 Count-Min Sketch 记录咱们的拜访频率，它是一品种 布隆过滤器的思维，能够升高频率信息的内存损耗

存储数据时，对 key 进行屡次 hash 函数运算后，二维数组不同地位存储频率（Caffeine 理论实现的时候是用一维 long 型数组，每个 long 型数字切分成 16 份，每份 4bit，默认 15 次为最高拜访频率，每个 key 理论 hash 了四次，落在不同 long 型数字的 16 份中某个地位）。读取某个 key 的拜访次数时，会比拟所有地位上的频率值，取最小值返回。对于所有 key 的拜访频率之和有个最大值，当达到最大值时，会进行 reset 即对各个缓存 key 的频率除以 2。

如下图缓存拜访频率存储次要分为两大部分，即 LRU 和 Segmented LRU。新拜访的数据会进入第一个 LRU，在 Caffeine 里叫 WindowDeque。当 WindowDeque 满时，会进入 Segmented LRU 中的 ProbationDeque，在后续被拜访到时，它会被晋升到 ProtectedDeque。当 ProtectedDeque 满时，会有数据降级到 ProbationDeque。数据须要淘汰的时候，对 ProbationDeque 中的数据进行淘汰。具体淘汰机制：取 ProbationDeque 中的队首和队尾进行 PK，队首数据是最先进入队列的，称为受害者，队尾的数据称为攻击者，比拟两者 频率大小，大胜小汰。

所以 caffine cache 其实是联合了 LRU 和 LFU 算法进行内存淘汰

参考文献

1. 缓存的更新套路
2. 极客工夫 MySQL 实战 45 讲
3. 极客工夫 Redis 核心技术与实战
4. 高性能缓存 Caffeine 原理及实战
5. Caffeine Cache- 高性能 Java 本地缓存组件