第9章：分层放置策略

第 8 章给出 LMObject 的统一抽象,placement 函数就是其中”决定 obj 该在哪一级”的引擎。本章把这个函数拆开写——四档算法各自适用什么场景、怎么组合成生产可用的 fallback 链、多 SLO 约束如何嵌入决策、放置质量如何评估。读完这章你能回答两个工程问题:给定我现在的集群规模和负载形态,该选哪种放置算法? 以及 怎么用最小的工程成本把效果做到接近最优? 这一章是 Ch8 形式化命题的”算法工具箱”,也是 Ch11 性能-成本协同优化的直接前置。

📑 目录

1. 放置决策的”三档天花板”
2. 档 1:静态启发式 + 类型偏置
3. 档 2:周期性 LP 求解
4. 档 3:在线启发式 + 成本反馈
5. 档 4:模型驱动决策
6. 多 SLO 约束的处理
7. 三层 fallback 的工程组合
8. 放置质量的评估方法
9. 设计准则
10. 给本项目的整合启示
自我检验清单
参考资料

1. 放置决策的”三档天花板”

放置决策的难度上限不是均匀的——按算法复杂度可以分成三档,每档对应不同天花板:

   优化质量
      ▲
      │
      │                                    ┌─── 强化学习(在线)
      │                              ┌─────┘   ~ 最优逼近
      │                        ┌─────┘
      │                  LP    │           ← 全局最优(静态假设)
      │              ┌────────┘
      │              │
      │     启发式   │                     ← 局部最优
      │  ┌──────────┘
      │  │
      └──┴──────────────────────────────────► 工程复杂度
        简单           中等                复杂

🌟 关键观察:优化质量的边际收益在递减,工程复杂度的边际成本在递增——选哪一档不是越复杂越好,而是看你的工作负载在曲线哪一段。

1.1 各档的工程现实

档	算法	决策频率	工程实现成本	典型来源
1	启发式 + 类型偏置	每次访问	低(几百行代码)	数据库 buffer pool 经验
2	周期性 LP	几秒-几分钟	中(LP solver 集成)	FlexGen 思路
3	在线启发式 + 反馈	每次访问 + 周期性参数更新	中-高	自适应缓存研究
4	监督 / RL 预测器	每次访问	高(训练 pipeline)	Decima / Park 等

📍 关键准则:生产系统应该同时部署多档,以低档兜底——单档解决方案在某些边缘场景一定崩。

2. 档 1:静态启发式 + 类型偏置

2.1 核心思想

不优化任何在线指标,纯靠”类型先验 + 简单访问历史” 决定放置:

   if obj.type == KV and obj.session_active:
       place HBM
   elif obj.type == VECTOR and obj.is_navigation_struct:
       place DRAM
   elif obj.type == BLOB and obj.size > 10MB:
       place SSD
   elif obj.type == TRACE and obj.importance == HIGH:
       place SSD with replicas
   ...
   # 各类型再按 LRU / LFU 内部决定淘汰

2.2 优点

几小时就能写完 —— Ch3 决策图加 Ch7 importance 字段,直接翻译成 if-else
可解释 —— 工程师能直接看出”为什么这个对象在这级”
低运行开销 —— 决策本身 O(1)
作为 baseline / fallback 极好用 —— 任何更复杂方案的”保底”

2.3 局限

类型先验可能错 —— 某用户的”冷数据”可能在他下次登录时全变热
工作负载变化反应慢 —— 改先验要重新调参
不能利用 sibling / 协同信息 —— 每个对象独立决策

2.4 何时用

🌟 新系统启动期 / 默认 baseline / 兜底层——所有更复杂方案在它的基础上跑。

3. 档 2:周期性 LP 求解

3.1 核心思想

把 SystemState 在某一时刻看作静态,求解 Ch8 的优化问题,采纳输出。每隔 N 秒重解一次。

3.2 求解形态

把 Ch8 的形式化优化变量做线性松弛:

   决策变量:  x[i, t] ∈ [0, 1]  (LMObject i 在 tier t 上的"份额")

   maximize  Σ_i Σ_t  benefit(i, t) × x[i, t]

   subject to:
     ∀t:  Σ_i  size(i) × x[i, t]  ≤  capacity(t)
     ∀i:  Σ_t  x[i, t]  =  1                       # 总份额 = 1
     ∀critical i:  x[i, HBM] + x[i, DRAM]  ≥  threshold

求解后取每个对象的最大份额对应的 tier 作为放置决策。

3.3 工程实现要点

LP 求解器:开源的 GLPK / HiGHS / SCS,商用的 Gurobi / CPLEX。十万级 LMObject 在分钟级可解
变量裁剪:把候选 tier 限制在合理子集(比如 KV 不会进 archive 层),变量数砍掉一个量级
Warm-start:用上一轮解作为本轮初值,加速收敛
决策切换 hysteresis:LP 输出在边界附近抖动时,加冷却期避免频繁迁移

3.4 优点

接近全局最优(在静态 SystemState 假设下)
约束自然嵌入(容量、SLO、durability 都是线性约束)
可解释——LP 对偶变量给出”哪些约束最紧”

3.5 局限

静态假设破坏:负载快速变化时,解一次就过期
求解时间 vs LMObject 数量:百万级对象规模 LP 顶不住
冷启动差:刚部署时缺历史数据,benefit 估不准

3.6 何时用

🌟 中等规模(10K-100K LMObject)+ 工作负载相对稳定 —— 周期性触发,作为档 1 启发式的”校准器”。

4. 档 3:在线启发式 + 成本反馈

4.1 核心思想

不全局求解,但比档 1 聪明:每次访问后用观察到的真实成本反馈,调整放置决策的内部参数。

4.2 经典原型:成本感知缓存

把 ARC(Adaptive Replacement Cache)/ LRU-K / TinyLFU 的思想扩展到多层级:

   每次访问 obj:
     real_cost = measure(latency)
     expected_cost = predict(obj.tier)
     surprise = real_cost - expected_cost

     update_predictor(obj, surprise)

     if predict_higher_tier_benefit(obj) > migration_cost(obj):
         schedule_migration(obj, higher_tier)

4.3 三个关键反馈信号

信号	含义	用法
真实访问延迟	当前 tier 实际表现	检测 SystemState 漂移
miss 后的恢复时延	预测错的代价	调整保守度
同类型对象命中率分布	类型内部冷热分布	自适应类型先验

4.4 优点

响应快——参数调整在每次访问后,秒级跟上工作负载漂移
不需要全局求解——单对象决策开销低
可与档 1 / 档 2 自然组合——档 1 给初值,档 3 在线微调

4.5 局限

局部最优——没有全局视图,容易在小范围内反复迁移
参数调优靠经验——learning rate、阈值等需要调
多对象间协调差——两个对象同时想升 HBM,谁让谁?

4.6 何时用

🌟 大规模(>100K LMObject)+ 中等动态性 —— 档 1 兜底 + 档 3 主决策,周期性档 2 校准。

5. 档 4:模型驱动决策

5.1 两种模型驱动方式

方式	思想	训练数据
监督学习预测器	学”对象特征 → 最优 tier” 的映射,模仿历史最优	历史决策 + 事后回顾打标
强化学习(RL)	学”在 SystemState 下采取什么动作能最大化长期回报”	在线交互 / 离线 RL

5.2 监督学习路径

   特征:  AccessProfile(六维) + obj_type + importance + 当前 SystemState 摘要
   标签:  事后回顾哪个 tier 是"最优"(用 LP 校准结果或人工打标)
   模型:  GBDT / 浅层 MLP(决策时延 < 1ms)

📍 优势:比 RL 简单一个量级,在数据足够时能拿到接近 LP 的质量。

5.3 强化学习路径

组件	内容
State	SystemState + 当前 LMObject pool 的统计摘要
Action	对一个或一批对象选择目标 tier(可以是连续份额)
Reward	一段时间窗口内的 goodput 提升 - 迁移成本
Algorithm	PPO / SAC / 离线 RL(CQL)

5.4 学术参考

Park / Decima(SIGCOMM’19):RL 调度集群作业,先驱
AutoSched / Park-X 系列:RL 缓存替换、内存分配等系统调度
LinUCB / 上下文 bandit:轻量 RL,适合在线决策延迟敏感场景

5.5 工业落地的关键挑战

挑战	缓解方法
冷启动数据不足	启发式 / LP 跑一段时间收集数据后再切 RL
决策时延	蒸馏到 GBDT / 小 MLP,推理 < 1ms
安全性	RL 永远在档 1 / 档 2 的 sandbox 内,不能输出不合法决策
可解释性	对关键决策做可解释性分析,故障时能回溯

5.6 何时用

🌟 超大规模(百万级 LMObject)+ 强动态性 + 长期数据可用 —— 投入 1-2 个全职 ML 工程师做半年起。

⚠️ 警示:RL 不是银弹。生产里 RL 跑赢启发式 + LP 的差距通常在 5-15%——能不能 justify 工程投入要算账。

6. 多 SLO 约束的处理

长记忆系统的 SLO 不是单一的”延迟”,而是多维:

SLO	典型阈值
TTFT(首 token 延迟)	< 500 ms
TPOT(token 间延迟)	< 50 ms
长记忆召回延迟	< 100 ms
任务完成时间	任务级
可用性	99.5% / 99.9% / …
数据持久性	关键步骤不可丢

6.1 SLO 嵌入放置决策的两种方式

方式 A:硬约束

   placement(obj) 必须保证:
     latency(obj.tier)  ≤  SLO_for(obj.type, obj.importance)

LP 自然支持线性硬约束。启发式可以加 hard rule:if SLO 不达标 → 强制升级 tier。

方式 B:软约束(罚函数)

   benefit(obj, tier)  -=  α × max(0, latency(tier) - SLO)²

适合”可以略超 SLO 但要付罚”的场景。

6.2 SLO 优先级

不同 SLO 同时被违反时,优先级:

   1. 数据持久性(数据丢了就什么都没了)
   2. 可用性(服务挂了)
   3. 关键 SLO(TTFT / TPOT)
   4. 次要 SLO(长记忆召回延迟)
   5. 资源效率

📍 设计建议:把优先级写成多目标 lexicographic optimization——先满足高优先级 SLO,再优化低优先级。

6.3 多租户 SLO 隔离

租户类型	SLO 强度	资源保留
付费高级	严格	HBM 配额保留
付费普通	中	弹性共享
免费	弹性,best-effort	抢占式

🌟 设计含义:namespace 在 LMObject 模型里是一等公民——SLO / 配额 / 抢占都按 namespace 分组。

7. 三层 fallback 的工程组合

把四档算法组合成生产可用的 fallback 链:

7.1 推荐组合

   Layer 1: 档 1 启发式(永远在线)
     └── 兜底 + 决定每次访问的实时放置

   Layer 2: 档 3 在线反馈(常驻)
     └── 调整档 1 的参数(类型先验、阈值)

   Layer 3: 档 2 周期 LP(每 30 秒-几分钟)
     └── 校准全局,输出 hint 给 Layer 1

   Layer 4: 档 4 模型(可选,长期演化)
     └── 长期数据训练,蒸馏后替换 Layer 1 的决策核

7.2 协作示意

                          ┌───────────────────────┐
                          │  访问到来               │
                          └──────────┬────────────┘
                                     │
            ┌────────────────────────▼─────────────────┐
            │  Layer 1 启发式(每次访问 < 1ms)         │
            │   + 模型蒸馏(若有 Layer 4)              │
            └────────────────────────┬─────────────────┘
                                     │ 决策
                                     ▼
                              访问数据 → 反馈
                                     │
            ┌────────────────────────▼─────────────────┐
            │  Layer 2 反馈(参数微调)                 │
            └────────────────────────┬─────────────────┘
                                     │
            ┌────────────────────────▼─────────────────┐
            │  Layer 3 周期 LP(秒级)                  │
            │   输出 hints / 重设阈值                  │
            └────────────────────────┬─────────────────┘
                                     │
            ┌────────────────────────▼─────────────────┐
            │  Layer 4 模型(后台离线训练 + 在线推理)  │
            └──────────────────────────────────────────┘

🌟 关键设计:任意一层失效都能回退——Layer 4 的模型出错,系统自动只用 Layer 1+2+3;Layer 3 LP 求解超时,系统自动只用 Layer 1+2。生产可用的关键就是不可单点依赖。

7.3 一份具体的实现节奏建议

阶段	部署	时间
Phase 0	Layer 1(纯启发式)	1 个月
Phase 1	+ Layer 2(反馈)	2 个月
Phase 2	+ Layer 3(LP)	3-4 个月
Phase 3	+ Layer 4(监督学习)	半年起
Phase 4	RL 替换 Layer 4	1 年+

📍 建议:每个 Phase 都要可独立交付——这样如果某个 Phase 没达预期,前面的不浪费。

8. 放置质量的评估方法

放置算法的好坏,需要可量化的评估指标。

8.1 一级指标

指标	定义	期望
命中率(各级)	访问命中各 tier 的比例	HBM / DRAM 命中越高越好
token 边际成本	总成本 / 服务 token 数	越低越好(Ch11 详解)
P99 长记忆延迟	长记忆访问尾延迟	满足 SLO
迁移开销占比	迁移耗时 / 总有效时间	< 5%

8.2 二级指标(诊断用)

指标	用途
各类型 LMObject 在各 tier 的占用分布	判断类型先验是否合理
迁移决策的”反复率”	高反复率 = 决策抖动
各 SLO 的违反率分布	哪一类 SLO 最难达成
miss 时的恢复时间分布	失效代价是否高估/低估

8.3 离线评估:用历史 trace 回放

录制生产环境的 access trace(几天-几周)
用同一份 trace 在不同放置算法上模拟
对比命中率 / 成本 / 延迟分布

📍 关键准则:任何放置算法上线前必须先在 trace 回放上跑赢上一档算法。

优先级	内容	难度
⭐⭐⭐	Layer 1 启发式 + Layer 2 反馈	低-中(2 个月)
⭐⭐⭐	Layer 3 周期 LP(用 HiGHS / SCS)	中(3 个月)
⭐⭐	trace 回放评估框架	中(必备工具)
⭐⭐	多 SLO 约束嵌入 LP	中-高
⭐	Layer 4 监督学习	高(半年)
⭐	RL 探索(可作为子项目论文)	高(1 年+)

10.2 项目第一模块在本章的科学问题落点

主问题:多类型 + 多约束 + 在线 + 多租户的 placement 是否存在一个可证明性能保证的算法?

子问题:

多 SLO 下的近似最优算法的性能保证(理论)
工作负载漂移下的稳定性(理论 + 实验)
与 RL 的样本复杂度对比(理论 + 实验)

⭐ 直接成果:这些问题都能出系统会议论文(SOSP / OSDI / NSDI / ATC)。

10.3 与第二、第三模块的协作

第二模块分离式 RDMA pool = LMObject 的一种 backend,本章 placement 算法直接管它
第三模块容错 / 副本通过 LMObject 的 durability 字段嵌入,placement 决策同时考虑成本和可靠性

🌟 关键观察:三模块的”协调点”全部沉淀到 LMObject + placement 决策——这是项目”统一框架”的具体体现。

FlexGen(ICML’23):arXiv 2303.06865 —— LP 放置先例
HeMem(ASPLOS’21) —— DRAM-PMEM tiering 启发式
TPP(Meta ASPLOS’23) —— 内核态透明放置
Pond(Microsoft ASPLOS’23) —— Azure CXL 放置

RL 调度系统经典

Decima(SIGCOMM’19) —— RL for cluster scheduling
Park(NeurIPS’19) —— RL 系统调度的开放平台
AutoSched 系列 —— 系统中 RL 应用综述

LP / 优化求解器

HiGHS(开源 MIP 求解器):highs.dev
GLPK / SCS / OR-Tools —— 各种开源选择
Gurobi / CPLEX —— 商用工业级

缓存 / 替换策略经典

ARC: A Self-Tuning, Low Overhead Replacement Cache(Megiddo & Modha, FAST 2003)
LRU-K(O’Neil et al., SIGMOD 1993)
TinyLFU(Einziger et al., 2017)

多 SLO / Lexicographic 优化

多目标优化教材(Miettinen 经典) —— Lexicographic Optimization 章节
系统中的应用:Borg / Kubernetes 资源 SLO 优先级

调研笔记

项目调研 - 长记忆分离式存储 —— 8 篇核心论文 + 三模块清单

本系列其它模块

本模块第 8 章统一表示与跨层资源映射机理 —— 形式化的 placement 命题
本模块第 11 章性能-成本协同优化 —— Ch11 把本章决策喂进成本模型
模块零第 1 章 Goodput —— “useful work” 度量

搜索