第 4 章 · 02 tier.h 替换策略 LFRU 与 NUMA

第 4 章 · 02 tier.h 替换策略 LFRU 与 NUMA

本节摘要:tier.h 用四个函数定义了热存(VRAM/RAM)与冷存(NVMe)之间的替换策略。tier_pick_swap 找最冷的 pinned slot、找最热的非 resident 专家,并用 fh<=fc+(fc>>2)+4 的 25%+4 滞后防乒乓;tier_lfru_score 把频率放高位、近期放低位,让"频率 256"压过"近期 255";tier_pick_lfru 在 score 域上重做同样的 25%+4 滞后;tier_decay 用 heat>>=1 衰减防止旧历史主导。整套设计是 LFRU(Less-Frequency-Recently-Used)而非纯 LRU。

内容来源:原项目源码 c/tier.h(全文 60 行)

⚠️ 注意:这是 Colibrì 替换策略的全部源码,只有 60 行。但每一行都经过精心设计——25% 滞后、4 偏移、频率/近期权重比、score 域上的 hysteresis,都是为了避免最常见的缓存病:乒乓、抖动、旧历史主导。读懂这 60 行,就读懂了"学习型缓存"为什么稳。

学习目标

1. 读懂 tier_pick_swap 的"找最冷 + 找最热 + 25%+4 滞后"三段式。
2. 读懂 tier_lfru_score 的频率优先近期破平权重设计。
3. 理解为什么 25%+4 滞后能防乒乓。
4. 理解 tier_decay 衰减防止旧历史主导。
5. 区分 LFRU 与纯 LRU,理解 NUMA 交错。

一、tier_pick_swap:纯频率信号的滞后替换

这是热存替换的基础路径。函数签名:

static int tier_pick_swap(const uint32_t *heat, int nexpert,
                          const int *pinned, int npin,
                          int *slot, int *eid, long *gain){
​

heat[e] 是专家 e 的累计访问热度,pinned[] 是当前驻留在热存的 npin 个专家 id。函数要回答:该不该换出某个 pinned slot、换入某个非 resident 专家?分成三段。

第一段,找最冷的 pinned slot:

1   #ifndef COLIBRI_TIER_H
2   #define COLIBRI_TIER_H
3   #include <stdint.h>
4   /* Pick one RAM/VRAM hot-store slot to replace from recent routing heat.
5    * The fixed margin handles tiny samples; the 25% margin prevents ping-pong. */
6   ...
12      int cold=0;
13      for(int z=1;z<npin;z++) if(heat[pinned[z]]<heat[pinned[cold]]) cold=z;
​

第 13 行在 pinned 列表里扫一遍,挑出 heat 最小的那个 slot(注意是 slot 下标,不是专家 id)。这是淘汰候选。

第二段,找最热的非 resident 专家:

14      int hot=-1; uint32_t fh=0;
15      for(int e=0;e<nexpert;e++){
16          int resident=0;
17          for(int z=0;z<npin;z++) if(pinned[z]==e){ resident=1; break; }
18          if(!resident && heat[e]>fh){ fh=heat[e]; hot=e; }
19      }
20      if(hot<0) return 0;
​

第 15-18 行扫描全部 nexpert 个专家,跳过已经在热存里的(resident),挑出 heat 最大的候选 hot,记录其热度 fh。如果所有非 resident 专家热度都是 0,hot<0,直接返回 0 不换。

第三段,25%+4 滞后防乒乓:

21      uint32_t fc=heat[pinned[cold]];
22      if(fh<=fc+(fc>>2)+4) return 0;
23      *slot=cold; *eid=hot; *gain=(long)fh-(long)fc;
24      return 1;
​

第 22 行是整个函数的灵魂。换入候选的热度 fh 必须严格超过冷 slot 热度 fc 的 fc + fc/4 + 4,才允许换。这里有两道闸:25%(fc>>2)的相对滞后,以及 +4 的绝对偏移。

为什么 +4?注释说"The fixed margin handles tiny samples"——在采样很少(比如刚启动)时,fc 可能只是 1 或 2,fc>>2 几乎为零,这时绝对偏移 4 提供最小门槛,避免一两个访问就触发换页。

为什么 25%?注释说"the 25% margin prevents ping-pong"。如果只要求 fh>fc 就换,两个专家热度接近时会反复互换位置,每次换都触发一次磁盘读,decode 延迟剧增。25% 滞后要求"显著更热"才动,把乒乓压到最低。

二、tier_lfru_score:频率优先,近期破平

纯 LRU(只看近期)有一个毛病:一个长期高频专家偶尔一两步没被路由,就会被一个刚被路由一次的新专家挤掉。tier_lfru_score 用"频率为主、近期为辅"的设计解决它。

27  /* LFRU: frequency is the primary signal; recency breaks close calls. A recent
28   * access contributes at most 255 points while one frequency count is worth
29   * 256, so a merely recent expert cannot displace a genuinely hotter one. */
30  static uint64_t tier_lfru_score(uint32_t heat, uint32_t last, uint32_t clock){
31      uint32_t age=clock-last, recent=age<255?255-age:0;
32      return ((uint64_t)heat<<8)|recent;
33  }
​

第 31 行:age 越小(越近期),recent 越大,但封顶 255。第 32 行:把 heat 左移 8 位(乘 256)放在高位,recent 放在低位,合成一个 uint64 score。

权重关系藏在位运算里:recent 最大是 255,而 heat 的最低一位对应 256。也就是说,一次频率计数 = 256 分,而近期最多贡献 255 分。注释里那句话就是这条数学事实:"a merely recent expert cannot displace a genuinely hotter one"(仅凭近期一次访问,挤不掉真正更热的专家)。

只有当两个专家 heat 相等时,recent 才起作用——这就是"频率优先、近期破平(close calls)"的精确含义。

三、tier_pick_lfru:在 score 域上重做滞后

35  static int tier_pick_lfru(const uint32_t *heat, const uint32_t *last, uint32_t clock,
36                            int nexpert, const int *pinned, int npin,
37                            int *slot, int *eid, long *gain){
...
49      if(hot<0) return 0;
50      uint64_t cs=tier_lfru_score(heat[pinned[cold]],last[pinned[cold]],clock);
51      /* Retain the existing 25%+4-frequency hysteresis in score units. */
52      if(hs<=cs+(cs>>2)+(4u<<8)) return 0;
53      *slot=cold; *eid=hot; *gain=(long)((hs-cs)>>8); return 1;
​

结构和 tier_pick_swap 完全一致——找最冷、找最热、滞后判断——只是把比较从 heat 域挪到了 score 域。第 52 行的滞后也是 25%+4,但那个 4 现在是 (4u<<8),即 score 域里的"4 个频率计数"(1024 分),保持和原始版本一致的物理含义。

第 53 行的 gain 把 score 差右移 8 位还原成"频率差"返回给调用者,语义清晰。

💡 深潜要点:tier_pick_swap 和 tier_pick_lfru 的差异不在结构,只在评分函数。前者是 LFU(纯频率),后者是 LFRU(频率+近期)。同一套滞后门槛复用两次,代码极其精炼。

四、tier_decay:用右移衰减防止旧历史主导

56  static void tier_decay(uint32_t *heat, int nexpert){
57      for(int e=0;e<nexpert;e++) heat[e]>>=1;
58  }
​

只有两行,但至关重要。如果不衰减,一个专家在过去某段长会话里被访问过几千次,heat 就永远居高不下,即使最近根本不再被路由,也会一直霸占热存——这就是 LFU 的经典病:旧历史主导。

heat>>=1 把所有专家热度同时减半。频繁衰减让"最近 N 次采样"的权重远高于远古历史,使热存真正反映当前工作负载。衰减周期由调用方控制(典型是每个 decode step 或每若干 token 一次)。

注意衰减对 heat 和 last 的影响:heat 被减半,但 last(最后访问时钟)不动,这样 tier_lfru_score 的近期信号在衰减后相对放大,近期专家更容易晋升。

五、LFRU vs LRU,以及 NUMA

LFRU vs LRU 的本质差异:LRU 只看"最后一次访问离现在多久",一次新访问就能把任何老专家挤下去;LFRU 让频率做主裁判、近期只做副裁判,高频专家拥有"容错窗口"——偶尔一两步没被路由不会被立即淘汰。对于 MoE 路由这种"专家热度有真实结构、不是均匀随机"的场景,LFRU 命中率显著高于纯 LRU。

NUMA 交错(COLI_NUMA=1,issue #82):在多 socket 主机上,常驻权重物理分布在多个内存控制器。如果默认 numa-local 分配,跨 socket 访问会走 inter-socket 总线带宽打折。开启交错后,常驻权重均匀分布到所有 numa 节点,任何线程的访问都能就近命中一个控制器,有效内存带宽拉满。这跟 tier.h 的替换策略是正交优化:tier.h 决定"谁驻留",NUMA 决定"驻留在哪个控制器"。

本节要点回顾

1. tier_pick_swap 三段式:找最冷 pinned slot、找最热非 resident 专家、fh<=fc+(fc>>2)+4 滞后防乒乓。
2. +4 处理小样本,25% 防乒乓,两道闸缺一不可。
3. tier_lfru_score:heat<<8 | recent,频率 256 > 近期 255,近期只在频率打平时破平。
4. tier_pick_lfru 在 score 域复用 25%+4 滞后,偏移改成 (4u<<8) 保持物理含义。
5. tier_decay 的 heat>>=1 衰减防旧历史主导;LFRU 比 LRU 更适合 MoE 路由结构;NUMA 交错跨控制器。

下一节:热存策略讲完了,我们去看 I/O 路径——第 5 章深潜双 SSD 镜像、io_uring 异步 IO、O_DIRECT 与读写算重叠,看清 Colibrì 如何把"磁盘层"逼近"内存层"的速度。