Redis的LRU缓存
Redis作为一个内存键值对存储的产品，以其高性能、多种数据类型、可选持久化且支持网络等特性成为了许多项目中的宠儿。
一般来说，缓存在获得超快的读写速度的同时，作为代替会牺牲其存储空间。Redis使用内存作为存储介质，比起传统的使用硬盘作为载体的数据库，读写速度快了许多，但是可存储的数据量也受到了内存大小的限制。在频繁的读写操作下，必然会发生对于旧数据的驱逐(eviction)，可能是删除数据，或者是置换到外存中。
Redis使用LRU作为唯一的驱逐算法(Redis4.0推出了LFU, Least Frequently Used算法，在本文的后面会提到)。本文将主要围绕Redis的最大内存限制和驱逐算法谈谈Redis作为缓存的一些细节。
Redis最大内存限制的配置
进行了Redis的最大内存配置后，Redis将按照配置使用一个确定大小的内存进行存储。
Redis最大内存有两种配置的方式，一种是在Redis运行时使用Redis的指令CONFIG SET maxmemory 100mb，可以将最大内存配置为100mb。另一种方式就是在redis.conf文件中进行配置maxmemory 100mb，也可以将最大内存配置为100mb。
将maxmemory参数置为0的时候，表示没有内存限制。在64位系统下，这是默认的配置，但是在32位系统下，最大内存限制将被设为3GB。
当Redis使用的内存达到最大内存限制的大小时，将会触发Redis的驱逐策略(eviction policies)。此时Redis可能会采取不同的行动，比如给造成内存超出限制的操作返回一个error，或者驱逐旧数据保证内存不超出限制。
Redis的驱逐策略
当Redis的内存使用达到上限时，会触发通过maxmemory-policy配置设置的驱逐策略。
具体的驱逐策略如下：
- noeviction: 如果发生了会使内存使用超出限制的操作(大部分是写操作)，则返回一个error。
- allkeys-lru: 尝试将符合LRU条件的key驱逐用来为新数据腾出空间。
- volatile-lru: 和allkeys-lru相似，不过只会驱逐设置了expire set(即有持续时间)的key。
- allkeys-random: 在所有的key中随机驱逐(比较迷)。
- volatile-random: 在设置了expire set的key中随机驱逐。
- volatile-ttl: 在设置了expire set的key中挑选**TTL(time to live)**最小的删除以腾出空间。
其中涉及到volatile的几个选项在没有设置expire set的key的情况下会像noeviction一样返回error。
驱逐策略可以在运行时动态配置，并且可以使用INFO实时监控缓存的命中情况。
以下是选择驱逐策略的几个推荐原则：
- 在有热点数据，或者不确定该选择哪种方式的时候，选择allkeys-lru。大部分情况下它的表现是最好的。
- 在数据被环形扫描访问，或者缓存中的数据访问几率呈均匀分布的时候，可以使用allkeys-random。
- 如果能提供一套对于不同TTL的数据的权衡方案，可以选用volatile-ttl。
另外值得一提的是，设置expire也会消耗内存，因此在内存压力较大，且数据并非硬性需要expire的情况下，使用allkeys-lru并且摒弃expire是一种比较好的做法。
Redis驱逐的过程
在这里非常有必要介绍一下Redis驱逐的大致流程：
- 客户端使用了Redis的指令并且造成了内存使用的增加
- Redis检查内存使用是否超出限制，如果是则按照驱逐策略进行操作
- 客户端执行新的指令，如此循环
整个流程简单来讲就是使用过量后，再通过驱逐key来使内存的用量降至限制之下。但是这样一来某个操作如果一次性增加了大量的内存使用量(比如插入一个超大的数据)，Redis的内存用量就有可能明显超出内存限制。
粗略LRU算法(Approximated LRU algorithm)
实际上Redis的LRU算法并非完全实现原版LRU算法，而是做了一些魔改。这就意味着Redis无法总是选出LRU算法的最佳的驱逐对象，即LRU中定义的最近最少访问的数据。作为代替，他会在一些基本符合要求的数据中选取最后一次访问时间最早的那个key进行驱逐。
从Redis3.0开始，该算法进行了一些改进，变得会为驱逐的对象建立一个pool。这样使得算法的性能更加接近原版LRU。
Redis的LRU算法有个好处就是用户可以调整选择对象的数量来平衡算法的精度。该参数可以通过配置maxmemory-samples 5来修改。
Redis之所以不选用原版LRU是因为原版LRU会消耗更多的内存。而且对于用户来说，Redis的LRU算法和原版LRU算法几乎是一样的，以下是一张测试结果对比图：
这个测试是通过使用一定数量的key来填充一个Redis服务器，之后按照插入顺序对所有key进行访问。这样一来按照LRU的规则，第一个被插入的数据将被选中。在此之后，插入原本插入key数量一半的key，根据LRU算法，原先插入数据的一半将被驱逐。
图中的点分别代表三种不同的数据，从左上到右下的顺序插入：
- 亮灰色代表被驱逐的点
- 深灰色代表第一批被插入并没被驱逐的数据
- 绿色表示后来新插入的数据
对比可以发现在选取样本数量均为5的情况下，Redis3.0要更接近原版LRU的结果，但是还是有较大的差别。而选取样本为10的话，则十分接近了。
需要注意的是，LRU只是一个预测数据被访问几率的模型。如果你的数据访问模式近似于幂律分布，即大部分被访问的数据都在一个确定的范围内，LRU算法的表现将会比较好。
LFU模式
Redis4.0中新增了LFU模式。该模式是通过计算数据访问频率，来进行数据到驱逐。所以热点数据保持的几率就更高。
对比起LRU算法，LFU更加可靠。试想一个很少用的数据恰好在最近刚被访问了一次，而另一个比它常用的数据最后一次访问的时间要早于它，这样就有可能将更常用的数据驱逐。LFU就避免了这一个问题。
可以通过以下驱逐策略配置LFU模式：
- volatile-lfu: 对设置了expire set的数据使用LFU进行驱逐。
- volatile-lfu: 对所有数据使用LFU进行驱逐。
LFU与LRU很相似，他维护了一个概率计数器，叫做Morris counter，仅用几个bits来估算数据的访问频率。这个值会绑定一个衰减周期，每过一段时间该值便会衰减。这样点好处在于可以在一个窗口内统计数据的访问频率。
与LRU不同的是，LFU有直接可调的参数：衰减的周期和计数器的上限。
可以通过lfu-decay-time 1和lfu-log-factor 10 进行配置(这里写的均为默认值)。衰减周期单位为分钟，计数器的上限就比较复杂。以下是一张对照表，表示不同factor下，访问次数和频率的关系：
1 | +--------+------------+------------+------------+------------+------------+ |
对于factor的定义在此就不做解释，大家可以自己感受下。
[原文链接]: https://redis.io/topics/lru-cache “lru-cache”