Redis的内存回收机制，以及LRU算法

Maxmemory配置指令回收策略LRU算法下面用JAVA代码简单实现下。回到上面留的问题，为什么要用双向链表？

说起Redis大家都不陌生，而JAVA程序员面试的时候，Redis也基本是必问的点之一。

Redis作为一款开源的nsql数据库，由于自身的高性能，一般在企业内会被作为缓存使用，像我之前的公司短信验证码缓存就用Redis实现。当新增数据时，让Redis自动地回收旧数据是件很方便的事情。LRU是Redis唯一支持的回收方法，Redis的maxmemory指令用于将可用内存限制成一个固定大小，还包括了Redis使用的LRU算法，这个实际上只是近似的LRU。

Maxmemory配置指令

maxmemory配置指令用于配置Redis存储数据时指定限制的内存大小。通过redis.conf可以设置该指令，或者之后使用CONFIG SET命令来进行运行时配置。

例如为了配置内存限制为100mb，以下的指令可以放在redis.conf文件中。 设置maxmemory为0代表没有内存限制。对于64位的系统这是个默认值，对于32位的系统默认内存限制为3GB。

当指定的内存限制大小达到时，需要选择不同的行为，也就是策略。Redis可以仅仅对命令返回错误，这将使得内存被使用得更多，或者回收一些旧的数据来使得添加数据时可以避免内存限制。

回收策略

当maxmemory限制达到的时候Redis会使用的行为由 Redis的maxmemory-policy配置指令来进行配置。

以下的策略是可用的:

noeviction:返回错误当内存限制达到并且客户端尝试执行会让更多内存被使用的命令（大部分的写入指令，但DEL和几个例外）

allkeys-lru: 尝试回收最少使用的键（LRU），使得新添加的数据有空间存放。

volatile-lru: 尝试回收最少使用的键（LRU），但仅限于在过期集合的键,使得新添加的数据有空间存放。

allkeys-random: 回收随机的键使得新添加的数据有空间存放。

volatile-random: 回收随机的键使得新添加的数据有空间存放，但仅限于在过期集合的键。

volatile-ttl: 回收在过期集合的键，并且优先回收存活时间（TTL）较短的键,使得新添加的数据有空间存放。

如果没有键满足回收的前提条件的话，策略volatile-lru,volatile-random以及volatile-ttl就和noeviction 差不多了。

选择正确的回收策略是非常重要的，这取决于你的应用的访问模式，不过你可以在运行时进行相关的策略调整，并且监控缓存命中率和没命中的次数，通过RedisINFO命令输出以便调优。

一般的经验规则:

使用allkeys-lru策略：当你希望你的请求符合一个幂定律分布，也就是说，你希望部分的子集元素将比其它其它元素被访问的更多。如果你不确定选择什么，这是个很好的选择。.

使用allkeys-random：如果你是循环访问，所有的键被连续的扫描，或者你希望请求分布正常（所有元素被访问的概率都差不多）。

使用volatile-ttl：如果你想要通过创建缓存对象时设置TTL值，来决定哪些对象应该被过期。

allkeys-lru和volatile-random策略对于当你想要单一的实例实现缓存及持久化一些键时很有用。不过一般运行两个实例是解决这个问题的更好方法。

为了键设置过期时间也是需要消耗内存的，所以使用allkeys-lru这种策略更加高效，因为没有必要为键取设置过期时间当内存有压力时。

LRU算法

那LRU算法究竟是是怎么实现的，怎么自己实现一个简易的LRU算法呢？

LRU 算法实际上是让你设计数据结构：首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个方法，一是 put(key, value) 方法存入键值对，二是 get(key) 方法获取 key 对应的 value，如果 key 不存在则返回 -1。而且get 和 put 方法必须都是 O(1)O(1) 的时间复杂度。

要让 put 和 get 方法的时间复杂度为 O(1)O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。

因为显然 cache 必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样： 思想很简单，就是借助哈希表赋予了链表快速查找的特性嘛：可以快速查找某个 key 是否存在缓存（链表）中，同时可以快速删除、添加节点。这里有个问题，为什么是双向链表，单向链表会有什么问题？

下面用JAVA代码简单实现下。

class Node { //双链表的节点类 简化算法 key val都用int类型 public int key, val; public Node next, prev; public Node(int k, int v) { this.key = k; this.val = v; } } class DoubleList { //依靠 Node 类型构建一个双链表，并实现几个O（1）复杂度的方法 private Node head, tail; // 头尾虚节点 private int size; // 链表元素数 public DoubleList() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; size = 0; } // 在链表头部添加节点 x public void addFirst(Node x) { x.next = head.next; x.prev = head; head.next.prev = x; head.next = x; size++; } // 删除链表中的 x 节点（x 一定存在） public void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; size--; } // 删除链表中最后一个节点，并返回该节点 public Node removeLast() { if (tail.prev == head) return null; Node last = tail.prev; remove(last); return last; } // 返回链表长度 public int size() { return size; } }

回到上面留的问题，为什么要用双向链表？

因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。

综合实现：

class LRUCache { // key -> Node(key, val) private HashMap<Integer, Node> map; // Node(k1, v1) <-> Node(k2, v2)... private DoubleList cache; // 最大容量 private int cap; public LRUCache(int capacity) { this.cap = capacity; map = new HashMap<>(); cache = new DoubleList(); } public int get(int key) { if (!map.containsKey(key)) return -1; int val = map.get(key).val; // 利用 put 方法把该数据提前 put(key, val); return val; } public void put(int key, int val) { // 先把新节点 x 做出来 Node x = new Node(key, val); if (map.containsKey(key)) { // 删除旧的节点，新的插到头部 cache.remove(map.get(key)); cache.addFirst(x); // 更新 map 中对应的数据 map.put(key, x); } else { if (cap == cache.size()) { // 删除链表最后一个数据 Node last = cache.removeLast(); map.remove(last.key); } // 直接添加到头部 cache.addFirst(x); map.put(key, x); } } }

这就是LRU算法的具体思路以及实现，希望对大家能有帮助。写的不好，仅供参考。

代码参考：力扣博主labuladong

扫码关注峡谷程序猿公众号，一起学习精进java技术！ [免费获取更多学习资料]