技术分享 缓存那些事儿

白菜

2018/12/12 发布于 编程 分类

文字内容
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 使用 <dependency> <groupId>com.github.ben-manes.caffeine</groupId> <artifactId>caffeine</artifactId> <version>2.6.2</version> </dependency>
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 Cache http:// highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html Redis 、 Memcached 、 Guava 、 Ehcache 中的算法 http:// calvin1978.blogcn.com/articles/lru.html LIRS 二级 Cache 替换策略解析 http://www.thinkingyu.com/articles/LIRS/ Caffiene Design https://github.com/ben-manes/caffeine/wiki/Design 一致性 Hash(Consistent Hashing) 原理剖析 https:// blog.csdn.net/lihao21/article/details/54193868 TinyLFU: A Highly Efficient Cache Admission Policy https://arxiv.org/pdf/1512.00727.pdf 深入解密来自未来的缓存 -Caffeine https://www.cnblogs.com/liujinhua306/p/9808500.html 如何优雅的设计和使用缓存? https://juejin.im/post/5b849878e51d4538c77a974a 缓存更新的套路 https://coolshell.cn/articles/17416.html
47. 5参考 and 答疑 还漏了啥? 前端缓存 CDN 缓存 Redis 使用 多级缓存实践和广播