缓存算法 #07：Redis LRU 近似算法

Redis 没有使用精确 LRU（双向链表），而是通过随机采样实现近似 LRU，同时在 4.0 版本引入了近似 LFU（基于 Morris 计数器）。本文深入两种算法的实现细节、误差分析，以及 8 种淘汰策略的适用场景。

相关文章：LRU（最近最少使用） · LFU（最少使用频率） · W-TinyLFU 与 Caffeine

目录

为什么不用精确 LRU

精确 LRU 需要：
  每个 key 对应一个双向链表节点（多两个指针 = 16B）
  每次 get 调用：将节点移到链表头部（写两个指针）
  
Redis 的问题：
  1. 内存开销：Redis 以内存效率著称，16B 额外指针不可接受
     一个 128-byte 的字符串 key，多 16B = 开销增加 12%
  
  2. 移动开销：Redis 是单线程，每次 get 修改链表
     高并发 get（百万 QPS）下，链表移动成为 CPU 热点

  3. 等效收益低：精确 LRU 与近似 LRU 在命中率上差异 < 5%
     工程上没有必要为 5% 的提升付出 12% 的内存

Redis 的解法：
  每个 redisObject 只存一个 24-bit 的 lru_clock（3 字节，复用已有字段）
  淘汰时随机采样 N 个 key，选 lru_clock 最小的（最久未用的）驱逐

近似 LRU：lru_clock

redisObject 的 lru 字段

// Redis 源码：server.h
typedef struct redisObject {
    unsigned type:4;        // 4 bit：对象类型（string/list/hash...）
    unsigned encoding:4;    // 4 bit：编码方式（raw/int/ziplist...）
    unsigned lru:LRU_BITS;  // 24 bit：LRU_BITS=24，存最近访问时间戳
    int refcount;           // 引用计数
    void *ptr;              // 指向实际数据
} robj;

// lru 字段：精度为 1 秒，以 LRU_CLOCK_RESOLUTION（1000ms）为单位
// 24 bit 最大值 = 2^24 秒 ≈ 194 天（超过后回绕到 0）

lru_clock 的读取与更新

# 全局时钟（server.lruclock），每 100ms 更新一次（event loop 中）
server.lruclock = (server.unixtime / LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX

# key 被访问时（get/set）
def touch_key(key):
    key.lru = server.lruclock    # O(1)，只写一个字段，无链表操作

# 计算 key 的空闲时间（秒）
def idle_time(key):
    now  = server.lruclock
    last = key.lru
    if now >= last:
        return (now - last) * LRU_CLOCK_RESOLUTION / 1000
    else:
        # 时钟回绕（超过 194 天）
        return (LRU_CLOCK_MAX - last + now + 1) * LRU_CLOCK_RESOLUTION / 1000

随机采样淘汰

# maxmemory-samples：采样数量，默认 5，增大提升精度但增加 CPU
def perform_lru_eviction():
    best_key   = None
    best_idle  = -1

    for _ in range(maxmemory_samples):
        candidate = random_key_from_db()    # 从所有 key 中随机取一个
        idle       = idle_time(candidate)

        if idle > best_idle:
            best_idle = idle
            best_key  = candidate

    evict(best_key)    # 驱逐空闲时间最长的

精度分析：

采样 5 个：命中率约为精确 LRU 的 75%（差 25%）
采样 10 个：约 90%
采样 25 个：接近精确 LRU（差 < 1%）

Redis 4.0 改进：维护一个"淘汰池"（eviction pool，默认 16 个）
  每次新采样加入淘汰池，保留 idle 最大的 16 个
  下次淘汰时从池中选最大 idle，避免重复随机浪费

近似 LFU：Morris 计数器

Redis 4.0 引入 LFU 策略，对 lru 字段的解释改变：

lru 字段（24 bit）重新分配：
  高 16 bit：ldt（Last Decrement Time，上次频率衰减的分钟时间戳）
  低  8 bit：logc（Logarithmic Counter，对数频率计数器，0~255）

logc 的范围：0~255，8 bit（只能存 255 的值，但需要表示百万次访问）
解法：Morris 近似计数器（对数计数）

Morris 计数器（对数递增）

# 每次访问时，不是直接 logc += 1
# 而是以越来越小的概率递增，使 logc 近似表示 log(访问次数)

LFU_INIT_VAL = 5  # 新 key 的初始频率（避免立刻被驱逐）

def lfu_log_incr(counter):
    if counter == 255:
        return 255    # 已达上限，不再增加
    r = random()      # [0.0, 1.0) 的随机数
    # LFU_DECAY_FACTOR 默认为 10
    # counter 越大，递增概率越小
    p = 1.0 / ((counter - LFU_INIT_VAL) * LFU_DECAY_FACTOR + 1)
    if r < p:
        counter += 1
    return counter

# 概率递减表（近似）：
# counter=5：p≈1.0（几乎必增）
# counter=10：p≈1/50
# counter=50：p≈1/450
# counter=255：p=0（不再增加）
# 效果：logc=10 对应约访问 100 次，logc=100 对应约访问 1000 次

时间衰减（解决历史频率污染）

# ldt：上次衰减的分钟时间戳（不是秒！精度更粗）
# 每隔 lfu_decay_time 分钟，logc 减 1

def lfu_decrr_counter(lfu_val):
    counter    = lfu_val & 0xFF           # 低 8 bit
    ldt        = (lfu_val >> 8) & 0xFFFF  # 高 16 bit（分钟时间戳）
    now_min    = (unix_time() / 60) & 0xFFFF

    # 计算经过了多少分钟
    if now_min >= ldt:
        elapsed = now_min - ldt
    else:
        elapsed = 0xFFFF - ldt + now_min + 1    # 时钟回绕

    # 每隔 lfu_decay_time 分钟，计数器减 1
    num_decr = elapsed // lfu_decay_time   # lfu_decay_time 默认 1 分钟
    counter  = max(counter - num_decr, 0)

    # 更新 ldt 为当前时间
    new_ldt = now_min
    return (new_ldt << 8) | counter

8 种淘汰策略

完整伪代码

performEvictions（淘汰主流程）

def performEvictions():
    # 检查是否超过 maxmemory
    mem_used = get_used_memory()
    if mem_used <= maxmemory:
        return EVICT_OK

    # 根据 maxmemory_policy 选择淘汰目标
    if policy == NOEVICTION:
        return EVICT_FAIL    # 直接报错 OOM

    # 选择候选 key 的范围
    if policy in (VOLATILE_LRU, VOLATILE_LFU, VOLATILE_RANDOM, VOLATILE_TTL):
        key_pool = keys_with_expire()   # 只考虑有 TTL 的 key
    else:
        key_pool = all_keys()

    # 选出驱逐目标
    if policy in (ALLKEYS_RANDOM, VOLATILE_RANDOM):
        best_key = random_key(key_pool)

    elif policy in (ALLKEYS_LRU, VOLATILE_LRU):
        # 维护淘汰池（eviction pool，size=16）
        fill_eviction_pool(key_pool)         # 随机采样更新淘汰池
        best_key = eviction_pool.max_idle()  # 池中空闲时间最长的

    elif policy in (ALLKEYS_LFU, VOLATILE_LFU):
        fill_eviction_pool_lfu(key_pool)     # 采样，按 logc 排序
        best_key = eviction_pool.min_freq()  # 池中频率最低的

    elif policy == VOLATILE_TTL:
        best_key = key_with_nearest_expire(key_pool)  # 最快过期的

    # 执行驱逐
    delete_key(best_key)
    notify_keyspace_event("evicted", best_key)
    return EVICT_OK

执行追踪

maxmemory=100MB，policy=allkeys-lru，samples=5，pool=16：

step1：内存使用达到 105MB（超过 maxmemory）
       触发 performEvictions()

step2：从所有 key 中随机采样 5 个：
       K_a: idle=0.5s，K_b: idle=3.2s，K_c: idle=0.1s，
       K_d: idle=8.7s，K_e: idle=1.1s

step3：与 eviction_pool 合并，保留 idle 最大的 16 个
       新增 K_d(8.7s) 进入 pool（可能替换 pool 中 idle 最小的）

step4：pool 中 idle 最大的是 K_old(15.3s)（上轮留下的）
       → 驱逐 K_old，释放约 1~10 KB

step5：检查内存是否降到 maxmemory 以下
       → 未达到：继续采样驱逐
       → 达到：退出淘汰循环

注意：每次写操作前都会检查并执行淘汰，Redis 主线程不会阻塞太久
     单次淘汰 O(samples) = O(5)，极快

异常场景

lru_clock 回绕（运行超过 194 天）

lru_clock 是 24-bit，最大 2^24 ≈ 1.67×10^7 秒 ≈ 194 天
超过后从 0 重新开始

idle_time 计算：
  if server.lruclock >= key.lru:
      idle = server.lruclock - key.lru    # 正常情况
  else:
      # 时钟回绕：lruclock 已绕回，key.lru 还在高位
      idle = LRU_CLOCK_MAX - key.lru + server.lruclock + 1

风险：
  若 key.lru 恰好在回绕点附近，idle 计算可能偏小（误以为刚访问）
  实际影响极小（194 天内所有 key 都至少被更新一次）
  Redis 默认接受这个误差

maxmemory-samples 设置过大

问题：samples=100 → 每次淘汰随机扫描 100 个 key → CPU 开销上升
     Redis 单线程：每次淘汰阻塞主线程

建议：
  默认 samples=5（精度和性能平衡）
  内存敏感场景可调到 10（提升精度）
  不建议超过 20（CPU 代价不值）

volatile-lru 无过期 key 时

场景：policy=volatile-lru，但所有 key 都没有 TTL

performEvictions 找不到候选 key
→ 等效 noeviction（写入失败，返回 OOM error）

建议：
  若 Redis 专做缓存 → 用 allkeys-lru（不依赖 TTL）
  若混合使用 → 确保缓存 key 都设了 TTL

参考资料

• Redis 源码：evict.c，server.h（redisObject 结构）
• Redis 官方文档：https://redis.io/docs/manual/eviction/
• Antirez 博客：http://antirez.com/news/109（LFU 设计原文）