Mooncake Store Fit-Aware 有界回退优化

---

项目简介

本项目针对 Mooncake Store 现有 free_ratio_first 分配策略的失败恢复路径进行优化。旧实现最多检查 100 个回退位置，即使某个 OffsetAllocator 已能保守证明当前 Segment 的最大可分配连续区域小于请求尺寸，该位置仍会消耗有限预算。在大规模 Segment 池中，大量已确定无法容纳请求的候选可能提前耗尽预算，使后方仍可分配的 Segment 没有机会被访问。

决赛方案不再新增独立的 fragmentation_aware 策略，而是在现有 free_ratio_first 内引入 Fit-Aware Bounded Fallback：被保守证明为 NO_FIT 的 Segment 不消耗可计费回退预算，但物理扫描仍受独立硬上限约束。方案因此同时保留原有配置、排序、兼容语义和最坏情况边界。

从初赛到决赛

初赛 PR #2797 通过独立碎片感知策略证明了一个机制事实：总空闲空间充足，不代表存在能容纳当前对象的连续空间。维护者随后指出，生产负载通常只有 1 至 2 种主要对象尺寸，初赛的宽混合尺寸假设代表性不足，单独增加新策略的维护成本也缺少充分依据。

决赛阶段据此完成三步收敛：

1. 开展 750 组尺寸/释放矩阵、1080 组有限生命周期扫描和 18 组 FAST’25 公开 Trace 回放，没有把“广泛生产碎片”作为未经证明的前提。
2. 放弃全局碎片评分和新增策略入口，将优化限制在已经发生真实分配失败后的大池回退路径。
3. 加入生产可观测指标、双尺寸生命周期 Store Benchmark、异常场景测试和 AB/BA 配对实验，使收益与代价都能被复核。

初赛材料完整保留在 initial/；决赛权威成果位于 finals/。

核心算法

free_ratio_first 采样、排序与 preferred 路径保持不变
                         |
                         v
                 发生真实分配失败？
                    否 /       \ 是
               保持旧行为       大池 Fit-Aware 回退
                                   |
                          读取保守连续空间提示
                                   |
                    +--------------+--------------+
                    |                             |
               全部已知且不足               MAY_FIT / UNKNOWN
                  NO_FIT                    fail-open
                    |                             |
             返还可计费预算                 调用真实 allocator
                    |                             |
                    +--------------+--------------+
                                   |
                最多 100 个可计费位置，最多 200 个物理位置

安全与兼容约束

• 仅在 Segment 数量大于 100 且本请求已经观察到真实失败后启用容量提示。
• 只有所有有效 Allocator 的提示均已知且严格小于请求尺寸时，才判定 NO_FIT。
• MAY_FIT、UNKNOWN 和可能过高的旧提示一律 fail-open，继续调用真实 Allocator。
• 可计费位置上限保持 100，物理扫描位置上限为 200，避免把有界重试退化为全局扫描。
• preferred、excluded、used、多副本去重和 best-effort 语义保持不变。
• 不新增策略枚举、CLI 参数、RPC 字段、对象元数据字段或持久化格式。
• 指标先在请求内聚合，退出回退路径时集中写入 Counter/Histogram，避免逐候选原子更新污染 P99。

工程实现

决赛统一补丁对应 Mooncake 上游 Draft PR #3347，基线为 64495bdfd3e215e495db714418c4b60c0f7d0fad，头提交为 ba84216951ca14f369bfe39bb9106f9dbdd54046。

组成	内容
修改规模	9 个 Mooncake Store 文件，+903/-11
核心算法	分离可计费位置与物理扫描位置，引入保守 NO_FIT 守卫和双上限终止
Allocator 接口	默认返回 UNKNOWN，OffsetAllocator 复用已有保守最大连续区域上界
可观测性	7 个 Counter、3 个 Histogram，覆盖激活、返还、真实调用、恢复和停止原因
Store Benchmark	同一会话执行“小对象写入、步进删除、大对象写入”的双尺寸生命周期场景
测试	小池、unknown、excluded、used、多 Allocator、扫描上限、真实 OffsetAllocator 和指标口径

PR-ready Patch：finals/mooncake_fit_aware_fallback_pr_3347.patch

验证结果

构建与功能回归

检查	结果
allocation_strategy_test	69 项通过，2 项上游既有跳过
buffer_allocator_test	19/19 通过
master_metrics_test	13/13 通过
Python Benchmark 测试	6/6 通过
Release CPU 构建	mooncake_master 与聚焦测试目标构建通过
静态质量	clang-format、Ruff、适用的 pre-commit、codespell、git diff --check 通过

分层性能证据

证据层	场景	结果	严格结论
合成机制压力	256 Segment，31 轮配对，每轮每策略 50000 请求	成功率 40.480% -> 78.643%；成功 Goodput +55.821%；原始请求速率 -19.798%；P99 +49.473%	特定 NO_FIT 几何下提高成功可达性，但存在吞吐定义与尾延迟代价
健康控制	64 Segment	成功率均为 100%，Goodput 与 P99 的 95% CI 均跨 0	小池不激活，不宣称收益或回归
真实 Store 压力见证	128 Segment 双尺寸容量边缘运行	118 次激活、9433 次预算返还、3 次越过旧边界恢复	真实 Store 路径能够触发并产生可归因恢复，不等同相对吞吐结论
真实 Store 配对	101 Segment，7 组 AB/BA、14 次运行	原始请求速率 +10.268%，P99 -15.946%；成功率与成功 Goodput 的 95% CI 跨 0	当前拓扑下减少无效调用并改善时延，但未证明容量成功率普遍提高
单尺寸负对照	128 Segment，2 MiB 固定对象，7 组 AB/BA	Goodput、P99、峰值 RSS 的 95% CI 均跨 0	常见单尺寸容量受限负载未检出显著收益或回归

原始 CSV、JSON、Prometheus 快照和测试日志位于 finals/关键证据/。

当前上游状态

• Draft PR：kvcache-ai/Mooncake#3347
• Fork 分支：Lorry1024/Mooncake:agent/store-fit-aware-fallback-budget
• 头提交：ba84216951ca14f369bfe39bb9106f9dbdd54046
• 官方运行：GitHub Actions #31388960313
• 状态口径：本地 Release 与聚焦回归通过；官方运行中的 build (3.10) 在全量 CTest 阶段失败，build (3.12) 随后取消，因此不声明官方 CI 全绿，也不在缺少完整日志时将失败归因于本方案。

决赛交付

材料	文件
完整技术报告	finals/KVCache_Forge_Mooncake决赛技术报告.pdf
LaTeX 源码	finals/KVCache_Forge_Mooncake决赛技术报告.tex
12 分钟答辩 PPT	KVCache Forge-Mooncake Store碎片感知优化-Mooncake KVCache存储设计和性能优化.pptx
PPT PDF 备份	finals/KVCache_Forge_Mooncake决赛答辩.pdf
决赛交付说明	finals/决赛交付说明.md
复现指南	finals/复现与验证指南.md
答辩讲稿	finals/决赛答辩讲稿.md
演示视频脚本	finals/5分钟演示视频脚本.md
研究摘要	finals/真实负载碎片研究摘要.md
提交清单	finals/决赛提交检查清单.md
最终压缩包	release/KVCache_Forge_Mooncake决赛交付_20260810.zip
压缩包校验	6433f6df84e5d620b0748d18c8e49b80f9e044da1e43bc37838e4fa6f5dc7a67
决赛全量材料（网盘）	KVCacheForge团队_决赛材料，提取码：5e6s

快速复现

git clone https://github.com/kvcache-ai/Mooncake.git
cd Mooncake
git checkout 64495bdfd3e215e495db714418c4b60c0f7d0fad
git apply --check /path/to/mooncake_fit_aware_fallback_pr_3347.patch
git apply /path/to/mooncake_fit_aware_fallback_pr_3347.patch
git diff --check

也可以直接检出 Fork 分支：

git clone https://github.com/Lorry1024/Mooncake.git
cd Mooncake
git checkout agent/store-fit-aware-fallback-budget
git rev-parse HEAD

完整构建、聚焦测试、Store 生命周期场景和指标核验命令见 finals/复现与验证指南.md。

仓库结构

.
├── README.md                 # 当前决赛方案、结果和入口
├── SUBMISSION.md             # 决赛提交索引与证据边界
├── finals/                   # 决赛最终报告、PPT、Patch、文档和关键证据
├── initial/                  # 初赛策略、PR #2797、报告、PPT、仿真与日志归档
└── release/                  # 可直接提交的决赛 ZIP 与独立 SHA-256 文件

结论边界

本项目证明的是：在大规模 Segment 池的特定 NO_FIT 几何压力下，保守容量提示与双预算回退能够减少可避免的分配失败；真实 Store 中也观察到路径触发、越界恢复和条件性的请求速率/P99 收益。

本项目不宣称所有生产负载都更快，也不把合成机制矩阵的 +55.821% 外推为普遍 Store 吞吐提升。当前未完成 RDMA、多节点、GPU 或 SGLang HiCache 端到端 E5 验证，因此不声明 TTFT、Prefix 命中率或 GPU 利用率改善。