k8s节点调度算法研究

发表于 分类于

背景

当前的运维平台节点选机器算法比较简陋，如cpu、内存够用的情况下选内存最小的，过滤算法也比较粗暴，只考虑内存、cpu和实例节点数小于某个阈值。最终造成了较大的资源浪费和不均衡，也经常选不出机器。

当前目标是优化当前的总体机器资源利用率，防止选不出机器部署节点。

本文调研了节点scheduler算法，或者称为装箱算法，需要找出一种适合我们管控平台的装箱算法，用于优化资源利用率。

总的来说，主要参考k8s的思想，装箱算法可以简化为两个阶段，即filter和score。对于filter来说，相对简单很多，即过滤掉无法使用的机器，这里无需调研业界做法，按自身情况定义即可。

通过filter阶段的机器，我们认为都是可以使用的机器，那么需要对这批机器做score打分，最终分数最高的机器选出。

filter

暂不叙述，后续用自己的方法

  • 机器cpu阈值
  • 机器内存阈值
  • 机器网卡阈值
  • 端口号不重复
  • maxmemory的和小于总内存的百分比
  • 同集群的master在某个机器上的个数小于总master个数的百分比
  • 昨天一天的最高点参考等。

score

最小资源利用率&资源比例均衡 (default)

该算法插件是k8s提供的默认方法，其中最小资源利用率和资源比例均衡的权重相同。

直接阅读的源码/kubernetes/pkg/scheduler/framework/plugins/noderesources。

强调一点，k8s默认只使用内存和cpu作为score的参考资源resources。若要加入gpu、rdma等资源，是需要用户自定义的。

该算法只使用了两个采集参数

  • 资源的可分配值allocatable，该值是静态值，在机器启动时则保持固定。比如内存资源可定义为内存总量*0.9。
  • 当前总的申请值requested，定义为已经绑定的所有节点累积的已经申请的资源总和，注意既包括了已经部署的节点也包含假定绑定的节点。该值在多节点选机器时是动态变化的。

值得注意，requested在k8s的场景下很容易计算出来，因为每个pod会声明自己需要的内存和cpu。但是在当前运维平台场景，我们无法预先知道每个redis节点或者proxy节点到底需要多少cpu。假如按单核来算，或者直接按maxmemory来算，可能会有很大的分配误差。

因此若需要使用该方案，建议把requested当成机器已经占用的资源，加上分配过程中已绑定节点预估的资源值。

最小资源利用率

公式如下，注意默认cpuWeight和memoryWeight均为1。

意义为选出资源利用率最低的机器。

1
score = (cpu((allocatable-requested)*100*cpuWeight/allocatable) + memory((allocatable-requested)*100*memoryWeight/allocatable) + ...)/weightSum

资源比例均衡

公式为

意义为选出各资源利用率标准差最小的

1
2
3
4
5
6
7
fraction = requested/allocable
mean = Σ(fraction(i))/len(fractions)
std = sqrt( Σ((fraction(i)-mean)^2)/len(fractions) )
score = (1 - std) * 100

当只有两种资源时
std = math.Abs((fraction[0] - fraction[1]) / 2)

举例说明

此时有3台机器

  • 总cpu和内存均为64核心、64G
  • 已分配cpu分别为50核、30核、10核心
  • 已分配内存分别为10G、30G、50G

我们需要依次分配2个节点，其信息分配为

  • 2核10G
  • 5核5G

分配第一个节点

当分配第一个节点2核心10G时，分数计算如下

3台机器的最小资源利用率得分

  • (（64-50-2）* 100 / 64 +（64-10-10）* 100/64）/2 = 43.75分
  • (（64-30-2）* 100 / 64 +（64-30-10）* 100/64）/2 = 43.75分
  • (（64-10-2）* 100 / 64 +（64-50-10）* 100/64）/2 = 43.75分

3台机器的资源比例均衡得分

  • (1-abs(((2+50)/64 - (10+10)/64)/2)) * 100 = 75分
  • (1-abs(((2+30)/64 - (10+30)/64)/2)) * 100 = 93.75分
  • (1-abs(((2+10)/64 - (10+50)/64)/2)) * 100 = 25分

因此我们选出第二台机器。

分配第二个节点

当分配第一个节点5核心5G时，分数计算如下，注意此时第三台机器已经分配了一个节点

3台机器的最小资源利用率得分

  • (（64-50-5）* 100 / 64 +（64-10-5）* 100/64）/2 = 45.3分
  • (（64-30-2-5）* 100 / 64 +（64-30-10-5）* 100/64）/2 = 35.9分
  • (（64-10-5）* 100 / 64 +（64-50-5）* 100/64）/2 = 45.3分

3台机器的资源比例均衡得分

  • (1-abs(((5+50)/64 - (5+10)/64)/2)) * 100 = 68.75分
  • (1-abs(((2+5+30)/64 - (10+5+30)/64)/2)) * 100 = 93.75分
  • (1-abs(((5+10)/64 - (5+50)/64)/2)) * 100 = 68.75分

因此第二个节点选中第二台机器。

Trimaran-目标资源利用率&负载风险均衡

该方法是另一个笔者认为很棒的策略，在阅读完后，我觉得其比默认策略更容易直观的或者用数据评估收益，其主要使用的是机器在滑动时间窗口内的资源利用率和方差来做抉择。

该时间窗口大小以我们线上的情况，我认为可以暂定义为1小时。

该策略跟默认策略类似，一共有两个相同权重的插件相辅相成。

  • 目标资源利用率：即定义一个资源利用率百分比X%，该打分算法会将大于该百分比的机器的分数降的很低，而小于该百分比的机器会优先选出离该百分比最近的机器。
  • 负载风险均衡：该策略用于多种资源，其会计算出机器部署目标节点后的各资源利用率，取最小利用率的资源作为分数。即短板效应，短板越明显的机器越不会选出来，其本质上是防范风险，而不是跟默认策略一样使机器的各资源利用率平衡。

但假设我们只考虑两种资源打分，按笔者线上情况建议使用内存资源利用率作为目标，如设置X=50%，那么累加负载风险均衡插件的分数实际上也不容易选出cpu太高的机器。

目标资源利用率

算法

  1. 获取待评分当前机器的利用率，记为 A。
  2. 计算当前 待调度节点 的 单资源 总请求量与开销，记为 B。
  3. 计算将该 节点 调度到该机器后的预期利用率（即 U = A + B，通过叠加得出）。
  4. 若 U ≤ X%，则返回评分：(100 - X)×U/X + X
  5. 若 X% <U ≤ 100%，则返回评分：X×(100 - U)/(100 - X)
  6. 若 U > 100%，则返回评分：0

示例

假设有 3 个节点 X、Y、Z，每个节点均为 4 核，当前利用率分别为 1 核、2 核、3 核。为简化计算，假设待调度 Pod 的 CPU 请求量与开销均为 0 核，目标利用率 X = 50%。

各节点利用率计算

1
2
3
Ux → (1/4)×100 = 25%
Uy → (2/4)×100 = 50%
Uz → (3/4)×100 = 75%

各节点评分计算

1
2
3
X 节点 → (100 - 50)×25/50 + 50 = 75 分
Y 节点 → (100 - 50)×50/50 + 50 = 100 分
Z 节点 → 50×(100 - 75)/(100 - 50) = 25 分

在上述算法中，50% 是我们希望所有节点达到的目标利用率。若希望降低调度激进程度，可将其下调至 40%，从而大幅降低在负载峰值或意外负载下利用率超过 50% 的可能性。因此，实践中若要实现 X% 的利用率目标，建议将配置值设为 X-10。

利用率阈值 X% 可配置。

算法分析

上述图像为算法中所述分段函数的可视化呈现(X=50)，从中可得出以下几点关键结论：

  1. 当利用率从 0 升至 50% 时，我们会优先选择这些节点进行 Pod 的打包调度。
  2. 当利用率超过 50% 后，节点会受到线性惩罚，以此避免 Pod 过度集中在这些 “高负载节点” 上。
  3. 正斜率从 50 分（而非 0 分）开始，原因在于评分范围为 0-100 分：我们希望让优先选择的节点得分最大化，使其评分更具分量，从而降低其他插件对该调度结果的干扰。
  4. 由于上述 “惩罚机制” 的存在，图表中出现断点，对应评分会产生大幅下降

后续调研发现：这个目标资源利用率其实效果不好，因为我们很多时候没法定义出目标资源利用率X%，比如增加机器或减少机器都会使这个抖动。

负载风险均衡

算法

  1. 获取待调度Pod的资源请求量，记为(r)。
  2. 获取待评分当前节点所有资源类型（CPU、内存、存储等）的资源利用率占比（范围0至1）的滑动窗口平均值(M)和标准差(V)。
  3. 计算当前节点每种资源类型的得分：
    [
    S_i = M + r + V
    ]
  4. 对每种资源的得分进行处理，将其限制在[0,1]范围内：
    [
    S_i = min(S_i, 1.0)
    ]
  5. 计算每种资源的节点优先级得分：
    [
    U_i = (1 - S_i) x 100
    ]
  6. 计算最终节点得分：
    [
    U = min(U_i)
    ]

示例

假设存在3个机器N1、N2、N3，待调度节点的CPU请求量为500毫核，内存请求量为1GB。所有节点的容量均为4核CPU和8GB内存。

可计算得出节点的资源请求占比为：
(r_{cpu} = 1/8)，(r_{memory} = 1/8)。

（注：CPU请求占比计算：500毫核=0.5核，0.5核÷4核=1/8；内存请求占比计算：1GB÷8GB=1/8）

注意下面的图，因为用k8s的概念画的，请把pod理解为我们上文一直说的节点，node理解为机器

按照步骤2～4，可以算出各资源利用率的平均值和标准差见下表

按照步骤5～6，可以算出每个机器的得分如下：

因此选出机器3。

后续

后续我们上面的算法全都试了试，核心算法都没有采用，因为跑出来的结果很难表现出是优越于当前的。

我们最后采用的算法是，高权重的全局方差最小 + 低权重Trimaran算法。

全局方差最小即：把节点放进机器后，计算某个指标的全局方差，最后全局最小方差的对应机器为结果。

跑出来绘图效果很明显，绝大多数的机器在分配一轮后都集中在了均值处。

参考文献