技术分享 缓存那些事儿

2020-02-27 172浏览

  • 1.技术 缓存的那些事儿 分享 by 陈文
  • 2.内容分布 NO.5 参考和答疑 NO.1 缓存定义和三要 素 NO.2 Caffeine NO.4 缓存设计 NO.3 一致性 hash
  • 3.1. 缓存定义和三要 素
  • 4.1 定义 缓存的定义 缓存就是数据交换的缓冲区（称作 Cache ），当硬件要读取数据时， 会首先从缓存中查找需要的数据，如果找到了则直接执行，找不到的话 则从内存中找。 两种介质之间存在传输速率差，速率较高的一方即为速率较低一方的 缓存。
  • 5.1 定义 速率差
  • 6.1 定义 缓存三要素 » 命中率（ hit ratio ）：衡量缓存机制的好坏 » 缓存更新策略：缓存管理机制，维护 key-value 的生命周期。 » 缓存最大数据量：在缓存中能处理的元素最大个数或能使用的最大存储空间
  • 7.1 简介 缓存三要素 - 策略 FIFO ：先进先出 FIFO With Second Chance ：基于 FIFO ，不同的是它不立刻踢出队列前端，而是检查被踢出的 对象之前是否有时用过的标记。没有，直接踢。有，清除标志，重新加入缓存。 LFU ：最少使用的元素会被清理掉 标准 LRU ：适用范围最广的算法。最近最少使用的元素被清理。 近似 LRU ：牺牲精度获得更好性能。如 Redis ，不严格按时间删除过期数据 变异 LRU ： LRU2 和 2Q 和 ARC 。 LRU2 需要跟踪对象两次， 2Q 算法则有两级 LRU 缓存， L1 存 放最近只使用过一次的对象（新数据）， L2 存放最近被使用两次的对象（常用对象） MRU ：和 LRU 相反，移除最近最多被使用的对象 其它： LIRS ， Sliding time-based expiration 等
  • 8.1 简介 缓存三要素 - 策略 -FIFO 先进先出的数据缓存器， 最简单
  • 9.1 简介 缓存三要素 - 策略 -LFU 使用一个计数器来记录条 目被访问的频率。通过使 用 LFU 缓存算法，最低访 问数的条目首先被移除
  • 10.1 简介 缓存三要素 - 策略 -LRU LRU （ Least recently used ， 最近最少使用）算 法根据数据的历史 访问记录来进行淘 汰数据，其核心思 想是“如果数据最 近被访问过，那么 将来被访问的几率 也更高
  • 11.1 简介 缓存三要素 - 策略 -LIRS JBoss 的 InfiniSpan 使用了 LIRS 算法。 LIRS 使用 IRR （ Inter-Reference Recency ）来表征 每个缓存块的历史信息，单从名字不容易看出 IRR 的具体含义，参照原论文的定义是这样的： 一 个缓存块的 IRR 是指在相继地访问这个块之间访问其它非重复缓存块的个数，听起来还是有点拗口 ，我们用图来说明，如图所示： 缓存块 1 的 IRR 就是 3 ，因为在相继地 访问 1 之间访问了 2,3,4 ，尽管 3 被访 问两次，但只算一次。特别的，我们把 一个块从最近一次访问到当前时间之间 访问其它块的非重复个数叫做这个块的 recency 。比如上图缓存块 1 的 recency 是 2
  • 12.1 简介 缓存三要素 - 策略 -LIRS LIRS 算法不同于 LRU 的地方就是在选择要被替换的块时不仅仅考虑 recency ，也考虑 IRR ，通过考量 一个块的 IRR 我们就能对这个块的访问历史有更准确的把握。具有较小的 IRR 的块 LIRS 称之为 LIR 块， 高 IRR 块称之为 HIR 块。 所有缓存块被分成 LIR 和 HIR 两个集合， LIR 块集合的大小需要控制小于 Cache 的大小以保证 LIR 块可 以常驻 Cache ，访问 LIR 块永远不会失效， Cache 的一小部分空间留给 HIR 块，缓存中 HIR 块会随时 被淘汰即使它最近被访问过。 HIR 块分为两种形式：驻 Cache 的 HIR 块（ resident-HIR ）和非驻 Cac he 的 HIR 块（ nonresident-HIR ）。 LIRS 算法的关键在于如何动态地维护 LIR 和 HIR 集合。当一个 HIR 块再次被访问，它会得到一个新的 IRR ，如果这个 IRR 小于 LIR 集合最大的 recency ，那么我们需 要让此 HIR 块和具有最大 recency 的 LIR 块互换角色以保持 LIR 和 HIR 集合的大小恒定。
  • 13. 2. 高性能 Java 缓存库 — Caffeine
  • 14.2 Caffeine 高性能 Java 缓存库 — Caffeine Caffeine 是使用 Java8 对 Guava 缓存的重写版本，在 Spring Boot 2.0 取代 Guava ，基于 Count-Min Sketch 算法实现，支持多种缓存过期策略。 spring5 已经放弃 guava ，拥抱 caffeine 。https://github.com/ben-manes/caffeine自动加载实体到缓存，可选异步 异步刷新 通知被驱逐（其他方式删除）的条目 传播到外部资源的写入 统计缓存访问数据
  • 15.2 Caffeine 现代缓存算法 现代缓存扩展了对历史数据的使用，结合就近程度（ recency ）和访问频次（ frequency ）来更好的预测数据。 其中一种保留历史信息的方式是使用 popularity sketch （一种压缩、概率性的数据结构）来从一大堆访问事件中 定位频繁的访问者。可以参考 CountMin Sketch算法，它由计数矩阵和多个哈希方法实现。发生一次读取时，矩阵 中每行对应的计数器增加计数，估算频率时，取数据对应是所有行中计数的最小值。这个方法让我们从空间、效率、 以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。
  • 16.2 Caffeine 现代缓存算法 Window TinyLFU（ W-TinyLFU ）算法将 sketch 作为过滤器，当新来的数据比要驱逐的数据高频时，这个数据才会 被缓存接纳。这个许可窗口给予每个数据项积累热度的机会，而不是立即过滤掉。这避免了持续的未命中，特别是在 突然流量暴涨的的场景中，一些短暂的重复流量就不会被长期保留。为了刷新历史数据，一个时间衰减进程被周期性 或增量的执行，给所有计数器减半。
  • 17.2 Caffeine 现代缓存算法 -Count-Min Sketch 如果需要记录一个值，那我们需要通过多种 Hash 算法对其进行处理 hash ，然后在对应的 hash 算 法的记录中 +1 ，为什么需要多种 hash 算法呢？ 由于这是一个压缩算法必定会出现冲突，比如我们 建立一个 Long 的数组，通过计算出每个数据的 hash 的位置。比如张三和李四，他们两有可能 hash 值都是相同，比如都是 1 那 Long[1] 这个位 置就会增加相应的频率，张三访问 1 万次，李四访 问 1 次那 Long[1] 这个位置就是 1 万零 1 ，如果取 李四的访问评率的时候就会取出是 1 万零 1 ，但是 李四命名只访问了 1 次啊，为了解决这个问题，所 以用了多个 hash 算法可以理解为 long[][] 二维数 组的一个概念
  • 18.2 Caffeine 现代缓存算法 -Count-Min Sketch
  • 19.2 Caffeine 现代缓存算法 -Count-Min Sketch 在 Count-Min Sketch 中，我这里直接说 caffeine 中的实现吧 ( 在 FrequencySketch 这个类 中 ), 如果你的缓存大小是 100 ，他会生成一个 long 数组大小是和 100 最接近的 2 的幂的数，也 就是 128 。而这个数组将会记录我们的访问频率。在 caffeine 中规定频率最大为 15 ， 15 的二 进制位 1111 ，总共是 4 位，而 Long 型是 64 位。所以每个 Long 型可以放 16 种算法，但是 caffeine 并没有这么做，只用了四种 hash 算法，每个 Long 型被分为四段，每段里面保存的是四 个算法的频率。这样做的好处是可以进一步减少 Hash 冲突，原先 128 大小的 hash ，就变成了 128X4 。
  • 20.2 Caffeine 现代缓存算法 -Count-Min Sketch 4 个段分为 A,B,C,D ，在后面我也会这么叫它们。而每个段里面的四个算法我叫他 s1,s2,s3,s4 。 下面举个例子如果要添加一个访问 50 的数字频率应该怎么做？我们这里用 size=100 来举例。 1. 首先确定 50 这个 hash 是在哪个段里面，通过 hash & 3(3 的二进制是 11) 必定能获得小于 4 的数字，假设 hash & 3=0 ，那就在 A 段。 2. 对 50 的 hash 再用其他 hash 算法再做一次 hash ，得到 long 数组的位置，也就是在长度 128 数组中的位置。假设用 s1 算法得到 1 ， s2 算法得到 3 ， s3 算法得到 4 ， s4 算法得到 0 。 3. 因为 S1 算法得到的是 1 ，所以在 long[1] 的 A 段里面的 s1 位置进行 +1, 简称 1As1 加 1 ，然 后在 3As2 加 1 ，在 4As3 加 1 ，在 0As4 加 1 。
  • 21.2 Caffeine 现代缓存算法 -Count-Min Sketch
  • 22.2 Caffeine 使用com.github.ben-manes.caffeinecaffeine2.6.2
  • 23.2 Caffeine 手动加载
  • 24.2 Caffeine 基于大小驱逐 Caffeine 还支持基于时间和引用的驱逐策略
  • 25.2 Caffeine Removal 监听器和统计
  • 26.2 Caffeine 性能 -Read (75%) / Write (25%)
  • 27.2 Caffeine 性能 -Compute 纠正一个误区： Java 内置库不一定效率最高；代 码量多不一定效率低。比如 Java 内置的 Base64 性能渣到想哭。
  • 28. 3. 分布式缓存 — 一致性哈希
  • 29.3 分布式缓存 传统 HASH 的问题 m = hash(o) mod n 公式 A 其中， o 为对象的名称， n 为机器的数量， m 为机器的编号， hash 为一 hash 函数。 扩容，机器数量 +1 时， m = hash(o) mod (n + 1) 公式 B 宕机，机器数量 -1 时， m = hash(o) mod (n - 1) 公式 C 扩容为例，假设机器由 3 台变成 4 台，对象 o1 由公式 A 计算得到的 m 值为 2 ，由公式 B 计算得到的 m 却可能为 0 ， 1 ， 2 ， 3 （一个 3t + 2 的整数对 4 取模，其值可能为 0 ， 1 ， 2 ， 3 ）， 大约有 75% （ 3/4) 的可能性出现缓存访问不命中的现象。
  • 30.3 分布式缓存 一致性 Hash 环 一致性 hash 算法通过一个叫作一致性 hash 环 的数据结构实现。这个环的起点是 0 ，终点是 2^32 - 1 ，并且起点与终点连接，环的中间的 整数按逆时针分布，故这个环的整数分布范围是 [0, 2^32-1]
  • 31.3 分布式缓存 一致性 Hash 环 - 放入数据 假设现在我们有 4 个对象，分别为 o1 ， o2 ， o3 ， o4 ，使用 hash 函数计算这 4 个对象的 hash 值（范围为 0 ~ 2^32-1 ） hash(o1) = m1 hash(o2) = m2 hash(o3) = m3 hash(o4) = m4 把 m1 ， m2 ， m3 ， m4 这 4 个值放置到 hash 环上
  • 32.3 分布式缓存 一致性 Hash 环 - 放入机器 使用同样的 hash 函数，我们将机器也放置到 hash 环上。假设我们有三台缓存机器，分别为 c1 ， c2 ， c3 hash(c1) = t1 hash(c2) = t2 hash(c3) = t3 把 t1 ， t2 ， t3 这 3 个值放置到 hash 环上
  • 33.3 分布式缓存 一致性 Hash 环 - 为对象选择机器 将对象和机器都放置到同一个 hash 环后，在 hash 环上顺时针查找距离这个对象的 hash 值 最近的机器，即是这个对象所属的机器。 例如，对于对象 o2 ，顺序针找到最近的机器是 c1 ，故机器 c1 会缓存对象 o2 。而机器 c2 则 缓存 o3 ， o4 ，机器 c3 则缓存对象 o1
  • 34.3 分布式缓存 一致性 Hash 环 - 处理机器增加的情况 增加机器 c4 的部署并将机器 c4 加入到 hash 环的机器 c3 与 c2 之间。这时，只有机器 c3 与 c4 之间的对象需要重新分配新的机器。对于我 们的例子，只有对象 o4 被重新分配到了 c4 ， 其他对象仍在原有机器上。
  • 35.3 分布式缓存 一致性 HASH 优势 使用简单的求模方法，当新添加机器后会导致大部分缓存失效的情况，使用一致性 hash 算法后这 种情况则会得到大大的改善。前面提到 3 台机器变成 4 台机器后，缓存命中率只有 25% （不命中率 75% ）。 而使用一致性 hash 算法，理想情况下缓存命中率则有 75% ，而且，随着机器规模的增加，命中率 会进一步提高， 99 台机器增加一台后，命中率达到 99% ，这大大减轻了增加缓存机器带来的数据 库访问的压力
  • 36.3 分布式缓存 一致性 Hash 环 - 处理机器减少的情况 将机器 c1 下线（当然，也有可能是机器 c1 宕 机），这时，只有原有被分配到机器 c1 对象需 要被重新分配到新的机器。对于我们的例子，只 有对象 o2 被重新分配到机器 c3 ，其他对象仍 在原有机器上
  • 37.3 分布式缓存 一致性 Hash 环 - 虚拟节点 新加入的机器 c4 只分担了机器 c2 的负载，机 器 c1 与 c3 的负载并没有因为机器 c4 的加入而 减少负载压力。 将每台物理机器虚拟为一组虚拟机器，将虚拟 机器放置到 hash 环上，如果需要确定对象的机 器，先确定对象的虚拟机器，再由虚拟机器确定 物理机器。 假如开始时存在缓存机器 c1 ， c2 ， c3 ，对于 每个缓存机器，都有 3 个虚拟节点对应
  • 38.3 分布式缓存 一致性 Hash 环 - 虚拟节点 假设对于对象 o1 ，其对应的虚拟节点为 c11 ，而虚拟节点 c11 对象缓存机器 c1 ，故 对象 o1 被分配到机器 c1 中。 新加入缓存机器 c4 ，其对应的虚拟节点为 c41 ， c42 ， c43 ，将这三个虚拟节点添加到 hash 环中 新加入的缓存机器 c4 对应一组虚拟节点 c41 ， c42 ， c43 ，加入到 hash 环后，影响的虚拟 节点包括 c31 ， c22 ， c11 （顺时针查找到第 一个节点），而这 3 个虚拟节点分别对应机器 c3 ， c2 ， c1 。
  • 39. 4. 缓存设计
  • 40.4缓存设计 确认需求 确定架构 是否需要缓存，浪费有限 需要分布式缓存吗？需 内存和节约 CPU 的收益 要分层吗？ 对比 2 4 1 选择缓存 数据活跃度，命中率，是 否需要持久化 3 缓存更新 更新策略与数据有效性
  • 41.4缓存设计 缓存三大坑 缓存穿透：指查询的数据在数据库是没有的，那么在缓存中自然也没有，所以，在缓存中查不到就会去 数据库取查询，这样的请求一多，那么我们的数据库的压力自然会增大。 缓存雪崩：指缓存不可用或者大量缓存由于超时时间相同在同一时间段失效，大量请求直接访问数据库 ，数据库压力过大导致系统雪崩 缓存污染：一般出现在我们使用本地缓存中，可以想象，在本地缓存中如果你获得了缓存，但是你接下来修改了这 个数据，但是这个数据并没有更新在数据库，这样就造成了缓存污染 缓存穿透 缓存雪崩 缓存污染
  • 42.4缓存设计 缓存套路 看到好些人在写更新缓存数据代码时，先删除缓存，然后再更新数据库， 而后续的操作会把数据再装载的缓存中。然而，这个是逻辑是错误的。试想， 两个并发操作，一个是更新操作，另一个是查询操作，更新操作删除缓存后， 查询操作没有命中缓存，先把老数据读出来后放到缓存中，然后更新操作更新 了数据库。于是，在缓存中的数据还是老的数据，导致缓存中的数据是脏的， 而且还一直这样脏下去了
  • 43.4缓存设计 Cache Aside Pattern 失效 应用程序先从 cache 取数据，没有得到，则从数据库中取 数据，成功后，放到缓存中。 命 应用程序从 cache 中取数据，取到后返回。 中 更新
  • 44.4缓存设计 Read/Write Through Pattern Read Through 套路就是在查询操作中更 新缓存，也就是说，当缓存失效的时候 （过期或 LRU 换出）， Cache Aside 是 由调用方负责把数据加载入缓存，而 Read Through 则用缓存服务自己来加载，从而 对应用方是透明的。 Write Through 套路和 Read Through 相 仿，不过是在更新数据时发生。当有数据更新 的时候，如果没有命中缓存，直接更新数据 库，然后返回。如果命中了缓存，则更新缓 存，然后再由 Cache 自己更新数据库（这是一 个同步操作）
  • 45.4缓存设计 Write Behind Caching Pattern Write Back 套路，一句说就是，在更新数据的时候，只更新缓存，不更新数据库，而我们的缓存 会异步地批量更新数据库。这个设计的好处就是让数据的 I/O 操作飞快无比（因为直接操作内存 嘛 ），因为异步， write backg 还可以合并对同一个数据的多次操作，所以性能的提高是相当可 观的。
  • 46.5参考 and 答疑 Design Of A Modern Cachehttp://'>http://