eviction policy、protected_size 与优先级驱逐#

这章解决什么问题#

前面的调度与内存章节已经把 prefix match、cache_protected_len、host hit 和 load-back 讲了出来，但还有一层非常关键的现实问题没有被单独讲透：当 cache 必须真的逐出节点时，系统到底按什么规则决定谁先走、谁后走？被请求保护住的前缀又怎样从 protected_size 回到 evictable_size？

这层问题集中在：

  • evict_policy.py
  • RadixCache.evict(...)
  • evictable_size_
  • protected_size_
  • priority

如果不把这一层讲清楚，读者会知道 cache 可以命中、可以保护，也会知道 host hit 可能需要 load-back，但仍然很难准确解释：

  • 为什么某些前缀总是很快被逐出
  • 为什么高优先级请求更容易保住自己的前缀
  • 为什么 lock ref 与 eviction policy 必须一起看

为什么这层值得单独成章#

因为 prefix cache 真正的工程价值，不只取决于“能不能命中”，还取决于“命中之后能在树里活多久”。而存活时间并不是靠运气，而是靠：

  • 节点当前是否受保护
  • 节点当前驱逐优先级是多少
  • 具体策略是 LRU、LFU、Priority 还是 SLRU

换句话说，前面几章解释的是“缓存如何被建立和持有”，这一章解释的是“缓存如何在压力下被取舍”。对一本系统书来说，这正是 cache 主线最后必须补上的那一层。

一张图：prefix cache 不只会命中，还会在 protected 与 evictable 之间切换#

这张图解决的理解障碍是：很多读者会把 cache 看成“命中或未命中”的二元状态，而源码里更像是一条会在多个集合之间迁移的状态线。

flowchart LR
    Match["match_prefix / node in tree"] --> Protect["inc_lock_ref -> protected_size"]
    Protect --> Run["request is using prefix"]
    Run --> Release["dec_lock_ref"]
    Release --> Evictable["evictable_size"]
    Evictable --> Policy["LRU / LFU / FIFO / Priority / SLRU"]
    Policy --> Evict["evict(...)"]

图比纯文字多解释的一点是：一个 prefix 节点不是天然可驱逐，也不是天然永久保留，而是在受保护和可驱逐之间迁移。

为什么 evictable_size_ 和 protected_size_ 是驱逐主线的两大核心计量#

radix_cache.py 里 inc_lock_ref(...) / dec_lock_ref(...) 的价值，不只在前面章节讲过的“保护当前前缀路径”，更重要的是它会实时改：

  • evictable_size_
  • protected_size_

这说明系统对 prefix cache 的存量看法非常明确：

  • 不是一锅总 cache
  • 而是至少分成“当前能驱逐的部分”和“当前被活动请求保护的部分”

从工程角度看，这是非常成熟的设计，因为 eviction 决策需要先知道“哪些节点根本不在候选集合里”。否则再聪明的策略，也可能把正在使用的前缀误逐掉。

evict_policy.py 在系统里真正扮演什么角色#

这份文件很短，但特别重要。它说明：

  • tree 结构负责表达共享关系
  • eviction strategy 负责定义取舍规则

也就是说，cache tree 和驱逐策略在实现上是明确分离的。当前支持至少包括：

  • LRUStrategy
  • LFUStrategy
  • FIFOStrategy
  • MRUStrategy
  • FILOStrategy
  • PriorityStrategy
  • SLRUStrategy

这是一处很值得技术书明确点破的边界：

  • “它是一棵 radix tree”不等于“它天然就是 LRU”
  • 真正的驱逐语义是在策略对象里定义的

各种策略最重要的区别是什么#

LRU#

按 last_access_time 驱逐更旧的节点。它最接近直觉，也最容易和“热点前缀”语义对齐。

LFU#

按 (hit_count, last_access_time) 取优先级。它更强调长期热门前缀，而不只看最近一次访问。

FIFO / FILO#

更接近“按创建顺序”或其反向驱逐，适合做行为对照或某些非常特定的实验策略。

MRU#

按最近使用反向驱逐，通常更像反例或对照策略，而不是默认生产直觉。

Priority#

按 (priority, last_access_time)。更低优先级的节点先被逐出，同优先级内部再按 LRU。

SLRU#

不是简单看最近时间，而是先把节点按 hit count 划成 probationary / protected 段，再在段内按 LRU 驱逐。

这几类策略的意义，不在于“名字很多”，而在于它们分别回答了：

  • 你更想保护最近热的前缀
  • 还是长期热的前缀
  • 还是明确优先级高的前缀

PriorityStrategy 为什么特别适合和调度一起看#

PriorityStrategy 返回的是：

  • (node.priority, node.last_access_time)

这说明 cache eviction 已经不再是 cache 内部的纯局部决策，而是把请求调度层的 priority 明确带了进来。

也就是说，优先级不仅影响：

  • waiting queue 如何排
  • batch 谁先被接纳

还影响：

  • 它留下的 prefix state 将来更容易被保住还是被逐出

这就是一种非常像系统书会强调的“跨层一致性”设计：调度层价值判断与缓存层保留策略被显式对齐。

SLRUStrategy 为什么值得特别提#

它不是简单的“另一种 LRU”，而是在做分段：

  • hit count 低于阈值：probationary
  • hit count 达到阈值：protected

然后再按 (segment, last_access_time) 比较优先级。

这说明它在表达一个很明确的工程意图：

  • 不要让刚刚碰巧命中过一次的节点，和真正稳定热点节点享有同等保留地位

从教学角度看，SLRU 很适合作为“为什么策略本身也在表达系统偏好”的例子。

RadixCache.evict(...) 应该怎么读#

更稳的阅读问题不是“这段堆操作怎么写的”，而是：

  1. 候选集合从哪里来
  2. 优先级怎样计算
  3. 逐出后树和 allocator 如何同步更新

源码的关键流程大致是：

  1. 从 evictable_leaves 构造堆
  2. 用当前 eviction_strategy.get_priority(node) 生成可比较键
  3. 逐个弹出候选节点
  4. 先 token_to_kv_pool_allocator.free(x.value)
  5. 再 _delete_leaf(x)
  6. 如父节点变成新的可逐出叶子，再把父节点推回堆

这说明 eviction 不是“删一个叶子就结束”，而是可能沿树向上不断产生新的可逐出边界。

为什么 priority 会沿路径传播#

_insert_helper(...) 里一个很值得读者记住的细节是：

  • 节点的 priority 会沿路径取 max(node.priority, priority)

这说明一个高优先级请求命中或扩展一条前缀时，不只是叶子拿到高优先级，整条共享路径都会被抬高。

这非常合理，因为共享前缀的价值往往不在叶子单点，而在整段路径。如果只提升叶子优先级，驱逐时仍可能在上层节点做出和整体价值不一致的决策。

protected_size_ 与策略本身为什么要分开理解#

这一点特别重要：

  • protected_size_ 决定“谁根本不能参与驱逐”
  • eviction strategy 决定“在可驱逐集合里，谁先走”

这意味着“受保护”与“高优先级”不是同一件事。

更准确地说：

  • lock ref 先决定候选资格
  • 策略再决定候选排序

如果把这两层混为一谈，就会很难解释为什么某个高优先级前缀在被请求释放后仍然可能被驱逐，或为什么某个低优先级前缀在请求运行中却根本不参与驱逐。

这层对排障有什么直接价值#

如果你观察到：

  • prefix reuse 总是很快退化
  • 某些热点前缀明明频繁命中却留不住
  • 高优先级请求留下的状态没有想象中稳

那么这时应该先回到：

  • evictable_size_ / protected_size_
  • 当前 eviction_policy
  • 节点 priority
  • lock_ref

而不是先怀疑 match_prefix 自己失效。

这是因为 prefix reuse 的失效不总是“没命中”，也可能是“命中了，但树在压力下很快把它逐掉了”。

这层最容易出现的误判#

1. 以为 prefix reuse 差就是匹配逻辑错了#

很多时候其实是驱逐策略和保护边界让它留不住。

2. 以为高优先级请求天然永久保住 cache#

只有在请求持有锁时它才会进入 protected_size_；释放后仍要参与策略竞争。

3. 以为 radix tree 的驱逐语义天然等于 LRU#

源码里策略是可切换的，而且支持 priority / SLRU 这类更复杂偏好。

如果你要顺着源码读这条驱逐主线，推荐顺序是什么#

建议按下面顺序：

  1. evict_policy.py
  2. RadixCache.__init__() 里策略选择
  3. inc_lock_ref(...) / dec_lock_ref(...)
  4. RadixCache.evict(...)
  5. _insert_helper(...) 里 priority 的路径传播

这样读，你先有“规则”，再看“候选资格”，最后再看“实际逐出流程”，最不容易把策略和资格混起来。

小结#

这一章真正要补齐的，是 prefix cache 主线的最后一块现实层：

  • prefix 状态不仅会被命中和保护
  • 还会在压力下被策略性逐出
  • protected_size_ 与 evictable_size_ 先决定候选资格
  • eviction strategy 再决定真正的取舍顺序

到这里，调度与内存部分对 cache 的解释，才真正从“能不能复用”走到了“为什么有些状态能长留，有些状态会很快消失”。