Skip to content

Latest commit

 

History

History
245 lines (155 loc) · 13.5 KB

File metadata and controls

245 lines (155 loc) · 13.5 KB

技术方案演进

1. 阶段 A:仅按总空闲比例

free_ratio_first 的优势是简单、低成本,并能在 Segment 间均衡容量。但它把“空闲总量”近似为“当前请求可分配性”,在混合尺寸和长期 churn 中可能失效。

例如,一个 Segment 有 16MiB 总空闲,但最大空洞只有 8MiB,不能容纳 10MiB 请求;另一个 Segment 只有 12MiB 总空闲,但连续区域为 12MiB,可以一次成功。只按总空闲率排序会把前者排在前面。

这一反例证明碎片信息有价值,但没有证明它应该在每个请求的高频路径中被无条件查询。

2. 阶段 B:初赛固定评分碎片感知

初赛策略为每个采样候选计算:

$$ \text{contiguity_ratio} = \frac{\text{largest_free_region}}{\text{total_free}} $$

$$ \text{score} = 0.70 \times \text{contiguity_ratio} + 0.30 \times \text{free_ratio} $$

排序时先比较 can_fit,再比较综合分数、最大连续区域、空闲率和稳定 tie-break。

2.1 初赛收益

  • 使排序与当前请求大小相关,而不是只看静态容量比例;
  • 在确定性反例中找到已经存在的可用连续空间;
  • 保留 bounded sampling,不扩大为全局扫描;
  • 作为独立策略接入,默认行为不变。

2.2 初赛局限

初赛实现对所有采样候选预先调用 getLargestFreeRegion() 并计算评分。若请求只尝试前一两个候选就成功,后续查询全部浪费。固定 0.70/0.30 权重也来自机制性设计,而非真实负载训练。

此外,旧异常处理把连续区查询失败返回为 0,混淆“元数据未知”和“明确没有连续空间”。如果策略据此提前过滤,会把观测故障放大为分配可用性故障。

3. 阶段 C:惰性三态 Fit Guard

8 月 2 日版本不再把碎片信息用于全候选精细评分,而是先按 free_ratio 排序,只在候选即将尝试时执行连续区检查。

三态语义为:

  • FIT:有正证据,可以尝试,但不能绕过 allocator;
  • NO_FIT:有明确负证据,可以跳过一次 allocator 调用;
  • UNKNOWN:证据不足,必须 fail-open 并继续尝试。

这一阶段还引入单 Segment 快速路径、成功后停止查询和候选尝试去重。其主要进步是把兼容性边界显式编码,但“即将尝试的每个采样候选”仍属于高频路径。

4. 阶段 D:请求级 CandidateSnapshot

8 月 3 日日初版本尝试复用一次 Allocate 调用中的 allocator 列表、容量、使用量和最大单 allocator 空闲量。它解决了三个机制问题:

  1. 常见单 allocator 候选的 capacity()/size() 不再重复读取;
  2. 最终分配复用 allocator 列表,减少映射查询;
  3. 多 allocator Segment 可先按最大单体空闲量快速拒绝,再惰性检查次级 allocator。

该设计坚持请求级生命周期,不引入跨请求缓存和失效协议。机制计数测试证明读取次数下降,但正式 Release 配对基准否决了“剩余成本已足够低”的假设。

旧碎片感知版本相对 FreeRatioFirst 在单尺寸和双尺寸场景中的吞吐下降 14.701% 至 23.482%,平均延迟上升 20.739% 至 34.459%。因此,快照复用不能作为当前最终方案。

5. 阶段 E:fallback-only Fit Guard 研究分支

5.1 核心决策

该阶段把采样路径恢复为与 FreeRatioFirst 接近的结构:

bounded sample
  -> aggregate free_ratio
  -> sort
  -> direct allocator attempt

采样路径不构造 CandidateSnapshot,不查询 getLargestFreeRegion()。任一采样分配失败只设置请求级 fit_guard_active。精确检查延迟到 fallback,并且只作用于尚未采样的 Segment:

untried fallback segment
  -> guard inactive: direct allocation
  -> guard active: FIT / NO_FIT / UNKNOWN
       NO_FIT  -> skip allocator
       FIT     -> allocator confirms
       UNKNOWN -> fail-open, allocator confirms

fallback 显式跳过本请求已经采样的全部 Segment,避免将前面已知失败的候选再次送入 allocator。

5.2 为什么不检查剩余采样候选

当天的中间提交曾在第一次失败后对剩余采样候选启用 guard,但采样阶段仍构造快照。成功路径 AB/BA 配对仍下降 10.409%,95% CI [-15.458%, -5.360%]。这说明 guard 的触发时机和采样路径数据结构都必须收敛。

5.3 已观察效果

在 10 种子、100000 请求的 E3 配对矩阵中,fallback-only 相对旧实现:

  • 吞吐提升 23.988% 至 32.025%;
  • 平均延迟降低 19.848% 至 24.609%;
  • P99 降低 26.255% 至 30.773%;
  • 四类失败数均保持 0。

相对 FreeRatioFirst,四类场景的最终碎片率、最大连续空闲区和失败数完全相同。单尺寸吞吐为稳定正向,双尺寸吞吐置信区间跨 0。因此该证据支持“控制路径与重复尝试减少”,不支持“最终碎片率改善”或生产系统收益。结合 PR #2797 对独立策略维护成本的反馈,本阶段保留为研究演进,不再作为当前上游候选。

6. 阶段 F:现有 FreeRatioFirst 请求级重试控制

6.1 问题收敛

阶段 E 的数据表明,继续查询连续区信息并没有证明最终布局改善,而“fallback 重试已采样失败候选”是一个不依赖宽混合尺寸假设的确定性浪费。8 月 6 日从官方 main@bdacc80 重新建立最小工作树,只修改现有 FreeRatioFirstAllocationStrategy。

早期候选 cac02d5 使用请求局部失败集合和采样环区间成员判断:

preferred failure -> request-local failed preferred set
sample failure    -> sampled ring interval already encodes attempted indices
fallback position -> skip failed preferred / sampled / used / excluded

采样窗口原本就是从 start_idx 开始、长度为 sample_count 的连续环区间。对 fallback 下标 $i$,成员关系为:

$$ \operatorname{offset}(i)= \begin{cases} i-\operatorname{start}, & i\geq \operatorname{start}\\ S-\operatorname{start}+i, & i<\operatorname{start} \end{cases} $$

当 $\operatorname{offset}(i)&lt;K$ 时,该位置属于采样窗口。这里 $S$ 是 Segment 总数,$K$ 是采样数。判断为 O(1),只在采样不足、真正进入 fallback 后执行;第一版 O(K) std::any_of 因 64/128 Segment 烟雾测试退化而被否决。

Store E4 随后证明,即使 O(1) 判断也不是零成本。早期候选在 7 Segment 压力链路吞吐均值下降 3.8104%,因此最终候选 1c14ad8 进一步删除失败集合和逐位置成员判断,改为门控索引域:

sample_count >= ceil(segment_count / 4)
  -> fallback 直接在连续 unsampled range 中随机扫描

sample_count < ceil(segment_count / 4)
  -> 保留官方原 bounded random fallback

这样,小池中重叠比例高时不需要逐位置判重,大池中采样稀疏时不为最多 6 个重复候选支付索引映射成本。

6.2 候选覆盖与并发边界

门控路径中的采样区间与未采样区间构成完整 Segment 池,fallback 仍以随机起点访问最多 min(100, S-K) 个未采样位置,因此不会为了去重而使未采样可用 Segment 不可达。稀疏采样路径完全保留官方原逻辑。最终实现不再去重 preferred,也不保存跨请求状态。

这种推理不假设失败永久有效。下一个请求会重新采样和尝试。单机 holder 强制退出实验已验证 TTL 清理、容量恢复和恢复后 I/O,但尚未覆盖同一 Allocate 栈帧内并发释放、多副本和网络分区。

6.3 E3 结果

10 轮固定 CPU2 的 AB/BA 微基准显示:

  • 7 Segment 失败路径调用由 13 降为 7,真实满载吞吐均值提升 19.601% 至 20.294%;
  • 16 Segment 调用由 22 降为 16,吞吐均值提升 9.464% 至 11.881%;
  • 64 Segment 只减少 8.571% 的调用,时间指标没有稳定收益;
  • 128 Segment 只减少约 4.425% 的调用,吞吐均值下降 1.613% 至 3.088%;
  • healthy 路径始终为 1 次 allocator 调用,未检测到统计上稳定的回归,但 P99 区间仍较宽。

该组数据对应早期候选,说明方案不是 Segment 数越多收益越高,而是小规模池在满载/失败 fallback 下的控制路径优化。最终门控候选复核中,7/16 Segment 尝试次数仍由 13/22 降为 7/16;64/128 Segment 尝试次数保持 70/106,与基线行为一致。

6.4 E4 结果与阶段退出

最终候选在真实 mooncake_master + Store client + 多 Segment holder 单机 TCP 路径执行 5 轮 AB/BA:

  • 健康 7 Segment、4 KiB:吞吐 +1.4726%,95% CI [-2.4103%, 5.3554%];
  • 压力 7 Segment、3,274,752 B:吞吐 +2.8918%,95% CI [-1.4636%, 7.2471%];
  • 压力 16 Segment、3,274,752 B:吞吐 +1.6848%,95% CI [-4.3994%, 7.7691%]。

两个压力场景都没有达到吞吐 +5% 或 P99 改善 +10% 的预注册门槛。机制存在,但 allocator 重复调用在完整 RPC、metadata 和数据路径中占比不够高。因此阶段 F 按退出规则关闭:不推送该行为补丁、不创建 PR,保留 benchmark、AB/BA、指标对账和故障恢复基础设施。

7. 成本模型

设采样候选数为 $K$,fallback 成功前访问的未采样候选数为 $F$。设空闲率读取成本为 $C_f$,候选快照成本为 $C_s$,连续空间查询成本为 $C_m$,allocator 尝试成本为 $C_a$。

初赛全量评分近似成本:

$$ T_{eager} \approx K(C_f + C_m) + J C_a $$

候选快照中间版近似成本:

$$ T_{snapshot} \approx K C_s + J C_m + J' C_a $$

fallback-only 近似成本:

$$ T_{fallback} \approx K C_f + K C_a + F(C_s + C_m + C_a) $$

早期请求级去重近似成本:

$$ T_{dedup} \approx K C_f + K C_a + F C_o + U C_a $$

其中 $C_o$ 是 O(1) 环形区间判断,$U$ 是 fallback 扫描中未在此前尝试过的位置数,满足 $U\leq F$。实际采样尝试数会受副本成功和 excluded/preferred 约束影响,上式只描述成本位置。

最终门控实现不再为每个 fallback 位置支付 $C_o$。当 $K\geq\lceil S/4\rceil$ 时,直接把随机扫描域改为 $S-K$ 个未采样位置;当 $K&lt;\lceil S/4\rceil$ 时成本模型退化为官方原 fallback。该实现不引入 $C_s$ 或 $C_m$,但 E4 表明局部节省的 $(F-U)C_a$ 在完整 Store 链路占比不足,因此成本模型成立并不等于服务性能门成立。

8. 正确性与兼容性

8.1 allocator 仍是最终事实

策略只改变尝试顺序和是否跳过明确 NO_FIT 候选,不直接构造 buffer,也不预留空间。查询后状态变化时,allocator 仍能拒绝真实不可分配请求。

8.2 unknown 保持 fail-open

连续区报告不支持或抛异常时,候选进入 allocator 尝试。代价是可能多一次无效调用,但不会把观测能力缺失转化为可用性故障。

8.3 多 allocator Segment

聚合总空闲不能证明任一 allocator 可容纳请求。fallback 快照记录最大单 allocator 空闲量,并在最大候选不适配时检查次级 allocator,避免 split-free 误判。

8.4 跳过已采样候选

确定性测试证明该规则减少 fallback 重复尝试。但在并发系统中,allocator 状态可能在同一请求内变化,因此仍需 E4 压力测试验证是否会丢失有价值的稍后重试机会。

9. 当前测试设计

当前最小分支不继承旧 InstrumentedBufferAllocator 和 Fit Guard 测试。新增 CountingTestAllocator 与随机引擎作用域保护,专门覆盖:

  1. 7 个 Segment 全部失败时,每个 allocator 最多调用一次,总数为 7;
  2. preferred 列表重复同一失败 Segment 时,跨 preferred、sample 和 fallback 仍不重复;
  3. 固定随机种子、只让采样窗口外第 7 个 Segment 成功时,fallback 仍能找到它。

第三项用于证明优化没有通过缩小候选覆盖来换取调用数。测试结束恢复线程局部随机引擎,避免固定种子污染同进程其他用例。完整结果与日志见 EXP-004,且本地策略测试不能替代官方全仓 CI。

10. 替代方案与取舍

方案 优点 缺点 当前结论
全候选固定评分 排序信息丰富 热路径查询随 $K$ 增长,权重缺乏负载依据 被 E3 否决
候选级惰性 Fit Guard 比全量评分更惰性,三态清晰 仍污染采样成功路径 被进一步收敛
失败触发 + 采样快照 只在失败后使用 guard 快照本身仍有稳定回归 被 E3 否决
fallback-only Fit Guard 正常路径低成本,兼容 unknown,减少重试 仍维护独立策略与连续区路径,生产价值证据不足 历史研究分支
FreeRatioFirst 请求级重试控制 不新增策略/API,因果小,调用数可确定测量 完整 Store 路径收益未达门槛 E4 后否决上游化
跨请求失败缓存 可减少连续请求重复故障 失效、并发和上下线复杂 暂不采用
预留/锁定连续空间 减少 FIT 后失败 协议、锁竞争和恢复复杂 暂不采用

11. 下一步演进

下一步不继续增加评分权重、恢复 Fit Guard 或微调 sample overlap 阈值,而是建立 batch size、并发度、对象尺寸和水位的 Store 服务基线,并对 BatchPutStart、BatchPutEnd、BatchGetReplicaList 做同 workload profile。只有当 profile 发现占比足够高、可以由小补丁处理的单一热点时,才进入新行为候选。

新的上游贡献仍必须保持小补丁,并复用本轮形成的独立服务生命周期、错误码对账、资源静默、5 轮 AB/BA 和异常恢复门禁。没有达到 E4 门槛前不在个人 Fork 创建 Draft PR;没有 SGLang/GPU 环境时不以 Store TCP 结果替代 E5。