《Kubernetes 分布式系统原理深入解析》6.2 PodTopologySpread 算法

6.1 定义了字段,本节把字段变成算法。PodTopologySpread 的计数口径是『已绑定 + 预扣 + 调度中』,skew 按域计数快照计算;覆盖域数不足 minDomains 时全局最小按 0 计,空域优先;ScheduleAnyway 模式下按『离全局最小越近分越高』归一化打分。本节用一个 3 节点 2 区域的算例逐步追踪放置前/后的 skew 变化,并从 EvenPodsSpread 插件视角看 PreFilter 如何一次算好计数供 Filter/Score 复用。lab 用 topology 包的 Score/Balance 验证空域高分、贪心均衡与硬约束上限。

6.2 PodTopologySpread 算法

6.1 节定义了约束字段,本节把它们变成可执行的算法:匹配 Pod 怎么数、skew 怎么算、minDomains 不足怎么办、ScheduleAnyway 怎么打分。理解这套算法,才能预测「同一个约束在不同副本规模下会发生什么」。

计数口径:已绑定 + 预扣 + 调度中

skew 的前提是「每个域上到底有多少个匹配 Pod」。真实调度器的计数口径是动态的:

  • 已绑定(bound):spec.nodeName 已写入、phase 不是 Succeeded/Failed、匹配 labelSelector 的 Pod,其所在节点落在该域内——这是主体。
  • 预扣(reserved):调度进行中、已通过 Reserve 扩展点、绑定尚未提交的 Pod。它虽未落定,但已「预定」了目标节点的资源,必须计入,否则两个并发调度会把同一个位子分给两个 Pod。
  • 调度中(assumed):调度器缓存里 Assume 过的 Pod。调度器每次选节点时用缓存里的域计数快照,多个调度循环并发时,先完成的更新立即被后到的看到。

排除项同样明确:phase 为 Succeeded/Failed 的 Pod 不计入,抢占中被驱逐的 Pod 不再占用计数。一句话:计数对象是「已经或正在落位」的匹配 Pod,不是「计划中」的 Pod。

skew 计算逐步示例

skew = 所有域的计数最大值 − 计数最小值。以 maxSkew=1、两个域为例:

初始:z1=3, z2=1   → min=1, max=3, skew=2
放 z1:z1=4, z2=1  → min=1, max=4, skew=3(> maxSkew=1,DoNotSchedule 拒绝)
放 z2:z1=3, z2=2  → min=2, max=3, skew=1(≤ maxSkew=1,可行)

判定式写成程序就是:候选域 d 放入新 Pod 后,d 的计数 + 1 ≤ 全局最小 + maxSkew。上面放 z2 满足:z2 从 1 变 2,全局最小变为 min(3,2)=2,2 ≤ 2+1 成立。注意全局最小在每一步都可能变化——这正是「均衡是动态的」的体现。

minDomains 不足:空域优先

当覆盖域数小于 minDomains 时,全局最小被强制按 0 计。效果是把「还有空域」变成最高优先级:

  • 已覆盖域再放 Pod:计数至少 1+1=2,2 ≤ 0 + maxSkew(1) 不成立 → 已覆盖域不可行。
  • 空域放 Pod:计数 1,1 ≤ 0 + maxSkew 成立 → 空域可行。

这解决了「冷启动」问题:没有 minDomains 时,第一批 Pod 可能全堆到同一个域(因为那里已经有一个 Pod、skew 不变),后面才慢慢铺开;有了 minDomains,一开始就把副本铺到目标数量的域上。lab 的 Feasible 用 len(d) >= c.MinDomains 作为取真实最小还是 0 的分界。

ScheduleAnyway 的打分公式

软约束模式不打分不行——它把「不均衡」翻译成「低分」,让调度器在可行节点里选更均衡的。归一化公式:

diff = 候选域计数 − 全局最小
若 minDomains 未达到,全局最小按 0 计

maxSkew = 0:diff ≤ 0 → 100 分,否则 0 分
maxSkew > 0:diff > maxSkew → 0 分
              否则 → 100 − diff×100 / (maxSkew+1)

几个关键点:

  • diff=0(最均衡的域)拿满分 100;diff 每增加 1,分数线性下降。
  • diff > maxSkew 的域拿 0 分——软约束不拒绝它,但让它几乎不可能被选中(除非所有可行节点都这样)。
  • 分数是 0-100 的整数,与其他 Score 插件(第 4 章)在同一尺度,方便加权组合。

这个公式是 lab 里 Score 的原样逻辑。真实调度器的 EvenPodsSpread 打分趋势一致:离全局最小越近分越高,超出 maxSkew 归零。

EvenPodsSpread 的实现视角

真实插件 PodTopologySpread 同时注册了 Filter 与 Score 两个扩展点,内部逻辑分三步:

  • PreFilter:解析约束列表,把每个约束的「域计数」算成一份快照(state),供后续复用。这一步避免在 Filter/Score 里对每个节点重复遍历全部 Pod。
  • Filter:对每个候选节点,用快照做 Feasible 判定(DoNotSchedule 时)。
  • Score:对通过 Filter 的节点,用同一份快照算归一化分(ScheduleAnyway 时),与其他打分插件按权重合并。

「计数只算一次、多处复用」是框架性能的关键:候选节点往往成百上千,若每个节点都重新扫描一遍匹配 Pod,复杂度从 O(域数) 退化到 O(节点数 × Pod 数)。这也是第 7.1 节框架扩展点要解决的问题——PreFilter 就是为这种「先算共享状态」设计的。

算例:3 节点 2 区域完整表

下面追踪一个具体算例。集群有 3 个节点:n1、n2 在 z1,n3 在 z2。约束为 topologyKey=zone、maxSkew=1、minDomains=2、labelSelector app=web。初始时 z1 已有 2 个 web Pod(n1、n2 各 1),z2 已有 1 个(n3 上)。

新 Pod 放置放置前计数 (z1,z2)放置后计数放置后 skew判定(maxSkew=1)
放 n1(z1)(2,1)(3,1)2拒绝:3 > 1+1
放 n3(z2)(2,1)(2,2)0可行
放 n2(z1)(2,2)(3,2)1可行
放 n3(z2)(2,2)(2,3)1可行
放 n1(z1)(3,2)(4,2)2拒绝:4 > 2+1
放 n3(z2)(3,2)(3,3)0可行

读表的要点:

  • 第 4 个 Pod 只能去 z2——z1 放下去 skew 变 2,超限。
  • 均衡后(2,2),第 5 个两边都可行——skew 都是 1,任意选一边;Score 会给两边同分,由其他打分插件(如资源余量)决定。
  • 到 (3,2) 后,z1 的容纳上限是「全局最小 2 + maxSkew 1 = 3」,所以第 6 个又只能去 z2。

这套追踪正是 lab 的 Balance 做的事:依次贪心选择「放置后全局 skew 最小」的可行域,某步找不到满足硬约束的域时整批落位失败。

多约束与权重组合

一个 Pod 可以带多个 spread 约束,算法对每个约束独立计算,再合并:

  • Filter 阶段:每个 DoNotSchedule 约束都要通过——任一约束的 Feasible 失败,该节点就被排除(AND)。
  • Score 阶段:每个约束各算一个 0-100 分,按约束在插件权重中的占比加权求和。zone 层与 hostname 层的约束可以给不同权重——比如「zone 均衡权重 3、hostname 均衡权重 1」,体现「跨可用区更重要」。
  • 组合失败:多个约束互相拉扯时(比如 zone 均衡与 hostname 均衡无法同时满足),DoNotSchedule 的那一个优先,Score 的那一个退化为「尽力」。

加权口径与第 4.2 节的评分权重完全一致:Σ(weight × score) / Σ weight。第 7.1 节会看到这套机制正是框架扩展点的通用语义。

打分与选择不止均衡:Score 只是给「均衡程度」打分,最终选择是多个 Score 插件的加权结果。调度一个 Pod 时:

  1. Filter 先淘汰不可行节点(资源不足、不满足亲和、spread 硬约束)。
  2. 剩下可行节点各自算分:spread 分 + 资源分 + 镜像本地性分……按权重合并。
  3. 选最高分的节点。

所以「均衡得分高」不等于「一定被选中」——一个资源几乎打满但很均衡的节点,可能输给一个资源充足、均衡分略低的节点。spread 是调度结果的一个维度,不是全部。这解释了为什么生产里常给 spread 配较高权重,让它真正影响决策。

冷启动与运行中的算法差异

算法在两种阶段行为不同:

  • 冷启动(第一批副本):minDomains 生效,空域优先,副本快速铺到目标数量的域。此时 skew 很快降为 0 或 1。
  • 稳态运行(扩容/滚动):覆盖域数已达标,全局最小按真实值计。新 Pod 放到计数最少的域,每域容量被「全局最小 + maxSkew」约束。
  • 收缩后(副本变少、某域清零):清零的域变成空域。若覆盖域数不足 minDomains,空域重新获得优先——算法会把新副本放回该域,实现「自愈式回填」。

理解阶段差异对排障有用:冷启动时 Pod 一直 Pending,很可能是 minDomains 导致的——比如 minDomains=5 但集群实际只有 3 个域,约束永远无法满足。minDomains 不能大于实际域数。

阶段差异也解释了为什么扩容要「分批」而不是「一次全加」:一次性加 10 个副本,算法要在几个域之间轮转补位,skew 峰值比分批加更高;分批加则每批都落在当前最空的域,skew 保持平缓。

与反亲和的算法对比

把 spread 和 required 反亲和放在同一张表里看,能彻底分清两者:

维度required 反亲和spread(DoNotSchedule)
判定单位单个目标 Pod 的域域内的整体计数
域内允许几个匹配 Pod1 个(有被选 Pod 就拒)多个,只要 ≤ 全局最小 + maxSkew
是否要求「各域数量相近」否是
组合方式按 topologyKey 逐条判定多约束 AND

反亲和回答「这个 Pod 不能和谁在一起」,spread 回答「整体要摊成什么样」。一个反亲和约束在功能上约等于「只看被选 Pod 的 maxSkew=0 spread」——spread 是反亲和的超集表达。选型原则:只要关心「数量均衡」用 spread,只要「禁止共存」用反亲和。

扩容预算:域数 × 每域容量

给定域数 D、maxSkew M,稳态下每个域能容纳的匹配 Pod 数是有上限的。把全局最小记为 g,每域最大容量是 g+M,总量上界约为:

总量上界 ≈ D × (g + M)

这个预算公式的用途是扩容前预判:期望副本数 R 若逼近甚至超过上界,要么放宽 maxSkew、要么增加域、要么接受「副本超出时 spread 无法严格均衡」。反过来,当 R 明显小于上界时,skew 可以长时间保持很低——这正是 minDomains 冷启动之后看到的稳态。

实际排障案例:一个 3 域集群、maxSkew=1、副本从 30 涨到 60,每域平均 20 个,全局最小在 1920 之间波动,每域容量约 2021,spread 仍可持续满足;若副本涨到 90(每域 30),每域容量还是 20 上下,spread 必然频繁不可满足——这时不该调大 maxSkew 掩盖问题,而应该先问「为什么一个域要挤 30 个副本」。副本数明显低于上界时,spread 会长期处于低 skew 的「舒适区」——这既是分散的成果,也意味着后续扩容还有余量。

三个常见误解

  • 「skew 是实时扫描所有节点算出来的」——错误。PreFilter 在调度 Cycle 开始时算一次域计数快照,Filter/Score 复用,不重复扫描。
  • 「ScheduleAnyway 就是不均衡地随便放」——错误。它照样打分,只是没有硬门槛;分低的域依然可能被选中,但只有在没有更均衡的节点时才会。
  • 「计数只算已绑定 Pod」——错误。预扣(Reserve 后未提交)与调度中(Assume 后)的 Pod 也计入,这是并发调度不互相踩踏的前提。

本节 lab

本节把计数、打分与贪心均衡落到 topology 包的 Domain.Score 与 Balance:

cd private/labs/k8s-sched-lab
go test ./topology -run 'TestScorePrefersEmpty|TestBalanceEven|TestBalanceSkewLimit' -v

三个用例(共 4 个断言)分别验证:TestScorePrefersEmpty(z1=5、z2=0 时空域 z2 得分更高,对应「离全局最小越近分越高」)、TestBalanceEven(初始 z1=z2=3,追加 4 个后 skew 仍 ≤1,对应贪心均衡)、TestBalanceSkewLimit(两域各 5 且 maxSkew=0 时,第 3 个新 Pod 无法满足硬约束,对应「绝对均衡下容量封顶」)。三条合起来,就是本节算法的三个结论:空域高分、贪心铺平、硬约束封顶。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图