哈啰Kubernetes基于水位的自定义调度器落地之路后端kubernetes调度器

背景 k8s原生调度器默认资源平衡是根据Node节点的空闲request来实现的，但是我们配置Pod request预设值时基本是虚拟机的思想，会比实际程序使用值偏大并且和实际偏差较大，造成Node的request已分配比和资源实际利用率(水位)偏差较大，如下图所示。如果集群规模较大或集群运行时间较长，每个节点中request分配虽然接近，但是节点间资源水位相差很大。负载很高的主机其上的业务存在运行不稳定，同时负载很低的主机资源被大量浪费，哈啰自研的基于水位平衡的调度器主要就是为了解决这个问题。

文章图片

水位调度器整体工作逻辑：通过监控获取Node节点和Pod历史资源占用，在调度时，根据水位平衡算法，将低水位的Pod调度到高水位的Node节点上，将高水位的Pod调度到低水位的Node节点上，最终使整个集群中的Node水位相近，使物理资源得到更充分的利用，整个集群的稳定性也大大提升。本篇旨在实现一个平衡集群中Node实际使用率的调度器，从而达到提升集群稳定性，提高资源使用率的目的。
调度器简介 Kubernetes Scheduler通过watch etcd，及时发现PodSpec. NodeName为空的Pods，通过一定的规则，挑选最合适的Node，将PodSpec.NodeName设置为该Node name。该Node上的kubelet会监听到新Pod并启动。
Scheduler从 Kubernetes 1.16 版本开始, 构建了一种新的调度框架Scheduling Framework 的机制。Scheduling Framework无论在功能上，还是效率上相对之前的调度器都有很大的提升。下面主要对Scheduling Framework作一个简单的介绍。
工作流程

文章图片

这是官网提供的一个Scheduler工作流程图，其中每个阶段都可以进行定制(也称为扩展点)。每个插件可以实现一个或多个扩展点。
1.一个Pod从生成到绑定到Node上，称为一个调度周期。一个调度周期主要分为两大周期: 调度周期, 绑定周期，还有一个之前的sort阶段。
2.一般我们主要对调度周期进行一些定制。调取周期最重要的就是Filter和Score，下面详细介绍下他们的工作流程:
a. PreFilter 预过滤
该扩展点用于预处理有关 Pod 的信息，检查集群或 Pod 必须满足的某些条件。如果 PreFilter 返回错误，则调度周期将中止。在一个调度周期中，每个插件的PreFilter钩子函数只会执行一次。
b. Filter 过滤
过滤掉不满足需求的节点。如果任意一个插件返回的失败，则该Node就会被标记为不可用, Node不会进入下一阶段。过滤插件其实类似于上一代Kubernetes 调度器中的预选环节，即 Predicates。在每个调度周期中，每个插件的Filter钩子函数会执行多次(由Node数量决定)。
c. PreScore 预打分
预打分阶段主要可以提前计算数据、提前指标用于下一阶段的打分。也可以进行一些日志的打印。每个插件的PreScore钩子函数只会执行一次。
d. Score 打分
Score 扩展点和上一代的调度器的优选流程很像，它分为两个小阶段：

Score “打分”，用于对已通过过滤阶段的节点进行排名。调度程序将为 Score 每个节点调用每个计分插件进行打分，这个分数只要在int64范围内即可。
NormalizeScore “归一化”，用于在调度程序计算节点的最终排名之前修改分数，一般是对上一步得出来的分出进行再一次优化，可以不实现，但是需要保证 Score 插件的输出必须是 [0-100]范围内的整数。

e. 调度周期工作流程伪代码

allNode = K8S所有的node节点for PreFilter in (plugin1, plugin2, ...): IsSuccess = PreFilter(state *CycleState, pod *v1.Pod) if IsSuccess is False: return // 调度周期结束feasibleNodes = []// 存储Filter阶段符合条件的Node for nodeInfo in allNode: IsSuccess = False for Filter in (plugin1, plugin2, ...): IsSuccess = Filter(state *CycleState, pod *v1.Pod, nodeInfo *NodeInfo) // 如果任意一个插件返回了False，说明Node不符合调度条件 if IsSuccess is False: break if IsSuccess = True: feasibleNodes.append(nodeInfo)// 如果只有一个Node通过了Filter阶段的检查，该Node会直接进入绑定阶段，跳过打分阶段 if len(feasibleNodes) == 1: return feasibleNodes[0]for PreScore in (plugin1, plugin2, ...): PreScore(state *CycleState, pod *v1.Pod)NodeScores = { } // NodeScores数据结构: {"plugin1": [node1_score, node2_score], "plugin2": [...], ... } // 每个插件对每个Node，都会进行一次打分，总共会有(Node数量*插件数)个分数 for index, nodeInfo in feasibleNodes: for Score in (plugin1, plugin2, ...): score = Score(state *CycleState, pod *v1.Pod, nodeInfo *NodeInfo) NodeScores[插件名][index] = score // 归一化，这个阶段处理过，分数都在[1-100]之间 for NormalizeScore in (plugin1, plugin2, ...): nodeScoreList = NodeScores[插件名] NormalizeScore(state *CycleState, p *v1.Pod, scores NodeScoreList) // 加上插件权重因子 for pluginName, nodeScoreList in NodeScores: for nodeScore in nodeScoreList: nodeScoreList[i].Score = nodeScore.Score * int64(pluginWeight)// 计算每个Node的总分 result = [] for nodeIndex, nodeName in feasibleNodes { _result = {Name: nodeName, Score: 0}) for pluginName, _ in NodeScores { _result.Score += NodeScores[pluginName][nodeIndex].Score } result.append(_result) }// result 结果为 [{Name: node1, Score: 200}, {Name: node2, Score: 100}, ...]// selectHost 找到得分最高的Node进入绑定阶段 Node = selectHost(result) return Node

3.绑定周期
一般都是对一些资源进行处理，或者增加一些日志、事件触发等，常用的是PreBind和PostBind。
a. Permit审批
在每个Pod的调度周期结束时，将调用Permit插件，以防止或延迟与候选节点的绑定。permit插件可以执行以下三项操作之一：

approve
一旦所有permit插件批准Pod，便将其发送以进行绑定。
deny
如果任何permit插件拒绝Pod，则将其返回到调度队列。这将触发Reserve插件中的Unreserve阶段。
wait(with a timeout)
如果Permit插件返回”wait”，则Pod会保留在内部的”waiting” Pods列表中，此Pod的绑定周期开始，但会直接阻塞，直到获得批准为止。如果发生超时，wait将变为deny，并且Pod将返回到调度队列，从而触发Reserve插件中的Unreserve阶段。

b. PreBind 预绑定
用于执行绑定Pod之前所需的任何工作。例如，PreBind插件可以设置网络卷并将其挂载在目标节点上，然后再允许Pod在此处运行。如果任何PreBind插件返回错误，则Pod被拒绝并返回到调度队列。
c. Bind 绑定
将Pod绑定到节点。在所有PreBind插件完成之前，不会调用Bind插件。每个Bind插件均按配置顺序调用。Bind插件可以选择是否处理给定的Pod。如果Bind插件选择处理Pod，则会跳过其余的Bind插件。
d. PostBind
成功绑定Pod后，将调用PostBind插件。绑定周期到此结束，可以用来清理关联的资源。
调度器插件配置
可以通过配置文件(可以是文件或者configmap)指定每个阶段需要开启或者关闭的插件。

apiVersion: kubescheduler.config.k8s.io/v1alpha2 kind: KubeSchedulerConfiguration profiles: - schedulerName: default-scheduler plugins: preFilter: enabled: - name: HheWaterLevelBalance filter: enabled: - name: HheWaterLevelBalance - name: HkePodTopologySpread preScore: enabled: - name: HkePodTopologySpread - name: HheWaterLevelBalance score: enabled: - name: HkePodTopologySpread// 启用自定义插件 - name: HheWaterLevelBalance disabled: - name: ImageLocality// 禁用默认插件 - name: InterPodAffinity postBind: enabled: - name: HheWaterLevelBalance pluginConfig:// 插件配置 - name: HheWaterLevelBalance args: clusterCpuMinNodeWeight: 0.2

方案调研 kubernetes-sigs的TargetLoadPacking插件
实现原理

通过一个Metrics Provider提供api，可查询Node cpu使用率(时间窗口为5分钟，10分钟，15分钟)
通过配置文件设置cluster_cpu(百分比)，表示期望每个Node的cpu 使用率都达到这个值
score阶段算法
获取要评分的Node的15m cpu利用率。记为node_cpu
根据Pod limit计算出当前 Pod 的cpu 使用量, 除以Node容量，计算出该Pod在当前Node的cpu 使用率。记为 pod_cpu
如果 Pod 调度在该节点下，计算预期利用率，即 target_cpu = node_cpu + pod_cpu
如果 target_cpu <= cluster_cpu，则返回 (100 - cluster_cpu)target_cpu/cluster_cpu+ cluster_cpu 作为分数，记为情况A
如果 cluster_cpu < target_cpu <= 100%，则返回 50(100 - target_cpu)/(100 - cluster_cpu) ，记为情况B// 注意这里的50有问题，后面我会特别说明
如果 target_cpu > 100%，返回 0，记为情况C

核心思想：
1.这个算法其实就是数学中装箱问题(背包问题)的变种，采用的best fit 近似算法
2.把Pod尽量调度到接近cluster_cpu线的node上
3.负载高的Pod会调度到相对低的node上，负载低的Pod会调度到负载相对高的node上

文章图片

4.热点问题:

scheduler本地维护了一个缓存ScheduledPodsCache
使用informer监听Pod事件
在Pod binding到Node后，会写入缓存ScheduledPodsCache
在打分阶段，取到Node的 metrcs update time记为metrics_time, 当缓存中该Node中的Pod的Timestamp 大于等于metrics_time, 记为missingUtil
计算Node实际负载时，会加上missingUtil
定时清理过久数据
监听Pod事件，如果Pod销毁，该Pod信息会从缓存中删除

总结 a. 该插件算法实现了负载偏低的Pod调度到负载高的Node上，负载偏高的Pod调度到负载低的Node上，这部分符合预期
b. Pod cpu使用量是通过limit取得，在我们公司内limit和Pod实际使用率偏差较大，造成计算出来的target_cpu不符合实际
c. 需要预设集群理想值cluster_cpu，因为互联网业务，存在明显的业务高峰和低谷，没办法配置一个固定值
d. 上面的算法50(100 - target_cpu)/(100 - cluster_cpu)中的这个50是有问题的，在计算出来的target_cpu过低的情况下，情况B的得分有可能比情况A高，Pod会被调度到高与cluster_cpu的Node上。在集群扩容节点的时候，这种情况尤为严重。下图为当cluster_cpu=10%的情况下，该算法的得分情况:

文章图片

这个问题我已经提了pr，详细见：https://github.com/kubernetes...
crane-scheduler
实现原理 a. 通过一个Node-annotator组件定期从Prometheus中拉取节点负载 metric(cpu_usage_avg_5m、cpu_usage_max_avg_1h、cpu_usage_max_avg_1d、mem_usage_avg_5m、mem_usage_max _avg_1h、mem_usage_max_avg_1d)，写入到节点的 annotation中
b. 为了避免 Pod 调度到高负载的 Node 上, 可以通过参数配置，在filter阶段直接把负载过高的Node过滤掉
c. 在score阶段，读取Pod annotation实际负载的上述指标，然后根据加权和运算进行打分
实现的目标：把尽可能多的Pod调度到实际负载低的Node上
d. 热点问题解决

如果节点在过去1分钟调度了超过2个 Pod，则优选评分减去1分
如果节点在过去5分钟调度了超过5个 Pod，则优选评分减去1分

总结 a. 大部分Pod实际负载偏低，但是根据crane-scheduler的算法，大量的这种Pod被调度到低水位的Node上，造成Node 的limit预分配已经满了，Node真实水位依旧很低
b. 没有考虑Pod实际应用负载，期望的情况应该是负载偏低的Pod调度到负载高的Node上，或者相反
自研方案整理核心前提
通过对上面两个方案的分析，自研方案必须要满足的前提条件:

必须获取到Node的历史和当前水位
必须获取到被调度Pod的资源利用率
通过计算Node和Pod水位，负载偏低的Pod调度到负载高的Node上，负载偏高的Pod调度到负载低的node上
需要考虑业务的波峰谷底
需要考虑热点问题

水位的获取
1.Node水位
Node水位实现比较简单，通过一个golang程序读取 Prometheus或其他监控系统中的 Node 真实负载信息,写入Node的annotation中。
2.Pod水位
Pod的水位获取会麻烦一些，这里分成两类，一类为通过Deployment、Cloneset管理的Pod。其他的都归为第二类。
a. 第一类(以Deployment示例):

监控信息的获取与Node一样，读取 Prometheus中的负载信息，写入Deployment或Cloneset中的annotation中
调度时，通过Pod的OwnerReferences属性，查到Deployment
读取Deployment 的annotation

b. 第二类

读取Pod的limit作为Pod的水位资源

计算公式
参考上面的TargetLoadPacking插件算法, 伪代码如下:

cluster_cpu = 预设理想值 target_cpu = node_cpu + pod_cpu if target_cpu <= cluster_cpu: score = (100 - cluster_cpu)target_cpu/cluster_cpu+ cluster_cpu else if cluster_cpu < target_cpu <= 100: score = cluster_cpu(100 - target_cpu)/(100 - cluster_cpu) else: score = 0

现在预设：
1.集群理想值为cluster_cpu=20%,
2.有一个需要调度的Pod，需要占用的水位为Pa =1
3.假设有5个Node，水位(node_cpu)分别是

Na = 0 Nb = 4 Nc = 24 Nd = 49 Ne = 98

4.当Pod分别调度到这5个Node上时，Node的水位(target_cpu)占用

Ta = 1 Tb = 5 Tc = 25 Td = 50 Te = 99

5.计算得分(score)

Sa = (100 - 20) * 1 / 20 + 20 = 24 Sb = (100 - 20) * 5 / 20 + 20 = 40 Sc = 20 * (100 - 25) / (100 - 20) = 19 Sd = 20 * (100 - 50) / (100 - 20) = 13 Se = 20 * (100 - 90) / (100 - 20) = 3

业务的波峰谷底
需要解决三个问题:
1.Pod、Node水位的获取要多个时间段
这里采用三个时间段: 15分钟、1小时、1天。
2.预设理想值根据实时集群整体水位进行动态调整
这里也可以直接使用实时集群Node的平均水位作为集群的理想值，但是有一个缺点: 通过上面的算法，可以得知Pod会尽量落到理想值附近的Node上，没办法及时填充到最低水位的Node上。所以最好最低node的水位也参与计算。调整过的算法如下:
cluster_cpu = (cluster_cpu_avg + min_node_cpu * min_weight) / (1+ min_weight )
min_weight可通过配置文件配置，cpu水位差值比较大的时候，min_weight可以配置的比较高，偏差小的时候配置低一些
3.打分公式需要多个维度
获取Node和Pod 15分钟、1小时、1天的水位，分别根据上面的公式计算出来三个分数score_15m, score_1h,score_1d，根据比例算出来一个新的分数，作为最终得分。
score = score_15m weight + score_1h weight + score_1d * weight
解决热点问题
1.scheduler本地维护了一个缓存ScheduledPodsCache，数据结构:

{ "node1": [ { "Timestamp": "unixTime", "PodName": "podName", "PodUtil": { "cpu": 100, "mem": 500 } }, { "Timestamp": "unixTime2", "PodName": "podName2", "PodUtil": { "cpu": 100, "mem": 500 } } ], "nodeName2": { "Timestamp": "unixTime", "PodName": "podName", "PodUtil": { "cpu": 100, "mem": 500 } } }

2.Pod binding到Node后，会写入缓存ScheduledPodsCache
3.在打分阶段，取到Node的 metrcs update time记为metrics_time, 当缓存中该Node中的4. Pod的Timestamp 大于等于metrics_time, 记为missingUtil
4.计算Node实际负载时，会加上missingUtil
5.定时5m 会清理过久数据
6.监听Pod事件，如果Pod销毁，该Pod信息会从缓存中删除
工作流程图

文章图片

方案落地社区主流的调度器扩展方案分为两种extender，framework plugin。两者都属于非侵入式的方案，无需修改scheduler核心代码。其中framework plugin在Kubernetes 1.16开始支持，具有灵活、效率高等优点。所以本次扩展通过framework plugin形式实现。
插件注册
可以在https://github.com/kubernetes... 找到示例

import ( "math/rand" "os" "time""k8s.io/component-base/logs" "k8s.io/kubernetes/cmd/kube-scheduler/app""pkg/hhewaterlevelbalance" "pkg/pugin2" )func main() { rand.Seed(time.Now().UnixNano()) // Register custom plugins to the scheduler framework. // Later they can consist of scheduler profile(s) and hence // used by various kinds of workloads. command := app.NewSchedulerCommand( app.WithPlugin(hhewaterlevelbalance.Name, HheWaterLevelBalance.New),// hhewaterlevelbalance.Name为插件名字 app.WithPlugin(pugin2.Name, pugin2.New), )logs.InitLogs() defer logs.FlushLogs()if err := command.Execute(); err != nil { os.Exit(1) } }

将cmd/main.go打包成新的kube-scheduler，替换掉线上的版本即可。
修改版本号
在执行./bin/kube-scheduler --version加上一些标识，方便识别是自定义调度器。
修改makefile

VERSION := $(shell git describe --tags --match "v*" | awk -F - '{print $$1}' 2>/dev/null || (printf "v0.0.0")) COMMIT := $(shell git rev-parse --short HEAD) RELEASE_DATE :=$(shell date +%Y%m%d)LDFLAGS=-ldflags "-X k8s.io/component-base/version.gitVersion=$(VERSION)-$(COMMIT)-${RELEASE_DATE}-hellobike -w"build: go build $(LDFLAGS) -o bin/kube-scheduler cmd/main.g

执行make install即可。
插件实现
在对应的阶段实现逻辑代码即可，示例：

// 插件名称 const Name = "HheWaterLevelBalance"type HheWaterLevelBalanceArgs struct { ClusterCpuMinNodeWeight float64 }type HheWaterLevelBalance struct { args*HheWaterLevelBalanceArgs handle framework.FrameworkHandle }func (h *HheWaterLevelBalance) Name() string { return Name }func (h *HheWaterLevelBalance) PreFilter(pc *framework.PluginContext, pod *v1.Pod) *framework.Status { klog.V(3).Infof("prefilter pod: %v", pod.Name) return framework.NewStatus(framework.Success, "") }func (h *HheWaterLevelBalance) Filter(pc *framework.PluginContext, pod *v1.Pod, nodeName string) *framework.Status { klog.V(3).Infof("filter pod: %v, node: %v", pod.Name, nodeName) return framework.NewStatus(framework.Success, "") }func (h *HheWaterLevelBalance) PreScore( pc *framework.PluginContext, cycleState *framework.CycleState, pod *v1.Pod, filteredNodes []*v1.Node, ) *framework.Status { klog.V(3).Infof("prescore pod: %v", pod.Name) return framework.NewStatus(framework.Success, "") }func (h *HheWaterLevelBalance) Score(pc *framework.PluginContext, cycleState *framework.CycleState, pod *v1.Pod, nodeName string) (int64, *framework.Status) { klog.V(3).Infof("score pod: %v, node: %v", pod.Name, nodeName) return score, framework.NewStatus(framework.Success, "") }func New(config *runtime.Unknown, f framework.FrameworkHandle) (framework.Plugin, error) { args := &HheWaterLevelBalanceArgs{} if err := framework.DecodeInto(config, args); err != nil { return nil, err } klog.V(3).Infof("get plugin config args: %+v", args) return &HheWaterLevelBalance{ args: args, handle: f, }, nil }

运行效果对比图一为开启HheWaterLevelBalance前的监控图，Node间的水位最大偏差达到50%多。图二为插件运行一段时间后的监控图，水位偏差基本维持在15%左右。

文章图片

文章图片

总结 1.现在Node和Pod的水位获取都是借助annotation来实现的，考虑性能，后续应该统一使用Kubernetes Metrics Server来实现。
2.后续可以加入时序变量，实现潮汐混部，提升业务低峰期集群利用率。
3.水位均衡可以明显提升集群稳定性。再配合弹性伸缩、Pod request/limit预测配置等措施，一起来实现降本的目的。
（本文作者：朱喜喜）
【哈啰Kubernetes基于水位的自定义调度器落地之路】