Open upan opened 1 year ago
当应用系统有大量用户进行访问时,导致系统的TPS极速上升,查询数据直接打到了数据库，达到了系统的性能瓶颈,接口的响应会变慢,用户体验变得非常差。 那么从技术架构的角度思考可以使用缓存技术对系统进行优化：
在计算机中,缓存是一个高速数据存储层,其中存储了数据子集且通常是短暂性存储，这样日后再次请求此数据时要比访问数据的主存储位置快，通过缓存可以高效地重用之前检索或计算的数据；
缓存分为以下三种：硬件缓存、客户端缓存、服务端缓存。
它是指一块芯片集成到硬盘、CPU上，作用是充当硬盘、CPU与外界接口之间的暂存器，外部接口通常是指硬盘或CPU和内存之间。
为了提高用户体验和减轻服务端压力,会将用户之前访问的一些数据缓存在客户端本地， 一般来说指的是浏览器缓存或APP缓存。
服务端缓存目的和客户端缓存是一样的,只是站在服务端的角度考虑， 如果客户端每次请求服务端都要直接连接到数据库,当客户请求数多的时候数据库压力会非常大， 这个时候可以把一些经常被请求的数据存放在内存中， 当有请求来访问的时候直接返回,不用经过数据库,这样就能减轻数据库的压力， 硬件缓存属于硬件层面上的优化而客户端和服务端缓存则属于技术优化手段， 缓存的本质是以空间换时间的手段来提升接.口的响应速度， 作为一个后端开发关注更多的是服务器端缓存。
高并发查询、高并发写入、热点数据、大对象初始化。
因为[内存]速度远远高于磁盘,所以大大的提升了应用程序的访问速度
一个缓存实例就可以提供数十万的QPS,可以取代大量数据库实例从而降低总成本
降低数据库负载,防止其在负载情况下性能下降甚至是雪崩
当有很少数据被频繁的访问,例如微博上某个明星突然官宣,很多用户都会去看一下 这会在数据库中产生热点,为了让访问速度更快,需要用特殊手段去维护这些热点数据 当使用了缓存以后就不需要考虑热点数据的问题
相比较于数据库除了更低的延迟外,内存系统还提供了更高的吞吐量, 比如说redis单个实例可以处理十几万的读请求.
缓存通常需要设置有效期,过期后应当失效 常见的过期策略有：定时、定期、惰性失效
缓存占用有空间上限,超过上限需淘汰部分缓存数据 常见的淘汰策略有：FIFO、LRU、LFU
缓存需要支持并发的读取和写入
请求数据库中不存在的数据导致每次查询都无法命中缓存,从而违背了降低数据库压力的本意
缓存失效的同时大量相同请求穿过缓存访问数据库
大量缓存同时失效,导致大量请求穿过缓存访问到数据库
基于JDK自带的Map容器类:HashMap、ConcurrentHashMap
Google提供的java增强工具包Guava的一个模块,社区活跃。Spring5之前默认的内存缓存框架
重量级的内存缓存,支持二级缓存,Hibernate中默认的缓存框架
基于Guava API开发的高性能内存缓存,Spring5默认的内存缓存框架
判断一个缓存的好坏最核心的指标就是命中率，影响缓存命中率有很多因素，包括业务场景、淘汰策略、清理策略、缓存容量等等。如果作为本地缓存， 它的性能的情况，资源的占用也都是一个很重要的指标。
上面说到淘汰策略是影响缓存命中率的因素之一，一般比较简单的缓存就会直接用到 LFU(Least Frequently Used，即最不经常使用) 或者LRU(Least Recently Used，即最近最少使用) ，而 Caffeine 就是使用了 W-TinyLFU 算法。
W-TinyLFU 看名字就能大概猜出来，它是 LFU 的变种，也是一种缓存淘汰算法。那为什么要使用 W-TinyLFU 呢？
TinyLFU 就是其中一个优化算法，它是专门为了解决 LFU 上述提到的两个问题而被设计出来的。
解决第一个问题是采用了 Count–Min Sketch 算法。
解决第二个问题是让记录尽量保持相对的“新鲜”（Freshness Mechanism），并且当有新的记录插入时，可以让它跟老的记录进行“PK”，输者就会被淘汰，这样一些老的、不再需要的记录就会被剔除。
如何对一个 key 进行统计，但又可以节省空间呢？（不是简单的使用HashMap，这太消耗内存了），注意哦，不需要精确的统计，只需要一个近似值就可以了，怎么样，这样场景是不是很熟悉，如果你是老司机，或许已经联想到布隆过滤器（Bloom Filter）的应用了。
没错，将要介绍的 Count–Min Sketch 的原理跟 Bloom Filter 一样，只不过 Bloom Filter 只有 0 和 1 的值，那么你可以把 Count–Min Sketch 看作是“数值”版的 Bloom Filter。
在 TinyLFU 中，近似频率的统计如下图所示： 对一个 key 进行多次 hash 函数后，index 到多个数组位置后进行累加，查询时取多个值中的最小值即可。
Caffeine 对这个算法的实现在FrequencySketch类。但 Caffeine 对此有进一步的优化，例如 Count–Min Sketch 使用了二维数组，Caffeine 只是用了一个一维的数组；再者，如果是数值类型的话，这个数需要用 int 或 long 来存储，但是 Caffeine 认为缓存的访问频率不需要用到那么大，只需要 15 就足够，一般认为达到 15 次的频率算是很高的了，而且 Caffeine 还有另外一个机制来使得这个频率进行衰退减半（下面就会讲到）。如果最大是 15 的话，那么只需要 4 个 bit 就可以满足了，一个 long 有 64bit，可以存储 16 个这样的统计数，Caffeine 就是这样的设计，使得存储效率提高了 16 倍。
注意紫色虚线框，其中蓝色小格就是需要计算的位置：
为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，Caffeine 有一个 Freshness Mechanism。做法很简答，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以 2。
前言
当应用系统有大量用户进行访问时,导致系统的TPS极速上升,查询数据直接打到了数据库，达到了系统的性能瓶颈,接口的响应会变慢,用户体验变得非常差。 那么从技术架构的角度思考可以使用缓存技术对系统进行优化：
缓存介绍
在计算机中,缓存是一个高速数据存储层,其中存储了数据子集且通常是短暂性存储，这样日后再次请求此数据时要比访问数据的主存储位置快，通过缓存可以高效地重用之前检索或计算的数据；
缓存分为以下三种：硬件缓存、客户端缓存、服务端缓存。
硬件缓存
它是指一块芯片集成到硬盘、CPU上，作用是充当硬盘、CPU与外界接口之间的暂存器，外部接口通常是指硬盘或CPU和内存之间。
客户端缓存
为了提高用户体验和减轻服务端压力,会将用户之前访问的一些数据缓存在客户端本地， 一般来说指的是浏览器缓存或APP缓存。
服务端缓存
服务端缓存目的和客户端缓存是一样的,只是站在服务端的角度考虑， 如果客户端每次请求服务端都要直接连接到数据库,当客户请求数多的时候数据库压力会非常大， 这个时候可以把一些经常被请求的数据存放在内存中， 当有请求来访问的时候直接返回,不用经过数据库,这样就能减轻数据库的压力， 硬件缓存属于硬件层面上的优化而客户端和服务端缓存则属于技术优化手段， 缓存的本质是以空间换时间的手段来提升接.口的响应速度， 作为一个后端开发关注更多的是服务器端缓存。
缓存应用场景
高并发查询、高并发写入、热点数据、大对象初始化。
使用缓存的好处
提升应用程序性能
因为[内存]速度远远高于磁盘,所以大大的提升了应用程序的访问速度
降低数据库成本
一个缓存实例就可以提供数十万的QPS,可以取代大量数据库实例从而降低总成本
降低(减少)后端负载
降低数据库负载,防止其在负载情况下性能下降甚至是雪崩
消除数据库热点
当有很少数据被频繁的访问,例如微博上某个明星突然官宣,很多用户都会去看一下 这会在数据库中产生热点,为了让访问速度更快,需要用特殊手段去维护这些热点数据 当使用了缓存以后就不需要考虑热点数据的问题
提高读取吞吐量
相比较于数据库除了更低的延迟外,内存系统还提供了更高的吞吐量, 比如说redis单个实例可以处理十几万的读请求.
常见缓存类型
缓存的特点
设置存活时间(过期策略)
缓存通常需要设置有效期,过期后应当失效 常见的过期策略有：定时、定期、惰性失效
空间占用有限(淘汰策略)
缓存占用有空间上限,超过上限需淘汰部分缓存数据 常见的淘汰策略有：FIFO、LRU、LFU
支持并发更新
缓存需要支持并发的读取和写入
缓存常见的问题
缓存穿透
请求数据库中不存在的数据导致每次查询都无法命中缓存,从而违背了降低数据库压力的本意
缓存击穿
缓存失效的同时大量相同请求穿过缓存访问数据库
缓存雪崩
大量缓存同时失效,导致大量请求穿过缓存访问到数据库
常见的内存缓存实现方式
Java容器
基于JDK自带的Map容器类:HashMap、ConcurrentHashMap
Guava Cache
Google提供的java增强工具包Guava的一个模块,社区活跃。Spring5之前默认的内存缓存框架
Ehcache
重量级的内存缓存,支持二级缓存,Hibernate中默认的缓存框架
Caffeine
基于Guava API开发的高性能内存缓存,Spring5默认的内存缓存框架
Caffeine
Caffeine 的高性能设计
判断一个缓存的好坏最核心的指标就是命中率，影响缓存命中率有很多因素，包括业务场景、淘汰策略、清理策略、缓存容量等等。如果作为本地缓存， 它的性能的情况，资源的占用也都是一个很重要的指标。
W-TinyLFU 整体设计
上面说到淘汰策略是影响缓存命中率的因素之一，一般比较简单的缓存就会直接用到 LFU(Least Frequently Used，即最不经常使用) 或者LRU(Least Recently Used，即最近最少使用) ，而 Caffeine 就是使用了 W-TinyLFU 算法。
W-TinyLFU 看名字就能大概猜出来，它是 LFU 的变种，也是一种缓存淘汰算法。那为什么要使用 W-TinyLFU 呢？
LRU 和 LFU 的缺点
TinyLFU
TinyLFU 就是其中一个优化算法，它是专门为了解决 LFU 上述提到的两个问题而被设计出来的。
解决第一个问题是采用了 Count–Min Sketch 算法。
解决第二个问题是让记录尽量保持相对的“新鲜”（Freshness Mechanism），并且当有新的记录插入时，可以让它跟老的记录进行“PK”，输者就会被淘汰，这样一些老的、不再需要的记录就会被剔除。
统计频率 Count–Min Sketch 算法
如何对一个 key 进行统计，但又可以节省空间呢？（不是简单的使用HashMap，这太消耗内存了），注意哦，不需要精确的统计，只需要一个近似值就可以了，怎么样，这样场景是不是很熟悉，如果你是老司机，或许已经联想到布隆过滤器（Bloom Filter）的应用了。
没错，将要介绍的 Count–Min Sketch 的原理跟 Bloom Filter 一样，只不过 Bloom Filter 只有 0 和 1 的值，那么你可以把 Count–Min Sketch 看作是“数值”版的 Bloom Filter。
在 TinyLFU 中，近似频率的统计如下图所示：
对一个 key 进行多次 hash 函数后，index 到多个数组位置后进行累加，查询时取多个值中的最小值即可。
Caffeine 对这个算法的实现在FrequencySketch类。但 Caffeine 对此有进一步的优化，例如 Count–Min Sketch 使用了二维数组，Caffeine 只是用了一个一维的数组；再者，如果是数值类型的话，这个数需要用 int 或 long 来存储，但是 Caffeine 认为缓存的访问频率不需要用到那么大，只需要 15 就足够，一般认为达到 15 次的频率算是很高的了，而且 Caffeine 还有另外一个机制来使得这个频率进行衰退减半（下面就会讲到）。如果最大是 15 的话，那么只需要 4 个 bit 就可以满足了，一个 long 有 64bit，可以存储 16 个这样的统计数，Caffeine 就是这样的设计，使得存储效率提高了 16 倍。
注意紫色虚线框，其中蓝色小格就是需要计算的位置：
保新机制
为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，Caffeine 有一个 Freshness Mechanism。做法很简答，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以 2。
参考