27 | 缓存被污染了，该怎么办？

Oct 19, 2020

27 | 缓存被污染了，该怎么办？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

27 | 缓存被污染了，该怎么办？

2020-10-19 蒋德钧来自北京

《Redis核心技术与实战》

课程介绍



讲述：蒋德钧

时长18:09大小16.63M



你好，我是蒋德钧。
我们应用 Redis 缓存时，如果能缓存会被反复访问的数据，那就能加速业务应用的访问。但是，如果发生了缓存污染，那么，缓存对业务应用的加速作用就减少了。
那什么是缓存污染呢？在一些场景下，有些数据被访问的次数非常少，甚至只会被访问一次。当这些数据服务完访问请求后，如果还继续留存在缓存中的话，就只会白白占用缓存空间。这种情况，就是缓存污染。
当缓存污染不严重时，只有少量数据占据缓存空间，此时，对缓存系统的影响不大。但是，缓存污染一旦变得严重后，就会有大量不再访问的数据滞留在缓存中。如果这时数据占满了缓存空间，我们再往缓存中写入新数据时，就需要先把这些数据逐步淘汰出缓存，这就会引入额外的操作时间开销，进而会影响应用的性能。
今天，我们就来看看如何解决缓存污染问题。
如何解决缓存污染问题？要解决缓存污染，我们也能很容易想到解决方案，那就是得把不会再被访问的数据筛选出来并淘汰掉。这样就不用等到缓存被写满以后，再逐一淘汰旧数据之后，才能写入新数据了。而哪些数据能留存在缓存中，是由缓存的淘汰策略决定的。
到这里，你还记得咱们在第 24 讲一起学习的 8 种数据淘汰策略吗？它们分别是 noeviction、volatile-random、volatile-ttl、volatile-lru、volatile-lfu、allkeys-lru、allkeys-random 和 allkeys-lfu 策略。
在这 8 种策略中，noeviction 策略是不会进行数据淘汰的。所以，它肯定不能用来解决缓存污染问题。其他的 7 种策略，都会按照一定的规则来淘汰数据。这里有个关键词是“一定的规则”，那么问题来了，不同的规则对于解决缓存污染问题，是否都有效呢？接下来，我们就一一分析下。
因为 LRU 算法是我们在缓存数据淘汰策略中广泛应用的算法，所以我们先分析其他策略，然后单独分析淘汰策略使用 LRU 算法的情况，最后再学习下 LFU 算法用于淘汰策略时，对缓存污染的应对措施。使用 LRU 算法和 LFU 算法的策略各有两种（volatile-lru 和 allkeys-lru，以及 volatile-lfu 和 allkeys-lfu），为了便于理解，接下来我会统一把它们叫作 LRU 策略和 LFU 策略。
首先，我们看下 volatile-random 和 allkeys-random 这两种策略。它们都是采用随机挑选数据的方式，来筛选即将被淘汰的数据。
既然是随机挑选，那么 Redis 就不会根据数据的访问情况来筛选数据。如果被淘汰的数据又被访问了，就会发生缓存缺失。也就是说，应用需要到后端数据库中访问这些数据，降低了应用的请求响应速度。所以，volatile-random 和 allkeys-random 策略，在避免缓存污染这个问题上的效果非常有限。
我给你举个例子吧。如下图所示，假设我们配置 Redis 缓存使用 allkeys-random 淘汰策略，当缓存写满时，allkeys-random 策略随机选择了数据 20 进行淘汰。不巧的是，数据 20 紧接着又被访问了，此时，Redis 就会发生了缓存缺失。
我们继续看 volatile-ttl 策略是否能有效应对缓存污染。volatile-ttl 针对的是设置了过期时间的数据，把这些数据中剩余存活时间最短的筛选出来并淘汰掉。
虽然 volatile-ttl 策略不再是随机选择淘汰数据了，但是剩余存活时间并不能直接反映数据再次访问的情况。所以，按照 volatile-ttl 策略淘汰数据，和按随机方式淘汰数据类似，也可能出现数据被淘汰后，被再次访问导致的缓存缺失问题。
这时，你可能会想到一种例外的情况：业务应用在给数据设置过期时间的时候，就明确知道数据被再次访问的情况，并根据访问情况设置过期时间。此时，Redis 按照数据的剩余最短存活时间进行筛选，是可以把不会再被访问的数据筛选出来的，进而避免缓存污染。例如，业务部门知道数据被访问的时长就是一个小时，并把数据的过期时间设置为一个小时后。这样一来，被淘汰的数据的确是不会再被访问了。
讲到这里，我们先小结下。除了在明确知道数据被再次访问的情况下，volatile-ttl 可以有效避免缓存污染。在其他情况下，volatile-random、allkeys-random、volatile-ttl 这三种策略并不能应对缓存污染问题。
接下来，我们再分别分析下 LRU 策略，以及 Redis 4.0 后实现的 LFU 策略。LRU 策略会按照数据访问的时效性，来筛选即将被淘汰的数据，应用非常广泛。在第 24 讲，我们已经学习了 Redis 是如何实现 LRU 策略的，所以接下来我们就重点看下它在解决缓存污染问题上的效果。
LRU 缓存策略我们先复习下 LRU 策略的核心思想：如果一个数据刚刚被访问，那么这个数据肯定是热数据，还会被再次访问。
按照这个核心思想，Redis 中的 LRU 策略，会在每个数据对应的 RedisObject 结构体中设置一个 lru 字段，用来记录数据的访问时间戳。在进行数据淘汰时，LRU 策略会在候选数据集中淘汰掉 lru 字段值最小的数据（也就是访问时间最久的数据）。
所以，在数据被频繁访问的业务场景中，LRU 策略的确能有效留存访问时间最近的数据。而且，因为留存的这些数据还会被再次访问，所以又可以提升业务应用的访问速度。
但是，也正是因为只看数据的访问时间，使用 LRU 策略在处理扫描式单次查询操作时，无法解决缓存污染。所谓的扫描式单次查询操作，就是指应用对大量的数据进行一次全体读取，每个数据都会被读取，而且只会被读取一次。此时，因为这些被查询的数据刚刚被访问过，所以 lru 字段值都很大。
在使用 LRU 策略淘汰数据时，这些数据会留存在缓存中很长一段时间，造成缓存污染。如果查询的数据量很大，这些数据占满了缓存空间，却又不会服务新的缓存请求，此时，再有新数据要写入缓存的话，还是需要先把这些旧数据替换出缓存才行，这会影响缓存的性能。
为了方便你理解，我给你举个例子。如下图所示，数据 6 被访问后，被写入 Redis 缓存。但是，在此之后，数据 6 一直没有被再次访问，这就导致数据 6 滞留在缓存中，造成了污染。
所以，对于采用了 LRU 策略的 Redis 缓存来说，扫描式单次查询会造成缓存污染。为了应对这类缓存污染问题，Redis 从 4.0 版本开始增加了 LFU 淘汰策略。
与 LRU 策略相比，LFU 策略中会从两个维度来筛选并淘汰数据：一是，数据访问的时效性（访问时间离当前时间的远近）；二是，数据的被访问次数。
那 Redis 的 LFU 策略是怎么实现的，又是如何解决缓存污染问题的呢？我们来看一下。
LFU 缓存策略的优化LFU 缓存策略是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，LFU 策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。
和那些被频繁访问的数据相比，扫描式单次查询的数据因为不会被再次访问，所以它们的访问次数不会再增加。因此，LFU 策略会优先把这些访问次数低的数据淘汰出缓存。这样一来，LFU 策略就可以避免这些数据对缓存造成污染了。
那么，LFU 策略具体又是如何实现的呢？既然 LFU 策略是在 LRU 策略上做的优化，那它们的实现必定有些关系。所以，我们就再复习下第 24 讲学习过的 LRU 策略的实现。
为了避免操作链表的开销，Redis 在实现 LRU 策略时使用了两个近似方法：
Redis 是用 RedisObject 结构来保存数据的，RedisObject 结构中设置了一个 lru 字段，用来记录数据的访问时间戳；
Redis 并没有为所有的数据维护一个全局的链表，而是通过随机采样方式，选取一定数量（例如 10 个）的数据放入候选集合，后续在候选集合中根据 lru 字段值的大小进行筛选。
在此基础上，Redis 在实现 LFU 策略的时候，只是把原来 24bit 大小的 lru 字段，又进一步拆分成了两部分。
ldt 值：lru 字段的前 16bit，表示数据的访问时间戳；
counter 值：lru 字段的后 8bit，表示数据的访问次数。
总结一下：当 LFU 策略筛选数据时，Redis 会在候选集合中，根据数据 lru 字段的后 8bit 选择访问次数最少的数据进行淘汰。当访问次数相同时，再根据 lru 字段的前 16bit 值大小，选择访问时间最久远的数据进行淘汰。
到这里，还没结束，Redis 只使用了 8bit 记录数据的访问次数，而 8bit 记录的最大值是 255，这样可以吗？
在实际应用中，一个数据可能会被访问成千上万次。如果每被访问一次，counter 值就加 1 的话，那么，只要访问次数超过了 255，数据的 counter 值就一样了。在进行数据淘汰时，LFU 策略就无法很好地区分并筛选这些数据，反而还可能会把不怎么访问的数据留存在了缓存中。
我们一起来看个例子。
假设第一个数据 A 的累计访问次数是 256，访问时间戳是 202010010909，所以它的 counter 值为 255，而第二个数据 B 的累计访问次数是 1024，访问时间戳是 202010010810。如果 counter 值只能记录到 255，那么数据 B 的 counter 值也是 255。
此时，缓存写满了，Redis 使用 LFU 策略进行淘汰。数据 A 和 B 的 counter 值都是 255，LFU 策略再比较 A 和 B 的访问时间戳，发现数据 B 的上一次访问时间早于 A，就会把 B 淘汰掉。但其实数据 B 的访问次数远大于数据 A，很可能会被再次访问。这样一来，使用 LFU 策略来淘汰数据就不合适了。
的确，Redis 也注意到了这个问题。因此，在实现 LFU 策略时，Redis 并没有采用数据每被访问一次，就给对应的 counter 值加 1 的计数规则，而是采用了一个更优化的计数规则。
简单来说，LFU 策略实现的计数规则是：每当数据被访问一次时，首先，用计数器当前的值乘以配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r 值时，计数器才加 1。
下面这段 Redis 的部分源码，显示了 LFU 策略增加计数器值的计算逻辑。其中，baseval 是计数器当前的值。计数器的初始值默认是 5（由代码中的 LFU_INIT_VAL 常量设置），而不是 0，这样可以避免数据刚被写入缓存，就因为访问次数少而被立即淘汰。
double r = (double)rand()/RAND_MAX;
...
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++; 
使用了这种计算规则后，我们可以通过设置不同的 lfu_log_factor 配置项，来控制计数器值增加的速度，避免 counter 值很快就到 255 了。
为了更进一步说明 LFU 策略计数器递增的效果，你可以看下下面这张表。这是 Redis官网上提供的一张表，它记录了当 lfu_log_factor 取不同值时，在不同的实际访问次数情况下，计数器的值是如何变化的。
可以看到，当 lfu_log_factor 取值为 1 时，实际访问次数为 100K 后，counter 值就达到 255 了，无法再区分实际访问次数更多的数据了。而当 lfu_log_factor 取值为 100 时，当实际访问次数为 10M 时，counter 值才达到 255，此时，实际访问次数小于 10M 的不同数据都可以通过 counter 值区分出来。
正是因为使用了非线性递增的计数器方法，即使缓存数据的访问次数成千上万，LFU 策略也可以有效地区分不同的访问次数，从而进行合理的数据筛选。从刚才的表中，我们可以看到，当 lfu_log_factor 取值为 10 时，百、千、十万级别的访问次数对应的 counter 值已经有明显的区分了，所以，我们在应用 LFU 策略时，一般可以将 lfu_log_factor 取值为 10。
前面我们也提到了，应用负载的情况是很复杂的。在一些场景下，有些数据在短时间内被大量访问后就不会再被访问了。那么再按照访问次数来筛选的话，这些数据会被留存在缓存中，但不会提升缓存命中率。为此，Redis 在实现 LFU 策略时，还设计了一个 counter 值的衰减机制。
简单来说，LFU 策略使用衰减因子配置项 lfu_decay_time 来控制访问次数的衰减。LFU 策略会计算当前时间和数据最近一次访问时间的差值，并把这个差值换算成以分钟为单位。然后，LFU 策略再把这个差值除以 lfu_decay_time 值，所得的结果就是数据 counter 要衰减的值。
简单举个例子，假设 lfu_decay_time 取值为 1，如果数据在 N 分钟内没有被访问，那么它的访问次数就要减 N。如果 lfu_decay_time 取值更大，那么相应的衰减值会变小，衰减效果也会减弱。所以，如果业务应用中有短时高频访问的数据的话，建议把 lfu_decay_time 值设置为 1，这样一来，LFU 策略在它们不再被访问后，会较快地衰减它们的访问次数，尽早把它们从缓存中淘汰出去，避免缓存污染。
小结今天这节课，我们学习的是“如何解决缓存污染”这个问题。
缓存污染问题指的是留存在缓存中的数据，实际不会被再次访问了，但是又占据了缓存空间。如果这样的数据体量很大，甚至占满了缓存，每次有新数据写入缓存时，还需要把这些数据逐步淘汰出缓存，就会增加缓存操作的时间开销。
因此，要解决缓存污染问题，最关键的技术点就是能识别出这些只访问一次或是访问次数很少的数据，在淘汰数据时，优先把它们筛选出来并淘汰掉。因为 noviction 策略不涉及数据淘汰，所以这节课，我们就从能否有效解决缓存污染这个维度，分析了 Redis 的其他 7 种数据淘汰策略。
volatile-random 和 allkeys-random 是随机选择数据进行淘汰，无法把不再访问的数据筛选出来，可能会造成缓存污染。如果业务层明确知道数据的访问时长，可以给数据设置合理的过期时间，再设置 Redis 缓存使用 volatile-ttl 策略。当缓存写满时，剩余存活时间最短的数据就会被淘汰出缓存，避免滞留在缓存中，造成污染。
当我们使用 LRU 策略时，由于 LRU 策略只考虑数据的访问时效，对于只访问一次的数据来说，LRU 策略无法很快将其筛选出来。而 LFU 策略在 LRU 策略基础上进行了优化，在筛选数据时，首先会筛选并淘汰访问次数少的数据，然后针对访问次数相同的数据，再筛选并淘汰访问时间最久远的数据。
在具体实现上，相对于 LRU 策略，Redis 只是把原来 24bit 大小的 lru 字段，又进一步拆分成了 16bit 的 ldt 和 8bit 的 counter，分别用来表示数据的访问时间戳和访问次数。为了避开 8bit 最大只能记录 255 的限制，LFU 策略设计使用非线性增长的计数器来表示数据的访问次数。
在实际业务应用中，LRU 和 LFU 两个策略都有应用。LRU 和 LFU 两个策略关注的数据访问特征各有侧重，LRU 策略更加关注数据的时效性，而 LFU 策略更加关注数据的访问频次。通常情况下，实际应用的负载具有较好的时间局部性，所以 LRU 策略的应用会更加广泛。但是，在扫描式查询的应用场景中，LFU 策略就可以很好地应对缓存污染问题了，建议你优先使用。
此外，如果业务应用中有短时高频访问的数据，除了 LFU 策略本身会对数据的访问次数进行自动衰减以外，我再给你个小建议：你可以优先使用 volatile-lfu 策略，并根据这些数据的访问时限设置它们的过期时间，以免它们留存在缓存中造成污染。
每课一问按照惯例，我给你提个小问题。使用了 LFU 策略后，你觉得缓存还会被污染吗？
欢迎在留言区写下你的思考和答案，我们一起交流讨论。如果你觉得今天的内容对你有所帮助，也欢迎你分享给你的朋友或同事。我们下节课见。

分享给需要的人，Ta购买本课程，你将得20元

生成海报并分享

赞 61

提建议

26 | 缓存异常（下）：如何解决缓存雪崩、击穿、穿透难题？

28 | Pika：如何基于SSD实现大容量Redis？

 写留言

精选留言(37)

Kaito
2020-10-19
使用了 LFU 策略后，缓存还会被污染吗？我觉得还是有被污染的可能性，被污染的概率取决于LFU的配置，也就是lfu-log-factor和lfu-decay-time参数。 1、根据LRU counter计数规则可以得出，counter递增的概率取决于2个因素： a) counter值越大，递增概率越低 b) lfu-log-factor设置越大，递增概率越低所以当访问次数counter越来越大时，或者lfu-log-factor参数配置过大时，counter递增的概率都会越来越低，这种情况下可能会导致一些key虽然访问次数较高，但是counter值却递增困难，进而导致这些访问频次较高的key却优先被淘汰掉了。另外由于counter在递增时，有随机数比较的逻辑，这也会存在一定概率导致访问频次低的key的counter反而大于访问频次高的key的counter情况出现。 2、如果lfu-decay-time配置过大，则counter衰减会变慢，也会导致数据淘汰发生推迟的情况。 3、另外，由于LRU的ldt字段只采用了16位存储，其精度是分钟级别的，在counter衰减时可能会产生同一分钟内，后访问的key比先访问的key的counter值优先衰减，进而先被淘汰掉的情况。可见，Redis实现的LFU策略，也是近似的LFU算法。Redis在实现时，权衡了内存使用、性能开销、LFU的正确性，通过复用并拆分lru字段的方式，配合算法策略来实现近似的结果，虽然会有一定概率的偏差，但在内存数据库这种场景下，已经做得足够好了。
展开
共 20 条评论
207
甜宝仙女的专属饲养员
2020-10-19
又刷新了对lru和lfu的认知，这种突然打开知识盲区的天窗的感觉就如同一盆冷水，把我从地铁上这种迷迷糊糊的状态给满血复活
共 2 条评论
25
test
2020-10-19
1.选候选集：volatile前缀的是设置了过期时间的key，all前缀的是全部key； 2.算法：lru是最近最少使用，lfu是最近最不频繁使用，ttl是距离到期时间长短，ramdon是随机； 2.1 lru是自带了访问时间 2.2 lfu是带了访问次数，但是因为只有八位保存所以不是每访问一次就+1，而是每次原来访问次数乘以lfu_log_factor，加一再倒数，看是否大于随机值，大于则+1：double r = (double)rand()/RAND_MAX;double p = 1.0/(baseval*server.lfu_log_factor+1);if (r < p) counter++; 还有衰减机制，由lfu_decay_time控制，已过去n个lfu_decay_time，则将idle time加n。 3.淘汰规则：每次sample n个key，比如10个，放到pool里面，淘汰idle时间最长的key。再次淘汰的时候，继续抽样10个key，只把小于原pool中某个idle时间的key插入进去，即如果抽样出来的key比pool中所有key的idle时间都小，则不插入。然后淘汰pool中idle小的，保持pool在10个；
展开
13
xueyuan
2020-11-03
这篇文章就学到了很多，lfu的设计理念很有参考学习的意义。
10
yeek
2020-10-19
偏极端情况下，数据短期内被高频访问，且计数器达到了很大值，且计数器的衰减设置的很大，导致衰减很慢，此时该数据就可能在缓存中长期驻留。从长期来看，我觉得应该是避免频繁执行数据淘汰，否则会影响redis的效率，较好的做法应该是监控redis服务器的内存情况，以及相应的报警机制，定期统计redis中的key分布情况，交由使用方check数据合理性，以检验程序中对redis数据设置的过期时间，访问失效等是否合理。
展开
4
escray
2021-03-30
有缓存过期时间和缓存淘汰机制，为什么还会出现缓存污染？这一讲算是补上了之前留下来的一个坑——前面讲过了 LRU 算法，但是对于 LFU 一直留到这里才讲。我之前望文生义的以为 LFU，就是按照访问频次来淘汰，但是没有考虑到如果次数相同，那么还是要看访问时间；另外就是巧妙的拆分了 RedisObject 里面的 lru 字段，用 ldt 和 counter 来实现算法。能看懂计数器规则的公式，但是不理解为什么要这么计算。还有那个衰减因子配置项 lfu_decay_time 的相关计算也比较有意思，但是不知所以然，此处必有蹊跷。之前看 LRU 和 LFU 比较多，忽略了 volatile-ttl 策略，这次正好补上了。使用了 LFU 策略之后，应该还是会有缓存污染的情况，但是被污染的比例，或者说造成的影响应该小很多。假设 Redis 每次收到的请求都是全量扫描或接近于，那么 LFU 是不是就会失效，或者说缓存污染就会比较严重？
展开
2
写点啥呢
2020-10-19
关于计数衰减想请问老师，它发生的时机是在缓存被访问到还是Redis会定时刷新所有缓存计数进行衰减呢？对这两种衰减时机感觉都有不足，再次访问时候衰减能维持较低的性能损耗但是对于短期热点数据如果不会被访问那么计数就不准确还会导致污染问题。如果是全量定时刷新那么又会带来很多性能损耗。
共 2 条评论
3
bigben
2021-07-07
未达到触发淘汰机制的阈值之前，会被污染的；淘汰时也不是所有被污染key被淘汰，所以也还是被污染的；
1
而立斋
2021-04-17
这才是美妙的设计！！！那个随机数的作用也是神奇，能够有限的减缓计数器增长的速度，而且是数越大，越稳定
1
zenk
2020-11-30
缓存污染还有一个实时性问题吧越小的时间范围内准确识别的难度越大，有时业务方都无法确保数据的时效性，更别说缺少业务信息的Redis 所以，不管什么策略，都无法避免绝对的没有污染
展开
1
简约风丶
2020-11-16
如果有两种类型的数据，一种是波段型访问频率高，一种是一直平稳的访问频率，这种情况下，是不是LFU算法就有可能造成缓存污染
1
小文同学
2020-11-11
LFU 策略需要反复再看才行。
1
Litt1eQ
2020-10-19
感觉下面这种情况会造成缓存污染比如说一个热点数据短时间可能会被大量的访问但是热点一过访问频率就会降低甚至不会被访问到这样热点数据只能通过计数衰减淘汰有可能这些数据成为污染缓存的数据
共 1 条评论
1
走路顺拐
2022-11-02 来自北京
这个热度衰减是主线程还是子线程做的，是怎么做的？
Breeze
2022-04-17
缓存被污染是一个相对概念，不是绝对的，带有一定主观上的判断。LFU策略的效果跟counter值累计的灵敏度和counter的衰减快慢有关系，所以说客观上还是会存在少量污染的情况存在（当然也可以认为不存在污染）。
阿昕
2022-04-14
lfu在很大程度上解决了淘汰访问频率较低数据的需求，并不是绝对性的避免缓存污染
Sk_Keith
2022-04-05
看完这块内容，有个疑惑：不同的Key的访问频率，这个配置是通用的话，能保证全局适用吗？还是只针对某个库的？有实践过的大佬帮忙解惑下吗？
星龙驹
2022-02-10
有个地方不太明白，8bit最大是255，为什么16bit能表示一个很大的时间戳，如202010010909？
共 1 条评论
Vic
2022-01-28
这个课后问题。。内存使用达到maxmemory后才触发内存淘汰机制，LRU&LFU也只是针对这种情况下的Redis释放内存的行为，有效解决缓存污染还是需要给Key设置合理的有效期，有Redis的惰性删除/定时删除即使释放内存
剑八
2022-01-19
一定程度不会，极端情况会有，未设置衰减机制，或衰减时间较长

