4.3 并行评分与结果排序
单节点集群评分是毫秒级,但真实集群有成百上千个节点,且调度吞吐要求每秒调度几十个 Pod——每个 Pod 都扫一遍所有节点的话,串行评分是硬瓶颈。
真实调度器用 worker 池并行评分:把节点分片,多个 goroutine 同时打分,结果合并排序。本节拆这个「分片-归并」模型,讲并行评分必须守住的纪律——结果与串行一致——以及排序与平票的确定性。
并行评分的模型:分片 → 归并
评分是「每个节点独立算分」的可并行结构:f(pod, node) 只依赖该节点自己的状态,节点之间无共享。所以可以按节点分片:
workers 个 goroutine,每个负责 len(nodes)/workers 个节点
各 goroutine 给负责的节点打分,结果写入共享 channel
主线程合并 channel → 完整分数表 {nodeID → score}
lab 的 Parallel 就是这个模型:chunk = ceil(len(nodes)/workers),每个 worker 跑一段节点切片,combineOne 算单节点加权分,channel 归并后 Ranked 统一排序。
并行只加速,不改变语义
并行评分最关键的纪律是:并行结果必须与串行结果逐节点一致。
- 评分函数是纯函数:同一个
(pod, node)输入必得同一个分数,与在哪线程跑、跑几次无关。 - 组合(加权、选最优)在归并后统一做,不在各 worker 内独立决定——选节点是全局的,如果每个 worker 只挑自己分片里的最优,会丢掉真正的全局最优。
lab 的 TestParallelEqualResults 就是这道纪律的测试:4 个 worker 的并行结果与串行 Combine 结果逐节点相等。并行化如果是真的,这个测试必须永远通过。
归并排序:全局的降序
并行打分只是把「算分」并行化,「选最优」仍然是归并后的全局操作:
- 合并得到完整分数表。
- 按分数降序排序(
Ranked)。 - 取第一个为最优,写入绑定。
排序的确定性值得较真:平票时选谁? K8s 与 lab 都取「先遍历到者」——绑定前把平票节点按某种稳定顺序排列,结果可复现。这看起来是细节,但对可观测性意义重大:同样的输入必须给同样的输出,否则「为什么选这台」无法重演。lab 的 Ranked 用选择排序且只在 > 时交换,平票保持遍历序——确定性的来源。
并行评分的收益与边界
| 视角 | 串行 | 并行(workers=8) |
|---|---|---|
| 单 Pod 评分延迟 | 扫描所有节点 | 分片后约 1/8(理想) |
| 吞吐 | worker 少、延迟高 | 多 Pod 并发 + 节点分片双并行 |
| 正确性 | 基准 | 必须与基准一致 |
并行收益有边界:评分插件若有共享状态或锁(比如都读同一个资源缓存),会退化;分片太小(节点数 < workers)收益为零。并行是吞吐手段,不是正确性手段——它必须「与串行等结果」,这是本节的中心结论。
并发调度下的节点预扣
第 4.3 节的并行评分只是「算分」并行。真实调度器还有多个 Pod 同时调度(worker 池各调度一个 Pod),此时共享状态是节点快照——两个 worker 同时绑到同一节点就会超售。
真实实现用节点锁(per-node lock):绑定前对目标节点加锁,检查剩余量、扣减、释放。lab 的 queue/scheduler.go 是单线程的(没有这个并发),但 2.1 节提过预扣;把「预扣」加上「加锁」就是并发调度下的正确性保证。第 4 章的并行评分与并发调度是两个层面的并行:算分并行(节点分片)与调度并行(多 Pod 同时),前者靠纯函数保证一致,后者靠节点锁防超售。
确定性:分布式系统里最容易被忽略的正确性
调度器的确定性不只是「好重演」,它直接决定可观测性与可测试性:
kubectl describe能看到调度器把 Pod 派到哪、为什么(reason)。- 一致性测试(同样的输入重放,输出必须一样)能发现评分插件的隐藏状态。
- 运维能相信「同配置的集群,调度行为一致」。
并行是确定性的敌人:goroutine 调度顺序不可预测,若把「选最优」做进 worker 内部,平票结果就随线程时序漂移。把不确定的并行限制在『算分』,把确定的排序留在『归并后』——这是调度器把并行与确定性共存的纪律。
并行评分的实现细节:channel 与确定性
lab 的 Parallel 用 goroutine + channel 归并,实现里有三个细节决定正确性:
- channel 有缓冲:
ch := make(chan result, len(nodes))——避免 worker 阻塞在发送上,且保证「发完再关闭」不 panic。 - WaitGroup 保证归并完整:
wg.Wait()后才close(ch)——否则提前关闭会丢结果。 - 分片覆盖全部节点:
chunk = ceil(n/workers),最后一个 worker 可能不足一片,但lo < hi判断保证每个节点恰好被一个 worker 处理。
这三个细节是「并行分片」的通用模板,任何把「独立计算」并行化的场景(批处理、MapReduce 的 map 阶段)都是同一套:分片无重叠 + 有界通道 + 等齐再归并。lab 的 TestParallelEqualResults 把这套模板的正确性钉死:结果必须与串行一致。
大规模集群的评分优化
节点规模上到千级,评分要额外优化:
| 手段 | 原理 | 章节 |
|---|---|---|
| 二分分片并行 | 评分成本摊到多核 | 本节 |
| 预过滤 | 先用廉价约束缩小候选集,再对少数节点算分 | 3.3 |
| 缓存节点状态 | 不实时问 apiserver | 1.2 |
| 按需评分 | 对每个 Pod 只算「可能赢」的节点 | 4.1 |
真实调度的目标不是「对每个节点都算分」,而是尽快淘汰大多数节点,只对幸存者算分。Filter 就是预过滤——先把 1000 个节点砍到 50 个,再并行评分 50 个。并行评分解决「幸存者怎么算」,Filter 解决「幸存者怎么少」——两者结合才支撑住千级节点集群的调度吞吐。
并行度的选择:多少 worker 合适
并行评分开多少 worker?工程判断而不是拍脑袋:
| 因素 | 方向 |
|---|---|
| 节点数 | 节点越多,分片越值得并行 |
| 插件成本 | 评分插件越贵,并行收益越大 |
| 调度吞吐目标 | 目标吞吐越高,worker 越多 |
| CPU 资源 | 调度器本身占用有限 CPU,别抢光 |
一个实用的校准方法:从 2 个 worker 起步,逐步加,观察调度延迟与 CPU 占用——收益变平(延迟不再降)就是拐点。刻意开「每节点一个 worker」通常是浪费,因为归并与锁的开销会吃掉分片收益。
还要注意:并行评分与并发调度(2.1 节的 worker 池)共享同一批 CPU 资源。评分并行度 + 调度并发度是同一个资源池的两个维度,调一个要同时看另一个的消耗。并行不是越多越好,是『延迟收益 = 并行开销』的平衡点。
三个常见误解
- 「并行评分更快,所以应该永远开很多 worker」——错误。分片小于节点数时无收益,插件若有锁会退化;worker 数是配置权衡,不是越大越好。
- 「并行评分的结果可能和串行不同,但都『差不多对』」——错误。必须是逐节点一致;不一致说明评分函数有副作用或归并逻辑错了。lab 用测试强制这道纪律。
- 「平票选谁无所谓」——错误。平票时选谁影响可观测性与测试确定性;必须定义稳定规则(先遍历者),否则同样的输入可能输出不同结果。
从并行评分到调度框架
第 4.3 节是「调度框架扩展」的前奏:并行评分对插件的要求是纯函数——只依赖输入、无副作用。这决定了评分插件的编写规范(第 7 章):
- 不写全局状态、不依赖执行顺序。
- 只读缓存快照,不实时问 apiserver。
- 输出 0-100,接受与权重解耦。
并行化把一个设计约束强加给所有评分插件:必须是纯函数。这不是巧合,而是「要并行就要可并行」,而可并行的最低要求就是无共享状态。
一句话总结本节
并行评分与结果排序收成三个要点:
- 分片-归并模型:节点分片交 worker 并行算分,channel 归并成完整分数表,再全局排序选最优。
- 并行只加速不改变语义:评分是纯函数,并行结果必须与串行逐节点一致(lab 用测试钉死)。
- 确定性:平票按稳定规则取先者;不确定的并行限制在算分,确定的排序留在归并后。
并行化给插件强加「纯函数」规范。下一章进入抢占:调度失败后的重手段,从流程与受害者选择开始。
并行正确性检查单
把一个并行评分实现做到正确,逐条检查:
- 分片无重叠:每个节点恰好被一个 worker 处理。
- 结果通道有界:缓冲足够,worker 不因发送阻塞或丢结果。
- 归并等齐:WaitGroup 等所有 worker 结束再关闭通道。
- 全局排序:选最优在归并后统一做,不在 worker 内局部决定。
- 纯函数插件:评分不写共享状态,与执行顺序无关。
- 平票规则:稳定规则取先者,结果可复现。
六条全过,并行评分才是「快而一致」。lab 的 TestParallelEqualResults 是第 1、3、4 条的可运行验证。
并行与并发的双层模型
第 4.3 节要同时记住两个层面的并行,别混:
| 层面 | 并行什么 | 正确性靠 |
|---|---|---|
| 算分并行 | 一个 Pod 的节点分片 | 纯函数 + 归并排序 |
| 调度并发 | 多个 Pod 同时调度 | 节点锁 + 预扣 |
第一层让「一次决策」变快,第二层让「整体吞吐」变高。lab 只实现了第一层(Parallel),第二层在 queue 包的单线程调度器里是教学省略。理解两层,才能看懂真实调度器的并发复杂度。
本节 lab
本节把并行评分与排序落到 score/parallel.go:Parallel(分片-归并)与 Ranked(降序稳定排序):
cd private/labs/k8s-sched-lab
go test ./score -run 'TestParallelEqualResults|TestRankedOrder' -v
两个用例验证本节两条结论:TestParallelEqualResults(4 worker 并行结果与串行逐节点一致)、TestRankedOrder(分数降序排列)。这正是「并行只加速不改变语义、归并后全局排序」的最小验证。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。