Kube-scheduler InterPodAffinity性能优化史

从事Kubernetes相关工作的同学对Kube-scheduler一定不会感到陌生，有的甚至还可能遇到过里面的一些问题，本篇主要介绍其中的一个优选策略：InterPodAffinity的性能优化过程，希望可以帮助到一些还在深受其困扰的朋友们，没有使用过此策略或者没有使用过Kubernetes也不要紧，其本质还是在以某种算法去解决某种问题，下面我会尽量以通俗易懂的话来解释需要解决的问题及算法优化过程。

策略介绍

InterPodAffinity作为优选策略就是在预选通过后的一堆宿主中找到一个最合适的宿主，寻找规则为按拓扑把宿主分类，针对拓扑级别，如果出现符合Pod要求的其他Pod，则为此拓扑下的所有Node计算一个得分，Pod的要求可以有多条，每一条都有一个权重（用来计算得分），同时得分也分正负，例如Pod期望拓扑下没有同类型的Pod，如果有则得分为负。下面通过一下生活中的例子来做个类比帮助理解要解决的问题，再引出对应的算法。

举个🌰

张三（Pod）大学刚毕业参加工作，需要租房（Node），于是找了中介公司（Kube-scheduler），张三提出了一些条件，比如房租不能高于2000一个月，上班耗时不超过1小时等，中介公司根据张三的需要筛选出来一批房子，张三看后觉得都不错，但只能租一个，于是又列出了一些其他非必须的加分减分项，比如房子所在小区如果有人是明星的话，加8分，如果房子所在街道有新冠肺炎患者，则减10分等条件，中介公司需要根据这些条件筛选出来最适合张三的一套房子。

上面提到的无论是小区还是街道都是一种拓扑，都可以看做是房子的一个属性并且有对应的值，例如小区：永泰东里，街道：西三旗街道。这些附加的加减分项是基于拓扑的，具有相同拓扑的房子内只要出现一个满足条件的人，则整个拓扑内的房子都会受到影响。例如小区内有一个明星，则整个小区符合条件的房子都会加8分。若街道有一个新冠患者，则整个街道所有符合条件的房子都会减10分。

化简一下为有M个符合条件的房源，每个房源里面住N个人（N可以不同），有X个加分减分项，求得分最高的一个房源。

初代

~1.15.4

InterPodAffinity采用的算法比较简单暴力，伪代码大致如下

1
2
3
4
5
6
7
8
9

for i房源 in 所有房源
	for j租客 in i房源
		for k项 in 加减分项
			if j租客 满足 k项
				for l房源 in 所有房源
					if 拓扑相等(l房源, i房源)
						lock()
						map[l] += k项分数
						unlock()

整体上是一个四层的循环，时间复杂度为M * N * X * M，工程中实现的时候采用多个goroutine进行计算，全局维护一个map，key为名字，值为得分，因此在每次更新map的时候都先加锁，更新完之后再释放锁。

二代

1.15.5 ~ 1.16.*

时间复杂度上没有变化，本次做的改进围绕锁来进行。使用切片取代字典，切片长度等于房源数量，利用下标一一对应。改进后如下

1
2
3
4
5
6
7

for i房源 in 所有房源
	for j租客 in i房源
		for k项 in 加减分项
			if j租客 满足 k项
				for i房源 in 所有房源
					if 拓扑相等(l房源, i房源)
						slice[i] = atomic add(slice[i], k项分数)

三代

1.17.0 ~ 1.18.*

时间复杂度发生变化，从M * N * X * M 变为 M * N * X。通过一个map[拓扑key]map[拓扑value]得分的结构取代了最里层的循环，在整个大循环结束后，最后再额外进行一次循环就可以了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

for i房源 in 所有房源
	for j租客 in i房源
		for k项 in 加减分项
			if j租客 满足 k项
				lock
				map[拓扑key]map[i房源拓扑value] += k项分数
				unlock
				
for i房源 in 所有房源
	score[i房源] += map[拓扑key][拓扑value]

本次虽然时间复杂度降低了一个数量级，但是又引入了锁，类似一代的实现，在全局有个map用来存放所有拓扑对应的分数，为防止多个goroutine并行访问map出现问题，所以加了锁。

四代

1.19.0~

本次的改进主要是去掉了锁，在时间复杂上没有变化。同样采用了全局map，但是在进行拓扑分数计算时并没有传入全局的map，而是每个房源对应一个map，暂且称为sub_map。代码中维护了一个sub_maps的切片，由于sub_map各用各的不存在并发问题，且把sub_map添加到sub_maps中时可以通过原子操作实现，在并发计算完所有房源的拓扑的分后，再统一把所有的子map进行处理，分数统一设置到全局的map中，剩下的处理逻辑就和三代最后的处理逻辑一样了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

index := -1

for i房源 in 所有房源
	for j租客 in i房源
		for k项 in 加减分项
			if j租客 满足 k项
				sub_maps[atomic add(index, 1)][拓扑key]map[i房源拓扑value] += k项分数
				
for sub_map in sub_maps
	map[拓扑key][拓扑value] + sub_map[拓扑key][拓扑value]

for i房源 in 所有房源
	score[i房源] += map[拓扑key][拓扑value]

总结

工程不同于纯算法实现，不仅需要在算法维度降低时间复杂度，也要考虑具体工程上的实现，比如这个例子中在涉及到并行计算时如何用原子操作替换掉锁。想要知道哪里是性能瓶颈，可以使用perf具体分析，也可以使用具体语言对应的性能分析工具，算法优化和工程优化同样重要，算法终归还是为工程服务的。