详解Redis的LRU算法
发布时间：2024-07-05 点击：71
下面由redis教程栏目给大家详解redis的lru算法，希望对需要的朋友有所帮助！
redis的lru算法
lru算法背后的的思想在计算机科学中无处不在，它与程序的"局部性原理"很相似。在生产环境中，虽然有redis内存使用告警，但是了解一下redis的缓存使用策略还是很有好处的。下面是生产环境下redis使用策略：最大可用内存限制为4gb，采用 allkeys-lru 删除策略。所谓删除策略：当redis使用已经达到了最大内存，比如4gb时，如果这时候再往redis里面添加新的key，那么redis将选择一个key删除。那如何选择合适的key删除呢？
config get maxmemory
"maxmemory""4294967296"
config get maxmemory-policy
"maxmemory-policy""allkeys-lru"
在官方文档using redis as an lru cache描述中，提供了好几种删除策略，比如 allkeys-lru、volatile-lru等。在我看来按选择时考虑三个因素：随机、key最近被访问的时间 、key的过期时间(ttl)
比如：allkeys-lru，"统计一下所有的"key历史访问的时间，把"最老"的那个key移除。注意：我这里加了引号，其实在redis的具体实现中，要统计所有的key的最近访问时间代价是很大的。想想，如何做到呢？
evict keys by trying to remove the less recently used (lru) keys first, in order to make space for the new data added.
再比如：allkeys-random，就是随机选择一个key，将之移除。
evict keys randomly in order to make space for the new data added.
再比如：volatile-lru，它只移除那些使用 expire 命令设置了过期时间的key，根据lru算法来移除。
evict keys by trying to remove the less recently used (lru) keys first, but only among keys that have an expire set, in order to make space for the new data added.
再比如：volatile-ttl，它只移除那些使用 expire 命令设置了过期时间的key，哪个key的 存活时间(ttl key 越小)越短，就优先移除。
evict keys with an expire set, and try to evict keys with a shorter time to live (ttl) first, in order to make space for the new data added.
volatile 策略(eviction methods) 作用的key 是那些设置了过期时间的key。在redisdb结构体中，定义了一个名为 expires 字典(dict)保存所有的那些用expire命令设置了过期时间的key，其中expires字典的键指向redis 数据库键空间(redisserver—>redisdb—>redisobject)中的某个键，而expires字典的值则是这个键的过期时间(long类型整数)。
额外提一下：redis 数据库键空间是指：在结构体redisdb中定义的一个名为"dict"，类型为hash字典的一个指针，它用来保存该redis db中的每一个键对象、以及相应的值对象。
既然有这么多策略，那我用哪个好呢？这就涉及到redis中的key的访问模式了(access-pattern)，access-pattern与代码业务逻辑相关，比如说符合某种特征的key经常被访问，而另一些key却不怎么用到。如果所有的key都可能机会均等地被我们的应用程序访问，那它的访问模式服从均匀分布；而大部分情况下，访问模式服从幂指分布(power-law distribution)，另外key的访问模式也有可能是随着时间变化的，因此需要一种合适的删除策略能够catch 住 (捕获住)各种情形。而在幂指分布下，lru是一种很好的策略：
while caches can’t predict the future, they can reason in the following way: keys that are likely to be requested again are keys that were recently requested often. since usually access patterns don’t change very suddenly, this is an effective strategy.
redis中lru策略的实现
最直观的想法：lru啊，记录下每个key 最近一次的访问时间（比如unix timestamp），unix timestamp最小的key，就是最近未使用的，把这个key移除。看下来一个hashmap就能搞定啊。是的，但是首先需要存储每个key和它的timestamp。其次，还要比较timestamp得出最小值。代价很大，不现实啊。
第二种方法：换个角度，不记录具体的访问时间点(unix timestamp)，而是记录idle time：idle time越小，意味着是最近被访问的。
the lru algorithm evicts the least recently used key, which means the one with the greatest idle time.
比如a、b、c、d四个key，a每5s访问一次，b每2s访问一次，c和d每10s访问一次。（一个波浪号代表1s），从上图中可看出：a的空闲时间是2s，b的idle time是1s，c的idle time是5s，d刚刚访问了所以idle time是0s
这里，用一个双向链表(linkedlist)把所有的key链表起来，如果一个key被访问了，将就这个key移到链表的表头，而要移除key时，直接从表尾移除。
it is simple to implement because all we need to do is to track the last time a given key was accessed, or sometimes this is not even needed: we may just have all the objects we want to evict linked in a linked list.
但是在redis中，并没有采用这种方式实现，它嫌linkedlist占用的空间太大了。redis并不是直接基于字符串、链表、字典等数据结构来实现kv数据库，而是在这些数据结构上创建了一个对象系统redis object。在redisobject结构体中定义了一个长度24bit的unsigned类型的字段，用来存储对象最后一次被命令程序访问的时间：
by modifying a bit the redis object structure i was able to make 24 bits of space. there was no room for linking the objects in a linked list (fat pointers!)
毕竟，并不需要一个完全准确的lru算法，就算移除了一个最近访问过的key，影响也不太。
to add another data structure to take this metadata was not an option, however since lru is itself an approximation of what we want to achieve, what about approximating lru itself?
最初redis是这样实现的：
随机选三个key，把idle time最大的那个key移除。后来，把3改成可配置的一个参数，默认为n=5：maxmemory-samples 5
when there is to evict a key, select 3 random keys, and evict the one with the highest idle time
就是这么简单，简单得让人不敢相信了，而且十分有效。但它还是有缺点的：每次随机选择的时候，并没有利用历史信息。在每一轮移除(evict)一个key时，随机从n个里面选一个key，移除idle time最大的那个key；下一轮又是随机从n个里面选一个key…有没有想过：在上一轮移除key的
服务器虚拟主机和云服务器有什么区别
云服务器流量收费标准
商标注册不成功可以用TM么
阿里云服务器优惠促销
云服务器怎么盈利
type-c接口是什么?type-c接口有哪些功能?
教你解决高清音频管理器老是跳出来的方法
本网站被黑客攻击网页设置被改变需要现在马上清理
redis的lru算法
lru算法背后的的思想在计算机科学中无处不在，它与程序的"局部性原理"很相似。在生产环境中，虽然有redis内存使用告警，但是了解一下redis的缓存使用策略还是很有好处的。下面是生产环境下redis使用策略：最大可用内存限制为4gb，采用 allkeys-lru 删除策略。所谓删除策略：当redis使用已经达到了最大内存，比如4gb时，如果这时候再往redis里面添加新的key，那么redis将选择一个key删除。那如何选择合适的key删除呢？
config get maxmemory
"maxmemory""4294967296"
config get maxmemory-policy
"maxmemory-policy""allkeys-lru"
在官方文档using redis as an lru cache描述中，提供了好几种删除策略，比如 allkeys-lru、volatile-lru等。在我看来按选择时考虑三个因素：随机、key最近被访问的时间 、key的过期时间(ttl)
比如：allkeys-lru，"统计一下所有的"key历史访问的时间，把"最老"的那个key移除。注意：我这里加了引号，其实在redis的具体实现中，要统计所有的key的最近访问时间代价是很大的。想想，如何做到呢？
evict keys by trying to remove the less recently used (lru) keys first, in order to make space for the new data added.
再比如：allkeys-random，就是随机选择一个key，将之移除。
evict keys randomly in order to make space for the new data added.
再比如：volatile-lru，它只移除那些使用 expire 命令设置了过期时间的key，根据lru算法来移除。
evict keys by trying to remove the less recently used (lru) keys first, but only among keys that have an expire set, in order to make space for the new data added.
再比如：volatile-ttl，它只移除那些使用 expire 命令设置了过期时间的key，哪个key的 存活时间(ttl key 越小)越短，就优先移除。
evict keys with an expire set, and try to evict keys with a shorter time to live (ttl) first, in order to make space for the new data added.
volatile 策略(eviction methods) 作用的key 是那些设置了过期时间的key。在redisdb结构体中，定义了一个名为 expires 字典(dict)保存所有的那些用expire命令设置了过期时间的key，其中expires字典的键指向redis 数据库键空间(redisserver—>redisdb—>redisobject)中的某个键，而expires字典的值则是这个键的过期时间(long类型整数)。
额外提一下：redis 数据库键空间是指：在结构体redisdb中定义的一个名为"dict"，类型为hash字典的一个指针，它用来保存该redis db中的每一个键对象、以及相应的值对象。
既然有这么多策略，那我用哪个好呢？这就涉及到redis中的key的访问模式了(access-pattern)，access-pattern与代码业务逻辑相关，比如说符合某种特征的key经常被访问，而另一些key却不怎么用到。如果所有的key都可能机会均等地被我们的应用程序访问，那它的访问模式服从均匀分布；而大部分情况下，访问模式服从幂指分布(power-law distribution)，另外key的访问模式也有可能是随着时间变化的，因此需要一种合适的删除策略能够catch 住 (捕获住)各种情形。而在幂指分布下，lru是一种很好的策略：
while caches can’t predict the future, they can reason in the following way: keys that are likely to be requested again are keys that were recently requested often. since usually access patterns don’t change very suddenly, this is an effective strategy.
redis中lru策略的实现
最直观的想法：lru啊，记录下每个key 最近一次的访问时间（比如unix timestamp），unix timestamp最小的key，就是最近未使用的，把这个key移除。看下来一个hashmap就能搞定啊。是的，但是首先需要存储每个key和它的timestamp。其次，还要比较timestamp得出最小值。代价很大，不现实啊。
第二种方法：换个角度，不记录具体的访问时间点(unix timestamp)，而是记录idle time：idle time越小，意味着是最近被访问的。
the lru algorithm evicts the least recently used key, which means the one with the greatest idle time.
比如a、b、c、d四个key，a每5s访问一次，b每2s访问一次，c和d每10s访问一次。（一个波浪号代表1s），从上图中可看出：a的空闲时间是2s，b的idle time是1s，c的idle time是5s，d刚刚访问了所以idle time是0s
这里，用一个双向链表(linkedlist)把所有的key链表起来，如果一个key被访问了，将就这个key移到链表的表头，而要移除key时，直接从表尾移除。
it is simple to implement because all we need to do is to track the last time a given key was accessed, or sometimes this is not even needed: we may just have all the objects we want to evict linked in a linked list.
但是在redis中，并没有采用这种方式实现，它嫌linkedlist占用的空间太大了。redis并不是直接基于字符串、链表、字典等数据结构来实现kv数据库，而是在这些数据结构上创建了一个对象系统redis object。在redisobject结构体中定义了一个长度24bit的unsigned类型的字段，用来存储对象最后一次被命令程序访问的时间：
by modifying a bit the redis object structure i was able to make 24 bits of space. there was no room for linking the objects in a linked list (fat pointers!)
毕竟，并不需要一个完全准确的lru算法，就算移除了一个最近访问过的key，影响也不太。
to add another data structure to take this metadata was not an option, however since lru is itself an approximation of what we want to achieve, what about approximating lru itself?
最初redis是这样实现的：
随机选三个key，把idle time最大的那个key移除。后来，把3改成可配置的一个参数，默认为n=5：maxmemory-samples 5
when there is to evict a key, select 3 random keys, and evict the one with the highest idle time
就是这么简单，简单得让人不敢相信了，而且十分有效。但它还是有缺点的：每次随机选择的时候，并没有利用历史信息。在每一轮移除(evict)一个key时，随机从n个里面选一个key，移除idle time最大的那个key；下一轮又是随机从n个里面选一个key…有没有想过：在上一轮移除key的
服务器虚拟主机和云服务器有什么区别
云服务器流量收费标准
商标注册不成功可以用TM么
阿里云服务器优惠促销
云服务器怎么盈利
type-c接口是什么?type-c接口有哪些功能?
教你解决高清音频管理器老是跳出来的方法
本网站被黑客攻击网页设置被改变需要现在马上清理
上一篇：双11云服务器ecs
下一篇：我想问的问题是我的底板是固定的