微信号:codedumpnote

介绍:写作是最好的记录,分享是最好的学习.

Redis中的LRU数据淘汰算法

2016-07-26 19:23 codedump

关于Redis中的数据淘汰算法,《Redis设计与实现》一书中已经有涉及到两种场景:惰性删除和定时删除。然而还有一个场景没有涉及到,就是当把Redis做为缓存服务器时,设置了最大可用的内存上限,此时Redis也会根据不同的策略进行数据的删除。


Redis中,可以使用配置项“maxmemory”来设置最大使用内存,如“maxmemory 100mb”表示最大使用内存为100MB,注意这个配置项在32位机器上最大为3GB。


Redis使用了几种不同的策略来进行缓存数据的淘汰:


  1. noeviction:不淘汰数据,由于内存已经用尽,此时会直接返回客户端报错信息。

  2. allkeys-lru:对所有的key进行LRU算法淘汰,后面会提到Redis这里的实现比较呵呵。

  3. volatile-lru:针对设置了过期时间的数据进行LRU数据淘汰。

  4. allkeys-random:随机从所有数据中抽取key进行淘汰。

  5. volatile-random:随机从所有设置了过期时间的数据中进行淘汰。

  6. volatile-ttl:从设置了缓存过期时间的数据中,抽取TTL时间更短的数据进行淘汰。


这部分的代码实现,在函数redis.c/freeMemoryIfNeeded中,从前面的策略说明可以看到,不同的算法之间除了策略的不同,还有选择对象的差异。allkeys相关的操作,其操作对象是redisdb的dict表,也就是所有数据所在的表;而volatile相关的操作,作用对象则变成了expires表,这个表的数据都是有缓存过期时间的数据。


下面来重点聊聊这里的LRU算法。众所周知,LRU算法是一种淘汰最近最少访问数据的算法。然而Redis的实现并不是完全精准的LRU算法,其伪代码大概如下:


  1. 根据配置的样本数量,随机抽取待抽查数据集(dict或者expires表)中的数据。

  2. 从这些样本数据中删除其中空闲时间最长的数据。


可以看到,Redis的LRU算法是“基于采样数据”的处理,而不是针对全局数据的,用作者的话来说,是一个近似的算法。


这里面的样本数量,由配置“maxmemory-samples”来决定,默认为5。


每次要决定哪个数据被淘汰时,都要首先扫描出maxmemory-samples个数据,再从中进行选择,牺牲了CPU,所以作者并不建议把这个数据设置的特别大,最好不要超过10了。


Redis 3.0中做了一个改进,引入了一个名为eviction_pool的对象,实际上是一个数组,这里会将抽取的样本数据按照空闲时间进行排序,这样减少扫描的时间。


参考资料:

《Using Redis as an LRU cache》


 
Codedump的技术笔记 更多文章 微信自研生产级paxos类库PhxPaxos实现原理介绍 Lua语言的前世今生 分布式网游服务器架构中的对象管理 几种一致性模型的分析 时钟向量在一致性问题中的应用
猜您喜欢 数据库优化思路 【心得体会】良同学北京技术交流分享 Android Studio 2.2 来啦 知识图谱在大数据反欺诈领域的应用与实践 | 点融黑帮 第一篇