在 Redis 中， LRU（Latest Recently Used，最近最少使用） 是一种非常常见的缓存淘汰算法。它用于管理 Redis 的内存使用，当 Redis 达到最大内存限制时，决定哪些键应该被删除，从而腾出空间给新的数据。

一、LRU 算法概述

LRU(Least Recently Used，最近最少使用)算法是一种缓存淘汰算法，其核心思想是：在缓存空间有限的情况下，当缓存满时，应该淘汰最久没有被使用的数据。换句话说，LRU 算法会清除那些最久未被访问的缓存数据，以腾出空间存储新的数据。

1.1 LRU 算法的工作原理

• 每当访问一个缓存项时（无论是读取还是写入），该缓存项都会被标记为最近访问过的。
• 当缓存空间已满，需要淘汰数据时，LRU 算法会删除最近最少访问的数据项，即链表尾部的数据项。

以下是一个LRU算法示意图：

1. 向一个缓存空间依次插入三个数据A/B/C，填满了缓存空间；
2. 读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
3. 插入数据D的时候，由于缓存空间已满，触发了LRU的淘汰策略，数据B被移出，缓存空间只保留了D/A/C。

一般而言，LRU算法的数据结构不会如示意图那样，仅使用简单的队列或链表去缓存数据，而是会采用Hash表 + 双向链表的结构，利用Hash表确保数据查找的时间复杂度是O(1)，双向链表又可以使数据插入/删除等操作也是O(1)。

1.2 手写LRU

手写一个 LRU（Least Recently Used） 缓存实现，通常使用 哈希表（HashMap） 和 双向链表（Doubly Linked List） 的组合来实现。哈希表用于存储数据项的引用，双向链表用于维护数据项的访问顺序，链表头部表示最近访问的数据，链表尾部表示最久未访问的数据。

下面是一个简单的 LRU 缓存的手写实现，使用 Java 实现了基本的 get() 和 put() 操作。

import java.util.HashMap;public class LRUCache {// 双向链表节点类class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}private final int capacity;  // 缓存最大容量private HashMap<Integer, Node> cache;  // 存储数据private Node head, tail;  // 双向链表的头尾节点// 构造方法，初始化容量和头尾节点public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();// 创建伪头尾节点，方便操作head = new Node(0, 0);tail = new Node(0, 0);// 初始化头尾节点连接head.next = tail;tail.prev = head;}// 获取数据public int get(int key) {Node node = cache.get(key);if (node == null) {System.out.println("缓存中没有该数据，key: " + key);return -1;  // 数据不存在，返回 -1}// 将访问的节点移动到链表头部moveToHead(node);System.out.println("访问数据，key: " + key + ", value: " + node.value);return node.value;}// 插入数据public void put(int key, int value) {Node node = cache.get(key);if (node == null) {// 如果缓存没有该数据，创建新节点Node newNode = new Node(key, value);cache.put(key, newNode);// 将新节点插入到链表头部addNode(newNode);System.out.println("插入新数据，key: " + key + ", value: " + value);if (cache.size() > capacity) {// 如果缓存超出容量，移除链表尾部节点Node tailNode = removeTail();cache.remove(tailNode.key);System.out.println("缓存已满，淘汰最久未使用的数据，key: " + tailNode.key);}} else {// 如果缓存已有该数据，更新值并移动到链表头部node.value = value;moveToHead(node);System.out.println("更新数据，key: " + key + ", 新值: " + value);}printCacheStatus();  // 打印当前缓存状态}// 将节点移动到链表头部（表示最近访问）private void moveToHead(Node node) {removeNode(node);addNode(node);}// 将节点添加到链表头部private void addNode(Node node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}// 从链表中移除节点private void removeNode(Node node) {Node prev = node.prev;Node next = node.next;prev.next = next;next.prev = prev;}// 删除链表尾部节点（最久未使用的节点）private Node removeTail() {Node res = tail.prev;removeNode(res);return res;}// 打印当前缓存状态private void printCacheStatus() {System.out.print("当前缓存状态：");Node current = head.next;while (current != tail) {System.out.print("{" + current.key + "=" + current.value + "} ");current = current.next;}System.out.println();}// 测试public static void main(String[] args) {LRUCache cache = new LRUCache(2); // 设置缓存容量为 2cache.put(1, 1);  // 缓存: {1=1}cache.put(2, 2);  // 缓存: {1=1, 2=2}System.out.println("获取数据：key=1, 返回值=" + cache.get(1));  // 返回 1，缓存: {2=2, 1=1}cache.put(3, 3);  // 缓存: {1=1, 3=3}，淘汰键 2System.out.println("获取数据：key=2, 返回值=" + cache.get(2));  // 返回 -1 (未找到)cache.put(4, 4);  // 缓存: {3=3, 4=4}，淘汰键 1System.out.println("获取数据：key=1, 返回值=" + cache.get(1));  // 返回 -1 (未找到)System.out.println("获取数据：key=3, 返回值=" + cache.get(3));  // 返回 3，缓存: {4=4, 3=3}System.out.println("获取数据：key=4, 返回值=" + cache.get(4));  // 返回 4，缓存: {4=4, 3=3}}
}

输出：

二、Redis 中的 LRU 算法

Redis 实现 LRU 算法时并没有精确计算每个数据的使用顺序，而是采用了 近似算法 来提高效率。Redis 利用 采样算法 来模拟 LRU 行为，而不是每次访问时都更新所有元素的访问顺序，Redis 的 LRU 实现称为 LRU-K（LRU-K Sampling）。

Redis内部只使用Hash表缓存了数据，并没有创建一个专门针对LRU算法的双向链表，之所以这样处理也是因为以下几个原因：

• 筛选规则，Redis是随机抽取一批数据去按照淘汰策略排序，不再需要对所有数据排序；
• 性能问题，每次数据访问都可能涉及数据移位，性能会有少许损失；
• 内存问题，Redis对内存的使用一向很“抠门”，数据结构都很精简，尽量不使用复杂的数据结构管理数据；
• 策略配置，如果线上Redis实例动态修改淘汰策略会触发全部数据的结构性改变，这个Redis系统无法承受的。

2.1 近似 LRU 算法

Redis的LRU 近似算法是指每次访问数据时并不会更新所有元素的顺序，而是通过随机抽取一定数量的键，估算这些键的使用频率来决定哪些键应该被淘汰。这种近似的方式避免了每次都精确计算访问顺序，减少了性能开销。在缓存满的时候，Redis 选择最近最少使用的元素进行淘汰。

2.2 如何判断“最近最少使用”的键？

它的基本思路是：

• 定期从缓存中随机挑选一部分数据。
• 对这些随机选中的数据，检查它们的使用情况，找出最久未使用的键进行淘汰。

采样的大小 是一个重要的参数。默认情况下，Redis 会随机抽取 10 个键，通过这些键来估算哪个是最近最少使用的。抽样的数量可以通过配置参数调整。

2.3 Redis 中的 LRU 配置

Redis 提供了两个关键的配置项来控制 LRU 淘汰策略：

• maxmemory：配置 Redis 的最大内存。一旦Redis 的内存使用超过该阈值，Redis 会根据maxmemory-policy配置策略，执行内存淘汰操作。
• maxmemory-policy：配置内存达到限制时，Redis 应该使用哪种淘汰策略。Redis 支持多种内存淘汰策略，其中与 LRU 相关的有以下几种：
  • allkeys-lru：对所有的键使用 LRU 淘汰策略，即当内存达到限制时，Redis 会移除最久未被访问的键。
  • volatile-lru：仅对设置了过期时间的键使用 LRU 淘汰策略，意味着只有那些设置了 TTL（过期时间）的键会根据 LRU 策略被淘汰。
  • allkeys-random：随机移除键，使用随机的方式淘汰数据。
  • volatile-random：仅删除那些设置了过期时间的键，并且使用随机策略。
  • volatile-ttl：仅删除设置了过期时间的键，并且删除那些即将过期的键。

示例：

maxmemory 100mb           # 设置最大内存为 100MB
maxmemory-policy allkeys-lru  # 设置内存达到限制时，使用 LRU 淘汰策略