但是，上篇文章我们也挖了一个坑，说过现有的近似算法模拟效果还有待提高，今天这篇文章就是来填上这个坑，讲一下在<code>redis 3.0</code>中对近似lru算法的优化，既提升了算法的性能也提升了模拟效果。
redis 3.0中主要做了如下优化：
<code>lru</code>时钟的粒度从秒级提升为毫秒级
使用新的<code>api</code>来获取lru替换时的采样样本
默认的lru采样样本数从3提升为5
使用<code>eviction pool</code>来选取需要淘汰的key
提升<code>lru时钟</code>的粒度，主要是为了在测试lru算法性能时，能够在更短的时间内获取结果，更新lru时钟的方法也有所变化，如果lru时钟的时间粒度高于<code>servercron</code>刷新的时间粒度，那么就主动获取最新的时间，否则使用server缓存的时间，
在源码的<code>utils/lru</code>目录下有测试脚本，测试前需要把<code>src/redis.h</code>中的<code>redis_lru_clock_resolution</code>宏设置为1，即lru时钟的分辨率为<code>1ms</code>，然后重新编译源码，执行方式如下，
测试完成后会生成一个<code>html</code>页面，包含测试结果，以及一个图形化的插入淘汰流程
在<code>redis 2.8</code>中每次选取淘汰样本时，都是调用<code>dictgetrandomkey</code>来随机获取一个key，会根据<code>maxmemory-samples</code>配置的大小，多次调用。这个流程在<code>redis 3.0</code>中被优化为一次调用获取指定数量的<code>key</code>，且不需要每次都调用随机函数，如下，
<code>dictgetsomekeys</code>会随机从db的某个起始位置开始，连续获取指定数量的<code>key</code>，需要注意的是，如果<code>db</code>对应的字典正在做<code>rehash</code>，可能需要从两个<code>hashtable</code>来获取key。如果需要根据某种分布来随机获取字典里面的key，这种采样方式可能是不合适的，但是如果只是为了随机获取一系列key来作为lru算法的淘汰样本，这种方式是可行的。
采样性能的提升带来的好处就是，我们可以在不牺牲淘汰算法性能的情况下，提高采样的样本数，让redis的近似lru算法更接近于严格lru算法，所以目前redis把超过<code>maxmemory</code>后默认的采样样本数从<code>3</code>个提升到<code>5</code>个。
eviction pool更新逻辑代码如下，
当选取的淘汰策略和lru相关时（allkeys-lru或volatile-lru），<code>freememoryifneeded</code>会调用<code>evictionpoolpopulate</code>来更新eviction pool，然后淘汰掉eviction pool里面的最后一个元素所对应的key，这样的选取淘汰key的方式的好处是：假设说新随机选取的key的访问时间可能比历史随机选取的key的访问时间还要新，但是在redis 2.8中，新选取的key会被淘汰掉，这和lru算法利用的访问局部性原理是相违背的，在redis 3.0中，这种情况被避免了。
此外，如果某个历史选取的key的idle时间相对来说比较久，但是本次淘汰并没有被选中，因为出现了idle时间更久的key，那么在使用eviction pool的情况下，这种idle时间比较久的key淘汰概率增大了，因为它在eviction pool里面被保存下来，参与下轮淘汰，这个思路和<code>访问局部性原理</code>是契合的。
我们可以看到在前面1/2需要淘汰的key里面（<code>浅灰色</code>的点），<code>redis 3.0</code>残留下来的key明显比redis 2.8少了很多，而且后面新插入的1/2的key里面（<code>绿色</code>的点），redis 3.0没有一个淘汰的key。
redis 3.0中对于<code>lru</code>替换算法的优化，在只维护一个eviction pool带来的少量开销情况下，对算法效率的提升是比较明显的，效率的提升带来的是访问命中率的提升。同时，在目前3.4的unstable版本中我们也可以看见redis计划实现<code>lfu</code>算法以支持更丰富的业务场景，阿里云redis服务团队也会持续跟进。此外，对于<code>lirs</code>这种基于lru的改进算法，在不影响性能的前提下，我们也会研究在内核上做支持。