Kubernetes Scheduler之balanced_resource_allocation

2023-07-04 17:57:28

1 Overview

balanced_resource_allocation 是 Kubernetes 调度算法的其中一种。balanced_resource_allocation 会计算的是 CPU 和 Memory 与 Allocable 资源量的分数，并且求出他们的方差 Variance，终会将 Pod 调度到前述方差更小的节点 Node 上。

算法是参考 Wei Huang et al. An Energy Efficient Virtual Machine Placement Algorithm with Balanced Resource Utilization 文章来设计的。

2 代码走读

先理解一个辅助方法 fractionOfCapacity。这是用来计算请求的资源 requested 和实际资源量 capacity 的比例的方法。显然，当 capacity 是0，作为分母的 capacity 是不能为0的，所以统一返回值为1。否则就是计算 requested/capacity 的比例了。

func fractionOfCapacity(requested, capacity int64) float64 {
    if capacity ==  {
        return 1
    }
    return float64(requested) / float64(capacity)
}

CPU 和 Memory 是通过上述的辅助公式来计算请求和可分配资源的分数的，如果有 Volumes 的需求，也会按照同样的方法来计算。

这个公式也很简单。

mean := (cpuFraction + memoryFraction + volumeFraction) / float64(3)
variance := float64((((cpuFraction - mean) * (cpuFraction - mean)) + ((memoryFraction - mean) * (memoryFraction - mean)) + ((volumeFraction - mean) * (volumeFraction - mean))) / float64(3))

然后就是去计算三个分式的方差。先计算三个分式的平均值 mean，然后每个请求实际容量比的值和前述的平均值作差的平方之和，再除以3。是一个很普通的方差计算的公式。

光看公式，会觉得很难理解为什么需要这样的调度算法，下面举个例子，有两个节点，他们的 allocable 的资源如下。

此时，需要申请一个 Pod，资源配置为4核/10GB/100GB。

所以如果按照这个算 Pod 会更倾向于调度到 Node A 上，因为 Node A 可分配的资源相对比较平衡（方差更小）。

3 Summary

简单看了一下 Paper，文章提出的方法主要可以减少因为调度而产生资源碎片的可能。试想一下，如果完全不考虑资源的平衡性，假设一个节点已经非常不平衡了，只剩下少量的 CPU 和大量的 Memory，这样在下次调度的时候还调度到这个 Node 上，这样只会加剧碎片资源的情况，进而导致剩余的 Memory 无法被有效使用。