详解Redis的LRU算法

比如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的过程中，其实是知道了N个Key的idle time的情况的，那我能不能在下一轮移除Key时，利用好上一轮知晓的一些信息？

However if you think at this algorithm across its executions, you can see how we are trashing a lot of interesting data. Maybe when sampling the N keys, we encounter a lot of good candidates, but we then just evict the best, and start from scratch again the next cycle.

start from scratch太傻了。于是Redis又做出了改进：采用缓冲池(pooling)

当每一轮移除Key时，拿到了这个N个Key的idle time，如果它的idle time比 pool 里面的 Key的idle time还要大，就把它添加到pool里面去。这样一来，每次移除的Key并不仅仅是随机选择的N个Key里面最大的，而且还是pool里面idle time最大的，并且：pool 里面的Key是经过多轮比较筛选的，它的idle time 在概率上比随机获取的Key的idle time要大，可以这么理解：pool 里面的Key 保留了"历史经验信息"。

Basically when the N keys sampling was performed, it was used to populate a larger pool of keys (just 16 keys by default). This pool has the keys sorted by idle time, so new keys only enter the pool when they have an idle time greater than one key in the pool or when there is empty space in the pool.

采用"pool"，把一个全局排序问题 转化成为了 局部的比较问题。(尽管排序本质上也是比较，囧)。要想知道idle time 最大的key，精确的LRU需要对全局的key的idle time排序，然后就能找出idle time最大的key了。但是可以采用一种近似的思想，即随机采样(samping)若干个key，这若干个key就代表着全局的key，把samping得到的key放到pool里面，每次采样之后更新pool，使得pool里面总是保存着随机选择过的key的idle time最大的那些key。需要evict key时，直接从pool里面取出idle time最大的key，将之evict掉。这种思想是很值得借鉴的。

至此，基于LRU的移除策略就分析完了。Redis里面还有一种基于LFU（访问频率）的移除策略，后面有时间再说。

JAVA 里面的LRU实现

JDK中的LinkedHashMap实现了LRU算法，使用如下构造方法，accessOrder 表示"最近最少未使用"的衡量标准。比如accessOrder=true，当执行java.util.LinkedHashMap#get元素时，就表示这个元素最近被访问了。

/**
     * Constructs an empty LinkedHashMap instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - true for
     *         access-order, false for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

再重写：java.util.LinkedHashMap#removeEldestEntry方法即可。

The {@link #removeEldestEntry(Map.Entry)} method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

为了保证线程安全，用Collections.synchronizedMap将LinkedHashMap对象包装起来:

Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map.

实现如下：(org.elasticsearch.transport.TransportService)

final Map timeoutInfoHandlers =
        Collections.synchronizedMap(new LinkedHashMap(100, .75F, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 100;
            }
        });

当容量超过100时，开始执行LRU策略：将最近最少未使用的 TimeoutInfoHolder 对象 evict 掉。

参考链接：

• Random notes on improving the Redis LRU algorithm
• Using Redis as an LRU cache

最后，再扯一点与本文不相关的东西：关于数据处理的一些思考：
5G有能力让各种各样的节点都接入网络，就会产生大量的数据，如何高效地处理这些数据、挖掘数据(机器学习、深度学习)背后的隐藏的模式是一件非常有趣的事情，因为这些数据其实是人类行为的客观反映。举个例子，微信运动的计步功能，会让你发现：哎，原来每天我的活动量大概保持在1万步左右。再深入一步，以后各种工业设备、家用电器，都会产生各种各样的数据，这些数据是社会商业活动的体现，也是人类活动的体现。如何合理地利用这些数据呢？现有的存储系统能支撑这些数据的存储吗?有没有一套高效的计算系统(spark or tensorflow...)分析出数据中隐藏的价值？另外，基于这些数据训练出来的算法模型应用之后会不会带来偏见？有没有滥用数据？网上买东西有算法给你推荐，刷朋友圈会给你投针对性的广告，你需要借多少钱，贷多少款也会有模型评估，看新闻、看娱乐八卦也有算法推荐。你每天看到的东西、接触的东西，有很多很多都是这些"数据系统"做的决策，它们真的公平吗？在现实中如果你犯了错，有老师、朋友、家人给你反馈、纠正，你改了，一切还可以从头开始。可在这些数据系统之下呢？有纠错反馈机制吗？会不会刺激人越陷越深？就算你很正直、有良好的信用，算法模型也可能存在概率偏差，这是不是影响人类"公平竞争"的机会？这些都是数据开发人员值得思考的问题。

原文：https://www.cnblogs.com/hapjin/p/10933405.html

以上就是详解Redis的LRU算法的详细内容，更多请关注其它相关文章！