如何用Redis做LRU-Cache

客官°小女子只卖身不卖艺 2022-10-02 05:42 119阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

LRU(Least Recently Used)最近最少使用[算法][Link 1]是众多置换算法中的一种。  
[Redis][]中有一个`maxmemory`概念，主要是为了将使用的内存限定在一个固定的大小。[redis][Redis]用到的LRU 算法，是一种近似的LRU算法。

### 1 设置maxmemory ###

上面已经说过`maxmemory`是为了限定Redis最大内存使用量。有多种方法设定它的大小。其中一种方法是通过`CONFIG SET`设定，如下：

127.0.0.1:6379> CONFIG GET maxmemory
    1) "maxmemory"
    2) "0"
    127.0.0.1:6379> CONFIG SET maxmemory 100MB
    OK
    127.0.0.1:6379> CONFIG GET maxmemory
    1) "maxmemory"
    2) "104857600"

另一种方法是修改配置文件`redis.conf`：

maxmemory 100mb

注意，在64bit系统下，`maxmemory`设置为0表示不限制Redis内存使用，在32bit系统下，`maxmemory`隐式不能超过3GB。  
当Redis内存使用达到指定的限制时，就需要选择一个置换的策略。

### 2 置换策略 ###

当Redis内存使用达到`maxmemory`时，需要选择设置好的`maxmemory-policy`进行对老数据的置换。  
下面是可以选择的置换策略：

>  *  `noeviction`: 不进行置换，表示即使内存达到上限也不进行置换，所有能引起内存增加的命令都会返回error
>  *  `allkeys-lru`: 优先删除掉最近最不经常使用的key，用以保存新数据
>  *  `volatile-lru`: 只从设置失效（expire set）的key中选择最近最不经常使用的key进行删除，用以保存新数据
>  *  `allkeys-random`: 随机从all-keys中选择一些key进行删除，用以保存新数据
>  *  `volatile-random`: 只从设置失效（expire set）的key中，选择一些key进行删除，用以保存新数据
>  *  `volatile-ttl`: 只从设置失效（expire set）的key中，选出存活时间（TTL）最短的key进行删除，用以保存新数据

设置`maxmemory-policy`的方法和设置`maxmemory`方法类似，通过`redis.conf`或是通过`CONFIG SET`动态修改。

如果没有匹配到可以删除的key，那么`volatile-lru`、`volatile-random`和`volatile-ttl`策略和`noeviction`替换策略一样——不对任何key进行置换。

选择合适的置换策略是很重要的，这主要取决于你的应用的访问模式，当然你也可以动态的修改置换策略，并通过用Redis命令——`INFO`去输出cache的命中率情况，进而可以对置换策略进行调优。

一般来说，有这样一些常用的经验：

>  *  在所有的key都是最近最经常使用，那么就需要选择`allkeys-lru`进行置换最近最不经常使用的key，如果你不确定使用哪种策略，那么推荐使用`allkeys-lru`
>  *  如果所有的key的访问概率都是差不多的，那么可以选用`allkeys-random`策略去置换数据
>  *  如果对数据有足够的了解，能够为key指定hint（通过expire/ttl指定），那么可以选择`volatile-ttl`进行置换

`volatile-lru`和`volatile-random`经常在一个Redis实例既做cache又做持久化的情况下用到，然而，更好的选择使用两个Redis实例来解决这个问题。

设置是失效时间`expire`会占用一些内存，而采用`allkeys-lru`就没有必要设置失效时间，进而更有效的利用内存。

### 3 置换策略是如何工作的 ###

理解置换策略的执行方式是非常重要的，比如：

>  *  客户端执行一条新命令，导致数据库需要增加数据（比如`set key value`）
>  *  Redis会检查内存使用，如果内存使用超过`maxmemory`，就会按照置换策略删除一些key
>  *  新的命令执行成功

我们持续的写数据会导致内存达到或超出上限`maxmemory`，但是置换策略会将内存使用降低到上限以下。

如果一次需要使用很多的内存（比如一次写入一个很大的set），那么，Redis的内存使用可能超出最大内存限制一段时间。

### 4 近似LRU算法 ###

Redis中的LRU不是严格意义上的LRU算法实现，是一种近似的LRU实现，主要是为了节约内存占用以及提升性能。Redis有这样一个配置——`maxmemory-samples`，Redis的LRU是取出配置的数目的key，然后从中选择一个最近最不经常使用的key进行置换，默认的5，如下：

maxmemory-samples 5

可以通过调整样本数量来取得LRU置换算法的速度或是精确性方面的优势。

Redis不采用真正的LRU实现的原因是为了节约内存使用。虽然不是真正的LRU实现，但是它们在应用上几乎是等价的。下图是Redis的近似LRU实现和理论LRU实现的对比：

![lru-compare][]

[测试][Link 2]开始首先在Redis中导入一定数目的key，然后从第一个key依次访问到最后一个key，因此根据LRU算法第一个被访问的key应该最新被置换，之后再增加50%数目的key，导致50%的老的key被替换出去。  
在上图中你可以看到三种类型的点，组成三种不同的区域：

>  *  淡灰色的是被置换出去的key
>  *  灰色的是没有被置换出去的key
>  *  绿色的是新增加的key

理论LRU实现就像我们期待的那样，最旧的50%数目的key被置换出去，Redis的LRU将一定比例的旧key置换出去。

可以看到在样本数为5的情况下，Redis3.0要比Redis2.8做的好很多，Redis2.8中有很多应该被置换出去的数据没有置换出去。在样本数为10的情况下，Redis3.0很接近真正的LRU实现。

LRU是一个预测未来我们会访问哪些数据的模型，如果我们访问数据的形式接近我们预想——幂律，那么近似LRU算法实现将能处理的很好。

在模拟测试中我们可以发现，在幂律访问模式下，理论LRU和Redis近似LRU的差距很小或者就不存在差距。

如果你将`maxmemory-samples`设置为10，那么Redis将会增加额外的CPU开销以保证接近真正的LRU性能，可以通过检查命中率来查看有什么不同。

通过`CONFIG SET maxmemory-samples <count>`动态调整样本数大小，做一些测试验证你的猜想。

转载于:https://my.oschina.net/sharesuiyue/blog/1529324

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/33d0b5bd2a184d7b8d45ea2151a6c9f0.png
[Link 1]: http://lib.csdn.net/base/datastructure
[Redis]: http://lib.csdn.net/base/redis
[lru-compare]: https://static.oschina.net/uploads/img/201709/05144305_2LLj.jpg
[Link 2]: http://lib.csdn.net/base/softwaretest