自适应混合淘汰算法 AHE

一种自调优的缓存淘汰算法：将「时间局部性、访问频率、TTL 紧急度」融合为单一分数，并依据实时命中率反馈自动调整自身权重。

• 状态： 原创算法，自 v0.3 起提供
• 源码： src/storage/eviction.rs
• 相关： 白皮书 §9.5

---

摘要

经典的缓存淘汰策略被迫做固定取舍：LRU 对突发流量反应快，却无力抵抗扫描污染，也无法识别长期热点；LFU 能保护稳定热点，但存在冷启动缺陷——刚到达的热点键频率低，还没热起来就被淘汰。当访问模式在运行中切换时，两者都无法自适应。

AHE（Adaptive Hybrid Eviction，自适应混合淘汰） 用一个统一的 淘汰优先级分数（EPS, Eviction Priority Score） 融合三个信号来解决：

• recency（最近度） —— 键距上次访问有多久（LRU 直觉），
• infrequency（稀访问度） —— 键被访问得有多稀少（LFU 直觉），
• TTL 紧急度 —— 键是否即将过期。

recency 与 frequency 之间的混合权重 alpha 不是需要运维人员手调的旋钮——它由反馈控制器驱动，监视引擎观测到的命中率，并朝当前负载所"奖励"的方向微调 alpha。最终效果是：同一个淘汰策略在突发时表现得像 LRU，在稳定热点时表现得像 LFU，且无需任何人工干预。

---

1. 设计动机

负载场景	LRU	LFU	问题
突发热点（秒杀）	✅	❌	LFU 冷启动，新热点频率低被误淘汰
稳定热点	❌	✅	LRU 在闲置一次读取后就丢弃长期热点
扫描污染（全表遍历）	❌	✅	LRU 让冷扫描键驱逐热数据
即将过期的键	❌	❌	两者都不感知 TTL，将死的键白白占槽
访问模式切换	❌	❌	固定策略无法跟随变化

核心思想。 为每个采样候选计算一个统一分数，分数最高者最应被淘汰。此外，由一个控制器依据观测命中率调整 recency/frequency 权重。

---

2. 淘汰优先级分数（EPS）

EPS = alpha · recency + (1 − alpha) · infrequency + ttl_penalty

EPS 越高 ⇒ 越该被淘汰。每一项都归一化到 [0, 1]，使三个信号可直接比较。

项	定义	含义
recency	min((now − last_access) / 600s, 1.0)	越久未访问得分越高
infrequency	1 − lfu_counter / 255	越冷得分越高（复用共享的 Morris 计数器）
ttl_penalty	剩余 TTL ≤ 30s 或 已过期时 +0.2；否则 0	让 AHE 优先清理将死的键
alpha	自适应权重，夹在 [0.05, 0.95]	→ 1.0 偏向 LRU，→ 0.0 偏向 LFU

recency 采用 600 秒窗口（RECENCY_HORIZON）：闲置 10 分钟的键即为"最陈旧"，无论再等多久都记 1.0。infrequency 复用驱动 *-lfu 策略的同一个 lfu_counter（Morris 计数器，0..=255），因此 AHE 的每键额外内存为零。

设计注记。 早期草稿使用 log2 频率归一化与 1/(1+elapsed) 时间衰减。最终版本改为共享 LFU 的 Morris 计数器加线性 recency 梯度——这让 AHE 的元数据存储开销恰好为零，并直接与 Redis 兼容的数据结构挂钩。

---

3. 自适应权重控制器（alpha）

alpha 存于 AdaptiveHybridState，是一个由引擎命中率驱动的 1 维梯度搜索。引擎在每次成功淘汰后调用 observe(hits, misses)；当积累满 window_size（默认 64）个样本时，控制器更新 alpha。

字段	默认值	作用
alpha	0.5	当前 recency/frequency 混合比
step	0.05	每次调整幅度
direction	+1.0	上次移动的符号；回归时翻转
last_hit_ratio	0.0	上一窗口命中率（回归检测器）
window_size	64	两次调整间的样本数（噪声过滤）
window_count	0	当前窗口已积累样本数

observe(hits, misses):
    window_count += 1
    if window_count < window_size:
        return                       # 仍在积累样本

    ratio = hits / (hits + misses)
    if ratio + 1e-4 < last_hit_ratio:
        direction = -direction       # 命中率回退 → 反向
    alpha = clamp(alpha + direction · step, 0.05, 0.95)
    last_hit_ratio = ratio
    window_count = 0

特性

• 目标函数是命中率，而非访问分布。 无需每键偏斜度指标，直接以 keyspace_hits / (keyspace_hits + keyspace_misses) 为目标。
• 回归翻转式梯度搜索。 仅记录上次移动的符号；命中率回退时翻转符号——以轻量方式替代梯度估计。
• 护栏保护。 alpha 夹在 [0.05, 0.95]，AHE 永不退化为纯 LRU 或纯 LFU。
• 自适应节奏。 因 observe 每次淘汰触发，自适应速率自然跟随写入压力。

---

4. 复杂度与内存

步骤	开销	说明
单候选打分	O(1)	recency + infrequency + ttl_penalty，全内联
选 victim	O(k)	k = maxmemory-samples（默认 5）
每键额外内存	0 字节	复用 lfu_counter 与 last_access
控制器更新	O(1) 摊还	每 window_size 次淘汰一次

这与 Redis 的采样法一致（Redis 6+ 同样采样 maxmemory-samples 个随机键，而非维护全局堆/链表），并以零内存代价叠加了自适应能力。

---

5. 与经典策略对比

维度	LRU	LFU	AHE（FerrumKV）
打分计算	O(1)	O(1)（Morris）	O(1)
选择	O(k) 采样	O(k) 采样	O(k)，k = samples
额外内存	—	—	—（复用 LFU 字段）
突发热点	✅	❌	✅ alpha → LRU
稳定热点	❌	✅	✅ alpha → LFU
抗扫描	❌	✅	✅ 频率兜底
感知 TTL	❌	❌	✅ ttl_penalty
模式切换	❌	❌	✅ 实时自适应
可调参数	无	lfu-log-factor、lfu-decay-time	alpha 初值、step、window、samples

---

6. 收敛行为

在负载从突发（偏向 recency）切换到稳定热点（偏向 frequency）时，控制器先将 alpha 推向 LRU，再反向推向 LFU，在逐渐收窄的区间内围绕当前负载所奖励的值振荡。下图路径为示意——真实轨迹取决于命中率信号，可通过 INFO memory 的 ahe_alpha、ahe_last_hit_ratio 实时观察。

平直线为固定权重策略作参照；AHE 的曲线展示了自调优的偏移与收敛。

---

7. 配置与可观测性

一行参数即可启用 AHE——无需任何算法专属调参：

./ferrum-kv --maxmemory 256mb --maxmemory-policy allkeys-ahe
# 或仅限带 TTL 的键：
./ferrum-kv --maxmemory 256mb --maxmemory-policy volatile-ahe

旋钮	默认值	说明
maxmemory-policy	noeviction	设为 allkeys-ahe / volatile-ahe 启用
maxmemory-samples	5	每次淘汰采样的候选数（与 *-lru/*-lfu 共用）
step / window_size / direction	0.05 / 64 / +1	内部常量，见 AdaptiveHybridState::default()

实时观察控制器收敛：

$ redis-cli -p 6380 INFO memory
# Memory
used_memory:268435456
maxmemory:268435456
maxmemory_policy:allkeys-ahe
ahe_alpha:0.71
ahe_last_hit_ratio:0.94

---

8. 延伸阅读

• 实现：src/storage/eviction.rs —— eps_score、pick_victim_ahe、AdaptiveHybridState
• 完整设计讨论：白皮书 §9.5
• 动手实验：内置控制台 会在负载变化时绘出 ahe_alpha 曲线。