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

常见的缓存模式

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本地缓存组件