作者简介
本文作者为携程Cloud Container团队的鸿飞，静雪，诗燕。该团队负责K8s容器平台的研发和优化工作，专注于推动基础设施云原生架构升级，以及创新产品的研发和落地，持续提升资源利用率、弹性和治理能力。
一、背景介绍
携程K8s容器服务承载着各BU的核心业务，容器数量超过10W，并仍然以每年数倍的速度增长。调度体系也经历了从Mesos上的自研调度器到K8s fork版本的调度器演进过程。
业务目标上，最初调度器只服务于在线应用发布，现在则致力于打造统一弹性调度体系，随着容器化的深入，逐渐完成统一资源池的构造，在此基础上持续提升资源效率，以及应对流量变化、灾难甚至业务国际化需求的混合弹性调度能力构建。实现上，我们当前以K8s官方版本调度器为基础，融合了在公司业务演进过程中积累的经验，进行大量改造和优化。
本文将部分分享Cloud Container团队在打造统一调度接入能力、算法和性能优化等方面的实践。
二、统一调度接入能力优化
整个K8s容器平台上已经接入了多种不同类型的应用，包括在线应用、Redis、MySQL、Spark Job、AI训练等，这些应用为了满足自身业务目标，会存在多样性的调度需求。同时调度体系本身也会基于资源统一调配、对资源效率持续优化的目的，也要能对调度行为进行透明干预。
如果要打造一个统一调度的资源池，为后续价值释放创造尽可能大的基数，就必须收口调度能力。构建统一调度体系的一大挑战，便是如何通过一个调度器，来抽象和管理这些需求，在业务和调度体系间构建一个良好的解耦边界，我们总体的解决思路可以用下图描述。
首先需要对共性需求进行整理，通过Configmap或者CRD抽象成Policy。对于一些需要参数化的Policy，还可以通过模板机制创建一个中间抽象PolicyTemplate。平台方或者业务方可以针对一类Pod创建Binding实例，指明需要绑定的Policy；或者绑定哪一个PolicyTemplate，并在Binding对象实例中指明用来渲染模板的参数集。
平台可以利用Pod绑定的Policy，重写Pod的Spec；也可以由Controller或者Scheduler来消费这些Policy，从而动态配置针对Pod的行为。当然，有时也可以将Binding对象简化为使用Pod的Annotation实现。以下，将用两个实际场景来说明。
2.1 算法集参数化配置
我们知道，K8s scheduler调度过程分为预选(Predicate)和优选(Priority)两个阶段，每个阶段又都有一系列的算法参与计算。Pod所属的业务类型不同，对Pod的调度算法选取以及权重参数等可能不同。在原生调度器中，调度器初始化入口处可以根据配置文件或者configmap来读取schedulerapi.Policy，从而配置调度器的算法集和参数。
代码语言：javascript复制type Policy struct {
metav1.TypeMeta
Predicates []PredicatePolicy
Priorities []PriorityPolicy
ExtenderConfigs []ExtenderConfig
HardPodAffinitySymmetricWeight int32
AlwaysCheckAllPredicates bool
}但这种方式的配置只在调度器启动时加载，运行过程中无法进行热更新，也无法根据Pod不同来指定不同的配置。如果想要同时支持多个算法集，就必须运行多个调度器实例，并通过指定Pod的schedulerName来选择对应的调度器实例。
这种方式不够灵活，而且当多个调度器对同一组Node进行调度管理时，资源分配状态并不能共享。我们希望能在一个调度器中通过参数化配置，针对Pod的类型动态指定需要的算法集以及算法集参数。
基于这个原因，我们增强了调度器Policy机制，引入了PolicyCacheProvider对象。PolicyCacheProvider对象通过watch调度Policy的configmap，在本地内存构建一个Policy对象的查询缓存。当某个Pod在创建时，就可以通过Annotation，来决定scheduler在调度一个Pod时，使用哪个Policy来进行调度。
代码语言：javascript复制sched.cloud.ctrip.com/policy=xxx通过这种方式，就可以在一个调度器实例中，实现调度算法参数化动态配置，满足不同业务的特殊算法需求。
2.2 亲和性参数化配置
在我们容器化过程中，经常会遇到各种亲和性调度需求，如：
- 尽量调度到avx512指令集的宿主机
- 尽量不与另一个或者某类应用共享宿主机
- 尽量调度到部门私有资源池上，如果私有资源池满了，再调度到公共资源池
一种做法是业务方自己组装Pod Spec中Affinity/AntiAffinity部分。但这种方式的问题，一个是业务方会涉及过多底层实现细节，增加心智负担，无法保证一致的质量，再者，平台方无法进行统一规范和干预，如利用应用画像，结合资源容量情况，来对应用亲和性调度规则进行持续地、透明地优化，以及共享资源池上的优先级协调。
基于此，我们对NodeAffinity/PodAffinity进行了PolicyTemplate的CRD抽象，分别提炼出NodeSchedulerConfig(简写nsc)和PodSchedulerConfig(简写psc)以及SchedulerConfigBinding(简写scb)对象。
Pod在创建时，会由sched-webhook根据绑定的Policy，更新Pod Spec。因此，业务方在使用时，不必再自己组装Pod Spec中的细节，可以直接通过Annotation指定预设好的Pod的亲和性调度规则，平台管理员也可以通过创建Binding对象透明改变Pod的调度行为。
以资源池需求为例，某个应用需要优先使用资源池A，若无法满足，就使用资源池B，对应的NodeSchedulerConfig可以定义为：
代码语言：javascript复制apiVersion: sched.cloud.ctrip.com/v1
kind: NodeSchedulerConfig
metadata:
name: resource-pool-example
spec:
nodeAffinity:
requiredDuringSchedulingIgnoredDuringExecution:
nodeSelectorTerms:
- matchExpressions:
- key: cloud.ctrip.com/pool
operator: In
values:
- {{.PrefferredPool}}
- matchExpressions:
- key: cloud.ctrip.com/pool
operator: In
values:
- {{.DefaultPool}}
preferredDuringSchedulingIgnoredDuringExecution:
- weight: 3
preference:
matchExpressions:
- key: cloud.ctrip.com/pool
operator: In
values:
- {{.PrefferredPool}}
- weight: 2
preference:
matchExpressions:
- key: cloud.ctrip.com/pool
operator: In
values:
- {{.DefaultPool}}
...对用来Binding的Pod Annotation可以定义为：
代码语言：javascript复制scb.sched.cloud.ctrip.com/nsc=resource-pool-example
scb.sched.cloud.ctrip.com/nsc-args='{"DefaultPool":"B","PrefferredPool":"A"}'通过这种方式，现在已经为各种业务方提供了几十种不同NodeSchedulerConfig和PodSchedulerConfig的配置组合。
三、算法优化
3.1 扩展的资源平衡算法
为了避免在调度过程中，造成不同资源之间配比产生碎片，即避免出现两个Node分别剩余32C1G和2C64G的情况，原生调度器提供了balanced_allocation算法。该算法通过计算资源的request和capacity的比值，并力求资源间的配比均衡来避免出现个别资源的分配碎片。
但这个算法只考虑了几个主要的资源CPU、MEM、Volume，并没有考虑其它维度的资源。如对AI应用而言，GPU资源远比其它资源珍贵，应该要参与资源平衡性计算，甚至该资源在计算时应该赋予更高的权重。基于此，我们扩展了balanced_allocation算法，将更多资源加入计算过程，同时赋予不同资源不同的权重，通过上面提到的参数化配置方法加以灵活的配置，解决了这个问题。
3.2 水位感知的堆叠与打散算法
原生调度器中，内置了most_requested和least_requested算法，对应于堆叠策略和打散策略，即尽量先选取剩余资源较少或较多的宿主机，默认选取的是打散策略。在我们的私有云中，一般倾向于各宿主机热点尽量均衡，所以使用的与默认调度器一样，为打散策略；在公有云上，考虑到autoscaler场景，尽量缩容那些较空闲的宿主机，一般使用堆叠策略。
但在私有云场景下，我们发现当集群总体水位较满时，大量宿主机剩余一些碎片不能被分配出去，特别是一些大配置的Pod无法调度成功，但这些碎片如果合并起来，总体的量仍然相当可观。为了将这些“边角料”利用起来，我们修改了策略，引入一个集群整体资源水位的概念，用来切换打散策略和堆叠策略。
如图所示，当整个集群中已经被分配出去的资源占总体资源的比例超过一个阈值，则切换为堆叠策略，这些“边脚料”资源就能攒在一起，被充分利用。通过这种方式，在资源紧张的时期，我们私有云的分配率极限可以达到98%。
3.3 运行时负载感知算法
Pod的request仅是对资源使用的一个静态估计值，与Pod实际资源使用会发生偏差，随着时间的推移，从资源分配视图来看，集群是平衡的，但从实际负载情况来看，会出现热点，在使用了超分和混部后，热点情况会更加严重。要解决这个问题，不管是在首次调度还是重调度，都应该考虑集群实际负载。
基于此，我们新增了一个负载感知算法most_available，倾向于选取实际负载较轻的Node。其中，第i个Node打分如下(k为资源编号)：
VirtualAvailable是Node运行时可用资源的Cache值，每当Node进行metric上报时，就会更新VirtualAvailable。每调度一个Pod到Node，因为metric更新延迟，需要在VirtualAvailable上减去VirutalRequest。VirtualRequest是对Pod实际使用资源的一个估计值，由Pod Annotation指定，否则取Pod的Request值。VirtualAvailable和VirtualRequest的引入，既在调度时考虑了集群实际负载，又能避免在超分的时候，短时创建的大量Pod都集中调度到部分Node上，形成热点。
四、性能优化
在大集群扩容时，会出现Pod阻塞在调度队列的情况，原生调度器的性能并不能满足我们的要求。我们对社区性能测试工具进行改造，去除大量公有云环境依赖，根据自身场景加入性能测试集；同时，对调度器调度的各个阶段进行prometheus埋点。
通过反复测试，最终定位到多个瓶颈点，其中最主要的是优选阶段的inter-pod affinity/anti-affinity算法。该算法主要用于完成某一组Pod在一个物理拓扑域上亲和性策略，如相同应用的实例在物理AZ上打散、互相数据交换量大的一组应用尽量部署在同一个机架等高级功能，被大量使用。我们对其关键的打分计算过程进行了分析，为了叙述的方便，忽略对称性等相似计算步骤，可以简化为：
代码语言：javascript复制fn CalcInterPodAffinityPriority(pod, nodes, nodeCandidates) nodeScoreMap
for node in nodes:
for np in nodes.Pods:
for at in np.affinityTerms:
if pod.match(at):
for cn in nodeCandidates:
if cn.labelMatch(at.topologyTerm):
nodeScoreMap[cn] = at.weight该算法会遍历每一个Node上的每一个Pod，若与待调度的Pod在AffinityTerm上匹配，则再遍历每个经预选算法筛选后的Node，若该Node的label命中Pod指定的Topology，将会增加该Node的得分。假定集群中Pod总数为Np, 平均每个Pod的AffinityTerm数为2，经过预选后的Node数为Nc，Node的label个数为5，所有Pod中，与待调度Pod匹配的同组Pod数为Npp，则算法复杂度为：
在优化过程中，我们参考了inter-pod affinity/anti-affinity在预选阶段的metadata计算过程，将上述计算过程也优化为两阶段计算，先算出所有topologyPair对应的分数，然后利用该中间结果计算每个候选Node的分数。
代码语言：javascript复制fn CalcTopologyPairScore(pod, nodes) topologyPairsScore
for node in nodes:
for np in nodes.Pods:
for at in np.affinityTerms:
if pod.match(at) && at.topologyKey in node.labels:
topologyPairsScore[topologyPair{at.topologyKey, node.labels[at.topologyKey]}] = at.weight
fn CalcInterPodAffinityPriority(topologyPairsScore, nodeCandidates) nodeScoreMap
for cn in nodeCandidates:
for topologyPair in cn.labels:
if topologyPair in topologyPairsScore:
nodeScoreMap[cn] = topologyPairsScore[topologyPair]则优化后的复杂度为：
为了方便分析优化效果，假定集群总Node数为N，每个Node上平均有30个Pod，进入优选阶段的Node比例为a，则可以得到：
若假定Npp及a为常数，则随着集群规模N增大，计算复杂度的优化倍数很快会收敛。
可以看出优化效果与Npp呈线性关系，同一个亲和组的Pod数越多，优化越明显。下面是a值在集群负载较轻和较满的时候，优化效果随Npp变化的图。
需要说明的是，上面的简化分析结果在程序中的实际表现之间，会受到其它很多因素的影响，导致偏差，但仍可以作为参考。叠加多个优化手段后，在我们构造的300 Node、1.5w Pod的测试集中，拉起1000个Pod的应用，调度的吞吐性能提升5倍以上(基于上游v1.13版本)。性能优化工作中发现的BUG和部分优化，已经合并和吸收到K8s上游代码中(#79474,#84264,#80018,#79465,#79774)。
五、未来规划
未来，我们仍然会以构建统一的弹性调度平台为目标，推进资源效率及弹性能力的提升。具体来看，主要在以下几个方面：
- 调度算法
- 基础设施弹性
- 混部
- 服务质量
一方面持续优化调度算法，将更多的资源维度纳入调度器的管控，如磁盘IO、网络IO、NUMA & HT，同时针对即时贪心调度方式的缺陷，探索与全局最优调度以及重调度结合等手段。为了应对未来更大规模、更高层次的弹性场景，需要对K8s容器服务及应用所依赖的基础设施进行优化和改造。
在混部方面，持续扩大离在线混部规模，同时探索对无差别混部的支持。最重要的，会继续完善调度平台本身性能及稳定性、应用服务质量影响、调度效果等评价体系的建立和落地，推进服务质量的优化，为调度体系业务价值的释放提供稳定的保障。
