背景

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阶段符合条件的Nodefor 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/v1alpha2kind: KubeSchedulerConfigurationprofiles:- 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_cpuif 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 = 0Nb = 4Nc = 24Nd = 49Ne = 98

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

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

5.计算得分(score) 

Sa = (100 - 20) * 1 / 20 + 20 = 24Sb = (100 - 20) * 5 / 20 + 20 = 40Sc = 20 * (100 - 25) / (100 - 20) = 19Sd = 20 * (100 - 50) / (100 - 20) = 13Se = 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预测配置等措施，一起来实现降本的目标。

（本文作者：朱喜喜）

本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者应用。非商业目标转载或应用本文内容，敬请注明“内容转载自哈啰技术团队”。