为什么Redis使用近似LRU算法来淘汰数据而不是真正的LRU？

在《??Redis 数据缓存满了怎么办???》中我们知道Redis缓存满后，可以通过淘汰策略删除数据，为新数据腾出空间。淘汰策略如下：Redis内存淘汰设置过期时间keyvolatile-ttl、volatile-random、volatile-lru、volatile-lfu这四种策略淘汰的数据范围是设置了过期时间的数据。keyallkeys-lru、allkeys-random、allkeys-lfu这三种淘汰策略都会在内存不足时被淘汰，不管这些键值对是否设置过期时间。这意味着即使它的过期时间还没有到，它也会被删除。当然，如果过了过期时间，即使没有被淘汰策略选中，也会被删除。volatile-ttl和volatile-randon很简单，重点是volatile-lru和volatile-lfu，涉及到LRU算法和LFU算法。今天码哥就带大家一起来解决Redis的LRU算法。什么是近似LRU算法？什么是LRU算法？LRU算法的整个过程是LeastRecentlyUsed。其核心思想是“如果数据最近被访问过，那么它将来被访问的机会就更高”。我们把所有的数据组织成一个链表：MRU：表示链表的头部，代表最近访问的数据。LRU：代表链表的尾部，代表最近最少使用的数据。LRU算法可以发现，LRU更新和新数据插入都发生在链表的头部，删除数据发生在链表的尾部。被访问的数据会被移动到MRU侧，被访问数据之前的数据会相应地向后移动一位。使用单向链表可以吗？如果使用单向链表，删除这个节点需要O(n)遍历找到前驱节点。因此，如果选择双向链表，删除时也可以在O(1)内完成。Redis是否使用这种LRU算法来管理所有的缓存数据？不行，由于LRU算法需要用一个链表来管理所有的数据，会造成大量额外的空间消耗。另外，当访问大量节点时，会发生频繁的链表节点移动操作，从而降低Redis的性能。所以Redis简化了算法。RedisLRU算法并不是真正的LRU。Redis对少量键进行采样，剔除采样数据中时间最长未被访问的键。这意味着Redis无法从数据库中驱逐最旧的访问数据。RedisLRU算法的一个重要点是可以通过改变样本的数量来调整算法的精度，使其近似接近真实的LRU算法，同时避免内存消耗，因为只需要少量的样本每次采样而不是所有数据。配置如下：maxmemory-samples50的运行原理大家还记得数据结构redisObject中有一个lru字段，用来记录每条数据最后一次被访问的时间戳。typedefstructredisObject{无符号类型：4；无符号编码：4；/*LRU时间（相对于全局lru_clock）或*LFU数据（最低有效8位频率*和最高有效16位访问时间）。*/无符号lru:LRU_BITS;int重新计票；void*ptr;}robj;Redis在淘汰数据时，会随机选择第一次的N条数据放入候选集中，淘汰lru字段值最小的数据。当需要再次淘汰数据时，会重新选择数据放入第一次创建的候选集中，但是有一个选择标准：进入集合的数据的lru值必须小于最小的lru值在候选集中。如果进入候选集的新数据数量达到了maxmemory-samples设置的值，则淘汰候选集中lru最小的数据。这样大大减少了链表节点的数量，同时不需要每次访问数据时都移动链表节点，大大提高了性能。LRUCacheLinkedHashMap在Java中的实现充分利用了Java中LinkedHashMap的实现，可以通过组合或继承来实现，“码哥”以组合的形式完成。公共类LRUCache{privateMap地图；私有最终int缓存大小；publicLRUCache(intinitialCapacity){map=newLinkedHashMap(initialCapacity,0.75f,true){@OverrideprotectedbooleanremoveEldestEntry(Map.Entryelderest){返回大小()>cacheSize;}};this.cacheSize=initialCapacity;}}重点是LinkedHashMap的第三个构造函数，构造参数accessOrder设置为true，表示LinkedHashMap内部维护访问顺序。另外，需要重写removeEldestEntry()。如果该函数返回true，则表示移除最长时间未被访问的节点，从而实现数据的淘汰。自己实施。代码取自LeetCode146.LRUCache。代码中有注释。importjava.util.Map;importjava.util.concurrent.ConcurrentHashMap;/***将最久未被使用的元素放在链头，将刚刚添加或访问的元素放在链尾链的*/classLRUCache{classNode{intkey,value;节点前、后；Node(intkey,intvalue){this.key=key;this.value=值；前=这个；接下来=这个；}}privatefinalintcapacity;//LRUCachecapacityprivateNodedummy;//dummy节点为冗余节点，dummy的next为链表的第一个节点，dummy的pre为链表的最后一个节点linkedlistprivateMapcache;//保存key-Node对，Node为双向链表节点publicLRUCache(intcapacity){this.capacity=capacity;虚拟=新节点(0,0);缓存=新的ConcurrentHashMap<>();}publicintget(intkey){Nodenode=cache.get(key);if(node==null)返回-1；删除（节点）；添加（节点）；返回节点值；}publicvoidput(intkey,intvalue){Nodenode=cache.得到（钥匙）；如果（节点==null）{if(cache.size()>=capacity){缓存。删除（虚拟。下一个。键）；删除（虚拟。下一个）；}节点=新节点（键，值）；缓存。放（键，节点）；添加（节点）；}else{cache.remove(node.key);删除（节点）；节点=新节点（键，值）；缓存.put（键，节点）；添加（节点）；}}/***在列表末尾添加一个新节点**@paramnodenewnode*/privatevoidadd(Nodenode){dummy.pre.next=node;node.pre=dummy.pre;node.next=虚拟；dummy.pre=节点；}/***从双向链表中删除节点**@paramnode要删除的节点*/privatevoidremove(Nodenode){node.pre.next=node.next;node.next.pre=node.pre;}}