Trimaran: 基于实际负载的K8s调度插件
接受范围｜初级
为了应对集群节点高负载、负载不均衡等问题，需要动态平衡各个节点之间的资源使用率，因此需要基于节点的相关监控指标，构建集群资源视图，从而为下述两种治理方向奠定实现基础：
在 Pod 调度阶段，加入优先将 Pod 调度到资源实际使用率低的节点的节点Score插件
在集群治理阶段，通过实时监控，在观测到节点资源率较高、节点故障、Pod 数量较多等情况时，可以自动干预，迁移节点上的一些 Pod 到利用率低的节点上
针对方向一，可以通过赋予Kubernetes调度器感知集群实际负载的能力，计算资源分配和实际资源利用之间的差距，优化调度策略。
针对方向二，社区给出了Descheduler方案，Descheduler 可以根据一些规则和策略配置来帮助再平衡集群状态，当前项目实现了十余种策略。
注意：Descheduler等方案存在一些与主调度策略不一致的可能性
本文将针对方向一的实现进行详细说明，方向二中Descheduler将在后续文中进行相关介绍。
需求背景
Kubernetes提供了声明式的资源模型，核心组件（调度器、kubelet和控制器）的实现能够满足QoS需求。然而，由于下述一些原因，该模型会导致集群的低利用率：
用户很难准确评估应用程序的资源使用情况，因而对于Pod的资源配置，无从谈起
用户可能不理解资源模型，从而直接使用Kubernetes默认调度插件（Score）（默认插件不考虑实际节点利用率值）。
依托实时资源使用情况，构建调度插件以调度pod，最终的目标是在不破坏Kubernetes资源模型的前提下，降低集群管理的成本，提高集群的利用率，为了实现上述需要，因此提出以下预期条件：
提供可配置的调度插件以提高集群利用率。
每个节点的预期CPU利用率不应超过设定百分比（约束条件）。
尽量避免影响默认score插件逻辑。
该功能以score插件方式实现
使用场景
场景一
作为一家使用公有云的公司，希望通过提升节点实际利用率的方式来降低机器成本。
作为一家拥有的数据中心的公司，希望通过提升节点实际利用率的方式，来减少集群相关的硬件开支和维护。
场景二
尽可能地提高资源利用率的方式可能无法解决所有问题，通过扩大集群的规模以处理突如其来的业务高峰总是需要一些时间的，因此集群管理员希望为突发的高峰留下足够的扩展空间，此时可能就需要有足够的时间向集群添加更多的节点，当然该问题可以通过空闲集群节点、forzen资源方式来缓解，类似函数计算中的热启动等。
设计方案
设计方案由以下组件组成，监控指标整合器（Metrics Provider）、负载监测器（Load Watcher）、数据库及调度插件组成，如下图所示，重点为两个插件算法，即 TargetLoadPacking和 LoadVariationRiskBalancing。这两个插件算法都使用来自负载监控器的指标，用不同的算法对节点进行评分。
监控指标汇聚器
监控指标整合器支持时间序列数据库，如Prometheus、InfluxDB、Kubernetes Metrics Server等。
负载监测器将缓存过去15分钟、10分钟和5分钟窗口的指标，并通过REST API提供查询服务。
这里使用了K8s的调度器框架，注册定制的基于实际负载感知的调度器插件。该插件主要包括以下两个算法：
TargetLoadPacking：它是bin pack算法的best fit变体(刷过算法应该知道，背包算法)，它通过节点的实际资源利用率给节点打分，使所有被利用的节点都有大约x%的利用率。一旦所有节点达到x%的利用率，它就会转到least fit。
LoadVariationRiskBalancing：这是一个节点排序插件，根据节点资源利用率的平均值和标准差对节点进行排序。它不仅是为了平衡负载，也是为了避免负载变化引起的风险。
插件将扩展Score的扩展点。K8s调度器框架在调度一个pod时，调用Score方法为每个节点打分。
以下是该算法步骤：
获取当前节点的利用率，以进行评分，假定该节点为A。
计算当前pod的CPU总的request和overhead，假定该结果为B。
计算如果pod被调度到该节点下预期的利用率，通过添加即U=A+B。
如果U <= X%，返回(100 - X)U/X + X作为分数
如果X% < U <= 100%，返回50(100 - U)/(100 - X)
如果U>100%，返回0
举例说明，假设有三个节点X、Y和Z，每个节点有四个cpu，分别使用了1、2和3个cpu。简单起见，假设要调度的pod有0个CPU request和overhead，设定X=50%。
每个节点的利用率：
Ux → (1/4)*100 = 25Uy → (2/4)*100 = 50Uz → (3/4)*100 = 75
X → (100 - 50)*25/50 + 50 = 75Y → (100 - 50)*50/50 + 50 = 100Z → 50 * (100 - 75)/(100 - 50) = 25
根据上述算法，50%是所有节点预设的目标利用率，当然可以把它降低到40%，这样在高峰期或意外负载期间，它超过50%的机会就会少得多。因此，一般来说，为了达到X%的利用率（在实践中建议使用X-10值）。
在算法的第二步，一个变体的算法是使用当前pod的总CPU limit而不是request，以期获取一个更宽松的利用率的上限预期。
其中节点利用率的X%阈值通过插件的参数进行配置。
上图表述了算法概述中函数表现，通过上图可以发现算法表征的多样性。
当利用率从0到50%时，优先选择调度pod至这些节点。
当利用率超过50%时，在这些 "热"节点之间调度pod时，针对这些节点线性降权。
正的斜率从50开始，而不是从0开始，因为分数的范围是0-100，分数越低的节点得分越高，这样分数就越可观，其他插件对调度结果的影响也不会太大。
图中有一个断点，由于我们的降权，产生了一个下降坡度。
参数配置
type PluginArgs struct {TargetCPUUtilisation intDefaultCPURequests v1.ResourceList}
插件将扩展Score的扩展点。K8s调度器框架在调度一个pod时，调用Score方法为每个节点打分。
因为没有考虑到突发性的变化，基于实际平均负载的策略有时是有风险的。LoadVariationRiskBalancing插件不仅可以平衡实际平均负载，还可以降低负载突发性变化引发的风险。假设把所有节点利用率的平均值（M）和标准差（V）绘制成下面的mu-sigma图。在这种情况下，LoadVariationRiskBalancing插件将进行处理，使所有节点的利用率在对角线上对齐，即V + M = c。这里，c是一个常数，表示整个集群的利用率平均值加上标准偏差。总之，考虑到所有节点上的负载随时间动态变化，LoadVariationRiskBalancing插件倾向于选择低风险节点，即负载超出节点可分配总量的节点。
以下是该算法步骤：
获取待调度的Pod 的request的资源，设为r 。
获取当前节点所有类型的资源（CPU、Memory、GPU等）的利用率的百分比（0到1），并根据计算的滑动窗口的平均数（V）和标准差（M），进行打分。
计算当前节点的每一类资源的得分: 。
为每种类型的资源获取一个分数，并将其映射到[0,1]区间: 。
计算每个资源的节点优先级分数为：。
得到最终的节点分数为：。
举例说明，假设有三个节点N1、N2和N3，要安排的pod的CPU和内存请求为500 milicores和1 GB。所有节点都有4个cpu和8GB的内存。
Pod的资源请求比例可以计算为
然后根据步骤2~4，可以计算出CPU和内存部分利用率的平均值和标准偏差，如下所示。
根据步骤5~6，每类资源和每个节点的得分如下。
根据我计算的分数，节点N3将被选中，分数如下。
如果把这些分数画在mu-sigma图中，经过线性拟合可以把节点的利用率推到对角线sigma = 1 - mu。这里的1表示100%的利用率。这里可以配置的是系数ita，表示mu + ita x sigma <= 100 %，这里选择ita = 1。ita在这里模拟使用率不超过节点容量，假设实际使用率遵循高斯分布，并遵循68-96-99.5规则。
因此，当ita设定为不同的值时，可以得到不同的但不超过容量的线性图。
ita=1，有16%的风险几率，使用量超过节点容量。
ita = 2，有2.5%的风险几率，实际使用量超过节点容量。
ita = 3，有0.15%的风险几率，实际使用量超过节点容量。默认情况下，选择ita=1，因为希望提高整体利用率。ita参数可以通过插件的SafeVarianceMargin配置。
参数配置
type PluginArgs struct {SafeVarianceMargin int}
API设计
a. REST API
GET /watcher说明：返回集群中所有节点的指标
GET /watcher/{hostname}说明：返回给定主机名的指标
注意：如果没有指标，则返回404
b. 返回结构
{"$schema": "http://json-schema.org/draft-04/schema#","type": "object","properties": {"timestamp": {"type": "integer"},"window": {"type": "object","properties": {"duration": {"type": "string"},"start": {"type": "integer"},"end": {"type": "integer"}},"required": ["duration","start","end"]},"source": {"type": "string"},"data": {"type": "object","patternProperties": {"^[0-9]+$": {"type": "object","properties": {"metrics": {"type": "array","items": [{"type": "object","properties": {"name": {"type": "string"},"type": {"type": "string"},"rollup": {"type": "string"},"value": {"type": "integer"}},"required": ["name","type","rollup","value"]},{"type": "object","properties": {"name": {"type": "string"},"type": {"type": "string"},"rollup": {"type": "string"},"value": {"type": "integer"}},"required": ["name","type","rollup","value"]}]},"tags": {"type": "object"},"metadata": {"type": "object","properties": {"dataCenter": {"type": "string"},"pool": {"type": "string"}}}},"required": ["metrics"]}}}},"required": ["timestamp","window","source","data"]}
注意事项
控制器以goroutine方式监听.spec.nodeName事件，其保持一个节点→pod映射的时间顺序状态，用于存储过去5分钟内成功调度的pod。在不同的调度周期中维护该状态，并供TargetLoadPacking/LoadVariationRiskBalancing Score插件使用。它将有助于在指标异常的时候根据前期实际分配情况来预测利用率。
小结
局限性
启用上述插件将会与调度器中的2个默认评分插件的产生冲突："NodeResourcesLeastAllocated "和 "NodeResourcesBalancedAllocation "插件。因此，建议在启用上述插件时禁用默认两个插件。
如果利用率的指标在很长一段时间内不可用，将退回到基于分配的best fit的bin pack算法，而无需用户干预。为了达到X%的利用率，建议在实践中将该值设置为X - 10，以下为其他注意项与缺陷：
将上述约束条件2作为Filter插件。
在最初的设计中没有解决不服预期的调度结果（热节点，碎片等）被取消的问题。
在最初的设计中没有考虑内存、网络和磁盘等利用率。
由于笔者时间、视野、认知有限，本文难免出现错误、疏漏等问题，期待各位读者朋友、业界专家指正交流。
参考文献
1.https://github.com/kubernetes-sigs/scheduler-plugins/tree/master/kep/61-Trimaran-real-load-aware-scheduling
真诚推荐你关注