Skip to content

redis LRU策略是如何实现的

Redis 为了在性能和内存使用之间取得平衡，并没有实现传统意义上精确的 LRU（Least Recently Used，最近最少使用）算法，而是采用了一种近似 LRU 算法。

传统 LRU 算法原理

首先，理解标准的 LRU 算法是理解 Redis 实现的基础。标准的 LRU 算法通常通过哈希表 + 双向链表实现：

  • 哈希表 (Hash Table): 用于存储键和对应链表节点的映射，确保可以 O(1) 复杂度快速查找到数据。
  • 双向链表 (Doubly Linked List): 用于维护数据的访问顺序。所有数据都在这个链表中，链表头部是最近访问的数据，尾部是最久未访问的数据。

工作流程如下： 1. 数据访问： 当一个数据被访问时，通过哈希表找到其在链表中的位置，然后将其移动到链表头部。 2. 数据新增： 新数据插入时，会创建一个新节点并放置在链表头部。 3. 数据淘汰： 当缓存空间已满需要淘汰数据时，直接将链表尾部的节点移除。

这种实现的优点是算法精度高，总能淘汰掉最久未使用的数据。但缺点是需要额外的内存空间来维护双向链表，并且每次数据访问都需要移动链表节点，在高并发场景下会带来性能开销。

Redis 的近似 LRU 算法实现

考虑到内存占用和性能问题，Redis 的作者认为严格的 LRU 实现过于复杂和耗费资源。 因此，Redis 采用了牺牲一部分准确性来换取更高效率和更少内存占用的近似 LRU 算法。

其核心实现依赖于以下两点：

a. 在 redisObject 中记录访问时间戳

Redis 的每个键值对都是一个 redisObject 对象。在这个对象结构中，有一个名为 lru 的 24 位（bit）字段。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:24; // 在LRU模式下，记录最后一次访问的时间戳
    int refcount;
    void *ptr;
} robj;
  • 当启用了 LRU 相关的淘汰策略时，这个 lru 字段会存储一个相对于全局时钟 server.lruclock 的时间戳。
  • 每次一个键被访问（读取或修改）时，Redis 就会更新这个键对应 redisObject 的 lru 字段为当前的 server.lruclock 值。
  • 由于 lru 字段只有 24 位，按秒为单位的时间戳大约能存储 194 天，超过后会发生回绕（wrap around），但这对于缓存场景来说通常足够了。

b. 基于随机采样的淘汰机制

当 Redis 的内存使用达到 maxmemory 上限并需要触发淘汰时，它并不会遍历所有的键来找出那个 lru 值最小（即最久未访问）的键。 这样做会非常耗时。

取而代之的是，Redis 执行以下步骤：

  1. 随机采样： 从所有的键中，随机选取 N 个键（这个 N 值可以通过 maxmemory-samples 参数配置，默认为 5）。
  2. 比较淘汰： 比较这 N 个被采样键的 lru 时间戳，将其中时间戳最小（也就是最久没有被访问）的那个键淘汰出去。
  3. 循环执行： 这个淘汰过程会一直执行，直到内存使用降到 maxmemory 限制以下。

Redis 3.0 及以后的优化：

为了提高近似 LRU 算法的精度，Redis 3.0 引入了一个候选池 (eviction pool)。

  • 这个候选池大小为 16，用于存放待淘汰的候选键。
  • 随机采样出的 N 个键会和候选池中的键进行比较。
  • 新采样的键如果其空闲时间（server.lruclock - key.lru）大于候选池中空闲时间最小的键，则会进入候选池，并挤掉原来池中空闲时间最小的键。
  • 最终需要淘汰时，会从候选池中选择空闲时间最长的键进行淘汰。

通过这种方式，采样过程可以逐步筛选出更接近全局最久未被访问的键，使得算法效果更逼近真实的 LRU。

Redis LRU 策略的优缺点

优点：

  • 节省内存： 无需像传统 LRU 那样维护一个庞大的双向链表，极大地节省了内存空间。
  • 性能高： 避免了每次数据访问时对链表的复杂操作，只在需要淘汰时进行采样和比较，性能损耗小。
  • 精度可调： 通过调整 maxmemory-samples 参数，可以在算法精度和性能之间进行权衡。采样值越大，算法越接近真实 LRU，但性能消耗也相应增加。

缺点：

  • 非严格精确： 由于是近似实现，无法保证每次都淘汰掉全局最久未被使用的键，可能会误淘汰一些相对较热的数据。
  • 缓存污染问题： LRU 算法的一个固有缺陷是，如果一个很久未被访问的数据被偶然访问了一次，它的排名会立刻提前，导致真正频繁访问的热点数据可能因为最近没有被访问而被淘汰。 为了解决这个问题，Redis 4.0 引入了 LFU（最不常用）策略。