Question

redis八种淘汰策略是什么

Answer 1

1、noeviction：默认策略，不淘汰数据；大部分写命令都将返回错误（DEL等少数除外）。

2、allkeys-lru：从所有数据中根据 LRU 算法挑选数据淘汰。

3、volatile-lru：从设置了过期时间的数据中根据 LRU 算法挑选数据淘汰 。

4、allkeys-random：从所有数据中随机挑选数据淘汰。

5、volatile-random：从设置了过期时间的数据中随机挑选数据淘汰。

6、volatile-ttl：从设置了过期时间的数据中，挑选越早过期的数据进行删除。

7、allkeys-lfu：从所有数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用）。

8、volatile-lfu：从设置了过期时间的数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用）。

LRU算法：

LRU（Least Recently Used）最近最少使用。优先淘汰最近未被使用的数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

LRU底层结构是 hash 表 + 双向链表。hash 表用于保证查询操作的时间复杂度是O(1)，双向链表用于保证节点插入、节点删除的时间复杂度是O(1)。

单链表可以实现头部插入新节点、尾部删除旧节点的时间复杂度都是O(1)，但是对于中间节点时间复杂度是O(n)，因为对于中间节点c，我们需要将该节点c移动到头部，此时只知道他的下一个节点，要知道其上一个节点需要遍历整个链表，时间复杂度为O(n)。

LRU GET操作：如果节点存在，则将该节点移动到链表头部，并返回节点值。

LRU PUT操作：

1、节点不存在，则新增节点，并将该节点放到链表头部。

2、节点存在，则更新节点，并将该节点放到链表头部。